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

作者: , 共 595 字

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

输入 \( 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 ,看看这两个网站上的题目就可以了。

Q. E. D.

类似文章:
珍爱生命,远离政治。我们继续讨论算法。
2007 年,我们 讨论过一个算法问题 , perfect shuffle ,据称是个微软面试题:
相似度: 0.085
这个题目听说是 MSRA 的面试题。
毛毛虫爬棍子,有三个变体:
数学 » 头脑风暴
发信人 : GGGGDDDDK ( 忠贾诩发动乱武,反华佗没法急救别人了 ), 信区 : SanGuoSha
标   题 : 据说此题是入职腾讯游戏策划部门一道题 zz
发信站 : 水木社区 (Mon Sep 20 11:10:40 2010), 站内
数学 » 搞笑, 数学之美
来自 University of WarwickMike Paterson 星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。
数学 » 圆周率
今天 gezhi 上有一篇关于 \( \pi\) 的八卦文章,里面讲到了 \( \pi\) 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。