Bloomberg LP Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
For sorting numbers between 1 and 50,000, the interviewer might have expected you to produce an O(50k)-time solution. Initialize an array from 1 to 50,000 with zeros. Iterate through your numbers and update the appropriate buckets. Then go through the 50k-sized array and emit the numbers in order, using the bucket counts to determine how many values you emit. I think the interviewer is kind of clever, because the 5:1 ratio of max-value to N is in the range where a traditional O(NlogN) might actually be faster.
The second question was about finding the best sort for arrays and linked lists. For arrays, quicksort and heapsort are pretty comparable, because they can both be done in place in O(NlogN) time. For linked lists, you can cheat by copying the linked list into an array in linear time, but linked lists also play really nice with quicksort. Pop the head off the list, and use that as a pivot. Partition the lows and highs into two new linked lists. Recursively sort the other linked lists, then chain them back together.
Here's the key piece of a linked list based quicksort:
LIST quicksort(LIST list) {
if (!list.head) return list;
PNODE head = list.head;
char *pivot = head->value;
LIST smalls;
smalls.head = NULL;
smalls.tail = NULL;
LIST bigs;
bigs.head = NULL;
bigs.tail = NULL;
PNODE p;
PNODE p_next;
for (p = head->next; p; p = p_next) {
p_next = p->next;
p->next = NULL;
if (strcmp(p->value, pivot) > 0) {
bigs = append_node(bigs, p);
}
else {
smalls = append_node(smalls, p);
}
}
head->next = NULL;
bigs = quicksort(bigs);
smalls = quicksort(smalls);
return concat(append_node(smalls, head), bigs);
}
If you are creating an array of size 50k, then what is the purpose of this statement given in the question "there are 10000 numbers between 1 and 50000". Is there any possible solution which uses only 10k size array.
Look at "counting sort" in wikipedia. I edited my answer to say 50k, not 500k--sorry, the I miscounted the zeros (dyslexia). There are perfectly valid solutions that run in the 10k size array (in-place heapsort, in-place quicksort, etc.), but many of them run in NlogN time, which is inferior to a counting sort for a small range of numbers. Like I said, I think the interviewer chose the numbers cleverly, because the counting sort might not actually beat the in-place sorts in terms of actual time, and the counting sort is obviously inferior in terms of space usage (but usually time is constrained more than space).
for 1-10K, use counting sort - O(n);
- vaticanoptimist September 30, 2013for 10K between 1-50K, use radix sort - O(nk); n = 10K, k = 5;