一个算法面试题 & 面试题库

zhiqiangApril 27, 2007 精华区网络资源计算机科学

一个面试题，号称是微软的

输入 $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还能用。

查看更多关于算法, 面试, 题库的内容。

14条留言 -> 跳到留言表格

At 2007.04.29 00:37, You XU said:

我在Google 遇到类似的题目：

用最小的内存做下题
假设p(k) 可以将 k=1..n 映射成1..n 的一个排列，如何将一维数组(x1, x2,..., xn) 排成 (x_p(1), x_p(2), ... , x_p(n))

其实，此问题被称为 In Situ Permutation (Knuth, 1972) TAOCP 有比较详细的讲解，大约就是说这些置换可以成环，关键是找到置换群的生成元。知道了这个，我当时很幸运的秒杀了这个题目 ...

[Reply]
- At 2007.04.29 01:20, zhiqiang said:
  
  你那个问题不要求运算时间么？不要求运算时间的话，都可以在O(1)空间内搞定。
  
  文章中的那个问题，似乎不是能够秒杀的。分治法可以在O(nlogn)时间，O(1)空间搞定，但线性时间就不容易了。你有什么好方法么？
  
  [Reply]
At 2007.04.30 01:25, Xie Xie said:

该置换问题的最坏情况下时间是O(nlogn)，呵呵。

比如20个的情况：
1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第1个是不需要动的；
第2个需要和2对应的置换即第11个位置所在元素恰好是11对换，换完之后数组有变化了；
第3个需要和3所对应的2对换，找法是先找到3对应的置换2，在位置2寻找，而位置2已经是11了，不是所需要的，再在位置11寻找，刚好是2，对换之；
...
这就是Knuth给出的方法：）写成程序稍微麻烦点，呵呵，用白话描述一下更好懂。
对于这种奇偶的问题，有其特殊性，应该可以在O(n)时间内完成，有空可以看看Sedgewick的Analysis of algorithms，里面有in situ permutation的一节，他证明了平均情况下是n logn。
它的时间依赖于该置换中的cycles数，而你给的那个论文就是计算它的，呵呵：）发在IPL上，档次不低。
回头有时间再想想......

[Reply]
- At 2007.05.26 15:50, szuxjq said:
  
  你说的20个的情况，是上一行变成下一行还是下一行变成上一行？看着犯晕了~~
  
  [Reply]
- At 2007.12.09 11:06, you_801204 said:
  
  该置换问题的最坏情况下时间是O(nlogn)?错了。只需要O(n).
  
  [Reply]
At 2007.04.30 06:55, You XU said:

那篇paper 我细心读了一下，他无非就是使用了超级复杂的数论定理想办法把每个循环群的生成元挑出了一个。只能听他说的有道理，我们这些凡人估计是想不出来的了⋯⋯
PS: 论文中Section 3 第 (5) 式就是对cycle 数量的估计.

[Reply]
At 2007.05.01 20:01, zhiqiang said:

test latex $\frac{\Large f(x)=\int_{-\infty}^x e^{-t^2}dt}{\Large f(x)= \int_{-\infty}^x e^{-t^2}dt}$

[Reply]
- At 2007.05.01 23:11, zhiqiang said:
  
  $\begin{eqnarray}a&=&b+c\\<br /> &=&d+e\\<br /> \sum x+\prod y&=&11<br /> \end{eqnarray}$
  
  [Reply]
At 2007.05.02 03:16, You+XU said:

Test
The total number of cycles is $\sum_{d\|m, d \neq 1} \frac{\phi (d)}{r_d}$
where $r_d$ is the order of 2 (mod d).

[Reply]
At 2007.05.02 03:17, You+XU said:

真的非常好用的插件我太喜欢了
上面发的公式就是那篇文章中的主要结论, 对cycle 的数量估计

[Reply]
- At 2007.05.02 10:46, zhiqiang said:
  
  问题难度不在于对cycle数量的估计，而在于从每个cycle抽出一个生成元。
  
  我大致浏览了那篇论文，用到一些数论上的计算技巧。过程倒也挺natural的。
  
  [Reply]
At 2008.01.09 07:29, zfy0701 said:

这是我想到的一个解法

用m代表整个数组,p,q分别代表两个变量

第i次迭代（i从1开始）

对p,q赋值：
当i为奇数，p赋值为m[2n - 1 - [i/2] ],q赋值为m[ 2 + [i/2] ]（[x]为下取整）
i为偶数，p赋值为m[n - i/2 ],q赋值为m[ n + i/2 ]

然后m[i + 1]与变量p迭代，m[2n- i]与q迭代

重复迭代n-1次即可

时间O(N),空间O(1)的算法

[Reply]
- At 2008.01.09 07:33, zfy0701 said:
  
  想法就是这样了，还没上机验证，应该不会错
  全文在：http://blog.csdn.net/zfy0701/archive/2008/01/09/2031162.aspx
  
  [Reply]
- At 2008.01.09 07:44, zfy0701 said:
  
  不好意思，有错，献丑了
  
  [Reply]