悬赏大牛解答求职题目，有现金和礼物答谢（ 1 月 5 日更新）

昨天在论坛上放出的三道题，前两道已经被@Funky 、@v2014领走了。

有朋友问为什么会做这个活动呢？为了方便大家找工作的时候备考，我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站牛客网，里面积累了谷歌、腾讯、百度等几十家互联网公司的笔试面试题目。但是呢，网站当前有部分题目还没有楼主觉得认可的最佳答案和解释，为了更好的服务程序猿们，我们做了一个活动，悬赏大牛解答，每道题目根据难度对应一定的现金奖励，最高一道题目奖励100元，还有iPhone、移动硬盘、小米手环等众多好礼相送。
活动地址猛戳→_→： http://www.nowcoder.com/activity/challenge

从今天开始到1月29日，我们会在论坛持续更新本贴，每天放出1-3道题目，欢迎大家跟帖解答，最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天公布。

今日题目上新：
1、
用任何编程语言实现乱序函数randomSort(array)函数，输出排序后的函数。如[1,2,3,4,5]，输出[3,2,4,5,1]。要求N次以内不重复。(假设全排列总数>N)

2、
在创新工场你可免费的吃顿午餐,不过得像在学校一样排队打饭打菜哦,打饭的队伍最长的时候0表示女性,1表示男性,某一次打饭的队伍是这样的：001111111010001,设第i个数字为ai则存在（）种ijkg满足i<j<k<g且ai=0,aj=1,ak=0,ag=1。
（ai,aj,ak,ag这里ijkg的下标不知道v2ex怎么搞，大家原谅我吧）
3、昨日未解难题
有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，两个文件的行数不一定相等，但均在一千万行左右。A文件中的数字两两不等，B文件中的数字两两不等，请用一个算法找出A和B两文件中所有相同的数，并且从小到大有序输出。请考虑统计程序如何实现，给出设计思路和关键算法（可使用伪代码），并估计程序核心代码的时间复杂度和空间复杂度。

论坛里这个每日答题的小活动也基本上是这个思路，算是一个分赛场吧~
欢迎大家关注我们，活动结束后我们会把面试题整理成PDF分发给参与的用户
微薄 http://www.weibo.com/nowcoder
微信 www_nowcoder_com
技术QQ群 157594705
邮件 admin@nowcoder.com
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~

附昨日帖子地址 http://www.v2ex.com/t/158980

再次感谢大家！祝大家新年行好运，早日找到女朋友！！

lightening

2015-01-05 18:25:07 +08:00

@zixincao 如果我没理解错的话，你的方案和我想的类似，但是每个数字多大没有限定，申请两个一千万个固定的位并不够。

我觉得还是预先设定一个 m，比如 1M 个，创建一个 struct 数组 array[m]。
struct 结构类似 inode，可以存一定数量（1~5，看情况) 的整型，每个整形对应一个 flag，还要包含一个指针，以防那个位置需要存放更多个数。

然后取第一个列表，每行的数字都对 m 取模，结果 i 作为下标，存入相应位置的 array[i] 中。

对于第二个列表，只要取每一行，取模，得下标 j，看看 array[j] 中有没有那个数即可。

空间复杂度和时间复杂度取决于 m 的大小。假设两个文件中最大的数字是 n：
取 m = n 的话，时间复杂度是 o(n). 空间复杂度则是 n * （struct 的大小）。此时 mod 也就不用做了。
m 越小，占得空间就越小，但是时间复杂度就越高。假设 m = n/2，则时间稍长，但是平均下来还是 o(n)的（只有个别情况需要动用 struct 中的指针），空间则几乎小了一半。

omegaga

2015-01-05 23:05:21 +08:00

第一题，首先对于n个数，可以知道总共有n!种方案，那么只需要生成一个[1, n!]的数i，然后找到第i个permutation就好了。由于n!可能很大，因此要用factoradic form来表示，也就是生成一个长度为n的数组，其中第i个数是[0, i]之间的随机数。然后从factoradic转成permutation的经典算法了，维护一个数组a，令a[i] = i，从factoradic form的最高位f[n-1]起，选择第a[f[n-1]]，然后把这个数从数组里删掉，重复这个过程就可以生成出来了（维基百科配了图描述得很清楚http://en.wikipedia.org/wiki/Factorial_number_system#Permutations）。

用哈希维护一个大小为n的cache保证n次都不相同。