百度二面面经

硬币放在长方形中心 之后按照中心对称的方法跟着后手放

刚刚看到了网上一模一样的题： 6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？     可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。     分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为，这里漏写个了a1）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。     hash_set统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

最后一题感觉考察智力啊。。第一个人放在正方形的最中间，根据正方形的对称性，以后只要第二个人能在其他处放下一枚硬币，那么第一个人都可以在对称的位置放下硬币。这样第一个人肯定能够获胜啊

第二题可不可以分别把a，b拆成小文件，每个文件中的url通过hash+散列分配到不同的文件中，再去找相同的url。 第三题回溯+剪枝 第四题先手必胜，第一步放中心

楼主现在三面了吗

第二题我面试的时候也问到了 一开始说的哈希和字典树, 他觉得内存还是不够 然后说的布隆过滤器 但布隆过滤器会误判, 问误判怎么办.

针对第二题，如果50亿条URL存在大量重复，是不是可以用字典树去解决，感觉存储效率和时间效率都还不错

第三题你怎么答得，枚举3个小数点的位置吗？还有没有更好的方法

第二题（根据题意应该是a、b文件本身url都不重复，而a与b的url才会重复）： 用两个2^16的bitmap分别记为bma和bmb（2^16+2^16=2^32=4G），分别与a、b文件中url的高16位想与，然后bma和bmb想与，这时的结果表示可能重复的url的高16位，再用这个结果分别过滤a、b中的url； 使用这种方法依次通过url从高到低的16位相与过滤不会重复的url，最后留下的就是重复的。

第二题应该是布隆过滤器

3. 19.213.1.12不是吗？怎么只返回两个

如果一个长方形最多放一个硬币，先放的必胜，如果最多可以放两个，先放的也必胜； 然后把大长方形分割成这样的小长方形，。这样不知道可以不可以

如果一个长方形只能放下两个硬币，那应该不是第一个放硬币的人必胜。请问面试官的意思是让回答“是不是第一个人必胜”这个问题，还是要写出算法呢？

我也想求最后一题的思路

最后一个咋答