高中课程伪代码

　　数组去重

　　我的邻桌小乐是个积极乐观的好孩子，他来自广大的欠发达地区，能在上海谋个前端工程师职位其实挺不容易的。虽然非科班的出身让他在很多方面的知识有欠缺，但是贵在踏实肯干，他在组里一直处于比较中坚的位置。

　　这天，我听到他无奈地抱怨了一句，“这谁会啊~”。

　　原来小乐在看一篇算法题的文章，讲解的题目是“数组滚动”，而讲解直接使用了公式，即先内部翻转，再整体翻转。对于这样的做法，其实我也是“望洋兴叹”的。

聊聊面试题和区分度面试题

　　“好”与“坏”从来都是主观的评判，而如何做到客观的评判，此时就需要有一定客观的评判标准。

　　就拿算法解法来说，要求的递进情况如下：

能够解决问题，满足各种情况有较好的时间复杂度和空间复杂度便于书写和理解

　　对应的三个维度的描述可以是“能用” --> “好用” --> “易用”。

　　反过来说，一个复杂度高方法是不够“好用”的，一个很容易出错或者很难理解的方法在实践中也是不“易用”的。

区分度

　　对于面试题，一般的衡量标准是“区分度”。这里我们先看一下百度百科的解释：

　　区分度，是指一个测验题目能够在多大程度上区分所要测量的心理品质，反映了测验题目对心理品质区分的有效性。一个具有良好区分度的题目，在区分被测者时应当是有效的。能通过该项目或是在该项目上得分高的被测者，其对应的品质也较突出；反之，区分度较差的项目就不能有效地鉴别水平高或低的被测者。因此，区分度也叫做项目的效度，并作为评价项目质量、筛选项目的主要依据。

　　简单理解一下，就是这道题答出来就能说明牛，答不出来就能说明待提高。而不是答出来也不能说明好，因为可能刚背过。答不出也不能说不好，因为可能只是忘记了。

　　就拿上面说的“数组滚动”来说，如果只提出一种“公式”的方法，那它的“区分度”本身就很差。因为万一候选人没有背过这道题，那他就是无法提供这种解法的。而以此为结论显然也是欠妥的。

一道有“区分度”的面试题：数组去重

　　个人在面试候选人时一定会出的一道题就是“数组去重”，下面我们来看看如何使用它来完成面试，它的区分度又如何。

　　题目：仅向候选人说明题目为“数组去重”，不提供样例输入和输出

第一层考察点：沟通候选人是否能理解题目。因为这并不是一个很难理解的问题，即去掉数组中的重复元素即可候选人是否会主动确认其中的一些细节。例如数组中的元素仅有基础类型么？引用类型如何判断是“相等”，即是只有同一个才相等？还是所有属性相同就相等？原型上的属性是否需要考虑？

　　对于第二个问题，我们可以先简化，即仅有基础类型。

第二层考察点：是否可实现

　　理解题目后，个人经验80%的候选人能够完成题目。那么20%的候选人确实在代码能力方面有欠缺。

　　最基本的方法：

　　描述：声明一个新数组，遍历输入数组，如果未曾在新数组中出现，则放入新输入

　　伪代码如下：

　　一般的去重方法

第三层考察点：效率

　　上述的思路其实不难，而最常见的判断“元素是否出现在新数组”中的条件如下

　　新数组.indexOf(每个元素) === -1

　　如果使用上述方法，优点是可以忽略很多边界情况，而缺点是整体方法的时间复杂度会成为O(n2)。因为有两层循环：访问每个元素一层，indexOf一层。

　　当候选人可以走到这里时，面试官可以引导一下，先是讨论优化方向，再确认优化方式。而此时，如果候选人无法给出正确的时间复杂度，那么本地的最终得分应该是50分。如果候选人此时可以给出正确的时间复杂度，而且有进一步优化的思路，那我们就继续往下走。

　　一般的优化方式是使用一个类Map的数据结构，使用索引来保存数据，这种属于“用空间换时间”的方案。使用这种方案的话，时间复杂度是O(n)，空间复杂度也是O(n)。

第四层考察点：数据类型和边界情况

　　上面提到了类Map的数据结构，在JavaScript中，可以用两种方式实现。一种是使用Object，另一种是使用ES6提供的Map数据结构。而其实直接使用Object是存在一些问题的，这里就要考察候选人是否知道这个关于“数据类型”的知识点了。

　　简单来说，Object的key只能是字符串String类型。而对于非字符串类型，会调用其toString方法，将返回值作为key。举例，如果让数字作为key，则保存后会成为字符串'1'；如果使用使用对象，则key会是[object Object]的形式，即Object.toString方法的返回值。

　　上述特性产生一些边界情况，导致原数组的中字符串和其他类型无法被区分，导致去重错误。例如

　　元素组输入：[1,'1',undefined, 'undefined']

　　期望输出：[1,'1',undefined, 'undefined']

　　错误输出：['1', 'undefined']

　　而如果使用ES6的Map数据结构则不会有上述问题，原因在于Map的key是有自己的数据类型的，而非全部转为字符串。

　　如果候选人能准确地说出上述区别，那么本题可得分60分。

　　另外还有一个边界情况，例如NaN如何判断相等，正0和负0是否相等。这些不做强行要求，但如果候选人能够自行察觉，则可以作为加分项。

第五层考察点：如果使用Object来完成任务

　　我们生活的现实世界就是存在各种限制的，而面对各种限制，如果把握其中的关键点，解决主要矛盾从而达到目标，这是一项很宝贵的能力。

　　如果上面的过程比较顺利，我们可以要求只能使用Object，如何来完成呢？

　　此处建议读者也自己想一想~

　　。。。

　　。。。。。

　　。。。。。。。

　　到这里了，希望是经过了一番思考后的，如果没有，请进行，如果已经过自行思考，那么请继续

　　上文提到Object最大的问题在于“无法区分类型”，那么有什么方法来区分类型呢？

　　这时就真正进入有趣的地方了，先直接说答案

　　Object.prototype.toString

　　错误答案：

　　typeof 因为无法区分对象和null

　　Instanceof 只能判断原型链是否存在

　　最后，上完整答案的JavaScript版本，请看下图：

　　时间复杂度：O(n)

　　空间复杂度：O(n)

总结

　　题目做完了，让我们来回顾一下，看看哪些是其中的重点，而哪些其实没那么重要。

　　重点：

候选人是否会主动沟通。这点在日后的工作中也非常重要，毕竟工程师会有很多与产品或QA“亲切沟通”的场景是否能够对于算法给出衡量标准对于数据类型和边界情况的考虑新问题出现时的态度。积极应对 or 怨天尤人

　　非重点：

　　候选人是否快速地给出了最终的完美版答案

　　好了，今天就到这里了。

　　再次表达一下个人观点，面试的最终目的是考察候选人的能力，所以要有“区分度”的题目。最终是否完成题目其实并不是最重要的，期间的思考和过程才是考察的重点。

　　最后祝大家都能在面试时被“温柔以待”~