## Amazon Interview Question for Software Engineer in Tests

• 0

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
12
of 12 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 .

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

dutch national flag problem..

Comment hidden because of low score. Click to expand.
0

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.

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....

Comment hidden because of low score. Click to expand.
0

We can use hash table, instead of three variables.

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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)

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.

Comment hidden because of low score. Click to expand.
0

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

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

My solution

``````public class sampleSort123 {

private static tailNode = null;

// ASSUMPTION: headNode and tailNode are given to us.

// Disconnect the node from the doubly linked list
Node leftNode = node.getLeftNode();
Node rightNode = node.getRightNode();

leftNode.setRightNode(rightNode);
rightNode.setLeftNode(leftNode);

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() {

while(currentNode.getRightNode != null) {
if(currentNode.getValue() == 1)
else if(currentNode.getValue() == 3)
moveToTail(currentNode);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

nice approach

Comment hidden because of low score. Click to expand.
0

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....

Comment hidden because of low score. Click to expand.
0

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

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

{
Node typeA = new Node (1);
Node typeB = new Node (2);
Node typeC = new Node (3);

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;
}

}

//combining the 3 parts

}

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 typeB = new Node (2);
Node typeC = new Node (3);

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

//combining the 3 parts

}``````

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.

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.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

question states that you can't exchange values

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

<pre lang="" line="1" title="CodeMonkey46359" class="run-this">class SortLinkedList {
Node[] starters = new Node;
do {
Node curNode = starters[head.getData() - 1];
if (curNode == null) {
} else {
Node lastNode = curNode.getPrev();
}

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>

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

Comment hidden because of low score. Click to expand.
0

Same as Dutch Flag Algorithm linked list version

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

Move 1's to head, Move 3 to tail

Comment hidden because of low score. Click to expand.
0

Correct! :)

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

Duplicate for qns 11561969

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

Comment hidden because of low score. Click to expand.
0

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.

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

{
{ return NULL;
}

{
}

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

else
{
return ptr2;
}
}

}

Comment hidden because of low score. Click to expand.
0

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

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

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

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)

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

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:
dll(){
}
void insert(int i){
Node *n=new Node(i);
while(temp->next!=NULL) temp=temp->next;
temp->next=n;
n->prev=temp;
}
void display(){
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;}
else{
tmp->prev=tmp2->prev;
tmp2->prev->next=tmp;
tmp->next=tmp2;
tmp2->prev=tmp;
}
}
void sort(dll list){
list.display();
cout<<endl;

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;
}

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.

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).

Comment hidden because of low score. Click to expand.
0

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

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.

### 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.