SDE - 1

You are given an array “ARR” of size N. Your task is to find out the sum of maximum and minimum elements in the array.

Follow Up:

Can you do the above task in a minimum number of comparisons?

You are given a string ‘str’ which consists of brackets and integers ∈ [1, 9]. Your task is to construct a binary tree from the given string and return the Pre-Order Traversal of it.

The rules are as follows

1. The first character of the string is guaranteed to be an integer which denotes the root element of the tree.

2. This is followed by zero, one or two pairs of parenthesis, which contains a child binary tree with the same structure.

3. The first parenthesis denotes the left child of the binary then the right child.

For Example

Let str= “1(2)(3)”

The tree will be:

The first element i.e 1 is the root node and the first bracket signifies the left child of the root node which has only 1 element i.e 2 and the second bracket signifies the right child of the root node that has only 1 node i.e 3 . Hence we have the binary tree as shown above.

You have been given a permutation of ‘N’ integers. A sequence of ‘N’ integers is called a permutation if it contains all integers from 1 to ‘N’ exactly once. Your task is to rearrange the numbers and generate the lexicographically next greater permutation.

To determine which of the two permutations is lexicographically smaller, we compare their first elements of both permutations. If they are equal — compare the second, and so on. If we have two permutations X and Y, then X is lexicographically smaller if X[i] < Y[i], where ‘i’ is the first index in which the permutations X and Y differ.

For example, [2, 1, 3, 4] is lexicographically smaller than [2, 1, 4, 3].

You are given an array 'ARR' of integers of length N. Your task is to find the next smaller element for each of the array elements.

Next Smaller Element for an array element is the first element to the right of that element which has a value strictly smaller than that element.

If for any array element the next smaller element does not exist, you should print -1 for that array element.

For Example:

If the given array is [ 2, 3, 1], we need to return [1, 1, -1]. Because for  2, 1 is the Next Smaller element. For 3, 1 is the Next Smaller element and for 1, there is no next smaller element hence the answer for this element is -1.

You are given an arbitrary binary tree with N nodes, whose nodes have their values in the range of integers. You have to print the values of leftmost and rightmost nodes at each level of the given tree. In other words, for every level in the given tree, print the values of corner nodes.

Two nodes are said to be at the same level if they are at the same distance from the root node.

Note:

1. For all such levels where there is only one corner node the leftmost and the rightmost nodes are the same.
2. In the output, you have to print the leftmost and rightmost values in level order fashion i.e, the leftmost node of level1 followed by the rightmost node of level1 followed by the leftmost node of level2 followed by the rightmost node of level2 and so on.