Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

swap Nodes values instead

- avico81 October 11, 2012 | Flag Reply
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

- JustCoding October 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Merge sort is best suited for linked list.

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

- Aashish October 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The example in the link uses at least 3 extra nodes

- Curious October 12, 2012 | Flag
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?

- Aashish October 13, 2012 | Flag
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.

- Brian October 18, 2012 | Flag
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

- Yateen October 28, 2012 | Flag
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)

- dontulakapil November 11, 2012 | Flag
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!!

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

Doesn't mergesort inherently uses extra nodes?

- girish October 11, 2012 | Flag Reply
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.

- Aashish October 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yeah thanks.. realized that.. :)

- girish October 11, 2012 | Flag Reply
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

- rahvii October 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rahvii October 11, 2012 | Flag
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

- rahvii October 11, 2012 | Flag
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[1000];
  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[0]);
    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;
}

- Charlene@tsynka.com October 12, 2012 | Flag Reply
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

- Internet747 October 12, 2012 | Flag Reply
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();
}

- shivi October 18, 2012 | Flag Reply
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)

- parikksit.b October 28, 2012 | Flag Reply
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.

- buckCherry November 13, 2012 | Flag Reply
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.

- Vikas November 21, 2012 | Flag Reply
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;
}
}

- Qamar Alam December 05, 2012 | Flag Reply
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;
}

- Anonymous June 09, 2013 | Flag Reply
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
-------------------------------
*/
}
}
}

- Nandu deshmukh January 08, 2016 | 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