一个面试题，号称是微软的
输入$ a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$ ，如何在 O(n)的时间，用 O(1)的空间，将这个序列顺序改为$ a_1, b_1, ..., a_n, b_n$ 。
刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换
x -> 2x mod 2n+1
我做了两小时没做出来，上网一搜，最近这个题目很热，已经有人在讨论这个题目，还翻出了问题的发源地http://www.cs.uvic.ca/\~jellis/perfect.html，一个完美洗牌的构造问题。此网页上一篇长达 12 页的论文Computing the Cycles in the Perfect Shuffle Permutation给出了完整的算法和证明。
不知道有没有人给出直接而简便的方法？
在搜索过程中发现两个很好的程序设计类面试题库（英文），共享一下，如果你想面试 Microsoft ， Google 或者 Goldman Sachs ，看看这两个网站上的题目就可以了。
- techInterview Discussion
- CareerCup：网站似乎被 G-F-W 了，幸好RSS还能用。
Q. E. D.
