百度网上笔试试题及答案
//////////////////////////////////////////////
4 题
(1)思路： 用哈希做
(2) 首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度 (注意值与日志项对应关系) my.chinahrlab.com 选出前十的频度，取出对应的日志串，简单不过了。 哈希的设计是关键。
//////////////////////////////////////////////////
5 题
(1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有 就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比 较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候， 就终止。
(2)处理流程：
1.将集合按照大小排序，组成集合合并待处理列表
2.选择最小的集合，找出与之有交集的集合， 如果有，合并之; 如果无，则与其它集合是独立集合，从待处理列表 中删除。
3.重复直到待处理列表为空
算法： 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索 是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。
2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素 都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集 合列表。转3。
3。如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m 排序的时间复杂度可以达到n*log(n) 然后对于元素在其他集合中查找，最坏情况下为(n-1)*m 查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。 所以最终最坏时间复杂度为O(m*m*n*n)
需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处 于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先 与最大的集合进行比较，这些都最大的回避了最坏情况。
(3)可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及 合并的效率增高。 另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
- 上一篇：大唐联诚系统招集成工程师笔试试题
《百度网上笔试试题及答案》相关文章
- 百度网上笔试试题及答案
- › 百度网上笔试试题及答案
- › 百度网上笔试题及答案
- 在百度中搜索相关文章：百度网上笔试试题及答案
- 在谷歌中搜索相关文章：百度网上笔试试题及答案
- 在soso中搜索相关文章：百度网上笔试试题及答案
- 在搜狗中搜索相关文章：百度网上笔试试题及答案
