Apple Interview Question
SDE1sCountry: United States
1 billion integers means 4GB or memory which is a strong indicative that they don't want you to do a traditional array sorting. I, too, believe that this should be solved using external sorting.
Yep, external sorting wins here. I'm pretty sure that this was the way a similiar problem (with additional conditions, of course), presented in the first article of "Programming Pearls" was solved.
for the huge amount of data the quick short is the best when data are in worst case. other wise aply merg short.
If you assume that the entire array fits in memory, I would choose heap sort since it can be done in place (O(1) additional space) and is guaranteed O(n lgn) time, where as quicksort requires worst case O(n) additional space (maybe the array fits in memory but not the additional space required for quicksort) and takes O(n^2) in the worst case.
Otherwise, if you don't assume the array can entirely fit in memory, external merge sort is a good option.
Because it's a billion integers.
If we go by understanding integer data type, we can create an array of size equal to integer data space which is 4GB.
And take a single pass through billion integers to find the count of each and remember them in 4gb array.
Next pass go through 4b array and write the non-zero count numbers back into first array.
It's an array so I'd do a radix sort. 32 passes and done.
- Noobie January 31, 2014