## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 6 vote

swap Nodes values instead

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

what is your complexity going to be? Mergesort is O(n log n) so

Comment hidden because of low score. Click to expand.
3
of 5 vote

Merge sort is best suited for linked list.

Follow this link for explanations and implementation:
geeksforgeeks.org/archives/7740

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

The example in the link uses at least 3 extra nodes

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

Do you even know the difference between a node and a pointer?
Node doesn't exist until memory is allocated for it. Can you tell how did you count three extra nodes?

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

The mergesort works, but if I had to whiteboard that, it'd be screwed.

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

Can u tell how quicksort will perform poorly than merge sort? In quicksort also, we just need to swap the nodes wherever our condition is valid. There is no randomized access and no traversing of list again and again

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

Worst case of quick sort is O(n2). if we take input as sorted array for quick sort, with last element as pivot, it takes O(n2) time.

Recurrence relation is
T(n)=T(n-1)+O(n)

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

The links geeksforgeeks.org/archives/7740 as well this one askville.amazon.com/scenarios-quicksort-faster-mergesort/AnswerViewer.do?requestId=1239017 state that quicksort performs poorly for linked list whereas heapsort is impossible for a linked list.

Like ‘Yateen’, am not yet fully convinced why quicksort works poorly. Conceptually I see quicksort for linked-list has avg. runtime of O(nlogn) just like for an array. As the later link hints that the nature of quick sort enforces a bi-directional traversing during portioning, it might cause cache misses for large sized linked list involving virtual memory (i.e. some data in secondary storage), I think it might be the reason but am not fully convinced yet. Any technical explanation on this or otherwise would be much appreciated!!
Moreover, I’ve no clue why the other sorting technique i.e. heapsort is impossible for a linked list. I can prove that a heapsort can be performed with O(nlogn) for a linked list just like for an array. To avoid cluttering I’m posting the pseudo algorithm and runtime calculation for heapsort for a linked list in a separate response at the bottom of this post (see below). Pls. enlighten me of any missing link causing the impossibility of heapsort in linked list!!

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

Doesn't mergesort inherently uses extra nodes?

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

Merge sort only uses extra pointers. We are not allocating any memory for nodes in merge sort.

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

Yeah thanks.. realized that.. :)

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

Quick sort is pretty efficient and doesn't use any other node, just swapping

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

wait, linked list don't just backtrack! Silly me :P

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

It can still be done anyways, just be smart on your code

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

``````/*
Hint: Do not allow using additional node, but is it allowed to use additional node values?
*/

#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef struct NodeT {
int data;
NodeT *right;
}Node;

void swapNode(Node *l, Node *r)
{
int tmp = l->data;
l->data = r->data;
r->data = tmp;
}

Node * newNode(int num)
{
Node * node = new Node();
node->data = num;
node->right = NULL;
return node;
}

Node * appendNode(Node *root, int data)
{
if (root == NULL) {
return newNode(data);
}

Node *node = newNode(data);

root->right = node;

return node;
}

Node * sortList(Node *head, int n)
{
if (head == NULL || head->right == NULL || n <= 1) {
return head;
}

int randIndex = rand() % n;

Node *target = head;

for (int i = 0; i < randIndex; i ++) {
if (target) {
target = target->right;
}
}

swapNode(head, target);

int i = 1, count = 0;
Node *tail = head;
for (Node *iter = head->right; i < n && iter; i ++, iter = iter->right) {
if (iter->data < head->data) {
count ++;
tail = tail->right;
swapNode(tail, iter);
}
}

swapNode(head, tail);

head = sortList(head, count);
tail->right = sortList(tail->right, n - count - 1);

return head;
}

void printList(Node *head, int n)
{
if (!head) {
return;
}

for (int i = 0; i < n && head; i ++) {
cout << head->data << " ";
head = head->right;
}

cout << endl;
}

void cleanList(Node *root)
{
if (root == NULL) {
return;
}

cleanList(root->right);

root->right = NULL;
root->data = 0;

delete root;
}

int main()
{
int a;
int n = 100;
while (cin >> n && n != 0) {
if (n > 1000) {
break;
}

for (int i = 0; i < n; i ++) {
a[i] = i;
}

for (int i = 0; i < n; i ++) {
int r = rand() % n;
int tmp = a[i];
a[i] = a[r];
a[r] = tmp;
}

Node *head = NULL;
head = appendNode(head, a);
Node *last = head;

for (int i = 1; i < n; i ++) {
last = appendNode(last, a[i]);
}

head = sortList(head, n);
printList(head, n);
cleanList(head);
}

return 0;
}``````

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

``````def sort_link_list(head_node):
while (True):
curr = head_node
changed = False
while (curr.next_node is not None):
if (curr.value < curr.next_node.value):
curr.value = curr.value ^ curr.next_node.value
curr.next_node.value = curr.value ^ curr.next_node.value
curr.value = curr.value ^ curr.next_node.value
changed = True
curr = curr.next_node
if (not changed):
break``````

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

mergesort for link lists does not use extra space...
it is an in place algorithm...
so O(nlogn)

//programme by shivi
#include<iostream>
#include<conio.h>
using namespace std;
class LinkList
{
private:
struct Node
{
int item;
Node* next;
Node(int k,Node* x)
{
item=k;
next=x;
}
};
Node* start;

public:
LinkList()
{
start=NULL;
}

void AddNode(int key)
{
Node *p=new Node(key,start);
start=p;
}

void Print()
{
pr(start);
}

void pr(Node *x)
{
if(x==NULL)return;
pr(x->next);
cout<<x->item<<" ";
}

void MergeSort()
{
mergesort(&start);
}

void mergesort(Node **start)
{
Node *x=*start,*lo,*mid;
if(x->next==NULL || x==NULL)
return;

splitlist(*start,&lo,&mid);
mergesort(&lo);
mergesort(&mid);
*start=mergelist(lo,mid);
}

void splitlist(Node *start,Node **lo,Node** mid)
{
if(start==NULL || start->next==NULL)
{
*lo=start;*mid=NULL;
}

else
{
Node *a=start,*b=start->next;

while(b!=NULL)
{
b=b->next;
while(b!=NULL)
{
a=a->next;
b=b->next;
}
}
*lo=start;
*mid=a->next;
a->next=NULL;
}

}

Node* mergelist(Node *lo,Node *mid)
{
Node *newstart=NULL;
if(lo==NULL)
return mid;
if(mid==NULL)
return lo;

if(lo->item>=mid->item)
{
newstart=lo;
newstart->next=mergelist(lo->next,mid);
}

else
{
newstart=mid;
newstart->next=mergelist(lo,mid->next);
}
return newstart;
}

bool CheckIdenticalLinkLists(Node * a,Node* b)
{
if(a==NULL && b==NULL)
return 1;
else if(a==NULL && b!=NULL)
return 0;
else if(a!=NULL && b==NULL)
return 0;
else if(a->item!=b->item)
return 0;

return CheckIdenticalLinkLists(a->next,b->next);
}

void alternate()
{
Node*a,*b;
AlternateSplit(start,&a,&b);
pr(a);
cout<<endl;
pr(b);
}

void AlternateSplit(Node *start,Node** a,Node** b)
{
Node *s1=start,*s2=start->next,*x=s1,*y=s2;
if(start==NULL || start->next==NULL)
{
*a=start;
*b=NULL;
}

else
{
while(b || a)
{
x->next=y->next;
x=x->next;
y->next=x->next;
y=y->next;
}

}

if(x->next!=NULL) x->next=NULL;
if(y->next!=NULL) y->next=NULL;
*a=s1;
*b=s2;
}
};
int main()
{
LinkList l;
LinkList k;
l.AddNode(2);
l.AddNode(1);
l.AddNode(4);
l.AddNode(6);
l.AddNode(3);
l.AddNode(9);
k.AddNode(2);
k.AddNode(5);
k.AddNode(19);
k.AddNode(6);
k.AddNode(8);
k.AddNode(1);
l.Print();
cout<<endl;
// l.Print();cout<<endl;k.Print();
l.MergeSort();//k.MergeSort();
//cout<<endl;
l.Print();cout<<endl;//k.Print();
//l.alternate();
}

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

I like the first answer to simply swap the value. Alternately, if we aren't even allowed to use a second variable, and assuming the singly linked list contains only numbers as data, we can use the typical math operations to swap the values.
a=21, b=5
1. a=a+b (a becomes 26)
2. b=a-b (b becomes 21)
3. a=a-b (a becomes 5)

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

This post is in reference to my previous response above where I'm wondering why some links say that heapsort for linked list is nearly impossible.
Here I provide an algortihm that runs in O(nlogn) time. Most of the algortihm is taken from cormen's book except the method 'heapsort'

``````Pseudo algorithm and runtime calculation for heapsort (ascending order) for a linked list (with single forward pointer/ref)
-------------------------------------------------------------------------
heapsort(Node h) {//first time invoke this with head of the list
n=get_length_of_list(h);  //runs in O(n)
build_max_heap(h);     //runs in O(nlogn)

//handle max element of the entire list which would be the tail after sorting in ascending order
Node h_dash=h->next;  //no additional node just a temporary variable thus fixed memory O(1)
h->next=h->next->next;  //null check for h->next and returning is omitted for simplicity
h_dash->next=null;     //ensure tail’s next field points to null

//now we keep on max_heapify the rest of the list and keep removing the max element from
//	head of the given list and subsequently adding them to the head of the new list identified by
//h_dash
while h->next != null
max_heapfy(h);  //runs in O(logn)
Node t=h_dash  //another temporary variable ensuring O(1) memory
h_dash=h->next;
h->next=h->next->next; //null check not required since h->next is not null
h_dash=t;
end-while
//point the new list to the original head
h->next=h_dash;
----------------------------------

build_max_heap(Node h){ //runs in n times of runtime-of(max_heapfy) i.e. O(nlogn)
n=get_length_of_list(h);  //this need not to be calculated again and can be passed as argument
for i from (n/2) downto 1 //indexing starts from 1 at head to n in the tail side.
max_heapify(h, i);      //runs in O(logn) time
end-for
----------------------------------

max_heapify(Node h, int i, int n){ //see below
l=left_child_index(i)       //runs in O(1)
r=right_child_index(i)      //runs in O(1)

if l <= n and element_at(l) > element_at(i)  //runs in O(n)
largest=l  //we can also improve by storing the largest value in another variable, but omitted here
else
largest=i
end-if

if r <= n and element_at(r) > element_at(largest)  //runs in O(n)
largest=r
end-if

if largest != i
swap element_at(i) with element_at(largest)   //can be made O(1) we store relevant references during previous visits, but here it is O(n)
max_heapify(h, largest);
end-if

Run time of max heapify is:
T(n)= O(n) + O(n) + O(n) + T(2n/3)  //with this algortihm
= O(n) + T(2n/3)               //see cormen et. al. on why 2/3 of n
= O(nlogn)

Thus we see even for a linked list with forward pointer/ref we can have worst case heapsort time as O(nlogn) which is same as for an array.``````

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

Find Max and swap with last node and so on is the simplest solution I guess.

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

/**
I am using pointers but no extra node for sorting link list
*/

void LinkList::sort() {
Node*out_loop= head, *q=NULL, *p=head, *r=NULL;

while(out_loop!=NULL)
{
q=p;
while(q->next!=NULL) {
r=q->next;
//cout << q->data<<endl;
if(q->data > r->data) {
q->next=r->next;
r->next=q;
if(q==head) {
head = r;
p=r;
} else {
p->next=r;
p=r;
}
}else{
p=q;
q=q->next;
}
}
p=head;
out_loop=out_loop->next;
}
}

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

``````Node mergeSort(Node head){
if (head == null || head.next == null)
return head;
Node mid = getMidNode(head);
Node secondHalf_head = mid.next;
mid.next = null;
return merge(mergeSort(head) , mergeSort(secondHalf_head));
}

Node merge(Node head1 , Node head2){
Node current;
Node head;
Node temp1 = head1;
Node temp2 = head2;
if (head2.content < head1.content){
current = head2;
head = head2;
temp2 = temp2.next;
}else{
current = head1;
head = head1;
temp1 = temp1.next;
}
while (temp1 != null & temp2 != null){
if (temp1.content <= temp2.content){
current.next = temp1;
temp1 = temp1.next;
}else{
current.next= temp2;
temp2 = temp2.next;
}
}
if (temp2 != null)
current.next = temp2;
else
current.next = temp1;
return head;
}

Node getMidNode(Node head){
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}``````

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

{
{
{
#include<stdio.h>
#include<malloc.h>
struct Node{
int data;
struct Node *next;
}*head=NULL;
void input(int);
void show();
main()
{
int value;
char choise='y';
while(choise=='y'||choise=='Y')
{
printf("\n Enter integer values:-");
scanf("%d",&value);
input(value);
fflush(stdin);
printf("\n Enter another elemenet(y/n):-");
scanf("%c",&choise);
}
show();
}
void show()
{
printf("\n");
struct Node *temp=head;
while(temp!=NULL)
{
printf(" %d",temp->data);
temp=temp->next;
}

}

void input(int value)
{
struct Node *temp=head,*element=(struct Node*)malloc (sizeof(struct Node));
element->data=value;
if(head==NULL)
{
element->next=head;

head=element;
}
else if(value<=temp->data)
{
element->next=temp;
head=element;
}
else
{
while(temp!=NULL)
{
if(temp->data>=value)
{
element->next=temp->next;
temp->next=element;
break;
}

else if(temp->next==NULL&&temp->data<=value)
{
temp->next=element;
element->next=NULL;
break;
}
else if( temp->data<= value &&temp->next!=NULL &&temp->next->data>=value)
{
element->next=temp->next;
temp->next=element;
break;
}
temp=temp->next ;

}
}
}
/*
output

Enter integer values:-5

Enter another elemenet(y/n):-y

Enter integer values:-34

Enter another elemenet(y/n):-y

Enter integer values:-45

Enter another elemenet(y/n):-y

Enter integer values:-32

Enter another elemenet(y/n):-y

Enter integer values:-9

Enter another elemenet(y/n):-y

Enter integer values:-34

Enter another elemenet(y/n):-y

Enter integer values:-563

Enter another elemenet(y/n):-y

Enter integer values:-45

Enter another elemenet(y/n):-n

5 9 32 34 34 45 45 563
-------------------------------
*/
}
}
}

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