当前位置:范文城>行业范本>计算机软件>

百度2012实习软件研发工程师(C/C++开发)笔试题

计算机软件 阅读(9.03K)

找兄弟单词,例如mary和army是兄弟单词,即所含字母是一样的,只是字母顺序不同,给出一个单词,要求在一个字典中找出该单词的所有兄弟单词,给出实现方案。我的解答:

百度2012实习软件研发工程师(C/C++开发)笔试题

把各个单词a的各个字母按照字母表顺序排序,排序后的新单词是b,然后根据b构建一棵二叉平衡树,节点值为b,各个节点存储一个数组 ,就是b对应的所有a,这样很容易找到所有的兄弟单词

2. 关于两个链表是否含有相同节点的,题目说什么网络爬虫,从一个页面开始爬,将爬到的url存到一个链表里,假设每个页面至多含有一个link(重点信息),现在从两个不同页面开始爬,将得到的url放到链表就得到了两个链表,要求判断两个链表是否含有相同的url,假设每个链表的'包含的url有上百亿个,不能用hash,给出算法。

我的解答:

上百亿个url应该是存在文件里面的,不会全部放到内存中。所以建立一棵B树来存储第一个链,对应的url存储在文件中。然后依次把第二个链各个url在B树做查找工作即可

3. 关于百度suggestion的

给出实现这个功能主要的数据结构和算法,以及优化的方法,提高时间和空间的效率。

我的解答:

采用堆排序算法

每个对应十个节点