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."
Add Tags [?]
Answer

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

Answers & Comments

This post has been removed. Please see our Community Guidelines or Terms of Service for more information.
1
of 3
votes
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
votes
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
votes
The key here is that the numbers don't repeat. Just use the megabyte of free space and set all bits within it to 0. Then, for each number encountered, set the corresponding bit to 1 (if we encounter a 2, we set the second bit to 1). Then, print out the numbers corresponding to the 1 bits. This works with 1 meg of memory because 1 megabyte = 8 megabits > 1 million bits.
- Anonymous on Nov 10, 2012

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.