SDE - 1

Given a string "pattern", which contains only two types of characters ‘(’, ‘)’.

Your task is to find the minimum number of parentheses either ‘(’, ‘)’ we must add the parentheses in string ‘pattern’ and the resulted string is valid.

Condition for valid string-

Every opening parenthesis ‘(’ must have a correct closing parenthesis ‘)’.

Example - ‘(()(()))’, ‘()()()’, ‘((()))’ are valid string, and ‘(((’, ‘(()’, ‘)(())’ are invalid string.

Note:

1. You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the minimum number of parentheses required to make a string valid.

You have been given a string 'S' which only consists of lowercase English-Alphabet letters.

Your task is to find the shortest(minimum length) substring of 'S' which contains all the characters of 'S' at least once. If there are many substrings with the shortest length, then find one which appears earlier in the string i.e. substring whose starting index is lowest.

For example-

If the given string is S = "abcba", then the possible substrings are "abc" and "cba". As "abc" starts with a lower index (i.e. 0, "cba" start with index 2), we will print "abc" as our shortest substring that contains all characters of 'S'.

Ninja and his two friends went to a picnic and enjoy their pizza. But they found that the slices of pizza are not uniform. Ninja is very hungry so he wants to take the bigger slices of pizza. So all friends decided to follow the rule while eating pizza:

1 . Ninja will pick a slice of pizza.
2 . One of his friends will pick the next slice in the anti-clockwise direction.
3 . the Second friend will pick the next slice in the clockwise direction of Ninja’s pick.

You are given an array ‘ARR’ having the weights of ‘N’ slices representing a circular array in the clockwise direction.N is a multiple of 3. Ninja wants to collect the slices such that their sum is maximum. Can you help Ninja to solve this problem and tell him the maximum sum he can achieve?

For Example

If the ARR is [4,3,11,12,2,4] , so the optimal answer will be as follows:
Ninja will pick the slice having weight 12, so his friends will pick the slices having weights 11 and 2. After that Ninja will pick the slice with weight 4 and his friends will pick 4 and 3.
Ninja’s sum will be 16 which is the maximum.

You have been given a Binary Search Tree of 'N' nodes, where exactly two nodes of the same tree were swapped by mistake.

Your task is to restore or fix the BST, without changing its structure and return the root of the corrected BST.

Note:

Given BST will not contain duplicates.

Example

A Binary Search Tree (BST) whose 2 nodes have been swapped is shown below.  

After swapping the incorrect nodes: 

Follow Up

Can you do this without using any extra space? 

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.

For example:

Consider ARR = [1, 2, 3, 4, 4], the duplicate integer value present in the array is 4. Hence, the answer is 4 in this case.

Note :

A duplicate number is always present in the given array.