## Directi Interview Question for SDE-2s

• 2

Country: India

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

Find LCA of 3 pairs - (a, b), (b, c) and (c, a)
LCA of at-least 2 pairs will be same.
If all 3 LCAs are same, remove that LCA node.
If only 2 LCAs are same, then we have two distinct LCA node here. One LCA node will be parent and other LCA node will be child. Remove the Child LCA Node (We may calculate height of the two LCA nodes here. The LCA node with lesser height will be the Child of the other and this lesser height node should be deleted).

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

In case of 2 LCAs the one which is LCA of only one pair will be the child of other LCA node

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

Not Possible in a binary tree

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

Actually this is not possible only if we consider "From", if we consider "To" then anurag's answer is correct

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

``````1: Let x be the root of the three.

2: While either the left of right subtree of x contains two of {a, b, c} do:
3:     set x to its child whose tree contains two of {a, b, c}.

4: Return x.``````

As it has been remarked, we need to remove all edges that come from or go to node x returned by the algorithm. This is so because there might be a donw path (from root to a leave) containning nodes a, b and c. If not, then we need to remove just the edges coming from x.

The loop 2-3 is repeated at most h times where h is the height of the tree.

At each iteration we need to check which, if any,subtree of x contains a, b and c. The complexity of this check depends on the data strored at each node and how the tree was build. For instance, consider these three cases:

* The tree is a binary search tree: then a node y is in the left subtree of x if, and only if, key(y) < key(x) which has the complexity of a comparison, normally O(1). In this case the total complexity of the algorithm is O(h).

* Each node of the tree stores a pointer to its parent. Then, starting from a node y and going up the tree we stop until we reach x or the root. If we reach x then we can determine if we came from left or right. If we don't reach x, it means that y is not in the subtree of x. The time for walking up the tree from y is O(h), so the total complexity of the algorithm is O(h^2).

* None of the above. Then, from x, we can do a DFS to check if a node y belongs to the subtree rooted at x and, if so, on which side. This costs O(|E(x)|) where E(x) is the set of edges of the subtree rooted at x. Since it's a binary tree, |E(x)| = |V(x)| + 1 where V(x) is the set of vertices of the subtree rooted at x. In a well balanced tree, |V(x)| = O(2^h). Then the total cost of the algorithm is O(h * 2^h) = O(2^h).

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.

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