昨天遇到的面试题

[xingboss3]

从前有个国家，有1千万的子民，每个人都有一个唯一编码18位，随即生成的。
然后皇帝要建一个档案管理部门，让子民来存档案，取档案。
你是那部门负责人，部门里面有个机器，用来存数据的，机器里有5千万个箱子，每个箱子放一个信封，信封里是子民的信息，可以贴字条在信封上。
子民来只把唯一18位编码告诉工作人员，取的时候也是通过18位编码。
你要写手册给部门的工作人员，叫他们怎么把子民对应的信息的信封放到机器里。
如果做不出，皇帝砍你头。

[pengjiayou]

我是要被砍头的那位，我做不出，哈哈

[013231]

這不就是散列表麼.
信封上貼上編號, 放在第`編碼%5千萬`個箱子裏; 如果那個箱子已經有一個信封了就往依次後看, 找到了空箱子就放進去.
取信的時候到`編碼%5千萬`個箱子去區; 如果不在那個箱子就往後找.

[xingboss3]

@013231 我也差不多你这样想，说我死得很快。还装逼说条条大陆通罗马，不会计算机的也有可能想出来。

[21grams]

就按编码取呗，实在看不懂要干什么。

[xingboss3]

@21grams 他就这么问，说我不管你有多少经验，你做个什么项目，我就问你这个问题。尼玛的招IOS问这个问题。

[gucheen]

机器工作的原理貌似不知道。。。

[xingboss3]

@gucheen 就像ATM一样，输入，然后有个口，让你存信封，取信封。

[013231]

@xingboss3 既然這樣, '王侯將相, 寧有種乎?'

[y051313]

题目不严谨吧，是说取的时候只能一次？也就是说不能再箱子里面翻来翻去？

[alexrezit]

@xingboss3 求爆公司名.

[xingboss3]

@y051313 应该能，反正子民只是存取时报编码就可以了

[xingboss3]

@alexrezit 某刚创业两个月的打算做IOS社交应用的公司，目测只有一台mac，其他都是x86

[chendeshen]

这题算是考数据结构,再套上一些故事情节而已.IOS考这个绝对是必要+出题出得好.
考得就是Hash(哈希表)的实现原理之一...答案貌似是 @013231 所说的±...本人小白路过...

[blacktulip]

话说虽然有5kw个箱子，我只用前1kw个不行么？

[ichigo]

哈希表+1

[013231]

@blacktulip 這樣不大好. 只用前一千萬個, 想必你是準備按18位編碼順序存放, 然後二分搜索來查找位置?
這就有兩個問題:
1. 查找信封的速度是O(log n), 而散列表是O(1).
2. 一旦有新人加入, 平均需要移動五百萬個信封.

[iYu]

数组+1 编程珠玑 第一篇 O(1)

[soarscnu]

把十八位编码和五千万个箱子各平均分为五部分，即一千万个箱子对应十八位编码的一部分。工作人员拿到十八位编码就到对应的部分第“十八位编码%1Kw”个箱子查找。若有多个信封对应一个箱子，则对应编号箱子放第一个对应的信封，再加一张字条，字条写明其它对应的信封放哪个编号箱子里。

[Veelian]

大家是不是想太多了，人家说了「不会计算机的也有可能想出来」，逛超市存包时柜子吐出一个条形码。。。

[dhysum]

最简单有效的应该还是树形结构

[yueq]

this is hash bucket...