消除数组的重量
我旁边的桌子kkdyx是个积极乐观的好孩子,他来自广泛的不发达地区,在上海谋个前端工程师的职位其实很不容易。 非科班出身的他缺乏很多方面的知识,但高一是踏踏实实地干着。 他在小组里一直处于骨干的位置。
这一天,我听到他无奈地抱怨,说:“谁能做到呢~”
原本kkdyx读的是算法问题的文章。 说明的主题是“数组滚动”,说明直接使用了内部反转后再整体反转的公式。 对于这样的做法,其实我也是“望洋叹息”的。
聊聊面试题和区分度
面试题
“好”和“坏”一直以来都是主观评价,但如何进行客观评价,这个时候需要一定的客观评价标准。就算法解法而言,要求的递归情况如下。
要解决问题,满足各种情况,时间复杂度和空间复杂度都很高,容易写和理解对应的三个维度的描述,可以是“好用”——“好用”——“好用”。
反过来说,复杂度高的方法“使用起来不充分”,容易出错或难以理解的方法在实践中也没有“使用起来不方便”。
区分度
的常见问题衡量标准为“区分度”。 在这里,我们先来看看百度百科的说明:区分度是指一个测试题能在多大程度上区分测量的心理质量,反映了测试题对心理质量划分的有效性。 具有良好区分度的主题在区分受试者时必须有效。 可以通过这个项目,或者在这个项目上得分高的被实验者,对应的质量也很突出,相反,区分度差的项目不能有效地鉴别水平高的被实验者和水平低的被实验者。 因此,区分度又称项目有效性,是评价项目质量和筛选项目的主要依据。
简单地理解,这个问题解决了就可以说明牛,回答不了就可以说明会提高。 回答也说明不了。 因为你可能刚背过。 即使不能回答也不能说不好。 因为你可能只是忘了。
就上述的“排列滚动”而言,如果只提出一个“公式”的方法,其“区分度”本身就很差。 因为万一候选人没有背过这个问题,他就不能提供这个解法。 以此为结论显然也是不恰当的。
一道有“区分度”的面试题:数组去重
人面试候选人时必然会出现的问题是“排列较重”。 下面,我们来看看使用它完成面试的方法及其区别度。主题:只向候选人说明“排列重复排除”的主题,不提供样本的输入和输出
第一层考察点:沟通
候选人能理解主题吗? 因为这并不是一个难以确定的问题,即如果删除数组中的重复元素,候选人是否可以主动检查其详细信息。 例如,数组中的元素只有基本类型吗? 引用类型如何判断“相等”,也就是说只有相同的东西相等? 还是所有属性都一样就相等? 原型的属性需要考虑吗? 关于第二个问题,可以先简单一下。 也就是说,只有基本类型。了解
第二层考察点:是否可实现
主题后,80%的个人经验候选人可以完成主题。 20%的候选人确实缺乏编码能力。最基本的方法:
说明:声明新数组,遍历输入数组。 如果未出现在新数组中,则输入新输入
伪代码如下:
一般的除重量方法
第三层考察点:效率
上述想法其实并不难,但最一般的判断“要素是否出现在新排列中”的条件如下新数组. indexOf (各元素)===-1
使用上述方法具有可以忽略许多边界情况的优点,但具有整体方法的时间复杂度为O(n2 )的缺点。 因为有两个循环,一个是访问每个元素的层,另一个是要索引的层。
候选人能走到这一步后,面试官可以引导,首先研究优化的方向,然后确认优化方式。 此时,如果候选人不能给出准确的时间复杂度,本地最终得分应该是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 怨天尤人非重点:
候选人是否快速地给出了最终的完美版答案
好了,今天就到这里了。
再次表达一下个人观点,面试的最终目的是考察候选人的能力,所以要有“区分度”的题目。最终是否完成题目其实并不是最重要的,期间的思考和过程才是考察的重点。
最后祝大家都能在面试时被“温柔以待”~