摘要: 多年前，我写了一篇关于我所鄙视的某些类型的面试题。今天我想讨论一个更具体的问题，而不仅是类型。我从来没有问过自己这个问题，但我已经看有人在实际面试中提这个问题，我正式提名它为最糟糕的编程面试题。 ...
| 多年前，我写了一篇关于我所鄙视的某些类型的面试题。今天我想讨论一个更具体的问题，而不仅是类型。我从来没有问过自己这个问题，但我已经看有人在实际面试中提这个问题，我正式提名它为最糟糕的编程面试题。 在之前的公司里，有个同事经常问这个问题，那次是我第一次在面试时听到它。这家公司结对面试，两个工程师，一个候选人。有一天，我和他作为一对，去面试一些杯具的应聘者。我觉得应聘者其实表现不错，然后我的同事抛出了这个问题。应聘者结结巴巴地回答，很明显他?辶恕Ｔ诿媸院蟮木刍幔??忻媸运?墓こ淌Χ枷蛩??鹆舜竽粗福?挥形掖畹捣炊怨陀盟??灰颉叭魏纬浦暗墓こ淌Χ加Ω媚芄换卮鹚?薄Ｋ?吩涞厮挡荒芨?歉鋈斯泊妗Ｖ档靡惶岬氖牵?飧龉适掠懈龃笸旁步峋郑?颐遣还宋掖畹档目挂椋?故钦辛四歉鋈耍?⒃诩父鲈履诔戳宋掖畹担??歉鲇ζ刚呷栽谀羌夜?荆?傻煤煤玫摹?/div> 无论如何，我认为有这个问题的面试都是“有问题”的，所以我想在这里说明为什么它几乎是恐怖的一个面试题： 写一个能检测链表是否存在环路的函数。 看来像是的基本算法问题，对吗？站起来，在白板上写函数。很正常，对吗？不是，这是不对的，别这么干。 1.这完全是不恰当的。 这是一个工作面试。你有一个实时的环境，跟你说话的人在面试着。紧张是很正常的。而那种带有“灵关一闪”的智力题是最坏的问题。你的大脑将致力于思考“该死，我正搞砸这个面试”而不是关注手边的问题。 人们喜欢“看到应聘者如何思考”，但智力题无助于此。正因为它是智力题。你只能希望智力题给你“恍然大悟”。有时我听到人们想知道应聘者如何处理压力，但你应该知道，面试中本来就是有压力的。 问人难题完全是浪费时间，这样做只是考察到应聘者以前有没看过这题。或者说考察了他们的演技（当他们听说过这问题并知道答案却假装没听说，然后装模作样逐步推导以得出答案）。 这条问题是最浪费时间的。你还问为什么？好，想象一下如果一个人真的是第一次听到这个问题，然后你期望他推出答案。 对于这条题，一般来说的“正确”的答案是龟兔算法，在链表头放两个指针，一个是一步走两个节点，另一个则一步一点；如果走着走着指针指向同一个节点，那就代表有环路了。 当然，还有更简单的答案，例如，将所有走过的节点标记为“走过”，或者从每个点出发，看能不能回答该点，又或者在遍历过程中做哈希，看有没有重复。但当你抛出这些答案时，面试官又会加条件，要求使用更少的内存或时间或不能改原本的数据结构。而最佳的答案就是龟兔。 是否一开始就该考虑到这么多？无论如何，看来你很觉得你能考虑周到。链表这种数据结构是1955年由Allen Newell，Cliff Shaw 和 Herbert A. Simon 发现的。而“正确”的链表环路检测算法，则叫做“Floyd 环查找算法”，以纪念发现者Robert W. Floyd，那是1967年的事。 1955至1967之间，这个问题是开放的，就是说，无数考数学或计算机博士的人都可能将它写进论文里。即使那么多人在钻研着，这个问题还是12年无解。 你真的觉得你行吗，用20分钟，仅凭超越所有学者的压力，搞定这个曾经12年无解的难题？看来是不行的，你觉得行，只不过是因为你看过答案，然后在面试中，你”似曾相识“、”灵关一闪“。 2.这完全是不切实际的 如果上面给的理由还不能让你耻笑那个烂问题，那你再想想，这个问题是否真的有用于日常工作。 我的意思是：你怎么会在实际中碰到有环的链表？ 我并不是说叫你故意搞出一个有指回自身的链表，而是说，无端端会有这样的东西？ 链表这种数据结构不是抽象的东西，栈或队列才是，你或者会在一些抽象的数据结构中用到链表这种实在的东西。例如栈，你就用来压入，弹出，查看，是吧？那怎么会造成环呢？没有人想把它搞成一团的吧？ 即使你自己写个链表，你也不会想做出这种样子。看下java的LinkedList类，你是无法从外部去操控它的next和prev的，你只能取得第一个或最后一个，添加节点到某一位置，按位置或值删除节点。 |
