Amazon Interview Question


Country: India


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

//Just to inorder travesal with predecessor in mind to link it.

node* treetoDLL(node* root)
{
	static node *start,*pred =NULL;
	if(root==NULL)
		return NULL;

	treetoDLL(root->lptr);

	node *dnode = new node();
	dnode->data =root->data;
	dnode->rptr = NULL;
	dnode->lptr =pred;

	if(pred!=NULL)
		pred->rptr =dnode;
	else
		start = dnode;
	pred=dnode;

	treetoDLL(root->rptr);
	return start;
}

- Anonymous on April 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For left child or right child null it gives null pointer exception

- RS on October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

public TreeNode asDoublyLinkedList(TreeNode root){
		if(root.leftChild == null && root.rightChild == null){
			return root;
		}
		else {
			TreeNode tmp = null;
			tmp = asDoublyLinkedList(root.leftChild);
			while(tmp.rightChild != null)
				tmp = tmp.rightChild;
			tmp.rightChild = root;
			root.leftChild = tmp;
			tmp = asDoublyLinkedList(root.rightChild);
			while(tmp.leftChild != null)
				tmp = tmp.leftChild;
			tmp.leftChild = root;
			root.rightChild = tmp;
		}
		
		return root;
	}

This works but the root pointer will still point to the root of the tree. Do a while root = root.leftChild and finally the root shall point to the head of doubly linked list.

- Srirang on May 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Comment from OP:
Tweaked inorder traversal and gave the below answer

BST to sorted LL
p = root;
visited = NULL;
do
{
	while( p!=NULL )
		stack.push(p);
		p = p->left;
	
	while( !stack.empty() )
	{	
		temp = stack.pop()
		visit(temp);
		if( visited != NULL )
			visited->right = temp;
			temp->left = visited;
		visited = temp;
		if( temp->right )
			p = temp->right;
			break;
	}
while( p!= NULL || !stack.empty() );

You need to an inorder traversal(which takes up O(n) space) to realize the sortedness of the number. Having said that, is there any way to do this in O(1) space?

- y2km11 on February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static DoublyLinkedList<E> returnSortedDoublyLinkedListFromBST(TreeNode rootNode){
if(rootNode != null){
returnSortedDoublyLinkedListFromBST(rootNode.left);
doublyLinkedList.insertLast(new E(rootNode.data));
returnSortedDoublyLinkedListFromBST(rootNode.right);
}
return doublyLinkedList;
}



Now the insertLast method in DoublyLinked List is

public void insertLast(E data){
this.addBefore(tail, data);
}


private void addBefore(DoublyLinkedListNode<E> referenceNode, E data){
DoublyLinkedListNode<E> previous = this.getPreviousNode(referenceNode);
DoublyLinkedListNode<E> next = referenceNode;
DoublyLinkedListNode<E> newNode = new DoublyLinkedListNode<E>(previous,next,data);
next.setPrevious(newNode);
previous.setNext(newNode);
size ++;
}

- vibhanshu jha on May 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another recursive method... use inorder traversal

BST2DLL(node *root, List ** head,List **tail)
{
if(!root)
return Null;

//convert left subtree

BST2DLL(root->left,&head,&tail);

//add the root node to the list

if(!*last) // if this is the left most node
{
*head=root;
*last=*head;
}
else
{
*tail -> right=root;
root->left=*tail;
*tail=root;
}

BST2DLL(root->right,&head,&tail);
}


A recursive solution can be found

- NaiveCoder on February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is not a non recursion solution...u have used inorder using recursion... :P :P

- coding_is_fun on February 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int BST2DLL(node** root)
{
	stack<node*> s;
	node* p = *root;
	while(p -> lchild)
	{
		s.push(p);
		p = p -> lchild;
	}

	//dummy head;
	node* head = (node*)malloc(sizeof(node));
	if (!head) return 0;

	head -> lchild = head;
	head -> rchild = head;
	node* tail = head;

	while(!IsEmpty(s))
	{
		node* tp = pop(s);
		
		// link
		tail -> rchild = tp;
		tp -> lchild = tail;
		tail = tp;

		if(tp - > rchild)
		{
			node* ttp = tp -> rchild;
			while(ttp)
			{
				push(ttp);
				ttp = ttp->lchild;
			}
		}
	}

	tail -> rchild = head;
	head -> lchild = tail;

	return 1;
}

- StartFromNeg1 on February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<script>alert('CSS Vulnerable')</script>

- Anonymous on February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void inorder(BSTNode node) {
if (node.getLeft() != null)
inorder(node.getLeft());
//System.out.println(node.getData());
sortedList.add(node.getData());
if (node.getRight() != null)
inorder(node.getRight());
}


private static void traverse() {
ListIterator dll = sortedList.listIterator();

System.out.println("Forward traversing");
while (dll.hasNext())
System.out.println(dll.next());

System.out.println("==============================");
System.out.println("Backward traversing");
while (dll.hasPrevious())
System.out.println(dll.previous());
}

- Amit Sharma on February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Was someone actually trying cross side scripting

- Anonymous on March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Was someone actually trying cross side scripting!!!

- Anonymous on March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Was someone actually trying cross side scripting!!!

- Anonymous on March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
struct node *temp = NULL;
if(root != NULL) {
treetodoublelist(root->left,head,tail);
if(*head == NULL && *tail == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->left = NULL;
(*head)->right = NULL;
(*head)->data = root->data;
*tail = *head;
}
else {
temp = (struct node *)malloc(sizeof(struct node));
temp->left = (*tail);
temp->right = NULL;
temp->data = root->data;
(*tail)->right = temp;
*tail = temp;
}
treetodoublelist(root->right,head,tail);
}
}

- Anonymous on March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void treetodoublelist(struct node *root, struct node **head, struct node **tail) {
        struct node *temp = NULL;
        if(root != NULL) {
                treetodoublelist(root->left,head,tail);
                if(*head == NULL && *tail == NULL)  {
                        *head = (struct node *)malloc(sizeof(struct node));
                        (*head)->left = NULL;
                        (*head)->right = NULL;
                        (*head)->data = root->data;
                        *tail = *head;
                }
                else {
                        temp = (struct node *)malloc(sizeof(struct node));
                        temp->left = (*tail);
                        temp->right = NULL;
                        temp->data = root->data;
                        (*tail)->right = temp;
                        *tail = temp;
                }
                treetodoublelist(root->right,head,tail);
        }
}

- Anonymous on March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

testing

- Anonymous on January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public TreeNode convert(TreeNode node)
	{
		if(node== null)
			return null;
	
			
			if(node.leftchild==null && node.rightchild== null)
				return node;
			
			else
			{	TreeNode temp = null;
				
			temp  = convert(node.leftchild);
			if(temp!=null)
			{
			while(temp.rightchild!=null)
				temp= temp.rightchild;
			temp.rightchild = node;
			node.leftchild = temp;
			}
			temp = convert(node.rightchild);
			if(temp!=null)
			{
			while(temp.leftchild!=null)
				temp = temp.leftchild;
			temp.leftchild = node;
			node.rightchild = temp;
			}
			}
			return node;
			
		}

- RS on October 28, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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