SDE - 1

You are given three strings 'A', 'B' and 'C'. Check whether 'C' is formed by an interleaving of 'A' and 'B'.

'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

For Example:

If A = “aab”, 'B' = “abc”, 'C' = “aaabbc”
Here 'C' is an interleaving string of 'A' and 'B'. because 'C' contains all the characters of 'A' and 'B' and the order of all these characters is also the same in all three strings.

If 'A' = “abc”, 'B' = “def”, 'C' = “abcdefg”
Here 'C' is not an interleaving string of 'A' and 'B'. 'B'ecause neither A nor 'B' contains the character ‘g’.

You are given arrays 'inOrder' and 'postOrder', which represent 'inorder' traversal and 'postorder' traversal of a 'Binary Tree' respectively.

Construct a 'Binary Tree' represented by the given arrays and return it's head.

Note:

Assume that the Binary Tree contains only unique elements.

Example:

Input: 'inOrder' = [9, 3, 15, 20, 7], 'postOrder' = [9, 15, 7, 20, 3]

Output:
We get the following binary tree from Inorder and Postorder traversal:

Kevin has written some integers on a paper. He then selects some integers and draws a line between them. Fortunately, his diagram represents a binary tree. Today, his friend challenged him to find the paths that start from root and end at the leaf in his diagram whose sum is exactly equal to the number ‘K’. But, Kevin has another important piece of work and so, he appoints you to do his task.

All you have to do is to find the paths in his diagram whose sum is exactly equal to the number ‘K’.

For Example:

Consider the above binary tree. If ‘K’ is 15 then the required paths are [5, 6, 4] and [5, 15, -5].

You are given a set of ‘N’ boxes. The boxes are given in the form of an array ‘gainPower’. Each box has some power associated with it. Also, you are given some initial power ‘power’. You are playing a game by choosing the boxes in such a way to maximize the total score. In one move, you can perform one of the two operations:

1. For any index ‘i’, If the current power is ‘power’, and gainPower[i] is less than or equal to ‘power’, you can lose gainPower[i] from your current power and gain 1 score and then remove it from the set of ‘N’ boxes.

2. For any index ‘i’, If the current power is ‘power’, and ‘score’ is greater than or equal to 1, you can gain gainPower[i] to your current power and lose 1 score and then remove it from the set of ‘N’ boxes.

Note:

The initial score is 0.

Each box can be used at most once.

The boxes can be used in any order.

You don’t have to remove all the boxes.