百度实习生笔试题
1、给一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么b是a的兄弟单词，比如的单词army和mary互为兄弟单词。
现在要给出一种解决方案，对于用户输入的单词，根据给定的字典找出输入单词有哪些兄弟单词。请具体说明数据结构和查询流程，要求时间和空间效率尽可能地高。
2、系统中维护了若干数据项，我们对数据项的分类可以分为三级，首先我们按照一级分类方法将数据项分为A、B、C......若干类别，每个一级分类方法产生的类别又可以按照二级分类方法分为a、b、c......若干子类别，同样，二级分类方法产生的类别又可以按照是三级分类方法分为i、ii、iii......若干子类别，每个三级分类方法产生的子类别中的数据项从1开始编号。我们需要对每个数据项输出日志，日志的形式是key_value对，写入日志的时候，用户提供三级类别名称、数据项编号和日志的key，共五个key值，例如，write_log（A,a,i,1,key1），获取日志的时候，用户提供三级类别名称、数据项编号，共四个key值，返回对应的所有的key_value对，例如get_log（A,a,i,1,key1）。
请描述一种数据结构来存储这些日志，并计算出写入日志和读出日志的时间复杂度。
3、C和C++中如何动态分配和释放内存？他们的区别是什么？
算法与程序设计、
网页爬虫在抓取网页时，从指定的URL站点入口开始爬取这个站点上的所有URL link，抓取到下一级link对应的页面后，同样对页面上的link进行抓取从而完成深度遍历。为简化问题，我们假设每个页面上至多只有一个link，如www.baidu.com/a.html链接到www.baidu.com/b.html再链到www.baidu.com/x.html，当爬虫抓取到某个页面时，有可能再链www.baidu.com/b.html，也有可能爬取到一个不带任何link的终极页面。当抓取到相同的URL或不包含任何link的终极页面，即完成爬取。爬虫在抓取到这些页面后建立一个单向链表，用来记录抓取到的页面，如：a.html->b.html->x.html...->NULL。
问：对于爬虫分别从www.baidu.com/x1.html和www.baidu.com/x2.html两个入口开始获得两个单向链表，得到这两个单向链表后，如何判断他们是否抓取到了相同的URL？（假设页面URL上百亿，存储资源有限，无法用hash方法判断是否包含相同的URL）
请先描述相应的算法，再给出相应的代码实现。（只需给出判断方法代码，无需爬虫代码）
系统设计题
相信大家都使用过百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何实现？请给出实现思路和主要的数据结构、算法。有什么优化思路可以使得时间和空间效率最高？
[解决办法]
笔试面试除了算法还是算法，对于应届生来说。。。
一，每个单词对应char[127]的数组，char[n]表示字母ASCII字母n的出现次数，于是查找的时候就可以memcmp高效的去比较了。
二，三个方案：
1，随便把5个key用各种变化+Hash算出个值开散列一下就行了。
2，也多级哈希，先按A+key散列，如果冲突那么进入2级哈希，用a+key散列，再冲突进入i+key散列，一共4级，第5级是极限了，必须开散列了，前边4级可以闭散列。这样的优点很明显，计算哈希比较快，前4级内存是静态的，效率也高。
3，如果将来希望按照级别来浏览日志，难度也不算大。
三，new分配内存+构造对象，malloc只分配内存，delete析构对象并释放内存，free只释放内存。
new = malloc + placement new, delete = ~Object() + free.
四,
算法版：链表的qsort+interact求交集（题意应该是不让用额外空间的意思）。
实际操作版：两个进程分别跑一个链表，把URL=>次数放到memcached里，最后出现次数为1的就是交集（违背题意，借助memcached这个高效的线程安全的哈希表）。
五，动态扩展Node的trie树+栈DFS。
[解决办法]
第一题我的思考答案：
因为一个单词由26个字母组成，那么可以设计一个映射算法，将每个单词转化为按字母顺序排序的bit表。用一个int（32,先不考虑重复字母）位就可以标识位特定兄弟的单词。
比如，mary、和army、marry都可以转化为amry对应的bit位 {1（a）000000 000001（m）0 000 1（r）00 000 01（y）0} 即转化这个整数。
那么所有的单词都可以进行相应的归类。
这样对于特定的单词只要经过一遍扫描这个单词就可以确定他的bit值K，然后根据这个K来寻找到他的兄弟。
如果需要区别是否含重复数值，可以再比较K里面的单词。
或者：
在上面的hash值设置的时候，每个bit位不用1表示，而用具体的整数值表示字符出现的个数， K就为一个整数数组。这样就可以一次区别出是否含重复字符。
[解决办法]
楼上说的有一定的道理，确实就是变相的考直接插入排序。
关键是将折半查找算法加入到插入元的位置的定位中，
该位置以及其之前的元素为所在数组的位置是这些元素的最终位置，可以整个数组的规模减小。
该从插入元之后的元素开始到数组结束形成新的和上述问题一样的归并排序。
这个算法应该比带折半查找的直接插入的排序的快的多，因为，数组的后半部分是有序的。
