CapitalIQ Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

if 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

- Ravi Kant Pandey April 04, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

grt

- aaska's_hub May 17, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

then how about given node b and e?

- Anna April 25, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

They 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..

- Mayank April 19, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess ur preorder traversal is itself wrong

- hacker May 08, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- santosh July 20, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More