Almost everything from professional literature I've been lately reading is written by the following authors: Jon Bentley, Donald Knuth, and Robert Sedgewick. In the process I've been also going through number of different programming problems. Here's one old problem which puzzled me and number of my colleagues from Speech Component Group (team which is responsible for core speech recognition engine and
SAPI) about two years ago. We never came up with efficient solution though ;-) The problem statement is pretty trivial, but be careful - it's not as simple as it seems.
The problem. An array which contains 2 N elements needs to be arranged from
a1, a2, a3, ..., an, b1, b2, b3, ..., bn
to
a1, b1, a2, b2, a3, b3, ..., an, bn.
Of course this needs to be done as efficiently as possible in terms of both computational complexity and memory usage. The best solution known to me (old coworker of mine from Estonia came up with the algorithm) has the complexity of O(N log(N)) and uses no more than constant amount of memory.
Can you code up the solution which has the same characteristics as the best solution known to me? Can you do better? Is it even possible to do better? If you can solve this problem under these constraints or prove mathematically that there's no better solution then you should definitely send your CV to Microsoft ;-)
I’ll post the best solution known to me in 1.5 weeks with full credits to the original author.
Update
Apparently I'm not the only one who has been thinking about this problem lately, one former teammate of mine pointed out some related articles: