Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Insertion sort works, but so does bubble sort.
Merge sort also works, if you just traverse once and find the length...
You cant traverse the list to find size. Sense the purpose of the question! Insertion sort will work.
True, Can't find the length. The data could be streamed into linked list.
Insertion sort.
Considering the insertion sort or bubble sort, I think insertion sort would be a bit better, as it is a linked list, we may not need to move elements too much, just changing pointers appropriately.
Could anybody please help me implementing insertion sort for the linked list? As I understand, insertion sort requires to traverse in the opposite direction of the linked list in order to shift items to the right. I am not quite sure how this can be done?
Insert sort:
Node pn = head; // previous to n
for(Node n=head.next; n != null; n = n.next) {
Node pi = null; // previous to i
Node i;
for(i = head; i != n && i.value < n.value; i = i.next)
pi = i;
// change pointers from pi -> i and pn -> n -> n.next
// to pi->n->i and pn->n.next
if(pi == null)
head = n;
else pi.next = n;
pn.next = n.next;
n.next = i;
pn = n;
}
Bubble sort is inefficient. May be merge sort can be used. But I am not sure how to do it in place.
selection sort can possibly reduce the inefficiency of bubblesort ..
void sort<int> (Node<int>* p) {
Node* currHead = p;
Node* scout = null;
Node* agent = null;
T min = INTEGER.MAX;
while(currHead != null) {
min = currHead->data;
agent = currHead;
scout = currHead->next;
while (scout != null) {
if (scout->data < min) {
min = scout->data;
agent = scout;
}
scout = scout->next;
}
if(scout != currHead) {
scout->data = currHead->data;
currHead->data = min;
}
currHead = currHead->next;
}
}
Merge sort seems the best answer for this problem because it takes care of the O(1) memory requirement. This can be done because rather than creating sets of temporary lists to merge back the results, the list pointers can be re-arranged themselves.
Wouldn't we take recursive ( stack frames) operations into consideration when talk about space complexity. I think it becomes important when 'n' is too large
Merge sort's memory complexity is O(log n) because of the recursion and given the merging is done in place.
MergeSort as mentioned by kbk and others is a good answer. However, it has to be done iteratively in bottom up way to avoid the space overhead of stack frames.
template <typename T>
struct ListNode {
ListNode *next;
T val;
void print()
{
for (ListNode<T> *node = this; node; node = node->next) {
cout << node->val << " ";
}
cout << endl;
}
};
typedef ListNode<long> Node;
// Merged two non-empty sorted lists
// Return the merged list and optionally its tail
//
Node *
merge_two_non_null_lists(Node *one, Node *two, Node **tail_p);
// Returns the node steps away from given list or the tail of the list
// if list has less than (steps + 1) nodes
Node *
forward(Node *list, int steps);
// Bottom-up iterative list merge sort using O(1) space
// Iterate over the list and successively merge increasingly longer runs
// until the list is sorted.
//
Node *
merge_sort_list_in_place(Node *list)
{
int len = 1; // run length
Node header;
header.next = list;
bool new_merged_runs = false;
do {
Node *rest = header.next;
Node *result_tail = &header;
new_merged_runs = false;
while (rest) {
Node * head_1 = rest;
Node *tail_1 = forward(head_1, len - 1);
if (! tail_1->next) {
// only one run left (as long as len)
result_tail->next = head_1;
result_tail = tail_1;
rest = NULL;
break;
}
new_merged_runs = true;
Node *head_2 = tail_1->next;
Node *tail_2 = forward(head_2, len - 1);
// separate next two runs from rest of list
rest = tail_2->next;
tail_1->next = NULL;
tail_2->next = NULL;
// merge next two runs, keeping track of the tail of the merged runs
Node *merged_tail = NULL;
Node *merged_head = merge_two_non_null_lists(head_1, head_2, &merged_tail);
result_tail->next = merged_head;
result_tail = merged_tail;
}
len *= 2; // double run length
} while (new_merged_runs);
return header.next;
}
// Merged two non-empty sorted lists
// Return the merged list and optionally its tail
//
Node *
merge_two_non_null_lists(Node *one, Node *two, Node **tail_p)
{
if (tail_p) {
*tail_p = NULL;
}
if (!one || !two) {
return NULL;
}
if (one->val > two->val) {
// To avoid special cases we want the first node of the first list to be the first in the result.
// Therefore, we swap one and two pointers when this pre-condition does not hold true
swap(one, two);
}
Node *tail = one;
do {
// tail is the last node added or present on the result so far. It's value is known to be
// smaller or equal to the first node on the other (i.e. two) list.
// Advance the tail pointer skipping over all the elements in the result which have smaller
// or equal value than the first node of the other list.
while (tail->next && (tail->next->val <= two->val)) {
tail = tail->next;
}
// Now list two's head has the next smallest element. It's value is smaller or equal
// to the value of tail's successor. We have to concat list two after tail and make
// tails' successor the head of the other list
swap(tail->next, two);
tail = tail->next;
} while (two);
if (tail_p) {
// advance tail to end of merged list
while (tail->next) {
tail = tail->next;
}
*tail_p = tail;
}
return one;
}
// Returns the node steps away from given list or the tail of the list
// if list has less than (steps + 1) nodes
Node *
forward(Node *list, int steps)
{
if (! list) {
return NULL;
}
Node *cur = list;
while ((steps > 0) && cur->next) {
steps--;
cur = cur->next;
}
return cur;
}
Merge sort cannot be applied as question categorically says to maintain constant space!
Use selection sort!.
temp = head
while temp !=NULL
temp1 = temp;
while temp1 != NULL
if(temp1->data < temp->data) exchange . temp1-> data and temp->data
temp1++;
temp++;
Space complexity : O(1) Time Complexity O(n^2)
Can you elaborate with some code or pseudocode on how you would implement quick sort against a linked list?
Quick sort's partition function usually requires moving in both directions. Since it is a singly linked list, it may not work.
agreed. also quick sort performance is a function of pivot, a bad choice of which may throw the whole things off. Best approach is, since constant space performance is the only criteria, to use Insertion Sort or Selection Sort both of which does in-place sorting thereby meeting the constant space constraint.
Here is a merge-sort solution, pardon the messiness. You just split and stick together the linked list at the different steps. Since the size is unknown the algorithm has to split by counting size and then splitting so it takes an extra O(N) in the log(N) sort/merges, but it's still O(N*log(N)). Still, for smaller arrays bubble sort would probably be faster.
public class LinkedListSort {
public static class Node
{
public int value;
public Node next;
public Node(int v, Node n)
{
value = v;
next = n;
}
public String toString()
{
String s = "";
Node n = this;
while(n != null)
{
s += n.value + ", ";
n = n.next;
}
return s;
}
public static Node createLinkedList(int ... listItem)
{
boolean first = true;
Node root = null;
Node cur = null;
// Node last = null;
for(int item : listItem)
{
if(first)
{
root = new Node(item, null);
cur = root;
first = false;
}
else
{
Node n = new Node(item, null);
cur.next = n;
cur = n;
// n.next = cur;
// cur = n;
}
}
return root;
}
}
public static void main(String[] args) {
Node n = Node.createLinkedList(6, 92, 1, 9, 3, 2, 8, 53, -4, 12, 21);
System.out.println(n.toString());
n = sort(n);
System.out.println(n.toString());
}
public static Node sort(Node cur)
{
System.out.println("At " + cur.toString());
if(cur.next == null)
return cur;
int length = 0;
Node copy = cur;
while(copy != null)
{
length++;
copy = copy.next;
}
Node left = cur;
Node prevRight = null;
Node right = cur;
int at = 0;
while(at < length/2)
{
prevRight = right;
right = right.next;
at++;
}
prevRight.next = null;
left = sort(left);
right = sort(right);
Node n = merge(left, right);
System.out.println("Merge result: " + n.toString());
return n;
}
private static Node merge(Node left, Node right)
{
System.out.println("Merging " + left.toString() + " and " + right.toString());
Node root = null;
if(left.value < right.value)
{
root = left;
left = left.next;
}
else
{
root = right;
right = right.next;
}
Node last = root;
while(left != null && right != null)
{
System.out.println(left.value + ", " + right.value);
if(left.value < right.value)
{
last.next = left;
last = left;
left = left.next;
}
else
{
last.next = right;
last = right;
right = right.next;
}
}
while(left != null)
{
System.out.println("L: " + left.value);
last.next = left;
last = left;
left = left.next;
}
while(right != null)
{
System.out.println("R: " + right.value);
last.next = right;
last = right;
right = right.next;
}
return root;
}
}
-We cant apply quick sort because traversing in reverse direction is quite costlier
-Bubble sort will give sol. but time complexity will be very high
-Merge sort is best:
-take a m size of array (as we can use cont size of memory)
-copy first m element into the array[m]
-sort the array
-place back the sorted array in the list
-now we have sorted linked list upto m size
-copy next m element from the linked list (m to 2m) into the array
-sort array
-now start applying merge sort in array and first m element of linked list
-now in case array element is needed to add in list as part of merge sort, traverse m to 2m elements of linked list and get the node reference say (*ptr)
-now traverse the first m element of linked list and get the node say (*insertAfter) either equal or just less then the *ptr node's content
-break the link after node (*insertAfter) and add (*ptr) node
for ex:
we have a linked list 1 5 3 2 6 4 8 ......
create a m=3 size of array
copy 3 element from list to array
array = 1 5 3
sort array 1 3 5 [complexity=mlogm]
copy next m=3 element from list (3 to 6)
array = 2 6 4
sort array 2 4 6 [complexity=mlogm]
apply insert sort b/z array [2 4 6] and first m=3 element of list [1 3 5]
as part of merge sort we have to add 1 at fist place of list
traverse list from m=3 to m=6 and get element 1's node reference
break the head of link list linking and make head point to 1 and 1 point to 2
same as we can insert 3 after 2 by just breaking linking b/w 2 and 4 and insert 3 in mid so that 2 will point to 3 and 3 will point to 4
after getting sorted 2m element of list again take next m element from list sort it apply merge sort with sorted 2m elements and so on...............
typedef struct node
{
int data;
struct node *next;
} node;
node *InsertNode(int data,node *p)
{
if(!p)
{
p=(node*)malloc(sizeof(node));
p->data=data;
p->next=NULL;
return(p);
}
node *k =NULL;
k=(node*)malloc(sizeof(node));
k->data=data;
k->next=NULL;
p->next = k;
return(k);
}
void print(node *p)
{printf("\n");
while(p != NULL)
{
printf(" %d ", p->data);
p = p->next;
}
}
void function( int inputs[], int size)
{
int i=0;
node *point =NULL;//create(point);
node *first =NULL;
node *newFirst =NULL;//create(newFirst);
node *tempPoint =NULL;//create(tempPoint);
//printf(" %d ", sizeof(inputs)/sizeof(int));
for(i=0 ; i<size; i++)// insert in link list
{
point =InsertNode(inputs[i],point);
if(i==0)//to get begining to link list
first= point;
}
print(first);
getchar();
//sorting
for(i=0 ; i<size ; i++)
{
if(first->next != NULL || first != NULL )
{
point = first;
first = first->next;
}else
{
break;
}
tempPoint = newFirst;
do
{
if(newFirst == NULL)
{
newFirst=point;
point->next = NULL;
tempPoint = newFirst;
}else if(tempPoint->data < point->data && (tempPoint->next == NULL || tempPoint->next->data > point->data ))
{
point->next = tempPoint->next;
tempPoint->next =point;
break;
}else if(tempPoint->data > point->data)
{
point->next = tempPoint;
newFirst=point;
break;
}else
{
tempPoint = tempPoint->next;
}
}while(tempPoint->next !=NULL);
print(newFirst);
getchar();
}
}
int main()
{
int inputs[5]={5,2,3,4,1};
int size = sizeof(inputs)/sizeof(int);
function(inputs, size);
getchar();
return 0;
}
Insertion sort is what needs to be used here. Even though with insertion sort we will have O(n-square) complexity. Here is how I see the implementation:
1. Create a new empty list
2. Traverse the original list node by node and insert the new node in the newly created list but in the right order. Meaning, we need to have another function ReturnIndex(Node head, int number), which well return the index where the new number needs to be inserted in the linked list with head "head".
3. Once we get that index, we insert it right there.
Very elegant implementation of insertion sort can be found on Wikipedia.
Bottom up merge sort for linked list using constant space, a small array of pointers to nodes, example C code. For other languages, the pointers could be replaced with references or nodes.
typedef struct NODE_{
struct NODE_ * next;
int data;
}NODE;
/* prototype */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2);
/* sort list using array of pointers to first nodes of list */
/* aList[i] = NULL or ptr to list with 2 to the power i nodes */
#define NUMLISTS 32 /* size of array */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS]; /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
if(pList == NULL) /* check for empty list */
return NULL;
for(i = 0; i < NUMLISTS; i++) /* zero array */
aList[i] = NULL;
pNode = pList; /* merge nodes into array */
while(pNode != NULL){
pNext = pNode->next;
pNode->next = NULL;
for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
pNode = MergeLists(aList[i], pNode);
aList[i] = NULL;
}
if(i == NUMLISTS) /* don't go past end of array */
i--;
aList[i] = pNode;
pNode = pNext;
}
pNode = NULL; /* merge array into one list */
for(i = 0; i < NUMLISTS; i++)
pNode = MergeLists(aList[i], pNode);
return pNode;
}
/* mergelists - compare uses src2 < src1 */
/* instead of src1 <= src2 to be similar to C++ STL */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL; /* destination head ptr */
NODE **ppDst = &pDst; /* ptr to head or prev->next */
if(pSrc1 == NULL)
return pSrc2;
if(pSrc2 == NULL)
return pSrc1;
while(1){
if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */
*ppDst = pSrc2;
pSrc2 = *(ppDst = &(pSrc2->next));
if(pSrc2 == NULL){
*ppDst = pSrc1;
break;
}
} else { /* src1 <= src2 */
*ppDst = pSrc1;
pSrc1 = *(ppDst = &(pSrc1->next));
if(pSrc1 == NULL){
*ppDst = pSrc2;
break;
}
}
}
return pDst;
}
The question says "unknown size" so merge sort, quick sort and bubble sort wont work as some of the answers here say.
- Anonymous March 26, 2013Insertion sort however can be applied in this case. The loop invariant to maintain here will be a sorted linked list. In the body of the loop a node will be scanned and added to the sorted linked list. Since we are only manipulating pointers, memory requirement is still O(1). Time req. O(n^2).