Amazon Interview Question
Software Engineer / DevelopersCountry: United States
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.
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.
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).
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;
}
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;
}
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);
}
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
Selection algorithm is applicable on linked lists.
- mahdi.oraei February 25, 2014