is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
The following solution works for any n-ary tree, not necessarily balanced or even a search tree :
- purushottam.kar November 04, 20121) Find out the depths of the two nodes, say n1 and n2 by blindly traversing up till the root. Lets say the depths come out to be d1 and d2.
2) If the depths are the same then go to step 4) else go to step 3) (assume that d1 > d2 w.l.o.g.)
3) For d1 - d2 steps n1 <= parent(n1)
4) Till parent(n1) != parent(n2), n1 <= parent(n1), n2 <= parent(n2)
Here the <= operator stands for assignment. The logic behind the algorithm is the following. Given two nodes at the same level in the tree, if we move one step up for both at the time then we are bound to collide at the lowest common ancestor. The problem is that the given nodes might be at different levels which is why in the first step we find the depths and let the deeper node go up till it reaches the level of the shallow node and then continue from thereon.