如何从大量的 URL 中找出相同的 URL?
给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。
对于这种类型的题目,一般采用分治策略,即:把一个文件中的 URL 按照某个特征划分为多个小文件,使得每个小文件大小不超过 4G,这样就可以把这个小文件读到内存中进行处理了。
首先遍历文件 a,对遍历到的 URL 求 hash(URL) % 1000 ,根据计算结果把遍历到的 URL 存储到 a0, a1, a2, …, a999,这样每个大小约为 300MB。
使用同样的方法遍历文件 b,把文件 b 中的 URL 分别存储到文件 b0, b1, b2, …, b999 中。
所有可能相同的 URL 都在对应的小文件中,即 a0 对应 b0, …, a999 对应 b999
比对 ai 与 bi 是否存在相同即可
如何从 5 亿个数中找出中位数?
从 5 亿个数中找出中位数。数据排序后,位置在最中间的数就是中位数。当样本数为奇数时,中位数为 第 (N+1)/2 个数;当样本数为偶数时,中位数为 第 N/2 个数与第 1+N/2 个数的均值。
维护两个堆,一个大顶堆,一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数;保证这两个堆中的元素个数的差不超过 1。
若数据总数为偶数,当这两个堆建好之后,中位数就是这两个堆顶元素的平均值。当数据总数为奇数时,根据两个堆的大小,中位数一定在数据多的堆的堆顶。