存档

2012年10月 的存档

二分查找,你真的会吗?

2012年10月6日 19 条评论

---

面试常让写二分查找或其扩展的程序,以前总觉得很简单,但是真动手写起来,细节很多,容易出错的地方也很多,真是秒杀眼高手低的利器,本节就二分查找以及相关扩展程序都实现一下,同时将可能出错的地方以及需要注意的细节也一并说明,水平有限,欢迎补充。

内容如下:

1)二分查找元素key的下标,如无 return -1

2)二分查找返回key(可能有重复)第一次出现的下标,如无return -1

3)二分查找返回key(可能有重复)最后一次出现的下标,如无return -1

4)二分查找返回刚好小于key的元素下标,如无return -1

5)二分查找返回刚好大于key的元素下标,如无return -1

注:以上所有问题可能出错的地方以及需要注意的细节说明在代码注释中。

直接上代码:

阅读全文...

2013百度校园招聘面经

2012年10月4日 9 条评论

---

百度校招在大连站比较早,也比较迅速,十一假期前已经发放offer,我投的研发职位,有幸拿到了offer,这里贴个面经。

笔试

笔试前面是考察知识型,后面算法设计和系统设计还是比较有意思,题目就不一一列举了,这里有童鞋都码出来了。简单说下算法设计和系统设计,欢迎讨论。

算法设计1,锦标赛排序,赢者树;

算法设计2,程序写起来简单,但是写完程序也不知结果,哈,如果要直接分析出答案,有一定难度,网上有分析很给力,在这里

算法设计3,多路归并,败者树

系统设计题

这个题目比较复杂,原因是需要检索出的结果可以是电话号码中的连续子串匹配结果,也可以是姓名拼音的匹配结果,我没有好的思路,只有个模糊粗糙的方案,列出来欢迎讨论。

数据结构:Trie树,树的节点结构大致包含Next指针数组与存储resultUser的Vector。

方案:对电话列表进行预处理,建立索引系统;索引即trie树,不过这里不是字符trie,而是数字trie,因为用户输入是数字号码串;考虑到电话号码的连续子串也进行匹配,我做如下处理(比较粗糙)。

阅读全文...