Walmart Labs Interview Question for Developer Program Engineers


Country: India
Interview Type: Phone Interview




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

Lets say BSTs are of m and n elements respectively. By doing individual in order traversal of each BST we can get two sorted linked list of m and n elements which will be achieved in O(m) and O(n). merging these to form an array is of O(m+n). Now creating a balanced BST out of this array will again be O(m+n), we can use the simple technique shown.

BST* sortedArrToBST(int arr[], int start, int end) {
  if (start > end) return NULL;
  int mid = start + (end - start) / 2;
  BST *node = new BST(arr[mid]);
  node->left = sortedArrToBST(arr, start, mid-1);
  node->right = sortedArrToBST(arr, mid+1, end);
  return node;
}
 
BST* sortedArrToBST(int arr[], int n) {
  return sortedArrToBST(arr, 0, n-1);
}

- apoorvagaurav July 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice

- Vikas August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

STEP 1
CONVERT BOTH TREES IN DOUBLY LINKED LIST O(n)
Step 2
Merge these linked list O(n)

Step 3
Again create back the tree O(n)

- SURAJ May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well what is the point in converting them specifically to DOUBLY LL's . We can do the same thing for SINGLY LL's.

- deam0n May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, how can we merge two lists in O(n)? It will be not be possible, isn't it?

- Anonymous May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

create a new linked list which is a merger of two

- Anonymous May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think since a Tree node is similar to a DLL node it is good to make a DLL. A BST can be converted to a DLL using recursion( Google The great tree list recursion problem). once you have a DLL its lchild * will point to previous node and rchild * will point to next node. This property will remain same even after merging.

Furthur to convert a BST To tree in O(n) is a little tricky algo. But it you think of it as inorder tree creation it becomes easy.

list *head;//global
tree * createBSTfromDLL(int num_nodes)
{
if (n==0) return NULL;
tree *root= new root;
root->l= createBSTfromDLL(n/2);
root->val= head->val;
head= head->next;
root->r=createBSTfromDLL(n/2);

return root;
}

- Yoda July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

First of all the question need modifications.

Two trees means two each of n node.. So the Algo is pretty easy for O (n).

Steps :-

1> Visit all node of tree One and push them in queue Q. i.e. O(n) // n is the no. of node in tree 1.
2> For each value in queue Q.
dequeue the value from the queue Q.
Now put this value into the Tree 2 using the BST rule.
end of For // O(m).. // m is the no of node in tree 2

So total time complexity is O(T)=O(n)+O(m) .
if m==n the O(n)
else if m<n
O(n)
else
O(m)

- hprem991 May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Adding each node of tree 1 (size n) to tree 2 is O(n * log(m) ).

- Anonymous June 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Travel second tree in inorder traversal add each element you read into the first tree

- Anonymous May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the trees are of nodes M and N then isnt your algo doing worst case O(M*N) ??

- Yoda July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ordered list itself can be considered as an skewed, unbalanced binary search tree

- mms August 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As we know each sub tree of BST is also BST. so just find the location where the root of the other tree can be inserted.
Here only consideration we have to take is that both the trees contain distinct values.

- Registered User February 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using an InOrderTreeIterator you scan and merge the nodes in on step. Then the list can be rearranged into a tree by using the 'reverse mergesort' suggested further up. If you use the original nodes you need to be careful since the old parent-children links still exist.
They need to be reset. Merge: O(m+n), Insert: O(m+n)

public Node createBinarySearchTreeFromSortedNodeList(List<Node> nodeList) {
	return this.createBinarySearchTreeFromSortedNodeListRecursive(nodeList, 0, nodeList.size() - 1);
}

private Node createBinarySearchTreeFromSortedNodeListRecursive(List<Node> nodeList, Integer minIndex, Integer maxIndex) {
	Node node = null;
	
	if (maxIndex > nodeList.size() - 1 || minIndex < 0)
		return null;
	
	if (minIndex == maxIndex) {
		node = nodeList.get(minIndex);
		node.setLeftChild(null);
		node.setRightChild(null);
		node.setParent(null);
		return node;
	}
	else
	if (minIndex > maxIndex)
		return null;
	
	Integer middle = (maxIndex + minIndex) / 2;		
	Node leftChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList,  minIndex, middle - 1);
	Node rightChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList, middle + 1, maxIndex);

	node = nodeList.get(middle);
	node.setLeftChild(leftChild);
	node.setRightChild(rightChild);
	leftChild.setParent(node);
	rightChild.setParent(node);
	
	return node;
}

public class InOrderTreeIterator {
	
	private Node currentNode = null;
	private Stack<Node> treeTraverserStack = null;
	private Node next = null;
	
	public InOrderTreeIterator(Node root) {
		treeTraverserStack =  new Stack<Node>();
		this.currentNode = root;
		this.fetchNextNode();
	}
	
	public Node next() {
		Node result = next;
		this.fetchNextNode();
		return result;
	}

	public boolean hasNext() {
		return this.next != null;
	}
	
	private void fetchNextNode() {
		Node result = null;
		boolean done = false; 
		
		while (!done) {
			if (!this.treeTraverserStack.isEmpty() || currentNode != null) {
				if (currentNode != null) {
					this.treeTraverserStack.push(currentNode);
					currentNode = currentNode.getLeftChild();
				}
				else {
					currentNode = this.treeTraverserStack.pop();
					result = currentNode;
					currentNode = currentNode.getRightChild();
					done = true;
				}
			}
			else
				done = true;
		}
		
		this.next = result;
	}

}

}

- gonzo July 27, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

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.

Learn More

Mock Interviews

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.

Learn More