算法面试题

只看该作者 · 2012-9-26 23:14

1. 有两个顺序一致的有序队列，其长度分别为M和N，试求归并这两个队列的最小比较次数，最大比较次数和平均比较次数，写出结果并简述思路。

2.给你若干字符串，判断这些字符串是否两两互不为前缀。

3.假设秒针某系统每天有超过10亿次的页面访问量，出于客户需求，该系统会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间爱你段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？

4.两个文本文件，文件名分别为A和B，内容分别为每行一个字符串(20-40个字节)，每个文件有10W行，记录可能重复。进使用Linux命令和shell脚本找出这两个文件爱你中重复的字符串.

只看该作者 · 2012-9-26 23:20

3. 建立一个查找二叉树. 不过非一般性查找二叉树. 其节点需要增加若干内容:
①增加以此节点为根的树含有子节点的数目.
②增加以此节点为根的树以时间段为key的区间范围. 或者说始终保留其中的最大值和最小值.
另外, 此树需要保持平衡, 例如使用红黑树. 则在保持节点新增属性的情况下, 仍需保持平衡.
具体细节相对复杂, 简易参考<<算法导论>>中的数据结构扩展一节(在红黑树一节之下).
查找的过程是显然的, 且有可能被分割到不同子树进行. 如果这个分割比较严重, 则速度是相当慢的.

只看该作者 · 2012-9-26 23:44

1. 最小是1，比如M的所有项都比N中的大，只比较一次就可以。最大是M+N，平均是log2(M+N),采用2分法比较。
2。可以用构建树的方式判断，不过实现相对复杂，取最短串的长度为N，每个串前N个字符算hash，如果hash冲突，比较字符串即可。
3.按时间段分开存储，比如每个小时的访问信息做一个独立数据结构，数据结构可以采用map，IP作key，，具体时间为value，或者自己用IP构造一个hash。如果访问比较均匀的话，效率还是可以。如果某个时间段访问量非常巨大，就会导致那个时间段数据量太大，查询慢
4。可以用wc统计文件行数，然后shell遍历文件，一行行比较，用sed也可以做全文搜索，好久没用shell了，有点忘了

只看该作者 · 2012-9-27 09:43

说到算法就头痛

只看该作者 · 2012-9-28 00:33

作为面试题，还是很有难度的

算法面试题

相关下载

相关帖子