3
一个算法面试题 & 面试题库
source link: https://zhiqiang.org/cs/an-algorithm-face-interviews-question-test.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一个算法面试题 & 面试题库
一个面试题，号称是微软的
输入a1,a2,...,an,b1,b2,...,bna1,a2,...,an,b1,b2,...,bn ，如何在 O(n)的时间，用 O(1)的空间，将这个序列顺序改为a1,b1,...,an,bna1,b1,...,an,bn 。
刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK