CapitalIQ Interview Question
Software Engineer / DevelopersThey solution is sweet and clever... surely the interviewer will be impressed... regarding Anna's question... b and e cannot have a common parent as b is parent of e.. so you have to check for that... correct me I am wrong... to make ravi solution more clear here is anthor ex...
10
5 12
3 6 11 13
4 15
so preorder : 10 3 4 5 6 11 12 13 15
inorder : 3 4 5 6 10 11 12 13 15
if you are looking for 3 and 11 then mark 3 and 11 in inorder array no now u have
inorder: 3 4 5 6 10 11
so when you check for 10 u get the solution right away... this is easy to determine as 3 and 11 are at same level...
now consider your looking for 11 and 15 then your inorder becomes: 11 12 13 15
so call inorder on 12 and then 13..
@hacker
Mayank's logic is correct ,it works .
For the above example
10
5 12
3 6 11 13
4 15
so preorder : 10 5 3 4 15 6 12 11 13
inorder : 4 3 15 5 6 10 11 12 13
if you are looking for 3 and 11 then mark 3 and 11 in inorder array no now u have
inorder: 3 15 5 6 10 11
so when you check for 10 u get the solution right away... this is easy to determine as 3 and 11 are at same level...
now consider your looking for 11 and 15 then your inorder becomes: 15 5 6 10 11
now check the preorder array u get 10 dividing the present inorder array 15 5 6 and 11 therefore 10 is he answer
Hi,
- Ravi Kant Pandey April 04, 2007if u have O(n) space you can do it in O(n) run time
traverse preorder the addresses of the nodes and store it.
then traverse inorder the addresses of the nodes and store it.
eg tree
a
b c
d e f
have PreOrder:a b d e c f
Inorder: d b e a c f
for two node ptrs eg d and c
mark the positions in inorder array and find first preorder ptr which seprates it into two
different parts of Inorder array
for above example first preorder ptr is a which seprates inorder into dbe and cf
so a is first commom ancester of d and c