不久前面试时碰到的一道算法题

get all count - array count = missing number

用SQL可以.... Something like this...

SELECT NUM + 1 FROM TABLE WHERE NUM + 1 NOT IN (SELECT NUM FROM TABLE) AND NUM<=N

dolphindream 写道:

故事先不说，

下面呢？没有了？

我当时心里第一个想法，和三，四楼一样。只是，我考虑到如果简单地回答出来，必定还有更难的题。因为这不是我的强项，我得想法绕过去。

从出题者的角度，我觉得他考量的有数据结构，算法，复杂性和沟通能力；从我的角度，没有成败之忧。

于是我先写了个很呆的算法，两个FOR　LOOP，数组每个元素与1...N一一比较；

果然这小子开始谈起了复杂性，说这方法可以做出来，但不够有效。

我然后改成将数组的元素按从小到大排序，然后用二进制树查找。这小子露出孺子可教的表情，但仍然指出可以用HASHMAP数据结构取代二进制树。又继续引申出去，谈起SDLC中种种ANTI PATTERN。我边听边拍，“听君一席话，胜读十年书”云云。

等他说的差不多了，我说其实不必知道什么数据结构和算法，小学5年级的时候我就能做这题了，将4楼的答案一写。然后说这个问题，在整个项目中所占比重或许很低，以他的职位，或者我面试的职位，或许重点在从一百万行代码中找出低效率的部分，至于如何优化，我们可以建议，但不见得要亲力亲为，好钢要用在刀刃上。固定的思维模式，本身就是一个Anti Pattern.

另外，时间复杂性，空间复杂性，不用嘴巴说或者脑袋想，现在CPU/MEMORY　PROFILING的工具多了，一目了然。

这小子的表情有些阴晴不定。时间到了，客套一番再见。第二天收到HR电话，要求再和大老板谈一谈，我婉言谢绝，说我们的METHODOLOGY不太一样，祝他们好运。

dolphindream 写道:

职业习惯，每三个月我都会试探一下市场，发几份简历，折腾几次面试，正所谓业精于勤荒于嬉么。 在我N年的职业生涯中，第一次有人出了道算法题。 他是个很年轻的人，估计不到30，就获得了公司Principal Engineer的头衔，从几句简短的寒暄中估摸出此人性格干练，思路敏捷，聪明才智高于常人，不是个容易对付的角色... 题目如下， There are N elements in an array, N is known; Its elements are from 1 to N+1, but not in any particular order. Each element is unique, no duplication. Find out which number is missing in the sequence. Pseudo code is fine. 我不是搞开发的人，没写过一行代码，不过我知道他的意图在于观察我的思路... 故事先不说，看看大家的思路吧。

此乃最常见的面试题之一，常见到泛滥的那种。除了加起来减，还有一种方法是减少计算量的，但是需要一定空间，就是用BITMAP。

这也是算法题的常见考法。一看算法熟悉程度，二看算法复杂度分析，就是常说的BIG O。要知其然，也是其所以然。