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

[nowcoder]

昨天在论坛上放出的三道题，前两道已经被@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
邮件 [e-mail]
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~

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

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

[icedx]

我擦咧 第三题没人解?

[nowcoder]

@icedx 第三题讨论的人不少，但是体系化解答的没有。求解答

[Valyrian]

@nowcoder 在这里回复回答就可以吗？

[xcv58]

不知道是不是我没看懂。

第三题中两个一千万行的文件，完全可以直接读到内存中。
最暴力的方法两个文件内容都归并排序，然后顺序扫一遍。 时间 O(n*log(n)) 就行了。
节省时间的方法用 Hash 之类的先过一遍，然后找到重复的值，再排序。时间 max(O(n), O(k*log(k))

[nowcoder]

@Valyrian 直接留言回答就可以。思路正确，解答详细我们就发奖品。 上我们网站答题额外有奖金，具体参考 http://www.nowcoder.com/activity/challenge

[nowcoder]

@xcv58 大神写个详细点啦～ 奖品等主人好久了呢

[xcv58]

@nowcoder 这种题目实在提不起兴趣啊。
要是我平时要用到的话肯定直接这样了：
sort -n file1 file2 | uniq -d
我平时排序几百兆的文件都这么干的。

所以千万级别的纯数字真没啥意思。
要论难度就限制内存大小或者增大数据量。

譬如只能用 32M 内存。
这样的话就需要用小的 bitmap 把整数的范围分段，每次过一遍两个文件然后得出这一段的结果。迭代数次之后得出答案。
保守一点拿其中 16M 做 bitmap，如果使用 四字节 表示整数，那一共需要 32 次迭代。
但在这里讨论时间复杂度没意义，因为读取文件的时间远远大于代码运行的时间。

或者根据分段把文件写入到 32*2 个不同的文件中去，每次处理其中的一对文件，直接内存中排序比较得出结果，迭代 16 次得出整个结果，这里时间复杂度一样没有意义，因为 IO 太多。

所以说没看懂这一题要干什么。

[nowcoder]

@xcv58 嗯，挺详细啦，请给[e-mail] 发邮件说下手机号码，我们给你充值。 多谢参与

[monsoon]

Ruby:
```
def randomSort(array, n)
array.permutation.to_a.shuffle[0,5].each { |e| p e }
end

array = [1, 2, 3, 4, 5, 6]
n = 5
randomSort(array, n)
```

不知道Markdown有没有用。

[xcv58]

@nowcoder 谢了，不过不用了。人不在国内，也没国内的手机号。祝你们的网站生意兴隆。

[sun1991]

第一题我考虑的思路:
算出array的全排列, 或者是前N种全排列, 把结果保存到list, 再乱序排列下list. 需要时从list依次返回即可.

[xcv58]

@nowcoder 突然发现去年 9 月内测的时候就注册了你们网站。

[monsoon]

@monsoon

def randomSort(array, n)
array.permutation.to_a.shuffle[0,n].each { |e| p e }
end

array = [1, 2, 3, 4, 5, 6]
n = 5
randomSort(array, n)

打错了了一个变量……

[flyee]

第一题，什么叫做“乱序”，有明确的要求吗，否则直接next_permutation不就可以吗

[xcv58]

第一题用 MATLAB 是最简单的：
array(1,randperm(size(array, 2)))

[ruoyu0088]

第三题用基数排序。用长度为256的bucket的话，对于64bit整数时间复杂度为O(8*n)，空间复杂度为O(n)。
然后归并两个已经排序的数组即可。

[ruoyu0088]

第二题我用递归，不知道对不对：

https://gist.github.com/ruoyu0088/80f89007c2ca0ed74cdc

[nowcoder]

@ruoyu0088 <script src="https://gist.github.com/ruoyu0088/80f89007c2ca0ed74cdc.js"></script> 你的代码被墙了，卡死了。看不到代码好捉急。

[sleeperqp]

第二题思路:
重点在于每位取0或1会对后面的状态造成什么影响。
从n-1到0遍历
当第i位为0时，会与后面所有的1 形成新的01串
当为1时，单独1串为加一，101串数目会增加01串的数目。
代码如下：
#include<stdio.h>
#include <string.h>
#define N 1024
int sum1[N],sum01[N],sum101[N];
int ans[N];
int main()
{
char str[N];

scanf("%s" ,str);
int n = strlen(str);
sum1[n-1]=sum01[n-1]=sum101[n-1]=0;

for(int i = n-1; i >= 0; --i)
{
if(str[i] == '0')
{
ans[i] = sum101[i+1];
}

if(str[i] == '0')
{
sum101[i] = sum101[i+1];
sum01[i] = sum01[i+1] + sum1[i+1];
sum1[i] = sum1[i+1];
}
else{
sum101[i] = sum101[i+1] + sum01[i+1];
sum01[i] = sum01[i+1];
sum1[i] = sum1[i+1] + 1;
}
}
for(int i = 0 ;i < n ; ++i)
if(str[i] == '0')
{
printf("%d:%d\n", i, ans[i]);
}
return 0;
}

//时间复杂度O(n),空间复杂度O(n),可以用%1来提升至O(1)

[Cee]

第一题去看 Standford 的算法...