复习笔记7

百度的面试题

引用

1、两个已排序数组a,b，怎样找两个数组中的不同元素
2、怪人豆问题：一个怪人装着60颗豆过80米的桥，每走一米吃一颗，每次最多只能装60颗
，可以在桥上任意地点储存豆子，问过桥最少要多少颗豆？如果是81米呢？
3、两个文件集合a,b分别存着网页名（如www.baidu.com）,找两个文件集的差集（即a中有
b中没有名称）？如果内存很小，文件很大应该怎么做？
4、如果两个英文单词所包含字母是相同但顺序不同，则两个单词是相似的，如果输入一个
字符串，比方说“abc bac aaa bbb...”找出相似词
5、设计一个blog系统的存储方案，包括用户，文章和评论三个元素，满足这样的功能：

a.用户可以浏览文章，评论
b.用户管理自己的评论
说是设计存储方案，是选数据库还是文件系统之类的，然后说说具体实现

1 归并排序的思路，最坏情况o（m+n），基本不需要辅助空间
2 80米简单，带60颗，走20米埋20颗，回来，再带60颗出发
  81米稍微复杂，需要两次存储，简单方程一下，第一次存储3颗，第二次存储18颗，129颗。
不过有牛人说125颗可以搞定，得再想想
------------------------
经提醒，发现思维漏洞，没有限制存储多少颗豆子
所以只需要在1m处存储61颗豆，用两次放豆，总共125颗豆

3 如果对正确率不是太苛刻，bloomfilter
4 设计一个hash算法，例如一个26位int数组，将每一个str先变为这样一个数组，在hash放入map
5 方案很多，没想明白最优的是什么