一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 180|回复: 7
收起左侧

发帖问个onsite的面试题

[复制链接] |试试Instant~ |关注本帖
Andrew007 发表于 2015-11-17 06:44:05 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@ - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天面试当地的一中型公司,最后给了个附加题,最后时间很赶,没打出来,现在也没想出来好办法。

题目大意:
一国王有1000瓶酒,其中有一瓶被下了毒,这种毒喝了之后30天才有效果。但是这个国王第31天的时候需要开个party,需要999瓶酒。可以从监狱里选10个犯人出来试酒,好像说最多只需要9个人就可以试出来。
还给了个提示,说如果超过1024瓶酒,就需要10个人来试。请问方法?

gorilazz 发表于 2015-11-17 06:57:53 | 显示全部楼层
10个人的解法:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2015-11-17 06:59):
把酒编号为1-1000,然后翻译成二进制,因为不超过1024,所以二进制最多10位。然后让第一个人喝所有第一位为1的酒,第二个人喝所有第二位为1的酒,依次类推。最后看哪几个人中毒了就可以知道毒酒编号里的哪几位是1
回复 支持 反对

使用道具 举报

lightmark 发表于 2015-11-17 07:00:46 | 显示全部楼层
binary search
回复 支持 反对

使用道具 举报

yongmat 发表于 2015-11-17 07:04:05 | 显示全部楼层
把每瓶酒编号,就有0到1000号酒。
然后把每瓶酒的编号化为10位的binary number,比如4号就是0000000100.
然后找10个犯人,每个人给一个杯子,准备往杯子里倒酒,(假设杯子足够大)每个人代表不同的二进制数位,从低到高为0到9.. 1point 3acres 璁哄潧
如果编号为n的酒化成binary code后,第m位是1,那么就往代表那个数位的囚犯杯子里到一点酒。
30天后,看看代表哪些数位的囚犯死了,并把那些死掉的囚犯所表示的位数置1,活着的置零,最后拼出的数,就是毒酒的编号。
回复 支持 反对

使用道具 举报

 楼主| Andrew007 发表于 2015-11-17 07:06:55 | 显示全部楼层
gorilazz 发表于 2015-11-17 06:57
10个人的解法:

补充内容 (2015-11-17 06:59):
. From 1point 3acres bbs
谢谢回复,可能是我理解的题意不对吗?因为一瓶毒酒,最后中毒的不是只有一个人吗?如果每个人都要尝多瓶酒的话,怎么知道哪一瓶有毒了?
回复 支持 反对

使用道具 举报

 楼主| Andrew007 发表于 2015-11-17 07:07:50 | 显示全部楼层

30天之后才有效果,所以没法二分吧。第31天的时候就需要酒了。
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-11-17 07:09:54 | 显示全部楼层
Andrew007 发表于 2015-11-17 07:06. more info on 1point3acres.com
谢谢回复,可能是我理解的题意不对吗?因为一瓶毒酒,最后中毒的不是只有一个人吗?如果每个人都要尝多瓶 ...
.1point3acres缃
比如毒酒编号的二进制表示是0010010011,那么10个人里,3,6,9,10号选手都会尝到这个酒,并且会中毒,而其他的选手不会喝到这个酒,所以不会中毒。用这个信息就可以重建出这个二进制编号了
回复 支持 反对

使用道具 举报

 楼主| Andrew007 发表于 2015-11-17 07:17:19 | 显示全部楼层
gorilazz 发表于 2015-11-17 07:09. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
比如毒酒编号的二进制表示是0010010011,那么10个人里,3,6,9,10号选手都会尝到这个酒,并且会中毒,而其 ...

懂了,太牛了,佩服。完全没想到。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 00:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表