39

那些经典的编程面试问题之一......

给你两颗弹珠,并告诉它们从某个特定高度掉落时会破裂(如果从该高度以下掉落,可能不会受到损坏)。然后你被带到一栋 100 层的建筑物(大概高于特定高度),并被要求找到你可以在不破坏大理石的情况下掉落的最高楼层。

额外信息

  • 您必须找到正确的楼层(不是可能的范围)
  • 弹珠都保证在同一楼层破裂
  • 假设您更换地板的时间为零——仅计算大理石滴的数量
  • 假设正确的楼层随机分布在建筑物中
4

10 回答 10

54

这里有趣的事情是你如何以尽可能少的滴数做到这一点。如果突破层是第 49 层,去第 50 层并掉第一个将是灾难性的,导致我们不得不进行 50 次下降。我们应该在第 n 层丢下第一个弹珠,其中 n 是所需的最大下落量。如果大理石在第 n 层破裂,我们可能必须在那之后滴下 n-1 次。如果弹珠没有破碎,我们就上到 2n-1 层,如果它在这里破碎,我们必须在最坏的情况下丢下第二颗弹珠 n-2 次。我们继续这样直到第 100 层,并尝试在 3n-2、4n-3....
和 n+(n-1)+(n-2)+...1 <=100
n=14处打破它是否需要最大滴数

于 2008-08-09T02:45:43.070 回答
15

这个问题在《 Cracking the Coding Interview (5th) 》一书中的问题 6.5 中有介绍,解决方案总结如下:

观察:

无论我们如何删除 Marble1,Marble2 都必须进行线性搜索。例如,如果 Marble1 在 10 层和 15 层之间断裂,我们必须用 Marble2 检查中间的每一层


该方法:

第一次尝试:假设我们从 10 楼掉落大理石,然后从 20 楼……</p>

  • 在第一滴(10 楼)的第一个 Marble 破裂中,我们最多总共有 10 滴。
  • 如果第一个 Marble 在最后一滴(100 层)破裂,那么我们最多总共有 19 滴(1 到 100 层,然后是 91 到 99 层)。
  • 这很好,但我们所考虑的只是绝对最坏的情况。我们应该做一些“负载平衡”以使这两种情况更加均匀。

目标: 创建一个掉落 Marble1 的系统,这样无论 Marble1 是在第一次掉落还是在最后一次掉落时破裂,所需的最多掉落次数都是一致的。

  1. 一个完美的负载平衡系统将是一个 Marble1 的 Drops of Marble2 + Drops of Marble2 始终相同的系统,无论 Marble1 在哪里损坏。
  2. 在这种情况下,由于 Marble1 的每一滴都会多走一步,因此 Marble2 可以少走一步。
  3. 因此,我们必须每次将 Marble2 可能需要的步骤数减少一​​滴。例如,如果 Marble1 掉落在 20 楼然后是 30 楼,则 Marble2 可能需要走 9 步。当我们再次放下 Marble1 时,我们必须将可能的 Marble2 步骤减少到只有 8 个。例如,我们必须在 39 楼放下 Marble1。
  4. 因此,我们知道,Marble1 必须从 X 层开始,然后向上 X-1 层,然后 X-2,……,直到达到 100。
  5. 求解 X+(X-1)+(X-2)+…+1 = 100。X(X+1)/2 = 100 -> X = 14

我们去 14 楼,然后是 27 楼,然后是 39 楼……这最多需要 14 步。


代码和扩展:

于 2014-01-15T09:32:13.247 回答
2

它们在从相同高度掉落时都会断裂,还是它们不同?

如果它们相同,我会去 50 楼丢下第一个弹珠。如果它没有破裂,我会去 75 楼做同样的事情,只要它没有破裂,我就会继续上升 50% 的剩余空间。当它真的破裂时,我会回到比之前高的地方(所以如果它在 75 楼破裂,我会回到 51 楼)并放下第二块大理石并一次向上移动一层直到它破裂,在这一点上,我知道我可以从没有大理石破损的最高楼层跌落。

可能不是最好的答案,我很好奇其他人如何回答。

于 2008-08-09T02:29:48.110 回答
2

我认为真正的问题是你想要答案有多准确。因为您的效率将真正取决于此。

如果你想要 100% 的弹珠准确率,我会同意贾斯汀的观点,那么一旦第一个弹珠破裂,你就必须从最后一个已知的“好”楼层一次上一层,直到你找出哪一层是赢家。” 甚至可以输入一些统计数据并从 25 楼而不是 50 楼开始,这样最坏的情况是 24 楼而不是 49 楼。

如果您的答案可以加或减一两层楼,那么可能会有一些优化。

其次,上下楼梯会影响你的效率吗?在这种情况下,每次上/下行程时总是放下两个弹珠并捡起两个弹珠。

于 2008-08-09T02:40:56.653 回答
2

在第 10、20、30 层等处丢下第一个弹珠,直到它破裂,然后跳回最后一个已知的地板,并开始一次一层地从那里丢下弹珠。最坏的情况是 99 是魔术地板,你总能在 19 滴或更少的时间内找到它。

于 2008-08-09T14:46:21.137 回答
1

我个人不是很喜欢这样的谜题,我更喜欢面试中的实际编程练习。

也就是说,首先这取决于我是否能从我将它们扔到的地板上判断它们是否坏了。我会假设我可以。

我会上二楼,丢下第一块大理石。如果它坏了我会尝试一楼。如果它坏了,我会知道它没有地板。

如果第一个没有坏,我会去四楼从那里掉下来。如果它坏了,我会回去拿另一块大理石,然后掉到 3 楼,不管坏与否,我会知道哪个是极限。

如果两个都没有坏,我会去拿两个,做同样的过程,这次从 6 楼开始。

这样,我可以跳过每隔一层,直到我得到一个打破的大理石。

如果大理石早早破裂,这将进行优化......我想可能有一个最佳数量的楼层我可以跳过以获得最大的每次跳过......但是如果一个打破,我将不得不单独检查每一层从最后一个已知楼层上方的一楼......如果我跳过太多楼层当然会很痛苦(对不起,现在不打算找出最佳解决方案)。

理想情况下,我想要一整袋弹珠,然后我可以使用二分搜索算法并将每一滴的楼层数分成两半……但是,这不是问题,是吗?

于 2008-08-09T02:37:41.760 回答
1

如果您想要一个可以为您提供 N 层结果的通用解决方案(在您的情况下为 N=100),那么您只需求解二次方程$x^2+x-2\cdot(N-1)=0$和结果是正根的上限

这是:

$$f(N)=天花板\bigg(\frac{-1+\sqrt{1+4\cdot2\cdot(N-1))}}{2}\bigg)$$

于 2019-03-27T10:48:17.580 回答
0

从 3 楼掉落第一块大理石。如果它坏了,你知道它是 1 楼或 2 楼,所以从 2 楼扔下另一个大理石。如果它没有坏,你发现 2 楼是最高的。如果它确实坏了,你会发现 1 楼是最高的。2滴。

如果从 3 楼掉下来没有破坏大理石,从 6 楼掉下来。如果它坏了,你知道 4 楼或 5 楼是最高的。从 5 楼丢下第二颗弹珠。如果它没有碎,你会发现 5 是最高的。如果是这样,4楼是最高的。4滴。

继续。

3 层 - 最多 2 滴

6 层 - 最多 4 滴

9 层 - 最多 6 滴

12 层 - 最多 8 滴

等等

3x 楼层 - 最多 2x 掉落

因此,对于一栋 99 层的建筑物,您最多可以有 66 滴。这是最大值。你的滴数可能会比这少。哦,66 也是 100 层建筑的最大值。如果休息地板是 98 或 97 楼,你只需要 66 滴。如果休息地板是 100,你会使用 34 滴。

即使你说没关系,这可能需要最少的步行量,而且你不必知道建筑物有多高。

部分问题在于您如何定义效率。总是在少于 x 滴的时间内得到解决方案是否更“有效”,或者在 y < x 的情况下有很好的机会在 y 滴中获得解决方案是否更有效,但需要注意的是,您可能有超过 x 滴?

于 2008-08-09T06:50:10.300 回答
-1

只需 7 个弹珠就可以做得更好。

所以按照投票的答案,说大理石至少打破了 49 楼。

  1. 50 楼 -> 休息(答案在 1 到 50 之间)
  2. 25 楼 -> 不破(26 到 50)
  3. 37 楼 -> 不破(38 到 50)
  4. 43 楼 -> 不坏(44 到 50)
  5. 46 楼 -> 不破(47 到 50)
  6. 48 楼 -> 不破(49 或 50)
  7. 49楼->休息(49楼,这一步实际上是需要的,因为它可能是大理石破裂的最低楼层在50楼)

这可以想象为在一个排序集中对某个 k 进行二分搜索,每次尝试我们将解决方案空间减半。对于 100 层,我们需要 log2 100 = 6.644(7 次尝试)。使用 7 块大理石,我们可以确定哪一层是大理石可以分解到 128 层的最低楼层。

于 2014-07-20T14:34:34.373 回答
-3

我要做的第一件事是使用从 1 楼开始的死简单算法,一次将大理石掉落一层,直到达到 100 或大理石破裂。

然后我会问我为什么要花时间优化它,直到有人能证明这将是一个问题。很多时候,当一个更简单的算法可以解决问题时,人们就会全神贯注于寻找完美的复杂算法。换句话说,在需要之前不要优化事物。

这可能是一个棘手的问题,看看你是否是那些能从鼹鼠山上造出一座山的人之一。

于 2008-09-25T15:42:09.657 回答