MJRocks
BAN USER- 0of 2 votes
AnswersQuestion 1 / 1 (Path Explosion EASY)
- MJRocks in India
You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties
Each internal node in T had exactly 2 children
Each internal node in T was represented by an uppercase English alphabet (A-Z)
Each leaf node in T was represented by a lowercase English alphabet (a-z)
You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below
toPostOrderString (node)
if node is leaf
return node.value
else
T = ""
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T
Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in "Now you see me" ( don't tell anyone they are real !! )
You remember the string you memorised back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves - 1 unique path to each leaf.
You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.
You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively
N, the number of nodes in T
S, the string representation of the post-order traversal of T. Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.
Note
It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node.
For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely.
It is not necessary that all characters in T are unique. There may be several nodes with the same value.
In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string.
Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.
Consider the following tree
A
/ \
t B
/ \
/ \
B A
/ \ / \
x y a b
This tree is given in Sample Case 1 as
N = 9
S = "txyBabABA"
K = 2
A = "AA"
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves - 1 for each leaf.
- A-t
- A-B-B-x
- A-B-B-y
- A-B-A-a
- A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which "AA" exists as a sub-sequence. Of course, there are only 2 such paths
- A-B-A-a
- A-B-A-b
Hence the expected answer is 2.
In the same T above
The answer for A = "BB", is 2
The answer for A = "BA", is 2
The answer for A = "AB", is 4
The answer for K = 1 and A = "A", is 5
The answer for K = 1 and A = "B", is 4
The Sample Case 2 has a little more complicated T. The string S in Sample Case 2 is yeBgeuCBxAB.
Constraints
N ≤ 10000
K ≤ 100
The expected time complexity of the algorithm is O(N).| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Trees and Graphs