Bloomberg L.P.

www.bloomberg.com
Work in HR? Unlock Free Profile

# Bloomberg L.P.Financial Software Developer Interview Question (student candidate)

I interviewed in New York, NY and was asked:
"Given a list of 1,000,000 integer (1 to 1,000,000 with no repeat), how to sort the list with only 1 mb of memory space."

Part of a Financial Software Developer Interview Review - one of 1,728 Bloomberg L.P. Interview Reviews

1
of 3
The sorted list of 1,000,000 jumbled numbers is going to be 1, 2, 3... 1,000,000. So we can just start printing the numbers as 1, 2, 3...

So we don't require a sorting algo at all! And neither do we need the 1MB of space!

Or did I misunderstand the question?

Thanks,
Izaaz
- Izaaz Yunus on Oct 4, 2012
2
of 2
External Sorting is the solution. External memory sorting is called for usually when the data is so huge that it wont fit in main memory, for instance, huge databases, file systems, graphics applications where the 3D models are huge, pattern recognition and machine learning applications, etc.

Make a first pass through the file to be sorted, breaking it into blocks about the size of the memory and sort these blocks. Then, merge the sorted blocks together, if necessary by making several passes through the file, creating successively larger sorted blocks until the whole file is sorted. This approach is called external memory merge-sort and has been in use since 1950s.

Note that this method does not use the fact that the keys are integers. For the least we could sort the blocks in internal memory using radix sort to make this implementation faster (since in this assignment the keys are integers). Here is some more material on external memory algorithms for sorting from Jeff Erickson. (1.1.1 B-Trees are a vairant of a-b trees) and from Peter Sanders. You might also want to look the chapter "Special purpose sorting methods" in the book "Algorithms in C++"/"Algorithms in Java" by Robert Sedgewick
- Ram on Oct 10, 2012
1
of 2