作者bleed1979 (十三)
看板Soft_Job
标题[讨论] Google面试问题
时间Sat Apr 12 02:07:46 2014
问题：
假设你有两颗蛋，然後有一栋100层楼高的大楼。
而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
有的可能很脆弱，一楼就可以摔破。
现在你只知道这这两颗蛋是完全相同的，
你想要知道蛋最高从哪一层楼摔下来不会摔破。
问题是：你要摔几次才能计算出来？
（如果你低於高度摔下蛋，蛋就没事，如果高於那个楼层，蛋就完蛋）
在这过程你可以摔破蛋。
--- 以下是完全不经大脑思考的 rough 策略，有雷 ---
http://ideone.com/B7E85H
策略是：
当我还有两次机会时，我使用二分法。
当我只剩一次机会时，选择已经安全的楼层 + 1。
附上此策略的解答 楼层 => 次数
1=>3
2=>4
3=>5
4=>6
5=>7
6=>8
7=>9
8=>10
9=>11
10=>12
11=>13
12=>14
13=>15
14=>16
15=>17
16=>18
17=>19
18=>20
19=>21
20=>22
21=>23
22=>24
23=>25
24=>26
25=>27
26=>28
27=>29
28=>30
29=>31
30=>32
31=>33
32=>34
33=>35
34=>36
35=>37
36=>38
37=>39
38=>40
39=>41
40=>42
41=>43
42=>44
43=>45
44=>46
45=>47
46=>48
47=>49
48=>50
49=>50
50=>3
51=>4
52=>5
53=>6
54=>7
55=>8
56=>9
57=>10
58=>11
59=>12
60=>13
61=>14
62=>15
63=>16
64=>17
65=>18
66=>19
67=>20
68=>21
69=>22
70=>23
71=>24
72=>25
73=>26
74=>26
75=>4
76=>5
77=>6
78=>7
79=>8
80=>9
81=>10
82=>11
83=>12
84=>13
85=>14
86=>15
87=>15
88=>5
89=>6
90=>7
91=>8
92=>9
93=>9
94=>6
95=>7
96=>7
97=>7
98=>7
99=>7
100=>7
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.203.156
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1397239669.A.7EE.html
1F：推 PasserDin:有点像资料结构中 讨论排顺序的感觉@@ 04/12 02:26
2F：→ lovdkkkk:2 颗时十层试一次, 一颗时每次加一层, 最多不超过 19 次 04/12 02:56
3F：→ lovdkkkk:以上是想了二分钟的想法 04/12 02:57
4F：推 sealer:最多14次? 04/12 03:02
5F：→ sealer:第一次从14层丢，没破就+13，没破再+12...依此递减 04/12 03:04
6F：→ sealer:中间如果一颗破了剩下那颗每次加一层 04/12 03:05
7F：推 lovdkkkk:推楼上, (我猜)重点是最佳化 worst case, best case 没差 04/12 03:17
8F：推 GX90160SS:sealer答案目前看来最好 04/12 03:24
9F：推 SheLoBDenI:直接从50楼丢，破了再从25，没破从75。这样呢？ 04/12 07:56
10F：推 SheLoBDenI:我蠢了... 04/12 08:00
11F：推 duck10704:为什麽是从14层开始丢压 @@ 04/12 10:00
12F：→ y3k:我有个笨问题 不是说只有两颗蛋吗.... 04/12 10:08
13F：→ y3k:当我没问 看错了XDDD 04/12 10:09
14F：推 YahooTaiwan:to y3k: 蛋砸了不一定会破阿 04/12 10:10
15F：→ YahooTaiwan:慢了一步 当我没回答 04/12 10:10
16F：→ y3k:XD楼上 04/12 10:22
18F：→ y3k:我的作法会同sealer 不过我第二颗是+2上去 因为你不用留蛋XD 04/12 10:33
19F：→ y3k:恩....?好像也不对 那sealer大的解应该是最好了吧@@ 04/12 10:34
20F：推 kkkmode:那可以讨论好解答再去google面试吗XD 04/12 10:39
21F：→ Lordaeron:第一颗从50楼丢下,破了, 就从1测到49,顶多50次 04/12 10:47
22F：→ Lordaeron:若没破,则再从75再测,破了就在51~74之间,没破就在 04/12 10:48
23F：→ Lordaeron:76~100之间, 再对半测,如此类推, 所以, 最多50次 04/12 10:48
24F：→ Lordaeron:最少就是100层才破的, 共6 次 04/12 10:51
25F：推 jej:这不就统计的负二项 懂点统计去面试google会不会变得很容易? 04/12 11:06
26F：→ x000032001:那如果1F摔一次没破 摔一万次破了呢 04/12 15:15
27F：推 aby0d6q5n:不确定是不是我题目理解错误... 我一次摔会摔N,N+1楼 04/12 17:05
28F：→ aby0d6q5n:之後就是binary search? 04/12 17:06
29F：→ michaelz:这是好多年的老题了 04/12 19:18
30F：推 usoko:推sealer 04/13 16:22
31F：推 chatnoir:其实我一直很好奇这类的问题要怎麽去练,念数学?资结? 04/14 00:45
32F：推 bobju:这类问题若要[练]的话 找本题库拼命[练]就对了 会有效果 04/14 08:30
33F：→ bobju:但若要入门的话 还是得修些离散数学 演算法之类的课程 至少 04/14 08:31
34F：→ bobju:知道资讯科学方面的知识是如何用数学以及符号来表达 04/14 08:32
35F：推 amozartea:Binary search? 04/20 16:06
36F：推 heerowei0802:sealer法不完全,一旦破了没必要1层1测,每次+2测即可 04/22 14:02
37F：推 heerowei0802:仔细想想没法每次+2丢...sorry~ 04/22 15:05
38F：推 orange7986:推sealer大 05/06 20:58