悬赏大牛解答求职题目，有现金和礼物答谢（ 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
邮件 [email protected]
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~

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

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

第三题话费由 @xcv58 获取，多谢参与。
第一第二题求大神解答，组合和随即排序木有思路吗？
奖品等主人好久了呢，嘤嘤

第二题已由@sleeperqp解答，多谢参与。

[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 嗯，挺详细啦，请给[email protected] 发邮件说下手机号码，我们给你充值。 多谢参与

[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 的算法...

[lijinma]

第一题全排列？然后记状态？

……这题目真是捉急。

[nowcoder]

@sleeperqp 代码结果准确，请教下 ’当为1时，单独1串为加一，101串数目会增加01串的数目。‘ 是什么意思？ 还是没看明白。

[sleeperqp]

@nowcoder 额
单独1串是以1为组成的子串，就是后面所有1的个数
101串就是说按1,0,1顺序的子串
01串就是按0,1顺序的子串
= =写得太过笼统了
逆序遍历时
当str[i]==‘1’时，在单独1串的个数加1(因为他就是1的个数)
101串的数目也增加，增加的部位为与i+1位的01串组合成新的101串 所以这里是加上i+1位的01串的数目

[zixincao]

第三题思路：可以用bit map来解决，首先申请2个1千万个位大小的空间，分别按照每个文件中的每个十进制下标来给相应的位置置状态1，没有的默认为0。这样置完状态就已经排好序了，输出的话就按状态输出。时间复杂度为O(n)，空间复杂度也就是2个1千万2进制位占的空间大小，为2448KB左右。

[nowcoder]

@sleeperqp 请发手机号到 [email protected] 我们给你充值，多谢参与

[lightening]

@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 中的指针），空间则几乎小了一半。

[lightening]

@lightening 当然 mod 只是最简单的散列方法。完全可以用个好点的 hash 算法，提高散列均匀度的话，就可以减少某个 struct 中需要动用那个指针的概率。不过相对的，散列运算花的时间就要久一点。

[exch4nge]

哦，看了 @sleeperqp 的答案想了半天才明白，第二题其实是求一个串的某子序列数量，用了动态规划的方法解决的。如果0101不是给定的话，定m为0101的长度时，时间复杂度为O(Nm)

[sleeperqp]

@exch4nge 是的 就是动态规划的方法 O(∩_∩)O~

[omegaga]

第三题不就是非常经典的table join吗……SQL里两个table join起来（以table_a.key = table_b.key为条件），不就跟这个题一模一样的情景吗。经典的table join算法有三种：nested loop, hash join和merge join，三种算法各有优点。在这个题目里，两个文件（table）的规模都很大，用hash做空间开销太大，如果是数据库的话就会用merge join，用归并排序的思路就可以了。当然，这个题目里因为是int，所以可以用基数排序先排序，然后再归并，就是一个线性算法了。

[omegaga]

第一题，首先对于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次都不相同。

[WKPlus]

看了一下，问题还蛮有意思，很多都是公司中系统设计时确实会遇到的问题，试着答了两个，期待看到更多大牛作答。

[nowcoder]

@omegaga 多谢解答，请发送手机号到[email protected] 我们给你充值