Directi Interview Question for Software Developers
- 0of 0 votes
AnswerAmr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.
- praveensinghraghav96 July 02, 2017 in India
Let's index all the leaf nodes from the left to the right from 1 to 2^h. The exit is located at some node n where 1 ≤ n ≤ 2^h, the player doesn't know where the exit is so he has to guess his way out!
Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:
Character 'L' means "go to the left child of the current node";
Character 'R' means "go to the right child of the current node";
If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;
If Amr skipped two consecutive commands, he goes back to the parent of the current node
before executing next command;
If he reached a leaf node that is not the exit, he returns to the parent of the current
node;
If he reaches an exit, the game is finished.
Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?
Input
First Line contains T the number of test cases
The next T lines contains 2 integers h, n
Output
Output T lines each containing an integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.
Constraints
1 ≤ T ≤ 10
1 ≤ h ≤ 50
1 ≤ n ≤ 2^h
Example
Input:
1
2 2
Output:
2
Explanation
Example case 1. Amr would visit first root node then root->left node and then go to the root->left->right node which is the exit. hence 2 nodes visited before reaching the exit| Report Duplicate | Flag | PURGE
Directi Software Developer
Let us consider left move as "0" and right move as "1" . As "n" is our target node then path from root to "n" will be binary representation of "n-1" represented in length "h".
let binary representation of "n-1" be string "destination".
Algorithm:
- While traversing from top to bottom if current command is equal to direction where we
want to procced then it is fine else we will have to visit all the nodes of other subtree.
There are pow(2,h) nodes in a subtree of height h.
will only come out of this subtree if we visit all the nodes of this subtree.
- SSwarnkar13 September 05, 2017