Amazon Interview Question for Software Engineer in Tests


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote
- vijayabhaskar April 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public DNode convertBinaryTreeToDLL(Node root)
{
if(root==null)
{
return null;
}
DNode head=null;
DNode tail=null;
if(root.left!=null)
{
DNode lhead=convertBinaryTreeToDLL(root.left);
DNode ltail=lhead.prev;
ltail.next=null;
lhead.prev=null;
head=lhead;
tail=ltail;

}

DNode node=new DNode(root.data);
if(head==null)
{
head=tail=node;
}
else
` {
tail.next=node;
node.prev=tail;
tail=node;
}

if(root.right!=null)
{
DNode rhead=convertBinaryTreeToDLL(root.right);
DNode rtail=rhead.prev;
rtail.next=null;
rhead.prev=tail;
tail.next=rhead;
tail=rtail;
}

head.prev=tail;
tail.next=head;

return head;

}


DNode process(Node root)
{
DNode node=convertBinaryTreeToDLL(root);
if(node!=null)
{
DNode tail=node.prev;
tail.next=null;
node.prev=null;
}

return node;
}

The above algorithm takes O(n) time. Please let me know if you find anything incorrect either in logic or in the time complexity mentioned.

- Prasad April 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please tell the algorithm?

- Anonymous April 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is just a traversal. I chose pre-order b/c it made returning the Linked List easier. In Ruby!!

class << self
  attr_accessor :linked_list
end

def self.convert_to_doubly_linked_list(root, current_pointer=nil)
  return linked_list unless root

  unless current_pointer
    self.linked_list = LinkedList.new
    linked_list.head = current_pointer = ListElement.new(root.value)
  end

  current_pointer.previous = ListElement.new(root.left.value) if root.left
  current_pointer.next = ListElement.new(root.right.value) if root.right

  convert_to_doubly_linked_list(root.left, current_pointer.previous)
  convert_to_doubly_linked_list(root.right, current_pointer.next)
end

O(n) b/c it's a traversal.

>> head
=> ListElement: data = 100
>> head.next.next
=> ListElement: data = 175
>> head.previous.previous
=> ListElement: data = 25

- curious_george April 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question (as is usual on any BST problem) is made for recursion. The trick is to pass a copy of the previous node to all subsequent recursive calls. Of course, when you start, there is no previous, so it should be set to NULL.

Here is the code:

Node * treeToDll(Tree* r, Node* pr) {
	if (!r) //The previous node is returned 
               return pr;
  
        Node* prev = treeToDll(r->left, pr);
        Node* c = new Node(r->val);
        if (prev) prev->next = c;
        c->prev = prev;

	return treeToDll(r->right, c); // Return the rightmost node, but if it does not
                                                     // exist then return the current node (c)
}

Yes, it's that simple! I urge you guys to try this code out (by hand or even better in any tree example that you could whip up). You will see that it works beautifully.

- barry.steyn April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi barry,

You are actually creating a new list. But the real fun part comes when you have to convert a BST to DLL in place without creating a new list..

- Vijay Muvva May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What happen when there are more than 3 nodes, says 7

A
/ \
B C
/ \ / \
D E F G

what does the double link list looks like?

- Anonymous September 30, 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