这是一个创建于 3646 天前的主题，其中的信息可能已经有所发展或是发生改变。
昨天在论坛上放出的三道题，前两道已经被@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
再次感谢大家！祝大家新年行好运，早日找到女朋友！！
第 1 条附言 · 2015-01-05 12:08:16 +08:00
第 2 条附言 · 2015-01-05 19:46:35 +08:00
第二题已由@sleeperqp解答，多谢参与。
 |
1
icedx 2015-01-05 11:08:54 +08:00 via Android
我擦咧 第三题没人解?
|
 |
4
xcv58 2015-01-05 11:32:17 +08:00
不知道是不是我没看懂。
第三题中两个一千万行的文件，完全可以直接读到内存中。 最暴力的方法两个文件内容都归并排序，然后顺序扫一遍。 时间 O(n*log(n)) 就行了。 节省时间的方法用 Hash 之类的先过一遍，然后找到重复的值，再排序。时间 max(O(n), O(k*log(k)) |
 |
5
nowcoder OP @Valyrian 直接留言回答就可以。思路正确，解答详细我们就发奖品。 上我们网站答题额外有奖金，具体参考 http://www.nowcoder.com/activity/challenge
|
|
7
xcv58 2015-01-05 11:56:51 +08:00  1
@nowcoder 这种题目实在提不起兴趣啊。
要是我平时要用到的话肯定直接这样了： sort -n file1 file2 | uniq -d 我平时排序几百兆的文件都这么干的。 所以千万级别的纯数字真没啥意思。 要论难度就限制内存大小或者增大数据量。 譬如只能用 32M 内存。 这样的话就需要用小的 bitmap 把整数的范围分段，每次过一遍两个文件然后得出这一段的结果。迭代数次之后得出答案。 保守一点拿其中 16M 做 bitmap，如果使用 四字节 表示整数，那一共需要 32 次迭代。 但在这里讨论时间复杂度没意义，因为读取文件的时间远远大于代码运行的时间。 或者根据分段把文件写入到 32*2 个不同的文件中去，每次处理其中的一对文件，直接内存中排序比较得出结果，迭代 16 次得出整个结果，这里时间复杂度一样没有意义，因为 IO 太多。 所以说没看懂这一题要干什么。 |
|
8
nowcoder OP @xcv58 嗯，挺详细啦，请给[email protected] 发邮件说下手机号码，我们给你充值。 多谢参与
|
 |
9
monsoon 2015-01-05 12:09:21 +08:00
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有没有用。 |
 |
11
sun1991 2015-01-05 12:13:26 +08:00
第一题我考虑的思路:
算出array的全排列, 或者是前N种全排列, 把结果保存到list, 再乱序排列下list. 需要时从list依次返回即可. |
|
13
monsoon 2015-01-05 12:15:37 +08:00
@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) 打错了了一个变量…… |
 |
14
flyee 2015-01-05 12:24:21 +08:00
第一题，什么叫做“乱序”，有明确的要求吗，否则直接next_permutation不就可以吗
|
|
15
xcv58 2015-01-05 12:31:52 +08:00
第一题用 MATLAB 是最简单的：
array(1,randperm(size(array, 2))) |
 |
16
ruoyu0088 2015-01-05 12:48:22 +08:00
第三题用基数排序。用长度为256的bucket的话，对于64bit整数时间复杂度为O(8*n)，空间复杂度为O(n)。
然后归并两个已经排序的数组即可。 |
|
17
ruoyu0088 2015-01-05 13:06:07 +08:00
|
|
18
nowcoder OP @ruoyu0088 <script src="https://gist.github.com/ruoyu0088/80f89007c2ca0ed74cdc.js"></script> 你的代码被墙了，卡死了。看不到代码好捉急。
|
 |
19
sleeperqp 2015-01-05 13:48:16 +08:00
第二题思路:
重点在于每位取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) |
 |
20
Cee 2015-01-05 13:58:30 +08:00
第一题去看 Standford 的算法...
|
 |
21
lijinma 2015-01-05 14:36:31 +08:00
第一题全排列？然后记状态？
……这题目真是捉急。 |
|
22
nowcoder OP 1
@sleeperqp 代码结果准确，请教下 ’当为1时，单独1串为加一，101串数目会增加01串的数目。‘ 是什么意思？ 还是没看明白。
|
|
23
sleeperqp 2015-01-05 15:06:08 +08:00
@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串的数目 |
 |
24
zixincao 2015-01-05 16:09:03 +08:00
第三题思路：可以用bit map来解决，首先申请2个1千万个位大小的空间，分别按照每个文件中的每个十进制下标来给相应的位置置状态1，没有的默认为0。这样置完状态就已经排好序了，输出的话就按状态输出。时间复杂度为O(n)，空间复杂度也就是2个1千万2进制位占的空间大小，为2448KB左右。
|
|
25
nowcoder OP @sleeperqp 请发手机号到 [email protected] 我们给你充值，多谢参与
|
 |
26
lightening 2015-01-05 18:25:07 +08:00 1
@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 中的指针），空间则几乎小了一半。 |
|
27
lightening 2015-01-05 18:28:28 +08:00
@lightening 当然 mod 只是最简单的散列方法。完全可以用个好点的 hash 算法，提高散列均匀度的话，就可以减少某个 struct 中需要动用那个指针的概率。不过相对的，散列运算花的时间就要久一点。
|
 |
28
exch4nge 2015-01-05 19:03:34 +08:00 1
哦，看了 @sleeperqp 的答案想了半天才明白，第二题其实是求一个串的某子序列数量，用了动态规划的方法解决的。如果0101不是给定的话，定m为0101的长度时，时间复杂度为O(Nm)
|
 |
30
omegaga 2015-01-05 22:41:55 +08:00
第三题不就是非常经典的table join吗……SQL里两个table join起来（以table_a.key = table_b.key为条件），不就跟这个题一模一样的情景吗。经典的table join算法有三种：nested loop, hash join和merge join，三种算法各有优点。在这个题目里，两个文件（table）的规模都很大，用hash做空间开销太大，如果是数据库的话就会用merge join，用归并排序的思路就可以了。当然，这个题目里因为是int，所以可以用基数排序先排序，然后再归并，就是一个线性算法了。
|
|
31
omegaga 2015-01-05 23:05:21 +08:00 1
第一题，首先对于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次都不相同。 |
 |
32
WKPlus 2015-01-05 23:28:40 +08:00
看了一下，问题还蛮有意思，很多都是公司中系统设计时确实会遇到的问题，试着答了两个，期待看到更多大牛作答。
|
|
33
nowcoder OP @omegaga 多谢解答，请发送手机号到[email protected] 我们给你充值
|
Select Language