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

我们将获得两把弹珠，并告诉它们从某个高度掉落时它们会破裂(如果从该高度以下掉落，可能不会受到任何损坏)。然后，我们被带到一幢100层高的建筑(可能高于特定高度)，并要求找到可以从中掉落大理石的最高楼层，而又不能使其尽可能高效地折断。

额外信息

• 我们必须找到正确的楼层(不可能的范围)
• 弹珠均保证在同一楼层破裂
• 假设我们更换地板只需要零时间-仅计算大理石滴数
• 假设正确的楼层随机分布在建筑物中

解决方案

回答

当它们从相同高度掉落时，它们各自会断裂，或者它们是否不同？

如果它们相同，我将转到50层并放下第一个大理石。如果它没有破裂，我会走到75楼并做同样的事情，只要它不破裂，我就会继续增加剩下的50％。当它确实破裂时，我回到比以前更高的位置(因此，如果它在第75层破裂了，我会回到第51层)，然后放下第二块大理石并一次向上移动一层直到它破裂为止，在那一点上，我知道我可以从最高的地板掉下来而没有大理石破损。

可能不是最好的答案，但我很想知道其他人如何回答。

回答

我个人不太喜欢这类难题，我更喜欢面试中的实际编程练习。

就是说，首先要取决于我能否确定它们是否从我摔落的地板上摔坏了。我想我可以。

我会去第二层，放下第一块大理石。如果破裂，我会尝试一楼。如果那破了，我会知道那不是最低限度。

如果第一个没有中断，我会去4楼，然后从那里下降。如果破裂了，我会回去拿另一块大理石，然后掉到三楼，是否破裂，我不知道这是极限。

如果两者均未损坏，我将同时获得两者，并执行相同的过程，这次从6层开始。

这样，我可以跳过其他所有楼层，直到获得大理石破裂为止。

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

理想情况下，我需要一整袋大理石，然后可以使用二进制搜索算法，将每一滴落地的地板数分成一半...但是，那不是问题，不是吗？

回答

我认为真正的问题是我们想要答案的准确性如何。因为效率将真正取决于此。

如果我们想使大理石达到100％的精度，我会同意贾斯汀的说法，那么一旦第一个大理石破裂，我们将不得不从上一个已知的"好"层一次爬升一层，直到找出哪一层是赢家。"甚至可能会添加一些统计数据，并从25楼而不是50楼开始，因此最糟糕的情况是24而不是49.

如果回答可以是上下两个或者三个以下，那么可能会有一些优化。

其次，上下楼梯会影响效率吗？在这种情况下，每次上下都一定要扔掉两个弹子，然后捡起两个弹子。

回答

有趣的是，如何以最少的滴水量做到这一点。如果破损的地板是第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是否需要最大滴水量

回答

从3楼放下第一块大理石。如果它破裂了，我们知道它是第1层或者第2层，因此请从第2层掉下另一块大理石。如果没有破裂，我们会发现第2层是最高的。如果确实破损，我们会发现1楼最高。 2滴。

如果从3楼跌落并没有破坏大理石，请从6楼跌落。如果摔落，则知道4楼或者5楼最高。从地板5放下第二块大理石。如果它没有破裂，我们会发现5最高。如果是这样，则第4层是最高的。 4滴。

继续。

3层，最多2滴

6层，最多4滴

9层，最多6滴

12层，最多8滴

等等。

3层楼，最多2层掉落

因此，对于99层的建筑物，我们最多可以掉落66滴。那是最大的。落差可能会少于该值。哦，对于100层楼的建筑来说，最大值也是66. 如果间隔层为98或者97，则只需要66滴。如果间隔层为100，则需要34滴。

即使我们说没关系，这也可能需要最少的步行时间，并且我们不必知道建筑物的高度。

问题的一部分是如何定义效率。总是有少于x个液滴的解决方案更"有效"，还是有一个很好的机会在y <x的y液滴中具有解决方案的机会更有效，请注意，y <x ？

回答

将第一个大理石放在地板10、20、30等处，直到其破裂，然后跳回到已知的最后一个好的地板，并开始一次从一个地板上将大理石投下。最糟糕的情况是" 99"是"魔术地板"，我们总是可以在19滴或者更少的时间内找到它。

回答

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

然后我问为什么我要花时间优化它，直到有人能证明这将是一个问题。当一个简单得多的算法可以解决问题时，太多的时间让人们全神贯注于寻找完美的复杂算法。换句话说，只有在需要时才对事物进行优化。

看看我们是否是可以从mole鼠山上爬山的人之一，这可能是一个棘手的问题。