3

有时我会遇到这样的面试问题： “查找树中任意 2 个节点的共同父节点”。我注意到他们也在谷歌、亚马逊等公司提出 LCA 问题。

正如维基百科所说，可以通过从给定节点到根的路径相交来找到 LCA，它需要 O(H)，其中 H 是树的高度。此外，还有更高级的算法可以在 O(N) 中处理树并在 O(1) 中回答 LCA 查询。

我想知道面试官究竟想了解关于提出这个 LCA 问题的候选人的哪些信息。路径交叉的第一个算法似乎微不足道。他们是否希望候选人记住预处理算法？他们是否期望候选人能够即时发明这些算法和数据结构？

4

2 回答 2

9

他们想看看你是由什么组成的。他们想看看你是如何思考的，你如何解决问题，以及如何处理截止日期的压力。我想如果你解决问题是因为你已经知道解决方案，那么他们只会给你带来另一个问题。这不是他们想要的解决方案，而是你的大脑。

于 2010-12-26T14:14:51.497 回答
2

面试中有很多算法问题，我不在乎（或希望）你记住答案。我希望你能够从你所知道的主要原则中得出答案。

现实地说：如果你已经知道“如何做 X”的答案，如果你能够快速构建答案，我可以少关心两件事。最终：在现实世界中，我不一定假设您有解决域 X 问题的经验，但是如果您在所述域中遇到问题，我当然希望您具有分析能力以找出合理的答案，基于您掌握的一般知识。

树是一种常见的数据结构，可以安全地假设大多数人都知道 - 如果您立即知道答案，您应该能够解释它。如果你不知道答案，但了解数据结构，你应该可以轻松得出答案。

于 2010-12-30T02:32:35.620 回答