1、给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？ 方 案 1： 可 以 估 计 每 个 文 件 安 的 大 小 为 50G×64=320G， 远 远 大 于 内 存 限 制 的 4G。 所 以 不可 能 将 其 完 全 加 载 到 内 存 中 处 理 。 考 虑 采 取 分 而 治 之 的 方 法 。 s 遍 历 文 件 a，对 每 个 url求 取，然 后 根 据 所 取 得 的 值 将 url分 别 存 储 到 1000个 小 文 件 （ 记 为） 中 。 这 样 每 个 小 文 件 的 大 约 为 300M。 s 遍 历 文 件 b，采 取 和 a 相 同 的 方 式 将 url 分 别 存 储 到 1000 个 小 文 件（ 记 为）。这 样 处 理 后 ， 所 有 可 能 相 同 的 url 都 在 对 应 的 小 文 件 （） 中 ，不 对 应 的 小 文 件 不 可 能 有 相 同 的 url。然 后 我 们 只 要 求 出 1000 对 小 文 件 中 相 同 的 url 即 可 。 s 求 每 对 小 文 件 中 相 同 的url 时 ， 可 以 把 其 中 一 个 小 文 件 的url 存 储 到hash_set 中 。 然 后遍 历 另 一 个 小 文 件 的 每 个url， 看 其 是 否 在 刚 才 构 建 的hash_set 中 ， 如 果 是 ， 那 么 就 是 共同 的 url， 存 到 文 件 里 面 就 可 以 了 。 方 案 2： 如 果 允 许 有 一 定 的 错 误 率 ， 可 以 使 用 Bloom filter， 4G 内 存 大 概 可 以 表 示 340 亿bit。 将 其 中 一 个 文 件 中 的 url 使 用Bloom filter 映 射 为 这 340 亿bit， 然 后 挨 个 读 取 另 外一 个 文 件 的 url， 检 查 是 否 与 Bloom filter， 如 果 是 ， 那 么 该 url 应 该 是 共 同 的 url（ 注 意 会有 一 定 的 错 误 率 ）。 2、有 10 个文件，每个文件 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求你按照query 的频度排序。 方 案 1： s、顺序读 取10 个 文 件 ， 按照 hash(query)的 结果 将query 写入到 另 外10 个 文 件 （ 记 为） 中 。 这 样 新生成的 ...
