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 ;-)
Read full article from Gunnar Kudrjavets - Think you're good with algorithms, try attacking this problem
No comments:
Post a Comment