最糟糕的编程面试题

面试算法| 2014-07-15

多年前，我写了一篇关于我所鄙视的某些类型的面试题。今天我想讨论一个更具体的问题，而不仅是类型。我从来没有问过自己这个问题，但我已经看有人在实际面试中提这个问题，我正式提名它为最糟糕的编程面试题。

在之前的公司里，有个同事经常问这个问题，那次是我第一次在面试时听到它。这家公司结对面试，两个工程师，一个候选人。有一天，我和他作为一对，去面试一些杯具的应聘者。我觉得应聘者其实表现不错，然后我的同事抛出了这个问题。应聘者结结巴巴地回答，很明显他囧了。在面试后的聚会，所有面试他的工程师都向他竖起了大拇指，只有我搭档反对雇用他，只因“任何称职的工程师都应该能够回答它”。他确凿地说不能跟那个人共存。值得一提的是，这个故事有个大团圆结局，我们不顾我搭档的抗议，还是招了那个人，并在几个月内炒了我搭档，而那个应聘者仍在那家公司，干得好好的。

无论如何，我认为有这个问题的面试都是“有问题”的，所以我想在这里说明为什么它几乎是恐怖的一个面试题：

写一个能检测链表是否存在环路的函数。

看来像是的基本算法问题，对吗？站起来，在白板上写函数。很正常，对吗？不是，这是不对的，别这么干。

1.这完全是不恰当的。

这是一个工作面试。你有一个实时的环境，跟你说话的人在面试着。紧张是很正常的。而那种带有“灵关一闪”的智力题是最坏的问题。你的大脑将致力于思考“该死，我正搞砸这个面试”而不是关注手边的问题。

人们喜欢“看到应聘者如何思考”，但智力题无助于此。正因为它是智力题。你只能希望智力题给你“恍然大悟”。有时我听到人们想知道应聘者如何处理压力，但你应该知道，面试中本来就是有压力的。

问人难题完全是浪费时间，这样做只是考察到应聘者以前有没看过这题。或者说考察了他们的演技（当他们听说过这问题并知道答案却假装没听说，然后装模作样逐步推导以得出答案）。

这条问题是最浪费时间的。你还问为什么？好，想象一下如果一个人真的是第一次听到这个问题，然后你期望他推出答案。

对于这条题，一般来说的“正确”的答案是龟兔算法，在链表头放两个指针，一个是一步走两个节点，另一个则一步一点；如果走着走着指针指向同一个节点，那就代表有环路了。

当然，还有更简单的答案，例如，将所有走过的节点标记为“走过”，或者从每个点出发，看能不能回答该点，又或者在遍历过程中做哈希，看有没有重复。但当你抛出这些答案时，面试官又会加条件，要求使用更少的内存或时间或不能改原本的数据结构。而最佳的答案就是龟兔。

是否一开始就该考虑到这么多？无论如何，看来你很觉得你能考虑周到。链表这种数据结构是1955年由Allen Newell，Cliff Shaw 和 Herbert A. Simon 发现的。而“正确”的链表环路检测算法，则叫做“Floyd 环查找算法”，以纪念发现者Robert W. Floyd，那是1967年的事。

1955至1967之间，这个问题是开放的，就是说，无数考数学或计算机博士的人都可能将它写进论文里。即使那么多人在钻研着，这个问题还是12年无解。

你真的觉得你行吗，用20分钟，仅凭超越所有学者的压力，搞定这个曾经12年无解的难题？看来是不行的，你觉得行，只不过是因为你看过答案，然后在面试中，你”似曾相识“、”灵关一闪“。

2.这完全是不切实际的

如果上面给的理由还不能让你耻笑那个烂问题，那你再想想，这个问题是否真的有用于日常工作。

我的意思是：你怎么会在实际中碰到有环的链表？

我并不是说叫你故意搞出一个有指回自身的链表，而是说，无端端会有这样的东西？

链表这种数据结构不是抽象的东西，栈或队列才是，你或者会在一些抽象的数据结构中用到链表这种实在的东西。例如栈，你就用来压入，弹出，查看，是吧？那怎么会造成环呢？没有人想把它搞成一团的吧？

即使你自己写个链表，你也不会想做出这种样子。看下java的LinkedList类，你是无法从外部去操控它的next和prev的，你只能取得第一个或最后一个，添加节点到某一位置，按位置或值删除节点。

看下java源码就知道，真的没有：

private static class Entry <E> {
  E element;

  java.util.LinkedList.Entry<E> next;
  java.util.LinkedList.Entry<E> previous;

  Entry(E e, java.util.LinkedList.Entry<E> entry, java.util.LinkedList.Entry<E> entry1) { /* compiled code */ }
}

它是一个私有静态类，你无法从外部实例化它。你不能直接操控next和prev，因为它们俩代表了链表的状态，它们就该这样被封装起来。

如果你真的把链表搞成有环了，那说明你写错。写错的话，你最好重新写对它，而不是写个“检测环”的方法。

“检测环”的方法就该这样写：

public class LinkedList { 
	public boolean containsCycle() { 
		return false;
	} 
}

如果你的链表写对的话，“龟兔算法”返回的结果也跟这个方法一样。

现实中你是很少有机会亲手写个链表的，即使有，你也别写个能造成环的方法。造成环的方法，只能是“留后门”，“元编程”，“反射”。既然是这样故意的话，那么绕过你的“检测环”也是轻而易举的。

结论

很多面试题，都中了以上其中一点，太过困难或者与工作无关。

而这个问题，两点都中了。

如果有人给到你满意的答案，就说明那个人死记硬背，无他。因回答不了而被你否决的人，说不定还比你更适合这份实务。

链表环路检测：别问了。

更新：有位评论者说如果问题问的是有向图，且每个节点的出度最多只有，即是问“检测这个有向图有没有环”。搞图的话，你确实可能会向API用户提供修改每点的指向的方法，这看上去符合实际。但是，还是那句话，你只是在考察应聘者把CS课程记住了多少，或者你只想随便问问，又或者你想听听他说除了龟兔算法以外的低效算法。