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 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 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 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 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 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 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 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 February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous 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 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 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 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 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 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 March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

testing

- Anonymous 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 October 28, 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