## Amazon Interview Question for Software Engineer in Tests

• 0

Team: Kindle
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 10 vote

``````node* findLCABinaryTree(node* head, node* a, node* b)
{
return NULL;
node *L, *R;

if(L != NULL && R!= NULL)
if(L == NULL && R!= NULL)
return R;
if(R == NULL && L!= NULL)
return L;
return NULL;
}``````

Slightly different version to sonny.c.patterson!!
Please comment, if anything is wrong.

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

Very nice. You don't really need R==null in the last if. You also can change R==null to !R and R!=null to just R, etc., because null evaluates to false.

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

It doesn't work if just one of the nodes is not in the tree. In that case it returns the node that is in the tree. But I think the original question allows the assumption that they are in the tree.

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

succinct and elegant

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

Simple but not elegant..

What if one of the input nodes is a child of another?
For example Say node *a is same as head and node *b exists somewhere in the left or right branches;

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

In that case "head == a" and so it will return the head as the LCA, which is correct.

The code is indeed quite clean, but can be a little confusing too because the method the intent of this recursive method is different between the main call and the recursive ones. The main call finds the LCA while the recursive one just finds whatever node is equal to "a" or "b". But no big deal.

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

It's covered.

Comment hidden because of low score. Click to expand.
2
of 8 vote

Very simple solutiion ^^

``````int find_node2( Node *node, int value1, int value2 ) {
int ret = 0;
if( node->data == value1 || node->data == value2 ) {
ret++;
}

if( node->left ) {
ret += find_node2( node->left, value1, value2 );
}

if( node->right ) {
ret += find_node2( node->right, value1, value2 );
}

if( ret == 2 ){
printf("this node is common parent: %d(%d,%d)\n",
node->data, value1, value2);
}

return ret > 0 ? 1 : 0;
}``````

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

+1 Nice. Very minimal solution. This assumes data is an identifier, which I wasn't assuming, but should have. I like the return counter... slick!

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

This assumes that the values are unique, which seems like an unreasonable solution.

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

Have you read the original question ? You have to find (and presumably return it) the LCA node, while your code just returns integers.

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

@ashot madatyan, yes it just returns integer, if it finds valid node, it is easy to return the node itself.

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

It functions for non-unique values, it just uses the nodes closest to the root.

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

It's the lca of two nodes, not the lca of two values. If you wanted to find the lca of nodes with values that duplicate ancestor nodes this would give incorrect results. You need to compare addresses, no values.

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

1. let A and B are the nodes
2. traverse from A to the root node using the parent link and hash each traversed node
3. traverse from B to the root node using the parent link and same time check in the hash table
4. if a node found in the hash table, that is the least commmon Ancestor

Here complexity is: T -> O(n) & S -> O(n) since it a binary tree.

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

But the Node class doesn't record parent links. How would you solve this if you can only go down the tree from a given node? I assume you would be given the root node of the tree as well as the two nodes A and B.

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

``````strucy Node *tmp=root;
while(tmp!=NULL)
{
if(tmp->data > fisrtNode->data && tmp->data > secondNode->data)
tmp=tmp->leftChild;
else if(tmp->data < firstNode->data && tmp->data < secondNode->data)
tmp=tmp->rightChild;
else
{
if(firstNode->parent == secondNode)
return secondNode->parent;
else if(secondNode->parent == firstNode)
return firstNode->parent;
else
return tmp;
}
}``````

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

It is not a BST and I do not see parent in the given structure, so it won't work.

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

The complexity of the above code is O(lgn)

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

A slight variation I was given stated that the desired nodes might not be in the Binary Search Tree, and that duplicates values in the BST are allowed, and will be put on the left.

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

It's not a BST

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

Let Node A and B the nodes in question.

1. Search for a Node A in the binary tree. Record a path to A as you search it.
2. Repeat above for Node B.
3. At this point you have a path from root to A and a path from root to B.
4. Search through these paths and find the least common nodes that appear in the paths.

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

Not sure if I am breaking rules of the asker with this solution. (I added params to track the parent as you look for the child)

``````class Program
{
static void Main(string[] args)
{
Node node5 = new Node(5, null, null);
Node node4 = new Node(4, null, null);
Node node3 = new Node(3, null, null);
Node node2 = new Node(2, node4, node5);
Node node1 = new Node(1, node2, node3);

Node common = NodeHelper.ParentFinder(node1, node4, node3);
Console.WriteLine(common.data);
}
}

class Node{
public int data;
public Node leftchild;
public Node rightchild;

public Node(int _data, Node _leftchild, Node _rightchild)
{
data = _data;
leftchild = _leftchild;
rightchild = _rightchild;
}

public Node parent;
public int level;
}

static class NodeHelper
{
public static Node ParentFinder(Node root, Node node1, Node node2)
{

if (nodeParentPopulater(root, null, node1, 0) && nodeParentPopulater(root, null, node2, 0))
{
//continue
}
else
{
return null;
}

Node temp1 = node1;
Node temp2 = node2;

//find each nodes parent node that lives at the same level
while (temp1.level > temp2.level)
{
temp1 = temp1.parent;
}
while (temp1.level < temp2.level)
{
temp2 = temp2.parent;
}

//now start checking if the nodes are the same
while (!temp1.Equals(temp2))
{
temp1 = temp1.parent;
temp2 = temp2.parent;
}

//parents are the same. return the parent node
return temp1;
}

private static bool nodeParentPopulater(Node node, Node parentNode, Node nodeToFind, int level)
{
bool found = false;

node.parent = parentNode;
node.level = level;

if (node.Equals(nodeToFind)) return true;

if (node.leftchild != null)
{
found = nodeParentPopulater(node.leftchild, node, nodeToFind, level + 1);
}
if (!found && node.rightchild != null)
{
found = nodeParentPopulater(node.rightchild, node, nodeToFind, level + 1);
}

return found;
}
}``````

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

Below is the code without using parent link

``````public class LCABT {
static BTNode lca = null;
static BTNode foundNode = null;
private static boolean findLCA(BTNode root,int a, int b, boolean inPath){
if(root == null)
return false;
if(root.getData() == a || root.getData() == b){
if(foundNode!=null && foundNode.getData()!=root.getData()){
if(inPath)
lca = foundNode;
return true;
}else{
foundNode = root;
inPath = true;
}
}
boolean inLeft = false;
boolean inRight = false;
if(lca == null)
inLeft = findLCA(root.getLeft(),a,b,inPath);
if(lca == null){
inRight = findLCA(root.getRight(),a,b,inPath);
if(lca==null && inLeft && inRight){
lca = root;
}
}

if(lca == null && root == foundNode){
inPath = false;
return true;
}

return inLeft || inRight;
}

public static void main(String[] argv){
BTNode n1 = new BTNode(5);
BTNode n2 = new BTNode(2);
BTNode n3 = new BTNode(3);
BTNode n4 = new BTNode(9);
BTNode n5 = new BTNode(11);
BTNode n6 = new BTNode(50);
BTNode n7 = new BTNode(7);
n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setRight(n6);
n4.setLeft(n7);
findLCA(n1,11,7,false);
System.out.println("LCA : "+lca.getData());
}

}

class BTNode{
private int data;
private BTNode left;
private BTNode right;
public BTNode(int data){
this.setData(data);
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getLeft() {
return left;
}
public void setRight(BTNode right) {
this.right = right;
}
public BTNode getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}

}``````

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

This assumes the values in the tree are unique. That seems like an unreasonable assumption.

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

The idea is to search for the nodes in the left sub tree and the right sub tree starting at the root. Recursive calls to the function FindCommonAncestorInBinaryTree() checks if the nodes are found. If one of nodes is found, it is marked as found and the search will continue for the next node. More explanation and code can be found here:

linearspacetime.blogspot.com/2012/04/find-common-ancestor-of-two-nodes-in.html

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

LCA of two nodes in a binary tree - complete implementation that also checks whether the nodes are in the tree at all. Algorithm description are inline, as well as inlined are the comments to help you understand the complete flow of the algo:

``````bool contains(Node *root, Node *sought)
{
if (NULL == root)
return false;

if (root->data == sought->data)
return true;

return (contains(root->left, sought) || contains(root->right, sought));
}

/**
Algorithm description:
Find the subtrees where the two nodes are contained.
return NULL
else
return the node starting from where the two nodes being sought are in different subtrees (the two nodes diverge)
*/
Node* LCA (Node *root, Node *firstnode, Node *secondnode)
{
bool ffound_in_left, ffound_in_right, sfound_in_left, sfound_in_right;

ffound_in_left = contains(root->left, firstnode);
if (ffound_in_left) {
sfound_in_left = contains(root->left, secondnode);
if (sfound_in_left) {
return LCA(root->left, first, second);
}
else {
sfound_in_right = conatins(root->right, second);
if (sfound_in_right) // the nodes diverge here (the first is in the left and the second is in the right, so return root)
return root;
return NULL; // the right node has not been found at all
}
}
else { // the first node not in left, try to find it in the right subtree
ffound_in_right = contains(root->right, first);

if (ffound_in_right) {
sfound_in_right = contains(root->right, second);
if (sfound_in_right) {
return LCA(root->right, first, second); // both the first and second nodes are in the right subtree, go to there
}
else { // the first found in the right and the second not found in the right, check to see whether the second exists in the tree at all
sfound_in_left = contains(root->left, second);
if (sfound_in_left == true) {  // second found in the left subtree, while the first is in the right, so they diverge
return root; //
}
return NULL;
}
}
}
}

// first not found in the right subtree either, so it is not present in the tree at all
return NULL;``````

}

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

What does the contains function do? Depth first search?
Whats the time complexity of the contains function?

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

Ugh

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

@CameronWills
The "contains" function is very straightforward - starting from the input node it just looks for the node with the given value. First it checks the input node's value, if it is not the one being sought, it looks in the left and then in the right subtrees of the given node.
Time complexity of this function is O(N). The overall time complexity of the given solution is quadratic, with constant space.

@sonny.c.patterson
Would you please bother yourself commenting the "Ugh" - for me this term does not contain any logic, neither does it provide us with any counterarguments or some constructive reasoning.

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

I stand by my comment. This is the most horrible piece of code imaginable. My children cried when they saw it. My dog ran into the road an threw himself under the first passing car. Jesus wept.

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

@sonny<...>
I'd suggest you to ask your late dog about how smart you are, you still may get some clever hints from it. Not sure about your kids - if they have gone after their father, then ... guess you already understood what they are in for. Live and learn (if you can)..

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

You should stick to comedy. You clear have a sense of humor.

Let me just say about your code, since you don't seem to see the issue, that if the LCA node is one million levels down the tree, you are going to find the two nodes one million times. Why not find them just one time?

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

Btw, the solution is not constant space. Every recursive call allocates multiple pointers. So it's O(n) space.

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

BTW, are you familiar with the tail recursion paradigm?

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

Is this tail recursive? I don't think so because of the double call.

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

In any case the question only applies to the contains function, the LCA function certainly is not.

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

``````Node* LCP(Node* tree, Node* node1, Node* node2, int* found = null)
{
if (tree == null) return null;
if (found == null) found = &0;
Node* result;
int rightFound = 0;
int leftFound = 0;
if (tree->rightchild) result = LCP(tree->rightchild, node1, node2, &rightFound);
*found = 2;
if (rightFound == 2)  return result;
if (tree->leftchild) result = LCP(tree->rightchild, node1, node2, &leftFound);
if (leftFound == 2) return result;
*found = leftfound + rightfound;
if (*found == 2) return tree;
return null;``````

}

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

Guys how do you Turn the following class into a Singleton:

public class Earth {
public static void spin() {}
public static void warmUp() {}
}

public class EarthTest {
public static void main(String[] args) {
Earth.spin();
Earth.warmUp();
}
}

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

Give it a private constructor and instantiate an object to a static member reference?

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

Give it a private constructor and instantiate an object to a static member reference?

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

My friend came up with this brilliant answer. He said :
1. List the pre and post order traversal of the tree.
(Now observe that the common parent of the two nodes will occur before both the nodes and after both the nodes in the pre and post order traversal listing respectively.)
2. In a pre-order traversal list place all the nodes occurring before n1 and n2 in a hash map h1
Preorder traversal P1: [....] n1....n2......
3. Now traverse the nodes which occur after both the Nodes n1 and n2. -
Postorder Traversal P2: ....n2....n1[....]
4. Return the first node which maps to the hash map h1 in the list P2

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

Explained here
In u tube / watch ? v = LFjCr2yDJdc

Comment hidden because of low score. Click to expand.
-1
of 1 vote

In other words,It means to find the Least common Ancestor of two nodes in binary tree,which is by itself common to both :)

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.