原作者:陈皓
算法面试可能是微软搞出来的面试方法,现在很多公司都在效仿,而且我们的程序员也乐于解算法题,我个人以为,这是应试教育的毒瘤!我曾经比较保守地说过,“问难的算法题并没有错,错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”,今天,我想加强一下这个观点——我反对纯算法题面试!(注意,我说的是纯算法题)
我再次引用我以前的一个观点——
能解算法题并不意味着这个人就有能力就能在工作中解决问题,你可以想想,小学奥数题可能比这些题更难,但并不意味着那些奥数能手就能解决实际问题。
好了,让我们来看一个示例(这个示例是昨天在微博上的一个讨论),这个题是——“找出无序数组中第2大的数”,几乎所有的人都用了O(n)的算法,我相信对于我们这些应试教育出来的人来说,不用排序用O(n)算法是很正常的事,连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了,这是我国教育最悲哀的地方。(广义的洗脑就是让你的意识依赖于某个标准答案,然后通过给你标准答案让你不会思考而控制你)
功能性需求分析
试想,如果我们在实际工作中得到这样一个题 我们会怎么做?我一定会分析这个需求,因为我害怕需求未来会改变,今天你叫我找一个第2大的数,明天你找我找一个第4大的数,后天叫我找一个第100大的数,我不搞死了。需求变化是很正常的事。分析完这个需求后,我会很自然地去写找第K大数的算法——难度一下子就增大了。
很多人会以为找第K大的需求是一种“过早扩展”的思路,不是这样的,我相信我们在实际编码中写过太多这样的程序了,你一定不会设计出这样的函数接口—— Find2ndMaxNum(int* array, int len),就好像你不会设计出 DestroyBaghdad(); 这样的接口,而是设计一个DestoryCity( City& ); 的接口,而把Baghdad当成参数传进去!所以,你应该是声明一个叫FindKthMaxNum(int* array, int len, int kth),把2当成参数传进去。这是最基本的编程方法,用数学的话来说,叫代数!最简单的需求分析方法就是把需求翻译成函数名,然后看看是这个接口不是很二?!
(注:不要纠结于FindMaxNum()或FindMinNum(),因为这两个函数名的业务意义很清楚了,不像Find2ndMaxNum()那么二)
非功能性需求分析
性能之类的东西从来都是非功能性需求,对于算法题,我们太喜欢研究算法题的空间和时间复杂度了。我们希望做到空间和时间双丰收,这是算法学术界的风格。所以,习惯于标准答案的我们已经失去思考的能力,只会机械地思考算法之内的性能,而忽略了算法之外的性能。
如果题目是——“从无序数组中找到第K个最大的数”,那么,我们一定会去思考用O(n)的线性算法找出第K个数。事实上,也有线性算法——STL中可以用nth_element求得类似的第n大的数,其利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:1)Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;2) Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)。
搞学术的nuts们到了这一步一定会欢呼胜利!但是他们哪里能想得到性能的需求分析也是来源自业务的!
我们一说性能,基本上是个人都会问,请求量有多大?如果我们的FindKthMaxNum()的请求量是m次,那么你的这个每次都要O(n)复杂度的算法得到的效果就是O(n*m),这一点,是书呆子式的学院派人永远想不到的。因为应试教育让我们不会从实际思考了。
工程式的解法
根据上面的需求分析,有软件工程经验的人的解法通常会这样:
1)把数组排序,从大到小。
2)于是你要第k大的数,就直接访问 array[k]。
排序只需要一次,O(n*log(n)),然后,接下来的m次对FindKthMaxNum()的调用全是O(1)的,整体复杂度反而成了线性的。
其实,上述的还不是工程式的最好的解法,因为,在业务中,那数组中的数据可能会是会变化的,所以,如果是用数组排序的话,有数据的改动会让我重新排序,这个太耗性能了,如果实际情况中会有很多的插入或删除操作,那么可以考虑使用B+树。
工程式的解法有以下特点:
1)很方便扩展,因为数据排好序了,你还可以方便地支持各种需求,如从第k1大到k2大的数据(那些学院派写出来的代码在拿到这个需求时又开始挠头苦想了)
2)规整的数据会简化整体的算法复杂度,从而整体性能会更好。(公欲善其事,必先利其器)
3)代码变得清晰,易懂,易维护!(学院派的和STL一样的近似O(n)复杂度的算法没人敢动)
争论
你可能会和我有以下争论,
· 如果程序员做这个算法题用排序的方式,他一定不会像你想那么多。是的,你说得对。但是我想说,很多时候,我们直觉地思考,恰恰是正确的路。因为“排序”这个思路符合人类大脑处理问题的方式,而使用学院派的方式是反大脑直觉的。反大脑直觉的,通常意味着晦涩难懂,维护成本上升。
· 就是一道面试题,我就是想测试一下你的算法技能,这也扯太多了。没问题,不过,我们要清楚我们是在招什么人?是一个只会写算法的人,还是一个会做软件的人?这个只有你自己最清楚。
· 这个算法题太容易诱导到学院派的思路了。是的这道“找出第K大的数”,其实可以变换为更为业务一点的题目——“我要和别的商户竞价,我想排在所有竞争对手报价的第K名,请写一个程序,我输入K,和一个商品名,系统告诉我应该订多少价?(商家的所有商品的报价在一数组中)”——业务分析,整体性能,算法,数据结构,增加需求让应聘者重构,这一个问题就全考了。
· 你是不是在说算法不重要,不用学?千万别这样理解我,搞得好像如果面试不面,我就可以不学。算法很重要,算法题能锻炼我们的思维,而且也有很多实际用处。我这篇文章不是让大家不要去学算法,这是完全错误的,我是让大家带着业务问题去使用算法。问你业务问题,一样会问到算法题上来。
小结
看过这上面的分析,我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质!
那么,在面试中,我们应该要考量程序员的那些综合素质呢?我以为有下面这些东西:
1.会不会做需求分析?怎么理解问题的?
2.解决问题的思路是什么?想法如何?
3.会不会对基础的算法和数据结构灵活运用?
4.另外,我们知道,对于软件开发来说,在工程上,难是的下面是这些挑战:
l 软件的维护成本远远大于软件的开发成本。
l 软件的质量变得越来越重要,所以,测试工作也变得越来越重要。
l 软件的需求总是在变的,软件的需求总是一点一点往上加的。
l 程序中大量的代码都是在处理一些错误的或是不正常的流程。
所以,对于编程能力上,我们应该主要考量程序员的如下能力:
5.设计是否满足对需求的理解,并可以应对可能出现的需求变化。
6.程序是否易读,易维护?
7.重构代码的能力如何?
8.会不会测试自己写好的程序?
所以,这段时间,我越来越倾向于问应聘者一些有业务意义的题,而且应增加或更改需求来看程序员的重构代码的能力,写完程序后,让应聘者设计测试案例。
比如:解析加减乘除表达式,字符串转数字,洗牌程序,口令生成器,通过ip地址找地点,英汉词典双向检索……
总之,我反对纯算法面试题!
(全文完)
——转自酷壳
相关推荐
掌握上述39道JAVA经典算法面试题及其解析,对于任何希望在软件开发行业中取得成功的人来说都是极其宝贵的。通过这些题目的练习,读者不仅能加深对JAVA编程语言的理解,还能提升在实际工作中解决复杂算法问题的能力。...
计算机常见算法面试题 本资源摘要信息涵盖了计算机常见算法面试题,主要涉及链表、...本资源摘要信息涵盖了计算机常见算法面试题,涵盖了链表、字符串操作、搜索算法等方面的知识点,为面试者提供了有价值的参考资源。
作为一名准备进入该领域或者寻求提升的工程师,掌握算法面试题的解法是必须的。本文总结了五道常见的算法面试题,并对每一道题目进行了详细解答和分析,旨在帮助大家深入理解算法设计的基本原理和方法。 首先,将...
【算法面试题】在计算机科学领域,特别是在面试过程中,算法能力是评估程序员技能的重要标准。题目涉及到了将二元查找树(BST)转换为排序的双向链表,这是一个典型的树结构转换问题,常出现在诸如百度、微软等科技...
数据结构与算法是计算机科学的基础,对于...以上知识点是数据结构与算法面试题中常见的部分,每个主题下都可能有深入的理论讲解和实践题目,对于准备面试的开发者来说,全面掌握这些内容将大大提升在面试中的竞争力。
百度,腾讯,阿里等等大公司的算法面试题精心总结,需要的朋友可以下载下来提前研究一下
根据提供的文件内容,我们可以提炼出以下30个典型的算法面试题的知识点。 1. 字符串中不含有重复字符的最长子串长度问题。这个问题考察对滑动窗口技巧的掌握,需要在遍历字符串的同时保持一个窗口,该窗口内没有...
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
java数据结构与算法面试题(2022最新版).docx
前端面试宝典、前端面试题库、高频前端面试题、大厂面试题、算法面试题、前端面试题大全。这是一个有答案的、高频前端面试汇总 按照高频排序,且附上最完整、通俗易懂的答案,拿必包做举例。 面试官问你必包,你...
计算机视觉算法工程师常见面试题1.pdf 本文总结了计算机视觉算法工程师常见的面试题,涵盖了反卷积、神经网络的万能逼近定理、Batch Normalization 和 Group Normalization、模型压缩、目标检测、深度学习优化等多...
在准备IT行业的面试,尤其是针对微软这样的顶级科技公司时,数据结构...通过这个包含100题的解答集锦,你可以系统地复习和巩固这些概念,为面试做好充分准备。记得不仅要理解答案,更要深入理解背后的原理和思维方式。
算法笔试题:(Python实现)—— 算法面试题汇总算法笔试题:(Python实现)—— 算法面试题汇总开始之前Python实现只出现一次的数字多数元素搜索二维矩阵 II合并两个有序数组鸡蛋掉落字符串Python实现验证回文串...
在PHP的世界里,面试题是衡量开发者技能和经验的重要手段,尤其在算法这一领域,它直接反映了开发者的逻辑思维能力和问题解决能力。算法是计算机科学的基础,对于PHP开发者来说,理解并能熟练运用各种算法至关重要。...
【微软数据结构和算法面试题】是专门为求职者准备的一份精选面试题集,由July精心整理而成。这些题目涵盖了数据结构和算法的核心概念,旨在帮助面试者提升在这两个领域的能力,以应对微软等知名公司的面试挑战。以下...
C++算法大全及面试题详解资料包包含两个word文档,一个C++算法大全,一个C++面试经典题及答案详解(包含大量代码)。这两份资料整理了C++的常见算法、常见考点和重要知识技巧,内容齐全,涵盖各类应试考点,满满干货...
算法面试题知识点总结 本资源摘要信息涵盖了八十道常见的算法面试题,涵盖了数据结构、算法设计、时间复杂度分析等多方面的知识点。 知识点一: 二元查找树转换为排序的双向链表 在这道题中,我们需要将一个二元...
- 通过辗转相除法求最大公约数:不断用大数除以小数,再用小数除以上一次得到的余数,直到余数为0,此时的小数即为最大公约数。 - 最小公倍数可以通过两个数的乘积除以它们的最大公约数得到。