One of my graduating PhD students has been interviewing with several big Internet companies (Google, Amazon, Microsoft, etc). One of the benefits of this is that my research group gets to hear many of the new job interview puzzles for this year. Here’s one of the more interesting ones:
You are given a large array in the form:
You want to output an array in the form:
The catch is that you have very little external memory (only O(log n)), so you need to change the array in place.
It’s not too hard to get a solution to this problem that runs in O(n log n) time (think recursion). But surprisingly, you can do better. Can you get a linear time solution? Beware: this is harder than it seems!
20 Comments so far
Leave a comment