发布于 2015-03-30 08:56:12 | 197 次阅读 | 评论: 0 | 来源: 网友投递
谷歌(Google)搜索引擎
Google公司（中文译名：谷歌），是一家美国的跨国科技企业，致力于互联网搜索、云计算、广告技术等领域，开发并提供大量基于互联网的产品与服务，其主要利润来自于AdWords等广告服务。
如何随机选取1000个关键字
给定一个数据流，其中包含无穷尽的搜索关键字(比如，人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?定义长度为1000的数组。对于数据流中的前1000个关键字，显然都要放到数组中。
对于数据流中的的第n(n>1000)个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。
将下列表达式按照复杂度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照复杂度从低到高为
n^Googol
2^n
n!
n^n
数组中是否有两个数的和为10
1.比较任意两个数的和是否为10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
复杂度为O(n*n)。
2.将数组排序后，对每个数m，使用二分查找在数组中寻找10-m。
复杂度为O(nlogn)。
3.将数组存储到hash_set中去，对每个数m，在hash_set中寻找10-m。
复杂度为O(n)。
4.如果数组很大，超过内存的容量，可以按照hash(max(m, 10-m))%g，将数据分到g个小的group中。然后对每个小的group进行单独处理。
复杂度为O(n)。