百度笔经分享(二)

　　算法:

　　1.在字典中查找单词

　　字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母

　　一个字母匹配.算法时间就是单词的长度k.

　　2.纠错算法

　　情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能 处理方法:

　　(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;

　　(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可 以有更多的)

　　根据分析字典特征和用户单词已输入部分选择(a),(b)处理

　　复杂性分析：影响算法的效率主要是字典的实现与纠错处理

　　(a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈;

　　(b)纠错策略要简单有效 ,如前述情况，是线性复杂度;

　　(3)改进

　　策略选择最是重要，可以采用统计学习的方法改进。

　　//////////////////////////////////////////////

　　4 题

　　(1)思路：用哈希做

　　(2) 首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度(注意值与日志项对应关系) my.chinahrlab.com 选出前十的频度，取出对应的日志串，简单不过了。哈希的设计是关键。

　　//////////////////////////////////////////////////

　　5 题

　　(1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。

　　(2)处理流程：

　　1.将集合按照大小排序，组成集合合并待处理列表

　　2.选择最小的集合，找出与之有交集的集合，如果有，合并之;如果无，则与其它集合是独立集合，从待处理列表 中删除。

　　3.重复直到待处理列表为空

　　算法：1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在：

　　1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。

　　2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。

　　3。如果待处理集合列表不为空，转2。

　　如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。

　　算法复杂度分析：

　　假设集合的个数为n，最大的集合元素为m 排序的时间复杂度可以达到nlog(n) 然后对于元素在其他集合中查找，最坏情况下为(n-1)m 查找一个集合是否与其他集合有交集的最坏情况是mm(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(mmnn)

　　需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。

　　(3)可能的改进：

　　首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。

　　、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

　　1)此题10分

　　对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18!=6402373705728000，尾部连续0的个数是3。 　　(不用考虑数值超出计算机整数界限的问题)

　　2)此题10分 　　编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url

　　如下形式叫做首页：

　　militia.info/

　　www.apcnc.com.cn/

　　http://www.cyjzs.comwww.greena888.com/

　　www.800cool.net/

　　http://hgh-products.my-age.net/

　　如下形式叫做目录页：

　　thursdaythree.net/greenhouses--gas-global-green-house-warming/

　　http://www.mw.net.tw/user/tgk5ar1r/profile/

　　http://www.szeasy.com/food/yszt/chunjie/

　　www.fuckingjapanese.com/Reality/

　　请注意：

　　a) url有可能带http头也有可能不带

　　b)动态url(即含有"?"的url)的一律不算目录页，如：

　　www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/

　　www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/

　　另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。

　　3)此题40分

　　如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。

　　4)此题40分

　　假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。 阅读此文的读者还阅读了：
建设银行全程笔试经验
北电笔试经验程序笔试
爱立信机考笔试经验