一.

有15个瓶子，其中最多有一瓶有毒，现在有四只老鼠，喝了有毒的水之后，第二天就会死。如何在第二天就可以判断出哪个瓶子有毒。

解答:

四只老鼠，用二进制可以给瓶子编码0001 - 1111；

具体操作:

image.png

这里我们将水瓶依次编号为1 - 15， 老鼠依次编号为1 - 4；每只老鼠分别喝下对应二进制位为1的水，最后根据老鼠的死亡情况，可以定位到哪一瓶水有毒。

比如说老鼠3和老鼠4都死了，就证明是第3瓶水有毒。

二.

六个海盗抢到共计100个宝石，现在由第一个海盗开始轮流提出分赃计划，只要同意计划的人不超过一半，提出计划的海盗会被处死，然后下个人继续提出计划。如果海盗无法获得认可的最大利益，那么一定会投反对。请问第一个海盗如何提出分赃计划，保证自己的利益最大化并且不死？

解:逆向推导题目:以最小的支出争取可以争取的人。

2人：                   【0 - 100】
3人：                【99 - 1 - 0】
4人：          【97 - 0 - 2 - 1】
5人：     【97 - 0 - 1 - 0 - 2】
6人：【96 - 0 - 1 - 2 - 1 - 0】

• 当只剩下2个海盗，海盗1和海盗2，由海盗1来提出分赃计划，海盗1只能是自己得0个金币，海盗2分得100金币，这样才能保证自己不会被处死。

• 当只剩下3个海盗，海盗1、海盗2、海盗3，由海盗1来提出分赃计划，海盗1给出的分赃计划是海盗1为99金币，海盗2位1金币，海盗3为0金币，这个计划海盗1和海盗2肯定同意，超过一半，海盗2之所以会同意是因为当只剩下海盗2和海盗3的时候，海盗2来提出分赃计划，海盗2一个金币都没有，所以海盗2会同意这个计划。

• 当只剩下4个海盗，海盗1、海盗2、海盗3、海盗4，由海盗1来提出分赃计划，海盗1提出的分赃计划是海盗1为97金币，海盗2为0金币，海盗3为2金币，海盗4为1金币，之所以这么分配是依据只有3个海盗的情况来判断，对于海盗2来说，如果只有3个海盗，他可以分得99个金币，所以干脆给他0个金币；海盗3，如果只有3个海盗可以分得1个金币，所以给他2个金币，海盗2肯定同意，海盗4，如果只有3个海盗可以分得0个金币，所以给他1个金币，他也会同意。这样就会超过一半的人同意这个方案。

• 当只剩下5个海盗，海盗1提出的分赃计划是海盗1为97个金币，海盗2为0个金币，海盗3为1个金币，海盗4为0个金币，海盗5为2个金币，这样就能保证超过一半的人同意这个计划。

• 当只剩下6个海盗时，海盗1提出的分赃计划是海盗1为96个金币，海盗2为0个金币，海盗3为1个金币，海盗4为2个金币，海盗5为1个金币，这样就能保证超过一半的人同意这个计划。

三.

有100个人抢红包，每6个人可以成组领取共计3元红包，每个人限领3次，请问100个人最多可以领取多少钱？

解:
首先100个人中找出4个人，称作A4，其余96人组成16组领取红包。接着从96个人中找出4个，称作B4，A4和另外92个人组成16组领取红包。再从剩下92个人里面找出4人称作C4，A4+B4+88人组成16组领取。最后剩下领取了两次的A4、B4、C4一起组成两组，领取红包，每个人都领取三次，共计领取150元

四.

假设有10GB的订单数据，我们希望按照订单金额(假设金额都是正整数)进行排序，但是内存有限只有100M,没办法一次性将10GB的数据都加载到内存中，请问要怎么进行排序。

解:

• 先将10GB的数据，分成100份，每份100M，然后分段加载进内存，遍历统计订单金额所在范围，假设统计范围为0 - 10万之间，我们将所有的订单依据订单金额划分为100个桶，第一个桶的金额为0 - 1000元， 第二个桶是1001 - 2000元，以此类推，每个桶对应一个存储文件，并且按照金额范围大小顺序编号命名(00, 01, 02, ... 99);

• 然后再次分段遍历10GB的订单数据，将依据订单金额，将订单放入对应的桶中，然后存储到相应的磁盘上，如果订单金额分布比较均匀，那每个桶最终的订单大小差不多是100M左右，但也可能出现相差较大的现象，那就将桶中订单数据大小超过100M的继续在该桶金额范围内继续划分，直到每个桶的订单数据大小，小于100M。

• 然后依次加载每个桶的订单数据，依据订单金额，对数据从小到大进行排序。

五.

在一个文件中有 10G个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。

解:
思路: 一个整数占4个字节，每个字节是8位,将整形的每1位作为一个关键字，如果最高位值越大，整数越大，如果最高位相同再比较次高位。整个比较过程类似于字符串的字典排序。

• 将10G整数分成5次，每次2G读入内存，然后遍历读入内存的数据，对每个数据利用位运算取出最高的8位(24 - 31)，这8bit最多可以表示255个桶，因此依据最高8bit的值，将整数放入对应的桶中。最后把每个桶写入磁盘中，同时在统计每个桶中的整数数量，并存储。

• 依据内存中统计的每个桶的整数数量，计算中位数在哪个桶中，然后对这个桶进行排序，取出中位数的值。

• 如果中位数所处的桶的大小超过2G，那么就对这个桶里面的数据依据次高8位继续进行划分(16- 23),并统计各个桶中的数量，然后依据之前算成来的桶的数量进行计算，算成中位数处于哪个桶，并对该桶进行排序，取出中位数。

六.

假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？

解:

• 遍历10万条数据，以URL作为Key，访问次数作为Value,存入散列表，同时记录下访问次数的最大值k,时间复杂度O(N);

• 如果K不是很大，可以使用桶排序，时间复杂度是O(N),如果K非常大，就使用快速排序，时间复杂度为O(nlogn);

七.

有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串。

• 以第一个字符串数组构建HashSet，key为字符串,再遍历第二个字符串数组，以字符串为key在HashSet查找，如果包含就说明存在与该字符相同的字符串，添加到相同列表里面。

八.

假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务(比如发布职位)来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这10万个猎头ID和积分信息，让它支持如下操作:

• 根据猎头的ID快速查找、删除、更新这个猎头的积分信息。

• 查找积分在某个区间的猎头ID列表;

• 查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。

解:

• 以猎头ID构建一个散列表，以积分排序构建一个跳表

• ID在散列表中所以可以O(1)查找到这个猎头

• 积分以跳表存储，跳表支持区间查询

九.

区块链使用的是哪种哈希算法吗？是为了解决什么问题而使用的呢？

解:

• 区块链是一块块区块组成的，每个区块分为两部分:区块头和区块体。

• 区块头保存着自己的区块体和上一个区块头的哈希值

• 因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。

• 区块链使用的是SHA256哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算后面所有区块的哈希值，短时间几乎不可能做到。