Amazon Interview Question for Software Engineer / Developers


Country: United States




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

Selection algorithm is applicable on linked lists.

- mahdi.oraei February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you provide the implementation of the quick select which is sorting the linked list? I just can't see how to randomly access list's elements during the partitioning phase.

- Anonymous February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have to correct myself. It is not applicable since a[n] in array can be reached in O(1) while linked_list.get(n) is applicable in O(n). The good way maybe is to use toArray function before using the selection algorithm.

It is hard to provide the whole description of selection algorithm. The idea is to divide the whole array to subarrays of size 5. Then use insertion sort on them. pick the median of each. use the same strateghy for the medians to find the median of medians. use partition of quick sort and the pivot is the median of medians. Now if the median of median is the k-th element after the partition, return, otherwise based on k > median of medians position or k< median of medians, find the K-th biggest in either sides of the array.

- mahdi.oraei February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two broad types/variants of the partition subroutines used for Quick(sort/select):

1) One broad type only has pointers/indices going from left to right

pos=0;
for(i=0; i<n; i++)
	if(A[i] < pivotVal ) swap(A[i], A[pos]), pos++;

swap(A[pivotPos], A[pos]); // assuming pivot was hiding on right edge

/* check code above  for bugs */

2) The other type has 2 pointers/indices going inwards from both ends, until there is a mismatch (left indexed array element > right indexed array element), and then a swap is triggered. Then the pointers start moving inwards again....

THIS is the Partition Subroutine type that runs very fast and makes Quick___ even more blazingly fast in practice .... and it is only a few lines of slick code. So MOST quicksort/select code with arrays will have type 2) partition subroutines.

------

Moral of the story, if you want to do quickselect(or quicksort) on singly linked lists, just use the Type 1) partition subroutine. You also need to adjust it a little such that you are always pointing to the elements before the to-be-swapped elements (the usual gotchas with linked lists).

- S O U N D W A V E February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

$1 to the person who finds the big bug in the code above :P

- S O U N D W A V E February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are using the array instead of list. So I assume that you have converted the list first but this is more space consuming. The question is if QS can be applied without the conversion.

- Anonymous February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

will the MAX heap help here?

- deepak.us7 February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

ُThe running time of max heap for extracting k Max is O(Klgn) It might not help if K is O(n).

- mahdi.oraei February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Building a heap might work out or for kth greatest number maintain k + 1 pointers. Just try it with 2nd largest and 3rd largest element and check if k + 1 pointer funda works or not.

- chandrani February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

getKthLargestInLL( linkedList, K ){
	for( int i = 1; i<= K; i++ ){
		NODE node = findMax( linkedList );
		if( node == linkedList )
			linkedList = linkedList.next;
	}
}

NODE findMax( linkedList ){
	Node maxNode = null;
	Node preMaxNode = null;
	Node lastNode = null;
	while( linkedList != null ){
		if( maxNode == null || maxNode.data < linkedList.data ){
			maxNode = linkedList;
			preMaxNode = lastNode;
		}
		lastNode = linkedList;
		linkedList = linkedList.next;
	}
	if( lastNode != null )
		lastNode.next = maxNode.next;
	return maxNode;
}

- struggler February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: We consider last node as the pivot and then partition the linked list using that pivot element. All the nodes smaller than the pivot will come before the pivot node and all the nodes greater than the pivot will come after the pivot node in the modified linked list.
We pass the pivot element back to the calling method and see if the pivot is the desired kth element, in case it is we just return the pivot.
In case the position of the pivot is greater than the desired position, say k then we run the algorithm on the left side of the pivot node(i,e. from the head to the node prior to the pivot node).
In case the position of pivot is less than the desired position, we run the algorithm on the nodes that are on the right side of the pivot node( i,e node next to pivot to the tail) and decrease the distance by i(i being the position of the pivot in the linked list).

Code:
#include <iostream>
#include <cstdio>
using namespace std;

struct node
{
int data;
struct node *next;
};

/* Insert a node at the beginning of linked list */
void push(struct node** head_ref, int new_data)
{
struct node* new_node = new node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}

/* A utility function to print linked list */
void printList(struct node *node)
{
while (node != NULL)
{
cout<<node->data<<"\t";
node = node->next;
}
cout<<endl;
}

// Returns the last node of the list
struct node *getTail(struct node *cur)
{
while (cur != NULL && cur->next != NULL)
cur = cur->next;
return cur;
}

struct node *partition(struct node **head, struct node **tail)
{
struct node *p,*q,*pivot=*tail,*temp;
p=*head;
while(p!=pivot)
{
if(p->data<=pivot->data)
{
q=p;
p=p->next;
}
else if(p->data>pivot->data)
{
if(p==*head)
{
*head=(*head)->next;
}
else{
q->next=p->next;
}
temp=p->next;
(*tail)->next=p;
p->next=NULL;
*tail=p;
p=temp;
}
}
return pivot;
}

void quicksort(struct node **head, struct node **tail)
{
if(*head==NULL || *head==*tail) return;

struct node *p, *n;
p=partition(head,tail);

n=*head;
if(n!=p)
{
while(n->next!=p) n=n->next;
n->next=NULL;
quicksort(head,&n);
n->next=p;
}
quicksort(&(p->next),tail);

return;
}

void quickSort(struct node **head)
{
struct node *n=getTail(*head);
quicksort(head,&n);
return;
}

struct node *kthElementHelper(struct node **head, struct node **tail, int k)
{
int i=1;
struct node *p,*n,*res,*temp;
p=partition(head,tail);
n=*head;

if(n==p)
{
if(i!=k) return kthElementHelper(&(n->next),tail,k-1);
else return p;
}

while(n->next!=p)
{
n=n->next;
i=i+1;
}
i=i+1;
if(k==i) return p;
else if(k<i)
{
n->next=NULL;
res= kthElementHelper(head,&n,k);
n->next=p;
}
else if(k>i)
{
temp=(*tail)->next;
(*tail)->next=NULL;
res= kthElementHelper(&(p->next),tail,k-i);
(*tail)->next=temp;
}
return res;
}

struct node *kthElement(struct node **h,int k)
{
struct node *n=getTail(*h);
return kthElementHelper(h,&n,k);
}

int main()
{
struct node *a = NULL;
int k=3;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
push(&a, 1);

cout << "Linked List before calling the Method \n";
printList(a);


cout<<"\nk is: "<<k<<endl<<"kth largest element is: "<<kthElement(&a,k)->data<<endl<<endl;

cout << "Linked List after calling the method \n";
printList(a);

return 0;
}

- Isha February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algorithm is correct. In your algorithm, the worst case scenario which the actual list is sorted and your are looking for the maximum takes O(n^2). The selection algorithm takes O(n), although it is much harder to implement.

- mahdi.oraei February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain a binary search tree of k nodes. Scan the input list, if current node value is larger than the smallest value of the tree nodes, remove that node and insert current node value into the binary search tree.

Time complexity is O(nlogk).

- zouzhile February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

quickSelect logic for a linked list
Need to know the tail of the list for the logic to work.

static class Node{int v;Node next;public Node(int v){this.v=v;}public String toString(){return ""+v+","+next;}}
        void swap(Node n1, Node n2){if(n1==n2) return; int tmp=n1.v;n1.v=n2.v;n2.v=tmp;}
        Integer quickSelect(Node h, Node t, int k)
        {
	            if(h==null||k<1) return null; if(h==t&&k==1)return h.v;
            //partition and search
            Node pivot = h, storeNode=h.next, t1=null;
            int leftSize=0;
            for(Node nd = h.next;nd!=null;nd=nd.next)
            {
                if(nd.v>=pivot.v){swap(nd,storeNode);t1=storeNode;storeNode=storeNode.next;leftSize++;}
            }
            if(leftSize+1 == k) return pivot.v;
            if(k<=leftSize)return quickSelect(h.next, t1, k);
            return quickSelect(storeNode, t, k-leftSize-1);
	}

- Anonymous February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

quicksort can be implemented on doubly linked list but not on singly linked list. So it depends. But you can copy linkedlist data from linkedlist to array and then apply quick select

- Anonymous March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

yes.. It can be applied as we can apply quick sort on SLL/

- Anonymous March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If we can modify this linked list:

Node * k_largest(root, k):
             If root == NULL:
                Return NULL
             Node *p = root
             counter = 0
             While p != NULL And counter < k - 1:
                   Node *mp = find_max(p)
                   If mp->val > p->val:
                      t = mp->val
                      mp->val = p->val
                      p->val = t
                   p = p->next
                   counter = counter + 1
             Return find_max(p)

       Node * find_max(p):
            If p == NULL:
               Return NULL
            max_val = p->val
            max_node = p
            p = p->next
            While p != NULL:
                  If max_val < p->val:
                     max_val = p->val
                     max_node = p
                  p = p->next
            Return max_node

- Anonymous February 25, 2014 | 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