4.2 of 5 2,093 reviews Mountain View, CA 5000+ Employees

Google Engineer Interview Question

I interviewed in New York, NY and was asked:
"How would you sort an array of one billions integers?"
Add Tags [?]
Answer Flag Question

Part of a Engineer Interview Review - one of 2,779 Google Interview Reviews

Answers & Comments

of 4
- Interview Candidate on Oct 12, 2010 Flag Response
of 0
I think that the trick here is to use some sort of a divide and conquer sorting algorithm
(such as merge sort or quick sort) and use this idea to divide the sorting between several computers so if you have p computers it will take O(n/p*log(n/p))
The problem arises when you need to merge all the data together back to a big array, but that only takes O(n) since the sub-arrays are already sorted.

The big con to this is that merge sort (the traditional method) requires extra memory for each iteration, so its possible to use merge sort to divide the array to p computers but in each computer use quick sort (which is in place sorting) to sort the sub-arrays. that way you save the memory (since you need to move the sub-arrays to other computer anyway) and still get sorting of O(n/plog(n/p))
- Tal on Oct 19, 2010 Flag Response
of 1
Here's an outside of the box answer. An array a[d] = r maps a domain to a range. Assuming 32 bit integers, the domain size in this problem is on the same order as the range (about 4 billion). We can use this to design an O(n) sorting algorithm. Count the number of occurrences of each possible integer and then spit them back into the array:

RangeSort(a, n)
    const MAXINT = 1 << 32;
    memset(counter, 0, sizeof(counter));
    for (i = 0; i < n; ++i)
    i = 0;
    for (j = 0; j < MAXINT; ++j)
        while (counter[j]-- > 0)
            a[i++] = j;

Both loops are O(n). MAXINT is a constant, so the memset is O(1).
- lamont on Oct 22, 2010 Flag Response
of 0
your answer would work only if you knew the integers in the array are distinct. If they`re not, each entry in your array should be able to keep a number up to one billions(in the case all integers in the array are equal)
- Anonymous on Nov 25, 2010 Flag Response
of 0
The integers need not be distinct. I failed to mention that the counters are 32 bit unsigned integers. They can handle 4 billion duplicate values in the original array, which is greater than the "one billions" requirement.

This whole problem is rather contrived. When you have a billion integers they're generally going to be in a file, not an array. But if you've already got an array of 1 billion integers, what's another 4 billion?
- lamont on Nov 29, 2010 Flag Response

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Google interview questions and advice. All interview reviews posted anonymously by Google employees and interview candidates.