## Amazon Interview Question for Software Engineers

Team: Amazon Alexa
Country: United States
Interview Type: In-Person

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

Are they balanced? Are they binary search trees? Do you need to balance them?

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

If I take the question as it is, here is what I would do.

``````public static Node Merge(Node leftRoot, Node rightRoot)
{
Node currentNode = leftRoot;
while(currentNode.left != null)
{
currentNode = currentNode.left;
}
currentNode.left = rightRoot;
return leftRoot;
}``````

Complexity : O(log(n)) + O(1).

Now, If there have preconditions such as the data should be merged one after another, like some sort of close merge, or if the tree is binary search tree. I would do the following.

``````public static Node Merge(Node leftRoot, Node rightRoot)
{
// if the tree is BST, I will do the merging in sorted maner, and If it is just binary, I will put elements one after another.
// I will consider BST
Node mergedList = MergeList(leftList, rightList);
Node start = mergedList;
Node end = mergedList;
while(end.right != null)
{
end = end.right;
}
Node root = ConvertIntoTree(start, end);
return root;
}

public static Node ConvertIntoTree(Node start, Node end)
{

if(start.data > end.data)
{
return null;
}
if(start == end)
{
start.left = null;
start.right = null;
return start;
}
Node currentNode, nextNode;
currentNode = start;nextNode = start;
while(nextNode.right != null)
{
currentNode = currentNode.right;
nextNode = nextNode.right.right;
}
currentNode.left = ConvertIntoTree(start, currentNode.left);
currentNode.right = ConvertIntoTree(currentNode.right, right);
return currentNode;
}

public static Node MergeList(Node left, Node right)
{
if(left == null || right == null)
{
return left==null?right:left;
}
Node currentNode = left;
while(true)
{
if(right == null)
{
while(left.left != null)
{
left = left.left;
}
return left;
}
if(currentNode.right == null)
{
currentNode.right = right;
right.left = currentNode;
while(left.left != null)
{
left = left.left;
}
return left;
}
if(currentNode.data < right.data)
{
currentNode = currentNode.right;
}
else
{
if(currentNode.left == null)
{
Node temp = right;
right = right.right;
temp.right = currentNode;
currentNode.left = temp;
}
else
{
Node currentLeft = currentNode.left;
currentLeft.right = right;
right.left = currentLeft;
currentNode.left = right;
Node temp = right;
right = right.right;
temp.right = currentNode;
}
}
}
}

{
if(node.left != null)
{
temp.right = node;
node.left = temp;
}
if(node.right != null)
{
node.right = temp;
temp.left = node;
while(node.right != null)
{
node = node.right;
}
}
return node;
}``````

Complexity of this is O(n+m) + O(1).

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

``````class Solution(object):
def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
def helper(node1,p1,node2,side):
if not node1 and not node2:
return None

elif node2 and not node1:
if side =="right":
p1.right = node2
else:
p1.left = node2
return

elif node1 and not node2:
return

else:
node1.val = node1.val + node2.val
helper(node1.left,node1,node2.left,"left")
helper(node1.right,node1, node2.right,"right")

if not t1 and not t2:
return None
elif not (t1 and t2):
return t1 or t2
else:
helper(t1,None,t2,None)
return t1``````

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

I am assuming that the destination is a BST and it needs to be kept that way. My solution is below

``````void MergeTrees(Node firstTree, Node secondTree)
{
if(secondTree.Left != null)
MergeTrees(firstTree, secondTree.Left);

if(secondTree.Right != null)
MergeTrees(firstTree, secondTree.Right);

secondTree.Left = null;
secondTree.Right = null;
InsertNode(firstTree, secondTree);
}

{
{
else
}

{
else
}
}``````

Complexity is O(n+m)

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

@sonesh Your first solution makes no sense whatsoever.

@Abcd I'm not sure how you arrived at the conclusion that your solution is O(n+m) when you're clearly doing m insertions into a BST of n elements.

Your solution is O(logn*m) if the first BST is balanced, O(n*m) otherwise.

Comment hidden because of low score. Click to expand.

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.