两个大理石和一个100层的建筑

Question

其中一个经典的编程面试问题......

给你两个大理石，并告诉他们从某个高度下降时会破裂（如果从那个高度以下掉落，可能不会受到伤害）。然后你被带到一座100层高的建筑物（大概高于一定的高度），并要求找到最高的楼层，你可以尽可能高效地将大理石从大脑中摔下来。

额外信息

• 你必须找到正确的楼层（不是可能的范围）
• 大理石都保证在同一层楼打破
• 假设您需要零时间更换地板 - 只计算大理石滴的数量
• 假设正确的楼层随机分布在建筑物中

Answer 1

这里有趣的是你如何以尽可能少的跌落来做到这一点。如果破土动工是第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是否需要最大滴数

Answer 2

书“Cracking the Coding Interview (5th)”的问题6.5中介绍了这个问题，解决方案总结如下：

观察：

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

---

该方法：

第一次尝试：假设我们从10楼掉落大理石，然后是20号，......

• 在第一次大理石破碎（第10层），然后我们总共最多10滴。
• 如果第一个大理石在最后一滴（100楼）上断裂，那么我们总共最多有19滴（楼层1到100，然后是91到99）。
• 这很不错，但我们所考虑的只是最糟糕的情况。我们应该做一些“负载平衡”来使这两个案例更加均衡。

目标：创建一个用于删除Marble1的系统，以便所需的最多滴数是一致的，无论Marble1是在第一滴还是最后一滴上断开。

1. 一个完美的负载平衡系统将是一个大理石1滴+大理石滴2总是相同的，无论Marble1在哪里破碎。
2. 对于那种情况，由于每一滴Marble1需要多一步，因此Marble2允许少一步。
3. 因此，我们必须每次将Marble2可能需要的步骤减少一滴。例如，如果Marble1掉落在20楼，然后是30楼，则Marble2可能需要9步。当我们再次放弃Marble1时，我们必须将Marble2的潜在步骤减少到8.例如，我们必须将Marble1放在39楼。
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步。

---

代码和扩展：

• 对于代码实现，您可以查看here。
• 对于扩展到qazxsw poi弹珠，qazxsw poi地板，结帐qazxsw poi。

Answer 3

它们在从同一高度落下时会断裂，还是不同？

如果他们是一样的话，我会去50楼放下第一块大理石。如果没有破坏，我会去75楼并做同样的事情，只要它不断，我继续上升50％左右。当它确实破裂时，我会回到比我之前更高的地方（所以如果它在75楼破裂我会回到第51层）然后放下第二块大理石并一次向上移动一层直到它破裂，在这一点上，我知道我可以从没有大理石破损的最高层落下。

可能不是最好的答案，我很想知道别人怎么回答。

Answer 4

将第一块大理石放在地板10,20,30等处，直到它破裂，然后跳回到最后一个已知的好地板，并开始一次从一层楼落下大理石。最糟糕的情况是99是Magic Floor，你可以在19滴或更少的时间内找到它。

Answer 5

我个人不是很喜欢这样的拼图问题，我更喜欢采访中的实际编程练习。

那就是说，首先它取决于我是否可以判断他们是否在地板上被打破了我正在放弃它们。我会认为我可以。

我会去二楼，放下第一块大理石。如果它坏了我会试试一楼。如果那件坏事我会知道它不是地板。

如果第一次没有破坏，我会去4楼从那里掉下来。如果那个坏了，我会回去买另一块大理石，然后掉到3楼，打破与否我会知道哪个是限制。

如果两个都没有打破，我会去两个，并做同样的过程，这次从6楼开始。

这样，我可以跳过其他所有楼层，直到我得到一个破碎的大理石。

如果大理石早期破裂，这将被优化...我想可能有一个最佳的楼层数量我可以跳过以获得最大的每个跳过...但如果一个休息，我将不得不单独检查每个楼层从最后一层楼上方的一楼开始......如果我跳过太多楼层当然会很痛苦（对不起，现在不想找出最佳解决方案）。

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

Answer 6

我认为真正的问题是你想要答案的准确程度。因为你的效率真的取决于那个。

我要同意贾斯汀，如果你想要大理石的100％准确性，那么一旦第一块大理石破坏你必须从最后一个已知的“好”地板一次上升到1层，直到你发现哪个楼层是获胜者，冠军。”甚至可能会输入一些统计数据并从25楼而不是50楼开始，这样你最糟糕的情况就是24而不是49。

如果您的回答可以加上或减去一两层，那么可能会有一些优化。

其次，走上楼梯/走楼梯是否会影响您的效率？在这种情况下，总是丢弃两个弹珠并在每次上/下行程中拾取两个弹珠。

Answer 7

从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 y的解决方案，其中y <x，但需要注意的是x可能超过x滴？

Answer 8

只需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层的最小楼层。

Answer 9

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

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

这可能是一个棘手的问题，看你是否是那些可以在鼹鼠山上建造一座山的人之一。