V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
a1310747
V2EX  ›  问与答

百度的一个面试题:从 1 亿个无序数据里找第 5000W 个

  •  
  •   a1310747 · 2017-02-28 16:44:35 +08:00 · 8000 次点击
    这是一个创建于 2826 天前的主题,其中的信息可能已经有所发展或是发生改变。

    具体该如何实现,我完全没头绪 只能想先排序然后找

    32 条回复    2017-03-01 22:30:45 +08:00
    msg7086
        1
    msg7086  
       2017-02-28 16:45:50 +08:00
    a[5000w]?

    你是想说排大小排第 5000w 的那个?
    xxdd
        2
    xxdd  
       2017-02-28 16:50:53 +08:00
    select t.numbe from table t order by t.number limit 50000000,50000000

    简单 粗暴!速度慢 加内存 加索引
    msg7086
        3
    msg7086  
       2017-02-28 16:54:02 +08:00
    要我做的话,小顶堆或者半个快排。
    exoticknight
        4
    exoticknight  
       2017-02-28 17:00:24 +08:00
    感觉像编程珠玑里面的一题?
    neosfung
        5
    neosfung  
       2017-02-28 17:06:53 +08:00
    morefreeze
        6
    morefreeze  
       2017-02-28 17:07:30 +08:00   ❤️ 3
    就是快排分组那个算法改一下,每次只用去其中一半找就行了,记得复杂度平均下来是 N
    Valyrian
        7
    Valyrian  
       2017-02-28 17:09:49 +08:00
    无序数组找中位数是经典面试题啊= =
    https://en.wikipedia.org/wiki/Median_of_medians
    srlp
        8
    srlp  
       2017-02-28 17:14:23 +08:00 via iPhone
    这是算法题吧,可以考虑快排或者最小堆。
    2lecl
        9
    2lecl  
       2017-02-28 17:16:20 +08:00
    可以反问一下面试官,数的分布情况
    如果分布均匀,就 mapreduce
    a1310747
        10
    a1310747  
    OP
       2017-02-28 17:33:20 +08:00
    最近面试被打击的不行...
    ninjadq
        11
    ninjadq  
       2017-02-28 17:40:22 +08:00   ❤️ 1
    先用 O(n)的 shuffle 算法打散,然后用快排的 partition 操作一步步逼近
    kindjeff
        12
    kindjeff  
       2017-02-28 17:41:39 +08:00
    是什么数据?如果是数值类型的话,我有一个思路不知道行不行。

    把 1 亿个数遍历一遍,找到数值的范围(最大值和最小值),比如是 0 到 100 亿。
    然后把它分成 10 万个区间,第一个区间代表数值是在 0 到 10 万,第二个区间是 10 万零 1 到 20 万以此类推。然后像桶排序那样,把这 1 亿个数遍历一遍并放入数值所在的区间。然后就可以知道每个区间的数值个数,然后直接可以定位到一个区间。

    然后以此类推。
    binux
        13
    binux  
       2017-02-28 17:46:54 +08:00
    百度拿这个问题问了 10 年了吧
    lishunan246
        14
    lishunan246  
       2017-02-28 18:33:34 +08:00
    quick select
    danielmiao
        15
    danielmiao  
       2017-02-28 19:35:04 +08:00
    @neosfung 这个文章我看了,关于分治法的一个疑问,一个大文件取出现概率前 100 的数,就是吧一个大文件分成 N 份以后取每个文件的前 100 ,再归并排序,但是为什么整个文件的前 100 的数一定在这 N 份文件的 TOP100 里面??会不会出现一个数是每个文件的 TOP101 ,但是整个文件里面是 TOP100 内的?
    h3nng
        16
    h3nng  
       2017-02-28 19:57:07 +08:00
    @binux 233 ,我当年面试也是这个问题。。
    a1310747
        17
    a1310747  
    OP
       2017-02-28 20:17:07 +08:00
    @h3nng 你是怎么回答的呢
    snnn
        18
    snnn  
       2017-02-28 20:54:24 +08:00 via Android
    方法有很多种,我告诉你一个一般人不知道的:区间估计。先采样,然后做区间估计。然后拿这个区间去筛原始的 input 。然后随便怎么搞都行。
    billlee
        19
    billlee  
       2017-02-28 21:07:21 +08:00
    半边的快排,复杂度 O(n), 这不是基础算法吗?
    neosfung
        20
    neosfung  
       2017-02-28 22:43:31 +08:00
    @danielmiao 你可能理解错我的分治法的意思了
    假设是 INT32 的类型,你就建个大小为 2^32 的 array
    遍历原始数据,每个数在 array 相对应的位置加一
    然后遍历 array ,就知道 5000W 是哪个数了
    内存不能够建 2^32 大小的数组?没关系,你可以建个 2^16 大小的数组,每个元素是个指针,指向一个 2^16 大小的数组。然后每个数据可以切分为前后两部分。
    百度问你这条题,是因为还有 follow up 的问题的
    就是如果这些数据都不能一次放到内存里面呢?如果这些数据都分散在很多台机器上呢。
    都可以用我提到的方法通过外存来解决
    roychan
        21
    roychan  
       2017-02-28 22:46:57 +08:00
    Median of medians … O(n)
    neosfung
        22
    neosfung  
       2017-02-28 22:50:23 +08:00
    @danielmiao 不好意思,以为你是题主,我搞错了,回复的是题主的问题,不是你的问题。
    neosfung
        23
    neosfung  
       2017-02-28 22:54:31 +08:00   ❤️ 1
    @danielmiao 关于你这个问题,是肯定存在的。所以这个文章后面就提到了解决方法 “因此不能将数据随便均分到不同机子上,而是要根据 hash 后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。”
    ic2y
        24
    ic2y  
       2017-02-28 22:55:28 +08:00   ❤️ 1
    1 亿数字是 4GB 内存,可以直接加载进内存

    对 快速排序做点改动,就能实现。

    快排第一趟分治结束的时候,会以一个数字为轴,左边小于这个数字,右边大于这个数字,而且这个轴的下标是知道的。

    如果下标等于 5000w ,那就直接买命中,如果下标小于 5000w ,对右半部进行快排的第二趟快排。如果大于 5000w ,对左半部进行快排的第二趟。

    以此类推,得出 5000w 的是几。
    danielmiao
        25
    danielmiao  
       2017-02-28 23:16:41 +08:00
    @neosfung 感觉自己突然傻 B 了。。。。
    mystzain
        26
    mystzain  
       2017-03-01 01:25:09 +08:00
    先对前面 N 条数据采样,分析一下分部规律,然后决定一个策略,分成多个区间,然后从原始数据那边取值分拣到多个区间里面,统计各个区间内的条目数。决定对哪个区间进行进一步的分拣或者排序。这样行吗……?
    eyp82
        27
    eyp82  
       2017-03-01 03:59:03 +08:00   ❤️ 1
    建议别这么急着就解题, 要先问一下详细情况, 暂时想到一些:
    1. 数据类型
    2. 每条数据的长度范围, 长度分布情况(最好给个 histogram)
    3. 全部数据的排序情况, 是基本有序, 还是乱序
    4. 对性能 /延迟和资源占用的要求(性能高延迟低的, 资源占用可能会很大, 合理取舍)
    5. 内存大小(是否能全部加载到内存)
    6. 解决这个问题的时间要求.(要求在多长时间内搞定之类)
    7. 可能还要考虑这个算法的可靠性要求(比如要求可靠性几个 9)

    根据具体的情况, 才能选择合适的算法.

    这只是问题本身, 如果考虑的更全面一点, 在问上述的问题前后, 还要问的是具体的也无需求, 是否真的需要这个场景, 还是可以用逻辑上等价的其他成本更小的操作代替?
    mcfog
        28
    mcfog  
       2017-03-01 08:15:15 +08:00 via Android
    当年面试唯一答不出来的就是类似的排序算法变形题,面试官都想往我脸上甩堆排序三个大字了,我愣是想不起来只能疯狂聊如何优化快排…

    不管怎么说,只能想到先排完序的话,算法没学好(或者说学成背公式了)
    ghui
        29
    ghui  
       2017-03-01 08:20:57 +08:00 via iPhone
    m
    vanquish70
        30
    vanquish70  
       2017-03-01 08:35:38 +08:00
    二分法
    ljcarsenal
        31
    ljcarsenal  
       2017-03-01 11:44:50 +08:00 via Android
    mark
    wohenyingyu02
        32
    wohenyingyu02  
       2017-03-01 22:30:45 +08:00
    既然是无序数组,直接随便取一个在 iterator 中把它定义成第 5000w 个不就行了吗?谁规定必须要从第一个开始遍历?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   928 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 21:11 · PVG 05:11 · LAX 13:11 · JFK 16:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.