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

作者: , 共 555 字

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

输入\( 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.086
这个题目听说是 MSRA 的面试题。
数学 » 头脑风暴
发信人: GGGGDDDDK (忠贾诩发动乱武,反华佗没法急救别人了), 信区: SanGuoSha
标   题: 据说此题是入职腾讯游戏策划部门一道题 zz
发信站: 水木社区 (Mon Sep 20 11:10:40 2010), 站内
一个非常好的面试题。难度适中。
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
值得最近找工作的人好好读读,虽然可能有点晚了 :)
数学 » 搞笑, 数学之美
来自University of WarwickMike Paterson星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。
数学 » 圆周率
今天 gezhi 上有一篇关于\( \pi\) 的八卦文章,里面讲到了\( \pi\) 的计算问题。但我对其中的一些数据起了疑心,并不是说数据错了,而是作者所用的数据实在是太老了。