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

昨天遇到的面试题

  •  
  •   xingboss3 · 2012-11-08 11:42:12 +08:00 · 4407 次点击
    这是一个创建于 4399 天前的主题,其中的信息可能已经有所发展或是发生改变。
    从前有个国家,有1千万的子民,每个人都有一个唯一编码18位,随即生成的。
    然后皇帝要建一个档案管理部门,让子民来存档案,取档案。
    你是那部门负责人,部门里面有个机器,用来存数据的,机器里有5千万个箱子,每个箱子放一个信封,信封里是子民的信息,可以贴字条在信封上。
    子民来只把唯一18位编码告诉工作人员,取的时候也是通过18位编码。
    你要写手册给部门的工作人员,叫他们怎么把子民对应的信息的信封放到机器里。
    如果做不出,皇帝砍你头。
    21 条回复    1970-01-01 08:00:00 +08:00
    pengjiayou
        1
    pengjiayou  
       2012-11-08 12:35:34 +08:00
    我是要被砍头的那位,我做不出,哈哈
    013231
        2
    013231  
       2012-11-08 12:46:30 +08:00
    這不就是散列表麼.
    信封上貼上編號, 放在第`編碼%5千萬`個箱子裏; 如果那個箱子已經有一個信封了就往依次後看, 找到了空箱子就放進去.
    取信的時候到`編碼%5千萬`個箱子去區; 如果不在那個箱子就往後找.
    xingboss3
        3
    xingboss3  
    OP
       2012-11-08 14:11:23 +08:00
    @013231 我也差不多你这样想,说我死得很快。还装逼说条条大陆通罗马,不会计算机的也有可能想出来。
    21grams
        4
    21grams  
       2012-11-08 14:16:11 +08:00
    就按编码取呗,实在看不懂要干什么。
    xingboss3
        5
    xingboss3  
    OP
       2012-11-08 14:19:19 +08:00
    @21grams 他就这么问,说我不管你有多少经验,你做个什么项目,我就问你这个问题。尼玛的招IOS问这个问题。
    gucheen
        6
    gucheen  
       2012-11-08 14:19:51 +08:00
    机器工作的原理貌似不知道。。。
    xingboss3
        7
    xingboss3  
    OP
       2012-11-08 14:22:31 +08:00
    @gucheen 就像ATM一样,输入,然后有个口,让你存信封,取信封。
    013231
        8
    013231  
       2012-11-08 14:26:57 +08:00   ❤️ 1
    @xingboss3 既然這樣, '王侯將相, 寧有種乎?'
    y051313
        9
    y051313  
       2012-11-08 15:00:19 +08:00
    题目不严谨吧,是说取的时候只能一次?也就是说不能再箱子里面翻来翻去?
    alexrezit
        10
    alexrezit  
       2012-11-08 15:05:51 +08:00
    @xingboss3 求爆公司名.
    xingboss3
        11
    xingboss3  
    OP
       2012-11-08 18:35:08 +08:00
    @y051313 应该能,反正子民只是存取时报编码就可以了
    xingboss3
        12
    xingboss3  
    OP
       2012-11-08 18:36:27 +08:00
    @alexrezit 某刚创业两个月的打算做IOS社交应用的公司,目测只有一台mac,其他都是x86
    chendeshen
        13
    chendeshen  
       2012-11-08 20:14:46 +08:00
    这题算是考数据结构,再套上一些故事情节而已.IOS考这个绝对是必要+出题出得好.
    考得就是Hash(哈希表)的实现原理之一...答案貌似是 @013231 所说的±...本人小白路过...
    blacktulip
        14
    blacktulip  
       2012-11-08 20:18:04 +08:00
    话说虽然有5kw个箱子,我只用前1kw个不行么?
    ichigo
        15
    ichigo  
       2012-11-08 20:35:47 +08:00
    哈希表+1
    013231
        16
    013231  
       2012-11-08 21:08:22 +08:00
    @blacktulip 這樣不大好. 只用前一千萬個, 想必你是準備按18位編碼順序存放, 然後二分搜索來查找位置?
    這就有兩個問題:
    1. 查找信封的速度是O(log n), 而散列表是O(1).
    2. 一旦有新人加入, 平均需要移動五百萬個信封.
    iYu
        17
    iYu  
       2012-11-08 21:25:02 +08:00
    数组+1 编程珠玑 第一篇 O(1)
    soarscnu
        18
    soarscnu  
       2012-11-08 22:02:24 +08:00
    把十八位编码和五千万个箱子各平均分为五部分,即一千万个箱子对应十八位编码的一部分。工作人员拿到十八位编码就到对应的部分第“十八位编码%1Kw”个箱子查找。若有多个信封对应一个箱子,则对应编号箱子放第一个对应的信封,再加一张字条,字条写明其它对应的信封放哪个编号箱子里。
    Veelian
        19
    Veelian  
       2012-11-08 23:32:19 +08:00
    大家是不是想太多了,人家说了「不会计算机的也有可能想出来」,逛超市存包时柜子吐出一个条形码。。。
    dhysum
        20
    dhysum  
       2012-11-09 01:48:27 +08:00
    最简单有效的应该还是树形结构
    yueq
        21
    yueq  
       2012-11-09 02:36:49 +08:00
    this is hash bucket...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3606 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 00:57 · PVG 08:57 · LAX 16:57 · JFK 19:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.