Amazon Interview Question for Software Engineer in Tests


Country: India
Interview Type: Written Test




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

take three pointers one, two and three.
first of all search for a 1 and move( delete from current) it to head (if 1 is already at head then omit this step)
now traverse the list starting from 2nd node
if found 1 delete it and move it to the head (update the head also)
if found 2 dont do anything just move to nect node.
if found 3 move it to last .

- getjar.com/todotasklist my android app November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

dutch national flag problem..

- swathi November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

With same time complexity of O(n) but will less visit, we can solve this.
Traverse once and if you encounter 1, keep the node and if otherwise move them to corresponding list identified by two pointers 2nd & 3rd. We also need another pointer to keep track of tail of the list holding 2's (i.e. the one having 2nd pointer as head). Now when you finish traversing and separating 2's and 3;s from the list, all you need to do is point last element of original node to the list with 2's and point the tail of this list to the start of the list with 3's.

- buckCherry November 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

why so much...

take 3 int variables.. count the occrence of each digit in the first parse of link list....
in the second parse replace the node value as the number of occrance of 1 then 2 and then 3....

- sanjay.2812 November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use hash table, instead of three variables.

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

I agree, take a hashmap where keys are the given integers ,i.e., 1,2,3 and values are number of occurrences of integers.
2. Traverse through the linkedList and keep incrementing the corresponding key's value.
3. Replace the values in linked list

- Sim February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the question says "without exchanging the values", we need to swap the nodes

- Avishek Gurung February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

2 pointers original_head, original_tail

1. orignal_head = head;
2. Traverse DLL from tail to original_head.
2a. If nodeValue = value 1 ; move node to head (start).

# original_head is required because in step 2a we add the node to beginning (head), thereby changing value of head. Without original_head we would be stuck in an endless loop.

3. orignal_tail = tail;
4. Traverse DLL from original_head to original_tail.
4a. If nodeValue = value 3 ; move node to tail (end).

# Value 2 falls in place by itself.

Complexity: O(n) + O(n) = O (n)

- Raj November 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

instead of keeping 3 separate lists and merging it in last . Keep two check-points which marks end 1's, and 2's . now you traverse the list , when ever you find a 1, detach it from current position and attach to 1's check point, same thing for 2's. after you traversed the list once , it will be sorted.

- i want a Job November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this solution is best because the earlier two solutions require an initial pass through all the nodes ?!

- Anonymous November 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution

public class sampleSort123 {

	private static headNode = null;
	private static tailNode = null;
	
	// ASSUMPTION: headNode and tailNode are given to us.

	public static moveToHead(Node node) {
		// Disconnect the node from the doubly linked list
		Node leftNode = node.getLeftNode();
		Node rightNode = node.getRightNode();
		
		leftNode.setRightNode(rightNode);
		rightNode.setLeftNode(leftNode);
		
		headNode.setLeftNode(node);
		headNode = node;
		
		return;
	}
	
	public static moveToTail(Node node) {
		// Let the address be of Long type
		// Disconnect the node from the doubly linked list
		Node leftNode = node.getLeftNode();
		Node rightNode = node.getRightNode();
		
		leftNode.setRightNode(rightNode);
		rightNode.setLeftNode(leftNode);
		
		tailNode.setRightNode(node);
		tailNode = node;
		
		return;
	}
	
	private static sort123Array() {
		Node currentNode = headNode;
		
		while(currentNode.getRightNode != null) {
			if(currentNode.getValue() == 1) 
				moveToHead(currentNode);
			else if(currentNode.getValue() == 3)
				moveToTail(currentNode);
		}
	}
}

- axecapone November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to add a line of code in the while loop
currentNode = currentNode.getRightNode();

- axecapone November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forget to update the new node previous and next, forget to return leftNode as currentNode

- Alan May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take 3 pointers to store 3 link lists for 1,2,3,
now start deleting all the nodes from the link list and instead of freeing the deleted node, append it to proper pointer above mentioned.
Then finally merge the lists

- Anonymous November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

delete will be overkill, just traverse thru the list and keep the pointers appending to proper pointers

- Anonymous November 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice approach

- getjar.com/todotasklist my android app November 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

take 3 int variables.. count the occrence of each digit in the first parse of link list....
in the second parse replace the node value as the number of occrance of 1 then 2 and then 3....

- sanjay.2812 November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your approach is correct . but i dont think that interviewer want this approach, i mean it straight forward.

- getjar.com/todotasklist my android app November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this?

Node sort(Node head)
{
Node typeA = new Node (1);
Node headA = typeA;
Node typeB = new Node (2);
Node headB = typeB;
Node typeC = new Node (3);
Node headC = typeC;
Node current = head;

while(current! = null)
{
if(current.Value == typeA.value)
{
typeA.next = new Node(current.value);
typeA = typeA.next;
}
else if(current.Value == typeB.value)
{
typeB.next = new Node(current.value);
typeB = typeB.next;
}
else if(current.Value == typeC.value)
{
typeC.next = new Node(current.value);
typeC = typeC.next;
}

}
Node tmp = headA;
headA = headA.next;
Node tmp = headB;
headB = headB.next;
Node tmp = headC;
headC = headC.next;

//combining the 3 parts
typeA.next = headB;
typeB.next = headC;

return headA;

}

- unemployed coder November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oops! forgot to progress the current pointer

Node sort(Node head)
{
        //make 3 dummy nodes 
	Node typeA = new Node (1);
	Node headA = typeA;
	Node typeB = new Node (2);
	Node headB = typeB;
	Node typeC = new Node (3);
	Node headC = typeC;
	Node current = head; 

	while(current! = null)
	{
		if(current.Value == typeA.value)
		{
			typeA.next = new Node(current.value);
			typeA = typeA.next;
		}
		else if(current.Value == typeB.value)
		{
			typeB.next = new Node(current.value);
			typeB = typeB.next;
		}
		else if(current.Value == typeC.value)
		{
			typeC.next = new Node(current.value);
			typeC = typeC.next;
		}
		current = current.next;
	}
       //deleting the first dummy nodes
	Node tmp = headA;
	headA = headA.next;
	Node tmp = headB;
	headB = headB.next;
	Node tmp = headC;
	headC = headC.next;
	
	//combining the 3 parts
	typeA.next = headB;
	typeB.next = headC;

	return headA;

}

- unemployed coder November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Must cosider the fact that the given link list is doubly. So, we can easily implement this in the same fashion as for grouping 1,2,3 together in an array.

Above stated methods are true for single link list.

- Nascent Coder November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Must consider the fact that the given link list is doubly. So, we can easily implement this in the same fashion as for grouping 1,2,3 together in an array.

Above stated methods are true for single link list.

- Nascent Coder November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about having 3 variables reprenting the number of occurences for 1, 2 and 3 in the list. Then just traverse the list counting 1s and 2s and 3s. Once ended create a new list with as many nodes as the counters describe

- Anonymous November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In my opinion, this is the simplest and the best one.

- Victor November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, this solution is workable for singly as well as doubly linked lists.

- Victor November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

question states that you can't exchange values

- vishal March 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey46359" class="run-this">class SortLinkedList {
public Node sort123(Node head) {
Node[] starters = new Node[3];
Node firstNode = head;
do {
Node next = head.getNext();
head.setNext(head);
head.setPrev(head);
Node curNode = starters[head.getData() - 1];
if (curNode == null) {
starters[head.getData() - 1] = head;
} else {
Node lastNode = curNode.getPrev();
lastNode.setNext(head);
head.setPrev(lastNode);
head.setNext(curNode);
curNode.setPrev(head);
}
head = next;
} while (firstNode != head);

firstNode = null;
for (int i = 0; i < 3; ++i) {
Node curNode = starters[i];
if (curNode != null) {
if (firstNode == null) {
firstNode = curNode;
} else {
Node prevLast = firstNode.getPrev();
Node lastCur = curNode.getPrev();
prevLast.setNext(curNode);
curNode.setPrev(prevLast);
lastCur.setNext(firstNode);
firstNode.setPrev(lastCur);
}
}
}
return firstNode;
}
}</pre><pre title="CodeMonkey46359" input="yes">
</pre>

- forinterview2 November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

American Flag, Link list version???

- appscan November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same as Dutch Flag Algorithm linked list version

- Maclane November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Move 1's to head, Move 3 to tail

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

Correct! :)

- Anonymous December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Duplicate for qns 11561969

- Puzzle November 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

People Proposing so complex ,

1st dutch nation flag problem but it requires the swapping elements isn't it ?

what else we can do , take 3 counter , traverse linked list , count for each 1,2,3
then just put 1 , 2, 3 on basis of corresponding counter isn't it ?

correct me if anything ?

Shashank

- WgpShashank November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Works if there is one and only one value in data field.

Consider this 2 data columns first and last name.

I am sorting only on first-name basis. Does not necessarily mean last name is the same too.

- Raj November 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Recursive sort doubly link list

node* sortDoubly(node *head)
{
node*ptr2=NULL,*ptr3=NULL, *ptr4=NULL, *headprev=NULL;
if (!head)
{ return NULL;
}

else if(head->next==NULL)
{
return head;
}


//ptr2=ptr->next;
ptr2=sortDoubly(head->next);
if(head->a > ptr2->a)
{ headprev=head->back;
ptr2->back=headprev;
headprev->next=ptr2;
ptr3=ptr2;
while(ptr3->next && head->a > ptr3->a )
{
ptr3=ptr3->next;
}
if (ptr3->next)
{
ptr4=ptr3->back;
ptr4->next=head;
head->back=ptr4;
head->next=ptr3;
ptr3->back=head;
return ptr2;
}

else
{
ptr3->next=head;
head->next=NULL;
head->back=ptr3;
return ptr2;
}
}

return head;


}

- divakargilani December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this soln simply sorts the data in the doubly link list.. and corrects the back and next pointer whenever node is moved.

- divakargilani December 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort(node p)
{
node r=null;
int i=0;
p=firstaddress;
boolean b=true;
while(b==true)
{
b=false;
p=firstaddress;

r=null;
i=0;
while(p!=null)
{
i++;
node q = p.next;
show(p);
System.out.println("\n");
if(q==null)
{
break;
}
else
{
if(p.val>q.val)
{
b=true;
r=p.prev;
if(r!=null)
r.next=q;
p.prev=q;
p.next=q.next;
if(q.next!=null)
q.next.prev=p;
q.prev=r;
q.next=p;

if(i==1)
firstaddress=q;

}
else
{
if(i==1)
firstaddress=p;
p=p.next;
}
}
}
}
}
not bothering aout the time complexcity..o(n2)

- noname December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check it, working correct:


#include<iostream>
#include<string.h>

using namespace std;
class Node{
public:
int n;
Node *next,*prev;
Node(int i){
n=i;
next=prev=NULL;
}
};
class dll{
public:
Node *head;
dll(){
head=NULL;
}
void insert(int i){
Node *n=new Node(i);
if(head==NULL) {head=n;return;}
Node *temp=head;
while(temp->next!=NULL) temp=temp->next;
temp->next=n;
n->prev=temp;
}
void display(){
Node *temp=head;
while(temp!=NULL){
cout<<temp->n<<" --> ";
temp=temp->next;
}
cout<<endl;
}
};
void correct(dll list,Node *temp){

Node *tmp=temp->next;
temp->next=tmp->next;
if(temp->next!=NULL) temp->next->prev=temp;
Node *tmp2=temp;
while(tmp2!=NULL&&tmp2->prev!=NULL){ if(tmp2->prev->n<=tmp->n){break;}tmp2=tmp2->prev;}
if(tmp2==NULL){tmp->next=list.head;
list.head->prev=tmp;
list.head=tmp;}
else{
tmp->prev=tmp2->prev;
tmp2->prev->next=tmp;
tmp->next=tmp2;
tmp2->prev=tmp;
}
}
void sort(dll list){
list.display();
cout<<endl;
Node *temp=list.head;

temp=list.head->next;
while(temp!=NULL&&temp->next!=NULL){
if(temp->n>temp->next->n){
correct(list,temp);
continue;
}
temp=temp->next;
}
cout<<endl<<"Sorted: "<<endl;
list.display();
}

int main(){
dll list;
int str[]={1,3,2,1,2,3,2,1,1};
int size=sizeof(str)/sizeof(int);
for(int i=0;i<size;i++){
list.insert(str[i]);
}
sort(list);
cout<<endl;
system("pause");
return 0;
}

- HarishIITR January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can implement this Quicksort style - use 2 as pivot to shove all 1's to the left and 3's to the right.

- kislay.nsit February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

A Naive solution:

Take three copies of the list, one for each of the three numbers. Eg, First list for 1, Second for 2, and Third for 3.

Traverse each linked list deleting elements other than the one it represents.
Then append all three lists in sorted order.

This has O(kn) running time and O(kn) space complexity, where 'k' is the number of unique elements (in this case - 1,2 and 3).

- Anonymous November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow... what an approach!! never knew a question with constant space complexity has to be done in O(kn).. slow clapping..please :P

- Brijesh November 27, 2011 | Flag


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