Bloomberg L.P. Interview Question: Given a list of 1,000,000 int... | Glassdoor

Interview Question

Financial Software Developer Interview(Student Candidate) New York, NY

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.
Answer

Interview Answer

4 Answers

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

1

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

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

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.