SDE - Intern

You have a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task is to print the time (in minutes) that it will take to burn the whole tree.

It is given that it takes 1 minute for the fire to travel from the burning node to its adjacent node and burn down the adjacent node.

For Example :

For the given binary tree: [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
Start Node: 3

    1
   / \
  2   3
     / \
    4   5

Output: 2

Explanation :
In the zeroth minute, Node 3 will start to burn.

After one minute, Nodes (1, 4, 5) that are adjacent to 3 will burn completely.

After two minutes, the only remaining Node 2 will be burnt and there will be no nodes remaining in the binary tree. 

So, the whole tree will burn in 2 minutes.

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

You want to visit your friend’s house who lives at some location in an infinite grid. You are initially at the origin of the infinite grid and can move only in four directions (i.e East, West, North, South).

For Example, If you are at cell (X, Y) then you can move to East i.e at cell (X+1, Y), or West i.e at cell (X-1, Y), or North i.e at cell (X, Y+1), or South i.e at cell (X, Y-1).

Your friend gives you a string ‘STR’ of length ‘N’ that represents the route to his house from the origin. The string ‘STR’ has only four different characters, i.e ‘E’, ‘W’, ‘N’, ‘S’. which represent direction East, West, North, South, respectively.

You find out that the route given by your friend is very long, and a shorter route is also possible. Your task is to find the smallest route to reach your friend’s house. See the example for better clarity.

Note:

1. There can be more than one shortest route, you should return the one which is lexicographically smallest among them.

Example:

Consider that your friend’s house is in the cell (2, 1) in the grid. And the route given by your friend is represented by the string ‘STR’= “NNSEWEE”.

One of the smallest route to reach cell (2, 1) from origin i.e cell (0, 0) is given by string  “EEN”  i.e you start from the cell (0, 0), then move East, i.e at cell (1, 0), then again move East, i.e at cell (2, 0), and then finally move North i.e at cell (2, 1).

Note, there are some other smallest routes such as “NEE”,  “ENE” etc, but “EEN” is the lexicographically smallest among them, so you should return it.