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

作者:, 发表于

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

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

[tags]算法,面试,题库[/tags]

Q.E.D.


上一篇:理论计算机初步:算法和计算模型2006年8月16日
下面是wikipedia上算法的定义: 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据,经过计算机程序的有限次运算

下一篇:帽子游戏二2007年6月25日
这个题目听说是MSRA的面试题。 在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。