V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wind3110991
V2EX  ›  C

问一个腾讯的算法题:有一个 vector 容器中,存有 1 亿个 qq 号(不重复),如何快速挑选出其中奇数号码?

  •  1
     
  •   wind3110991 · 2015-04-07 22:22:37 +08:00 · 5391 次点击
    这是一个创建于 3507 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题,今年春季的笔试题,不知道腾讯想表达什么意思,自己不是很精通STL。
    感觉直接遍历一遍然后考察vector[i]>>1;
    如果奇数就提出来,算法开销O(n),不知道是不是有什么更好的方法?
    大神勿喷,这题有没有必要用hash?

    48 条回复    2015-04-30 23:03:05 +08:00
    jiang42
        1
    jiang42  
       2015-04-07 22:54:56 +08:00
    听说腾讯有让做fib53的,我觉得。。。这题O(n)算法就行了?
    vibbow
        2
    vibbow  
       2015-04-07 23:31:57 +08:00
    直接循环一遍,在内存里判断QQ号最后一位二进制是不是1?
    wind3110991
        3
    wind3110991  
    OP
       2015-04-07 23:36:31 +08:00
    @vibbow 我也觉得。。不知道他要表达什么了
    wind3110991
        4
    wind3110991  
    OP
       2015-04-07 23:36:55 +08:00
    @jiang42 fib53?斐波那契?
    xvsfezz
        5
    xvsfezz  
       2015-04-07 23:45:57 +08:00
    内存够不够。。
    wy315700
        6
    wy315700  
       2015-04-08 00:02:27 +08:00
    是不是不允许copy
    wind3110991
        7
    wind3110991  
    OP
       2015-04-08 00:08:17 +08:00
    @xvsfezz 假如不够呢,是不是hash到n个文件里?
    HanSonJ
        8
    HanSonJ  
       2015-04-08 00:12:09 +08:00 via Android
    明天面试楼主才来问之前的问题…
    wind3110991
        9
    wind3110991  
    OP
       2015-04-08 00:18:59 +08:00
    @HanSonJ 今天看大数据时突然想起没有比较好的解决方案,身边同学也觉得题有问题,就搁浅了,你觉得怎么解决?
    wind3110991
        10
    wind3110991  
    OP
       2015-04-08 00:19:38 +08:00
    @wy315700 好像没提到
    HanSonJ
        11
    HanSonJ  
       2015-04-08 00:21:37 +08:00 via Android
    @wind3110991 我是战斗力只有5的渣
    spacewander
        12
    spacewander  
       2015-04-08 00:27:24 +08:00   ❤️ 1
    count += (v[i] & 1);
    类似这样?
    没用无重复的条件,但是O(n)加较小的常数因子,感觉没有比它更快了
    再快就只能用并行算法了……
    acros
        13
    acros  
       2015-04-08 01:09:13 +08:00 via iPhone
    考内存管理的效率吗?
    qq号一亿个int,长度按4算,内存肯定不够一次载入。
    另外还有vector内部内存模型问题吧,我需要复习下.....
    acros
        14
    acros  
       2015-04-08 01:14:35 +08:00 via iPhone
    2了,现在qq号是11位以上了吧?存的string还是数值?
    jesse_luo
        15
    jesse_luo  
       2015-04-08 01:16:15 +08:00
    @acros QQ 号好像有11 位了? 所以按 64 位计算,8*100000000 Byte 约为 700 多 MB吧

    可能要考虑 QQ 号数据动态变化,能多次迅速计算?
    acros
        16
    acros  
       2015-04-08 01:24:39 +08:00 via iPhone
    @jesse_luo 怀疑int够不够....好像需要收集很多前置条件
    acros
        17
    acros  
       2015-04-08 01:27:34 +08:00 via iPhone
    @jesse_luo 估计考官第一条审批还是看有没区分64,32呢....
    jiang42
        18
    jiang42  
       2015-04-08 04:21:44 +08:00
    @wind3110991 对啊。。。
    NCE
        19
    NCE  
       2015-04-08 08:49:56 +08:00
    11wei % 2
    lucifer9
        20
    lucifer9  
       2015-04-08 09:15:30 +08:00   ❤️ 11
    给所有qq在线用户弹窗:
    今天是马化腾的生日,挑出以下所有的偶数号码并回复偶数号码的个数有机会点亮头像哦

    然后每个用户发10个号码,正好用上号码不重复的条件
    运气好的话一遍就出来结果了
    cheng007
        21
    cheng007  
       2015-04-08 09:17:30 +08:00
    有一个1亿的vector,说明内存不是问题,要拿出所有的奇数,必须完成一次遍历也就是O(n),这题目应该是考并发吧,开多个线程每个线程负责一个段数据。
    wibile
        22
    wibile  
       2015-04-08 09:20:06 +08:00
    @lucifer9 你是个人才!请收下我的膝盖。ps,运气不好咋办。。。
    zwzmzd
        23
    zwzmzd  
       2015-04-08 09:21:26 +08:00 via Android
    我记得题目是删除qq号

    不过意思一样,用remove_if,原理类似于partition
    sigarron
        24
    sigarron  
       2015-04-08 09:32:23 +08:00
    @spacewander 这哥们貌似对的,位运算总是最快的,但是vector的意义是啥呢?存储的是int64还是string呢?这些问题都值得考虑下。
    lucifer9
        25
    lucifer9  
       2015-04-08 09:49:39 +08:00
    @wibile 用户基数在那摆着呢,运气再不好也不至于需要1亿次吧
    xinyewdz
        26
    xinyewdz  
       2015-04-08 09:59:34 +08:00
    普通的qq号是9位,大概就是1亿个。这数组不是稀疏数组,遍历一遍标注每个数组(用0和1标注)。然后直接输出下标是奇数并且值是1的。
    ybh37
        27
    ybh37  
       2015-04-08 10:06:53 +08:00
    字符串和数字无所谓,只判断二进制的最后一位是不是0就可以了。
    imn1
        28
    imn1  
       2015-04-08 10:18:52 +08:00
    @ybh37 +1
    ugvfpdcuwfnh
        29
    ugvfpdcuwfnh  
       2015-04-08 12:30:02 +08:00
    拆半查找都可以吧,2的27次方大于一亿。

    前几次是外部排序,后面就是内部排序。
    lijinma
        30
    lijinma  
       2015-04-08 13:22:49 +08:00
    @ugvfpdcuwfnh 还要排序?排序那就更复杂了
    ugvfpdcuwfnh
        31
    ugvfpdcuwfnh  
       2015-04-08 13:56:29 +08:00
    @lijinma 不是排序,本身就是排好的,应该是外部查找和内部查找。
    ugvfpdcuwfnh
        32
    ugvfpdcuwfnh  
       2015-04-08 13:58:57 +08:00
    哎?我突然发现我没看清题目,是要选出奇数号,我以为是从一亿号里选出一个号。

    好吧,我楼上的回复都无视吧.....
    zcljy
        33
    zcljy  
       2015-04-08 14:01:26 +08:00
    @ybh37 re
    ether
        34
    ether  
       2015-04-08 14:14:05 +08:00
    map reduce!
    yuankui
        35
    yuankui  
       2015-04-08 14:27:35 +08:00
    把奇数插入到首部,吧偶数插入到尾部
    要取奇数的话,就循环从首部取完,直到遇到偶数...
    要取偶数的化,就循环从尾部取,直到遇到奇数...
    yuankui
        36
    yuankui  
       2015-04-08 14:41:34 +08:00
    我靠,如果有这种需求,为什么不用两个vector存储?
    yuankui
        37
    yuankui  
       2015-04-08 14:42:02 +08:00
    你可以直接跟面试官说,你们这个前提很没水平
    sage417
        38
    sage417  
       2015-04-08 16:10:23 +08:00
    我觉得考的是大数据,跟技术还是偶数没什么关系,应该是map-reduce
    sen506
        39
    sen506  
       2015-04-08 16:42:18 +08:00
    2个迭代器A B
    当当前数位奇数时*A++ = *B++;
    当当前数为偶数时++B;
    B到达容器结尾时结束;
    最后vector.erase(A, vector.end());

    应该就这样了吧。。
    laotaitai
        40
    laotaitai  
       2015-04-08 17:12:11 +08:00
    拿Python, 3秒就能把1亿个QQ遍历完
    also24
        41
    also24  
       2015-04-08 17:35:06 +08:00
    看到中间越看感觉越奇怪……
    返回头又看一遍才反应过来是 奇数 不是 质数 的我面壁去了……

    (:o 」∠)_
    quericy
        42
    quericy  
       2015-04-08 17:41:27 +08:00
    @lucifer9 然后有用户手滑的,有无聊随便选的,还有好奇心害死猫觉得有隐藏条件然后全点一遍的23333
    blank4me
        43
    blank4me  
       2015-04-09 09:45:50 +08:00
    @quericy 一组数据不要发给一个人撒。多发几个人看看,再判断是否相信他们的结果。就和reCAPTCHA一样。
    luoqeng
        44
    luoqeng  
       2015-04-18 00:09:55 +08:00
    khan
        45
    khan  
       2015-04-28 09:36:12 +08:00
    判断低 bit位是否为1
    khan
        46
    khan  
       2015-04-28 11:00:02 +08:00
    8byte int_64 * 100,000,000L 需内存约 100M

    位运算 比 / %都要省 cpu, 剩下的内存问题可以多段分块加载
    khan
        47
    khan  
       2015-04-28 11:08:00 +08:00   ❤️ 1
    体死早. 800M 内存 换成字符串大概不过2G, 加上指针 和 字符串本身内存, 分块处理 合并不可少
    wind3110991
        48
    wind3110991  
    OP
       2015-04-30 23:03:05 +08:00
    @khan 谢谢你的解答!我再想想,有点不理解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1037 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 20:22 · PVG 04:22 · LAX 12:22 · JFK 15:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.