## Amazon Interview Question for SDE-2s

Country: United States

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

If link to parent is not given then perform BFS while keep track of parents then build the path to each list of nodes from root ( say in linkedlist). traverse the linked list at the same time until current node is common across all lists

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

Either use segment tree RMQ on the Euler tour of the tree or use sqrt decomposition of the tree.
Note- both methods need preporcessing.

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

C#:

``````private Node CommonParentNode(Node ptr, List<Node> nodes)
{
if (ptr == null)
return null;

if (nodes.Contains(ptr))
return ptr;

Node left = CommonParentNode(ptr.left, nodes);
Node right = CommonParentNode(ptr.right, nodes);

if (left != null && right != null)
return ptr;

if (left == null && right == null)
return null;

return left ?? right;
}``````

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

C#

``````private Node CommonParentNode(Node ptr, List<int> nodes)
{
if (ptr == null)
return null;

if (nodes.Contains(ptr.val))
return ptr;

Node left = CommonParentNode(ptr.left, nodes);
Node right = CommonParentNode(ptr.right, nodes);

if (left != null && right != null)
return ptr;

if (left == null && right == null)
return null;

return left ?? right;
}``````

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

private TreeNode LCA(TreeNode root, List<TreeNode> nodes) {
return helper(root, nodes));
}

private TreeNode helper(TreeNode node, List<TreeNode> set) {
if(node == null) return null;
if(set.contains(node)) return node;
TreeNode left = helper(node.left, set);
TreeNode right = helper(node.right, set);
if(left != null && right != null) return node;
if(left == null) return right;
if(right == null) return left;
return null;
}

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

``````private TreeNode LCA(TreeNode root, List<TreeNode> nodes) {
return helper(root, nodes);
}

private TreeNode helper(TreeNode node, List<TreeNode> set) {
if(node == null)  return null;
if(set.contains(node)) return node;
TreeNode left = helper(node.left, set);
TreeNode right = helper(node.right, set);
if(left != null && right != null) return node;
if(left == null) return right;
if(right == null) return left;
return null;
}``````

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

1) Post order like traversal where all parents are in a stack when a node is visited.
2) When each node in lstpNodes is visited, record the size of the stack. Pick out the smallest among those values. Call it M.
3) When all nodes in lstpNodes have been visited, the M-th last element in the stack is the LCA.

``````void Visit (CNode* pNode, const list <CNode*> lstpNodes, const CStack &Stack, unsigned &uFoundNodes, unsigned &uLCADepth)
{
if (!std::find (lstpNodes.begin (), lstpNodes.end (), pNode))
return false;

uFoundNodes++;
uLCADepth = min (uLCADepth, Stack.size () - 1 /* depth of parent */);
}

CNode* LCAOfNNodes (CNode* pRoot, const list <CNode*> lstpNodes)
{
CStack Stack;
CNode* pNode = pRoot, pLastVisited = NULL;
unsigned uFoundNodes = 0, uLCADepth = (unsigned) -1;

while (pNode)
{
while (pNode)
{
Stack.Push (pNode);
pNode = pNode->pLeft;
}

while (!pNode)
{
pNode = Stack.Top ();
if (pNode->pRight == NULL || pNode->pRight == pLastVisited)
{
Stack.Pop ();
Visit (pNode, lstpNodes, Stack, uFoundNodes, uLCADepth);

if (uFoundNodes == lstpNodes.size ())
{
Stack.Pop ();
return Stack.Top ();
}

pLastVisited = pNode;
pNode = NULL;
continue;
}

pNode = pNode->pRight
}
}

return NULL;
}``````

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

``````public TreeNode findLca(TreeNode root, List<TreeNode> nodes) {
if (nodes.size() == 0) {
return null;
}

VisitResult result = visitNode(root, nodes);
return result.lcaNode;
}

private VisitResult visitNode(TreeNode node, List<TreeNode> nodes) {
if (node == null) {
return new VisitResult();
}

VisitResult leftResult = visitNode(node.left, nodes);
if (leftResult.lcaNode != null) {
return leftResult;
}

VisitResult rightResult = visitNode(node.right, nodes);
if (rightResult.lcaNode != null) {
return rightResult;
}

VisitResult result = new VisitResult();
result.foundNodes = leftResult.foundNodes + rightResult.foundNodes;
if (result.foundNodes == nodes.size()) {
result.lcaNode = node;
} else if (nodes.contains(node)) {
result.foundNodes++;
}
return result;
}

private class VisitResult {

int foundNodes = 0;
TreeNode lcaNode = null;
}``````

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

``````public int findLCA(Node root, List<Node> nodes){
int lca = root.value;
if(nodes != null && !nodes.isEmpty()){
//Define paths from the root to each node
List<List<Integer>> pathsToRoot = LCALib.buildPaths(nodes);
//Get min path length
int min = LCALib.getMinPath(pathsToRoot);
//iterate paths limited to shortest path
for(int i = 0; i < min; i++){
//get path node at current level
int lcaCandidate = pathsToRoot.get(0).get(i);
int level = i;
//evaluate candidate for all paths at same level,
//if true we are not diverged from the same path for all nodes.
boolean matchedCandidate = LCALib.matchedCandidate(pathsToRoot, level, lcaCandidate);
if(matchedCandidate){
//set new lca
lca = lcaCandidate;
}
}
}
return lca;
}``````

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.