很多年前我进入硅谷人才市场,当时是想找一份高级工程师的职位。如果你有一段时间没有面试过,根据经验,有个非常有用的提醒你应该接受,是:你往往会在前几次面试中的什么地方犯一些错误。简单而言是,不要首先去你梦想的公司里面试。面试中有多如牛毛的应该注意的问题,你可能全部忘记了,所以,先去几个不太重要的公司里面试,它们会在这些方面对你起教育(再教育)作用。
  我第一家面试的公司叫做gofish.com,据我所知,gofish这家公司如今的情况跟我当时面试时完全的不同。我几乎能打保票的说,当时我在那遇到的那些人都已不再那工作了,这家公司的实际情况跟我们这个故事并不是很相关。但在其中的面试却是十分相关的。对我进行技术性面试的人是一个叫做Guy的家伙。
  Guy穿了一条皮裤子。众所周知,穿皮裤子的面试官通常是让人“格外”恐怖的。而Guy也没有任何让人失望的意思。他同样也是一个技术难题终结者。而且是一个穿皮裤子的技术难题终结者——真的,我做不到他那样。
  我永远不会忘记他问我的一个问题。事实上,这个问题是非常的普通——在当时也是硅谷里标准的面试题。
  问题是这样的:
  假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法上讲,什么方法能快的查出所有小字符串里的字母在大字符串里都有?
  比如,如果是下面两个字符串:
  String 1: ABCDEFGHLMNOPQRS
  String 2: DCGSRQPOM
  答案是true,所有在string2里的字母string1也都有。如果是下面两个字符串:
  String 1: ABCDEFGHLMNOPQRS
  String 2: DCGSRQPOZ
  答案是false,因为第二个字符串里的Z字母不在第一个字符串里。
  当他问题这个问题时,不夸张的说,我几乎要脱口而出。事实上,对这个问题我很有信心。(提示:我提供的答案对他来说显然是糟糕的一种,从面试中他大量的各种细微表现中可以看出来)。
  对于这种操作一种幼稚的做法是轮询第二个字符串里的每个字母,看它是否同在第一个字符串里。从算法上讲,这需要O(n*m)次操作,其中n是string1的长度,m是string2的长度。拿上面的例子来说,坏的情况下将会有16*8 = 128次操作。
  一个稍微好一点的方案是先对这两个字符串的字母进行排序,然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m)+ O(n log n)次操作,之后的线性扫描需要O(m+n)次操作。同样拿上面的字串做例子,将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长,你会发现这个算法的效果会越来越好)
  终,我告诉了他一个佳的算法,只需要O(n+m)次操作。方法是,对第一个字串进行轮询,把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作)。然后轮询第二个字串,在Hashtable里查询每个字母,看能否找到。如果找不到,说明没有匹配成功。这将消耗掉8次操作——这样两项操作加起来一共只有24次。不错吧,比前面两种方案都要好。
  Guy没有被打动。他把他的皮裤子弄的沙沙响作为回应。”还有没有更好的?“他问道。
  我的天?这个家伙究竟想要什么?我看看白板,然后转向他。”没有了,O(n+m)是你能得到的好的结果了——我是说,你至少要对每个字母至少访问一次才能完成这项操作——而这个方案是刚好是对每个字母只访问一次“。我越想越确信我是对的。