SDE - Intern

You have been given a Binary Tree of integers. You are supposed to return the level order traversal of the given tree.

For example:

For the given binary tree

The level order traversal will be {1,2,3,4,5,6,7}.

You are given an arbitrary binary tree consisting of N nodes numbered from 1 to N, an integer 'K', and a node 'TARGET_NODE_VAL' from the tree. You need to find the Kth ancestor of the node 'TARGET_NODE_VAL'. If there is no such ancestor, then print -1.

The Kth ancestor of a node in a binary tree is the Kth node in the path going up from the given node to the root of the tree. Refer to sample test cases for further explanation.

Note:

1. The given node 'TARGET_NODE_VAL' is always present in the tree.
2. The value of each node in the tree is unique.
3. Notice that the Kth ancestor node if present will always be unique.

You have been given an array/list 'SEQUENCE' denoting the sequence of 'N' integers. Your task is to find the equilibrium indices of the sequence in 'SEQUENCE'.

The equilibrium index of a sequence of integers is defined as the index such that the sum of all the elements at lower indices is equal to the sum of elements at higher indices.

Note:

1. 'SEQUENCE' may contain more than one equilibrium indices.

2. If there are no equilibrium indices, return an empty sequence.

3. Consider the sum of elements lower than the first index and higher than the last index to be 0 (zero).

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Given a binary tree with 'N' number of nodes, convert it to a Greater Tree such that data of every node of the original BST is changed to the original node’s data plus the sum of all node’s data greater than or equal to the original data of the node in the BST.

A binary search tree (BST) is a binary tree data structure that has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.

• The right subtree of a node contains only nodes with data greater than the node’s data.

• Both the left and right subtrees must also be binary search trees.

Example:

Answer:

Because only 5 is greater than 4 in the above BST, node 4 will be updated to 9 (4 + 5 = 9).

Nodes 3, 4, and 5 are greater than 2, hence node 2 will be modified to 14 (2 + 3 + 4 + 5 = 14). 

Node with data 5 will remain the same because there is no node in the BST with data greater than 5.

Nodes 2,3, 4, and 5 are greater than 1, hence node 1 will be modified to 15 (1 + 2 + 3 + 4 + 5 = 15).   

Nodes 4 and 5 are greater than 3, hence node 3 will be modified to 12 (3 + 4 + 5 = 12). 

Given a set of ‘N’ nuts of different sizes and ‘N’ bolts of different sizes. There is a one-one mapping between nuts and bolts. Your task is to find the correct match of nuts and bolts from the given set and assign a nut to a bolt when it is matched.

Note:

1. A comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with a nut to see which one is bigger/smaller.

2. The set of Nuts/Bolts will consist of numeric strings that represent their sizes. The size of each nut/bolt will be equal to its numerical value. For example, the size of ‘10’ will be equal to 10. 

3. For every bolt, there will exist a nut of the same size.

4. Don’t return or print anything. Modify the original sequence of nuts and bolts such that each nut of a particular size matches its bolt of the same size.

5. Store the matched pair of nuts and bolts in any order.