百度、google 海量数据搜索算法题解
下面是某同仁在 baidu 和 google 的笔试中遇到的两道“百度、google 海量数据搜索算法题解”
Google 和 baidu,人家的数据量在那里摆着,他们的命题思路很明确,不要求具体语言,只
要求程序的效率和可行性,题目大多数是关于海量数据搜索的算法问题。
百度、google 的海量数据搜索算法题
1、有 1 亿个浮点数,请找出其中最大的 10000 个。提示:假设每个浮点数占 4 个字节,
1 亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。
2、有一篇英文文章(也就是说每个单词之间由空格分隔),请找出“csdn”这个单词出现的
次数,要求效率最高,并写出算法的时间级。
Peak Wong 的海量数据搜索算法题解
1、有 1 亿个浮点数,请找出其中最大的 10000 个。提示:假设每个浮点数占 4 个字
节,1 亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。
其实占用内存不算大, 可以接受. 呵呵.既然不可以一次读入内存, 那可以这么试试:
方法 1: 读出 100w 个数据, 找出最大的 1w 个, 如果这 100w 数据选择够理想, 那么以
这 1w 个数据里面最小的为基准, 可以过滤掉 1 亿数据里面 99%的数据, 最后就再一次在剩
下的 100w(1%)里面找出最大的 1w 个咯~~
方法 2: 分块, 比如 100w 一个块, 找出最大 1w 个, 一次下来就剩下 100w 数据需要找
出 1w 个了.