Chinaunix首页 | 论坛 | 博客
  • 博客访问: 5143043
  • 博文数量: 1696
  • 博客积分: 10870
  • 博客等级: 上将
  • 技术积分: 18357
  • 用 户 组: 普通用户
  • 注册时间: 2007-03-30 15:16
文章分类
文章存档

2017年(1)

2016年(1)

2015年(1)

2013年(1)

2012年(43)

2011年(17)

2010年(828)

2009年(568)

2008年(185)

2007年(51)

分类: IT职场

2010-06-08 02:42:32

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

输入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

我做了两小时没做出来,上网一搜,最近这个题目很热,已经有人在讨论这个题目,还翻出了问题的发源地,一个完美洗牌的构造问题。此网页上一篇长达12页的论文给出了完整的算法和证明。

不知道有没有人给出直接而简便的方法?

在搜索过程中发现两个很好的程序设计类面试题库(英文),共享一下,如果你想面试Microsoft,Google或者Goldman Sachs,看看这两个网站上的题目就可以了。

阅读(571) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~