据说是百度的面试题

sankt · #1 (**permalink**) 2008-06-07

在CSDN上看到的，大家有兴趣的话就一起讨论下啊，^_^

1 给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。、

2 给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。（这道题面试官说有O(1) 的解法，。。。。。）

3 五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。

sankt · #2 (**permalink**) 2008-06-07

偶再来补充一题：

给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数；

polyrandom · #3 (**permalink**) 2008-06-07

第二题如果不可以预处理，是做不到O(1)的，二分还要O(lgn)呢。不过如果可以预处理，那是可能的，hash就行了。
第三题觉得不可能，天平称一次只能区分三个状态，它有5个状态。如果不是脑筋急转弯，我比较好奇答案。

summersnowe2006 · #4 (**permalink**) 2008-06-07

如果知道正常球的重量的话，还是可以做出第三题的。否则的话，感觉也不可能

Elminster · #5 (**permalink**) 2008-06-12

第三题可能不全吧，估计应该有球的轻重和这个天平的刻度之类的额外信息。
我倒是比较好奇最后那个补充题：我想了半个小时也没做出来，而且直觉上似乎做不出这个结果。有谁做出来了么？或者楼主提供一下答案？

sankt · #6 (**permalink**) 2008-06-13

引用:

作者: Elminster

第三题可能不全吧，估计应该有球的轻重和这个天平的刻度之类的额外信息。
我倒是比较好奇最后那个补充题：我想了半个小时也没做出来，而且直觉上似乎做不出这个结果。有谁做出来了么？或者楼主提供一下答案？

Yep,it is very probable that the third question may lost some information.
I just copyed them from CSDN.

For the additional question,I have also absolutely no idea for it till now.
Just hope some guys jump in here and do a brain storm freely.

polyrandom · #7 (**permalink**) 2008-06-13

引用:

作者: sankt

偶再来补充一题：

给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数；

a和b没有别的条件？假设都不是排序的，那么：
1.a里面都是1，b里面也都是1。B也是1。
2.a里面都是1，b里面也都是0。B也是1。
那么，情况2有n^2个结果。而情况1是0个结果。但是乱序情况下，我看不出1和2有啥大区别。而一旦排序，那么就是O(nlgn)了。

Elminster · #8 (**permalink**) 2008-06-14

引用:

作者: polyrandom

a和b没有别的条件？假设都不是排序的，那么：
1.a里面都是1，b里面也都是1。B也是1。
2.a里面都是1，b里面也都是0。B也是1。
那么，情况2有n^2个结果。而情况1是0个结果。但是乱序情况下，我看不出1和2有啥大区别。而一旦排序，那么就是O(nlgn)了。

应该是排好序的数组才对. 我想了一下, 有排好序这个条件, 算法就是 O(n+k) 复杂度. 估计应该是这个条件漏掉了吧.

liuxinyu · #9 (**permalink**) 2008-06-14

引用:

作者: sankt

偶再来补充一题：

给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数；

我也觉得好像少条件了。跑个题啊，这个题目拿Haskell写特别直接：

代码:

bar xs ys a= [(x,y) | x <- xs, y <- ys, x+y<=a]

直接运行结果如下：

代码:

Bar> bar [4,1,2,5,3,8] [5,6,9,20,7] 15
[(4,5),(4,6),(4,9),(4,7),(1,5),(1,6),(1,9),(1,7),(2,5),(2,6),(2,9),(2,7),(5,5),(5,6),(5,9),(5,7),(3,5),(3,6),(3,9),(3,7),(8,5),(8,6),(8,7)]
Bar> length (bar [4,1,2,5,3,8] [5,6,9,20,7] 15)
23

Elminster · #10 (**permalink**) 2008-06-15

引用:

作者: liuxinyu

我也觉得好像少条件了。跑个题啊，这个题目拿Haskell写特别直接：

代码:

bar xs ys a= [(x,y) | x <- xs, y <- ys, x+y<=a]

直接运行结果如下：

代码:

Bar> bar [4,1,2,5,3,8] [5,6,9,20,7] 15
[(4,5),(4,6),(4,9),(4,7),(1,5),(1,6),(1,9),(1,7),(2,5),(2,6),(2,9),(2,7),(5,5),(5,6),(5,9),(5,7),(3,5),(3,6),(3,9),(3,7),(8,5),(8,6),(8,7)]
Bar> length (bar [4,1,2,5,3,8] [5,6,9,20,7] 15)
23

这种事情拿 haskell 来做确实很方便, 不过不是正道啊, 因为程序员自己很难分析这里的时间复杂度了.

afey · #11 (**permalink**) 2008-08-11

第三题如果只能使用一个天平的话，称一次不能保证一定能找到那个坏的。
而题目中没有限制只能使用一个天平，所以我们使用3个天平的话，只需称一次就可以找到那个坏的：
（1）把两个天平（a和b）放在第三个天平（c）的两端
（2）天平a和天平b的两端各放一个桶，这样有4个桶在天平上，还剩余一个桶
（3）如果天平c是平衡的，说明剩余的那个是坏的
如果天平c不平衡，那么坏桶一定在a和b中不平衡的那个天平上；
我们假设天平a不平衡，而且天平c的a端轻（重），那么天平a上较轻（重）的那个是坏桶。

polyrandom · #12 (**permalink**) 2008-08-12

引用:

作者: afey

第三题如果只能使用一个天平的话，称一次不能保证一定能找到那个坏的。
而题目中没有限制只能使用一个天平，所以我们使用3个天平的话，只需称一次就可以找到那个坏的：
（1）把两个天平（a和b）放在第三个天平（c）的两端
（2）天平a和天平b的两端各放一个桶，这样有4个桶在天平上，还剩余一个桶
（3）如果天平c是平衡的，说明剩余的那个是坏的
如果天平c不平衡，那么坏桶一定在a和b中不平衡的那个天平上；
我们假设天平a不平衡，而且天平c的a端轻（重），那么天平a上较轻（重）的那个是坏桶。

这个想法非常巧妙，只是怎么定义一次？要读出三个天平的读数我觉得算三次了。

afey · #13 (**permalink**) 2008-08-12

引用:

作者: polyrandom

这个想法非常巧妙，只是怎么定义一次？要读出三个天平的读数我觉得算三次了。

我认为这算是一次称量，只是一次使用了三个天平而已，因为这三只天平可以同时得到结果。如果不是这样的话，我觉得没有其它答案了。

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式

LinkBacks (?) LinkBack to this Thread: http://www.cpper.com/c/t4873.html
作者	For	Type	日期
{Algo}һ	This thread	Refback	2008-06-27 12:45 PM
TopLanguage \| Google Groups	This thread	Refback	2008-06-27 01:57 AM
{Algo}一道百度面试题 - TopLanguage \| Google	This thread	Refback	2008-06-27 12:58 AM