RecursiveFrog 发表于 2021-7-4 05:44

为什么最难不过二叉树的算法出现在面试题中都会被应聘者抱怨?

为什么最难不过二叉树的算法出现在面试题中都会被应聘者抱怨?

yukamu 发表于 2021-7-4 05:52

因为他们觉得反正招进来之后我也用不上二叉树,你们谁写业务代码的时候用上二叉树了?所以我不会就不会呗。这其实就是“高等数学有啥用,又不能用来买菜”的进化版本。
的确很少有写业务代码的时候会直接用上二叉树。但是真的没有吗?XML/DOM是什么?是不是一棵树?为什么DOM可以和XML一一对应?因为XML序列化就是树的遍历的结果。能和XML对应,也就能跟JSON对应,因为两者都可以对应到树(只是表示逻辑上有些区别)。
一个业务系统里有任务(Task),任务有相应的执行计划(Plan),计划可以用子任务组成,子任务可以是基础任务,也可以通过Plan拆分成更多的子任务。这是什么?这不就是树吗?那么怎么存储?JSON不就很好吗。怎么从JSON加载、再保存会JSON?树的遍历。怎么计算任务总共需要多少个基础任务?树的遍历。怎么计算计划总共需要多少时间?树的遍历。
一个社交系统里,用户可以加好友,好友还有别的好友,这是什么?无向图。如果是知乎这样的关注系统呢?有向图。一个用户点了个赞,扩散到另一个用户至少要经过几次转发?最短路径。我要画一个小圈子里的人之间的关系图,怎么做?最小生成树。我要整理信息路径,看这批用户里哪些生产内容,哪些阅读内容,按什么次序传播,怎么做?拓扑排序。


我们只是不想招一个看到上面这些话的时候一脸懵逼的人。

xiaozongpeng 发表于 2021-7-4 06:00

先亮明观点:身为程序员,算法知识100%是必要的!

本人从事的不是什么高大上的研究工作,跟数据挖掘模式识别自然语言处理云计算大数据blahblah全都不沾边。做过一段时间的J2EE开发,现在主要做基于HTML5的前台开发。看到这儿很多人要说了,不就是个做网页的嘛,做网页还用的上算法?不就是表单验证提交一下?我的回答是绝对用的上!

举个例子,很多人在微博上见过tagcloud分析图,展示的是一些关键字的出现频率:

这里不谈文本检索这些,只说对已知数据如何安排各个关键字的位置进行渲染。这是个很典型的结合实际的算法问题,在此我用到了wordle算法,这和我们上学时常谈到的那些算法不太一样,但很多核心思路(例如空间换时间)还是相通的。感兴趣的同学可以自行了解。

接下来说说面试的问题。正式工作近9年,一直在coding的第一线,近年来也经常参与对技术人员的面试工作。我和同事们对面试时要不要涉及到算法的问题没有丝毫分歧,仍然是有必要。但算法问题如何问,也是有讲究的。我反对上来就指定一个算法让面试者写答案,例如前面有知友提到的写个快速排序之类的。这样的做法有掉书袋的嫌疑,而且除了证明对方为了面试做过精心准备,其他方面根本考核不出来。

自己在面试中经常会问的一个问题:
有一组长度为n的对象,每个对象里都有一个startTime和endTime,表示一个时间段。请面试者设计一个小算法,把这些对象中时间段存在重合关系的所有对象列出来。

这个问题不难,但一定程度上能考验面试者对算法本身的理解和sense。对这个问题的典型讨论过程是这样的:
Candidate:我想可以作个双重循环,把这些对象两两比较
me:好的,这显然是个很直观的方法。那么按照你的方法,时间复杂度是多少呢?
Candidate:n^2吧
me:OK,那么你看看是不是有改进的余地
Candidate:……也许我可以先排序,后面还没想好
me:根据什么排序呢?
Candidate:startTime
me:好,那么我们画个图来看看排好序后这些对象的分布
Candidate:……我想到了!blahblah
me:好的,那么这个算法的复杂度是多少?你能分析一下吗?
Candidate:前面排序用快速排序是n*log(n),后面的过程是线性的,所以总体就是n*log(n)
……

当然,这是一个比较正面的例子,candidate第一时间解决了问题,但不算完美。在一些提示下发挥和表现了自己对算法、数据结构的认识,比较完整的给出了解。作为interviewer,我就足够满意了。当然也不排除有些candidate上来就能给出很好的解答,那我也没有理由去鸡蛋里挑骨头。作为interviewer,目的是快速的了解对方的能力和水平,而不是为了考住对方

ainatipen 发表于 2021-7-4 06:08

我觉得是题目太简单导致的问题。
面试官觉得,我擦,那么简单都不会。
面试者觉得,我擦,没法调试没法查资料我怎么写的对,这种基础题目写错就没分啊。
然后不欢而散。

面算法的时候,我一般允许对方做不出来,但是至少要给一个解决思路。就算你告诉我你用谷歌一下可以解决也比遇到算法题就放弃反感大惊小怪好得多。

如果面社招的,我出的题目一般都是可以用暴力解决掉的搜索题这种难度的 ,我直接允许对方上网查资料,给予对方一台装好开发环境的电脑去解决,甚至是来面试前给一个homework。
题目不难,所以有的同学用暴力解决,有的会用简单的搜索,也有的会用A*这类比较漂亮的解答方案。从而区分度还是很好的

我觉一直得比较重要的是对问题的解决能力,至于你用什么工具我并不在意,我所提供的工作环境网络都是畅通的,能够找到有用资料的能力也弥足珍贵,远比单纯的说背个二叉树遍历好太多了。

一家之言,仅供参考,如果觉得这种面试深得汝心,也欢迎投简历给我
哦,工作地点是上海
-----更新-----
目前暂时不需要招人了,感谢各位支持。。。

c0d3n4m 发表于 2021-7-4 06:10

写在前面:很多热心的朋友在评论里面讨论算法,由于讨论的效率太低,况且本人悟性也一般,有的朋友说的算法我也看不懂,因此不展开讨论算法,这里只是抛砖引玉给个案例,目的是为了说明问题,不是为了讨论算法。
============================================================
绝大部分人吐槽算法面试,并不是认为面试不该问算法,也不是认为算法不重要,而是吐槽“面试算法的方式”,吐槽最多的两点:
1. 现场手写代码:面试本来就紧张,写代码绝大部分人都会更紧张;
2. 你冒泡快排细节都不清楚,代码都写不出,所以你能力不行;
口口声声算法很重要,为何面试官只会让面试者写写冒泡、快排、二叉树,而不会写B+树、Paxos算法、梯度下降?即使问到B+树、Paxos算法、梯度下降的时候也只是问个原理而已!
因为这些算法面试官也不会写啊,就算有人真的背出来了,面试官也看不懂!
我就不会面试这类算法题,这类算法题唯一能考核的就是面试者有没有背算法和数据结构而已,真要面试算法,结合实际的案例最好,例如:
如何计算两个微信号有多少个共同好友?
地铁卡机如何计算两个站之间的费用?
姚晨发了微博,如何快速的推送给所有粉丝?
====================第一次补充==============================
有同学问“如何计算两个微信号有多少共同好友”,我详细说一下需求,然后给出我的一个答案,我不知道我的这个算法是否最优的,期望有大神指正。
需求详细如下:假设你有一个微信号(QQ号、手机号都可以,有关系链就可以),推荐你好友的好友给你作为“你可能认识的人”,推荐的时候通过共同好友数量来推断你们认识的可能性;
最简单的做法:拿出两个微信号的好友数据,进行交集运算,然后得到交集的数量。
缺点:非常耗费CPU,实际业务肯定不止计算两个用户,而是几百上千万用户,这样需要大量的机器来支撑。
我的算法:如下图,先找到UID的好友集合(Operator1),然后再找好友的好友(Operator2),这两部分和简单算法是一样的,但第三步不同,拿到两个集合后,并不进行集合交集运算,而是将好友的好友保存起来,用一个hash表记录UID以及一个数字,每次通过好友的好友找到某个用户,这个数字就加1,所以最终的算法就转换为计算有多少条路径到达某个用户,路径数量就是共同好友数量。
这个算法是典型的“空间换时间”,简单算法内存占用少,但集合交集运算耗费大量CPU;我的算法耗费一定的内存空间,但CPU计算很快。我们以一个模型来估算一下,假设平均每个人100个好友:
【简单算法】内存:两个100个好友的集合;CPU:10000次两个100个元素的集合求交集;存储:10101次读取好友集合;
【路径算法】内存:最大10000元素的hash表;CPU:10000次hash表操作;存储:101次读取好友集合;
实测性能提升100倍以上。
以上例子其实我也不推荐大家在面试的时候问,面试的时间短,对业务背景不太熟,面试者很难快速答出来,这个算法,我自己都是想了一两天才想出来,哎,天性愚笨啊,23333
附加:这个需求稍微变一下,算法就又不一样了,有兴趣的同学可以自行思考,例如:
假设你有一个微信号(QQ号、手机号都可以,有关系链就可以),通过计算你与你的好友的共同好友数量,可以推断出你和你某个好友的亲密度;


==============第二次补充=========================
我不是说我完全不问算法和数据结构的基础,一般只会考原理和关键点,不会让人现场手写,例如:
vector尾部插入和头部插入有什么区别?链表尾部插入、头部插入、中间插入有什么区别?为何Java字符串拼接要用StringBuffer ? C语言怎么做呢 ?为何磁盘用B+树,内存用红黑树?。。。。。。。。。。

IT圈老男孩1 发表于 2021-7-4 06:15

最简单的解释:典型的工人去面试工程师职位,通不过面试是应该的。(假设如描述所说最难只问到二叉树。)

我反对面试官随便网上找一道题就拿来问的做法,我也反对@归辰 所说的只应该考察工作上实际所需知识的做法,因为这两者都基于一个错误的面试思路,那就是用面试来考察你懂不懂什么的。面试不是用来考察你懂不懂什么的,而是用来考察你有没有解决问题的能力的,以及将来和你一起解决问题是否容易。我知道中国绝大多数人在经历了十多年应试教育后,无论是站在面试者的角度来看,还是若干年后成为面试官了从面试官的角度来看,都只会用这种方式来思考问题——「面试」嘛,有个「试」字不就应该跟「考试」差不多咯,而我们习惯的考试就是考察你是否懂某个知识咯,只要死记硬背就可以了。然而真正好的面试不是这样做的,有兴趣的可以去看我之前写的那篇《理想的技术面试过程》。

回到问题上来,我认为正确的面试方式是这样子的:现在你来我这里面试,我就告诉你我们在做一辆车子的原型,现在少了一个轮子问你怎么办。没错,我就是要让你重新发明轮子。谁不知道楼下 7-11 有轮子卖,但我就想知道你会如何解决没有轮子的问题。

你可以从各种听起来非常愚蠢的方法开始,例如问我这个原型是不是只是用来展出的,是的话把车子放在展厅一角然后让缺了轮子的一侧对着角落,这样子随便拿几块砖头把车撑起来就可以了,反正没人会去看车子的那一侧。然后我会告诉你,展厅的天花不可能打开,所以我们不能直接用吊车把原型放进去,最终原型在展厅外面卸下来后你还是是要想个办法把它弄进去。你可能会说,那就用埃及人用圆木搬动大石块的方法咯,在原型的底下放几条滚动的圆木至少能让它推得动吧。这听起来还是比较蠢,但我会告诉你这个思路的方向是正确的。这个讨论延续下去,最终你还是会提出用金属做轮子外面再包一圈橡胶的做法,从而完成了重新发明轮子的过程。

之后我会把你带到车间里,告诉你这里有你所需的所有电动工具和原材料,你把你刚才发明的那个轮子造出来吧。有些人手艺非常好,一下子就能做出来一个非常好的轮子。有些人无论说得轮子有多圆,做出来的东西永远只能是方形的。大多数人介乎两者之间,对此我会说你不如把你造出来的轮子装到原型上试试看是否合适,不合适的话拿下来再调整一下。

这是正常的面试流程。我不指望你一开始能够给我一个轮子,我也知道外面卖的轮子很便宜,但我需要验证你有没有遇到问题后解决问题的能力,这包括思维和动手两方面。在这个比喻的基础上,我们可以来探讨一下面试过程中遇到的各种面试者。

那些不懂算法同时也非常拒绝面试算法的面试者,就如同一条汽车流水线上的工人来面试汽车工程师一样。「没有轮子?老板你这不是耍我么。我能够纯熟地把轮胎和轴承对齐,然后用电动工具把所有螺丝都拧紧。但没有轮子这就不是我的问题了。这要么是采购的问题,要么是仓管的问题,反正轮胎没有出现在流水线上我就什么都做不了。如果说没有电动工具,我可以去找两把手动工具来,用脚踩两下也能拧紧,但没有轮胎真的不是我能负责的。」

当然这都不是最搞笑的,还有更搞笑的类型。ACM/ICPC 竞赛选手或者是面试前专门在网上刷题的面试者,基本上一上来就「哦,你要个轮子是吧。我知道怎么造轮子,你给我工具和材料就行了」,然后就以极快的速度造了一个轮子出来,装上去也没有任何问题。有一定的概率我在仔细检查后发现,这个轮子是用铆钉装上去的,所以拆不下来了,橡胶是一次充气后完全密封的,因此漏气之后不可能再打气。不过想想也合理,这类工程师专业做撞击测试,所以在他们的世界里面任何东西造出来都不是长期使用的,而是拿去测试一下,通过或通不过都立即变废品。

还有一些情况是这样子的,例如我问超大整数乘法然后对方说用 Python 直接用乘号,又或者说我问快速排序对方说用 Haskell 一行写完。这就如同一个面试者打开公文包掏出一个轮子说「我这正好有一个,不知道是否合适?」呃……你的百宝袋里面还有什么?

最后从面试官的角度来说,面试 ACM/ICPC 竞赛选手往往都很无聊。他们能够给出一个完美的轮子,但我不觉得我能从他们身上学到新东西。(面试过足够多的人后,要见到一个比已知完美轮子更完美的轮子其实非常难。)更有趣的面试者会说,「你知道吗,其实中国古代独轮手推车的轮子设计得比古罗马战车的轮子要合理」。其实我不知道你在说什么,但如果你能够把整套理论说得自圆其说的话我觉得你至少有点思维能力,同时你还真的对轮子感兴趣。事后我可能会去搜索一下看看你说的理论是否正确,但至少我会学到点新东西。

super1 发表于 2021-7-4 06:16

不要那么激动,面试者不是傻子,这不过是一种制造心理平衡的手段罢了。
这年头谁不知道面试会面算法?面试之前肯定要准备的啊。
用不着解释为什么算法有用,其实他们一定知道,而且至少听说过。
但他们学不进去,不想学新东西了,已经在舒适圈待舒服了,畏惧困难了。
但谁会承认自己不好?
怎么办?只能贬低好喽。
算法有啥用?了解底层原理有啥用?架构有啥用?抽象有啥用?名字起得好有啥用?
反正技术没用,就他的土办法有用。真遇到困难的时候,他们就不说话了,等大牛搞定了困难问题,他们又回跳出来喷技术。
人人都需要心理平衡,身在这么个竞争激烈的时代,谁都会遇到身边人比自己强很多的挫败感觉。
所谓技术好的同学也别沾沾自喜,看到你们周围升职或创业成功的朋友们,是否偶尔也感慨自己像一个sb一样傻乎乎的做技术,结果只能安慰自己说“我喜欢技术而已”“他不过是搞关系厉害”之类的,其实你就是比人家弱,人家做技术的时候未必比你差多少,可能做技术就是错的。算法好面试好的同学,看到各种大牛的技术分享,是否也觉得自己差太远?所谓业内大牛也问问自己,做的事情有多少是实在货,多少是吹的,是否真的比老实做技术的同学厉害?岁数越大,人的差距也就越大,都是日积月累的。
往上看都是猴屁股,往下看都是猴脸,面试技术的时候沾沾自喜,看看朋友圈里前同事都当上市公司副总裁了,再看看自己什么几万月薪的又算个啥?
谁最强?二马见了工信部领导也要拿个小本本记东西。往上看总是没有头的,很多时候自我安慰也是有用的。这些都是人类本能的心理保护机制而已,真正觉得自己是个废物一无是处的人,就离自杀不远了。

zt3ff3n 发表于 2021-7-4 06:26

如果以求职者的角度来看,很多求职者的项目与技能和这些面试算法题有出入和差别,所以出现了leetcode,剑指Offer等专门应试面试算法的网站或书籍(个人极度反感,但是现实就是大部分面试就要考这些类型的,你不刷题不看就是容易被毙掉)。所以很多求职者认为自己的技能还没有表现出来,就被面试的算法直接给枪毙掉了,自然有所不服,无论你认为这是多么简单的算法,也许他在工作的时候,根本和这些算法完全不搭边,工作个几年不忘光才怪。

那么除了算法以外,如何挖掘出求职者的闪光点,这也是对面试官的一个考验,因为考验算法的不外乎就一个根本目的:他到底聪不聪明。但是算法不好,就一定证明他不聪明,或者工作能力不好了吗?我觉得不一定。这就是要看面试官和面试者的交谈了,面试官去尽力挖掘,面试者去尽力表达推销自己,这就是一个交互的过程。

zifa2003293 发表于 2021-7-4 06:36

作为面试官,我曾经听说过几个面试者对我给他们的面试经历评价为“明明小公司一个,面什么算法”。
后来我曾经找出了其中一些人的简历,回忆了一下面试过程,基本上他们都满足以下四条中的两条以上:

1、简历上4-5个项目经历,结果一问,别说不是项目主持了,根本就是参与度极低,一问三不知。(我曾遇到过同一个大概不超过1万行的项目在3个人简历上同时出现的,而且他们都不是项目主持)
2、简历上声称熟练掌握的内容,掌握程度仅限于最基本的使用,缺乏任何的设计分析能力。
3、对所面试的岗位毫无概念,不明白自己是否符合岗位描述上的必要条件
4、对面试提问思路不清晰,或思路表达不清晰。面对问题时,不是仅仅得不到完美的最终答案,而是思路一片空白。
5、坚决认为C++是王道,“我还是想做C++”,拒绝多语言工作和学习。但实际上C++掌握的并不好。

鄙公司(小公司招人不容易啊!)面试程序时,除非简历上写明了ACM获奖经历,否则我给他们安排的所谓“算法题”基本上不会超过二分查找的难度,而且其实并没有太多思路上的扩展,仅仅是算法实现而已。而且这仅限于我实在找不出任何的其它亮点,完全无法满足一个C++岗位的要求,还坚持想从事C++岗位的时候才会进行这样的提问。因为我们其实是相信员工在岗位上的成长的,面试时不允许查找资料,时间也有限,能解决的问题难度不如工作时所能解决的问题难度也是很正常的。但至少你要有点思路吧?二分查找不会写个枚举也好吧?白卷是闹哪样?

结果他们认为是因为算法题表现不好而被我拒绝了。

除了鄙公司,以我在大公司的被面试以及面试经验,虽然连基本的算法题都答不出实在是一件值得鄙视和怀疑的事情,但我依然觉得如果你各方面能力均表现优秀,十分符合岗位所需的要求,其实是不太会因为一个复杂的算法题没有答上来而直接被挂掉的。当然,如果你在面试算法题时毫无思路,或缺乏基本的算法复杂度分析等能力,被扣分也几乎是一定的。你被各方面都不比你差,算法问题表现比你更强的面试者干掉,也是很有可能的。

说了那么多,总结起来只有一句:“因为公司面算法而义愤填膺的,肯定是面试挂掉了而不知道自己究竟为什么挂掉了的。”

我觉得未来的面试都改成综艺节目那种形式,四个人一组,现场用答题板答题,这样被刷掉的就不会有那么多怨言了……

PS: 爱抱怨的还是少数。我遇到的面试者中,还是有不少虽然我没有录取(不符合岗位需求),但性格和沟通上还是很喜欢的孩子的。

======================================================

算法题是用来衡量你思考和解决问题的能力的。如果是大公司的研发岗位,面一些很难的算法题我也不觉得为过,当然,不代表一定要答出最完美的答案,更重要的是你的思考、沟通、验证、以及执行过程。我当初在面试百度的时候,面的是一个算是很高端的字符串匹配题,最完美的答案(改进版AC自动机)我当时是既不知道又是即使知道了也写不出来,然而我给出了我能力范围内最漂亮的答案(后缀数组),复杂度虽然多了一个lgN,但面试官也看到了我的分析能力以及思考过程的清晰、方案的完整度以及快速可实施性,后来一样还是过了。至于“ACM级别”,我想你太小瞧ACM了,真的,就这道题目,在ACM圈子里是最low的模板题而已,稍微集训过几个月的人都会,完全不值得讨论……

至于“没本事不要设立高门槛”,我倒是觉得,不管有没有本事,有钱就有资格设置高门槛。至于门槛是设在这种看似不直接产生作用的算法能力上,还是设在什么管理、项目经验上,还是设在外貌性别上,这是企业站在自己的角度根据自己的需求选择的,你觉得不合适,大可选择别的企业,而不是到处抱怨。大企业,以及大企业出身的管理人员,尤其是面试应届毕业生的时候,都有可能会更倾向于成长型的员工。这种情况下,不面算法面什么?面你行业背景吗?面你项目经历吗?

可笑死了,没本事就嘲笑别人没本事。

DomDomm 发表于 2021-7-4 06:43

在微博上看到的:“玩算法的码农,打拼靠蓝条,像是法师。数学就等于蓝条最大值,数学差,魔法值不高,很快就到瓶颈了。外语影响回蓝速度。经验和智力加急速和穿透的。不玩算法的码农,像是战士,打拼靠血条,体质加生命,精神加生命回复,经验和敏捷加急速和破甲。”
页: [1] 2 3
查看完整版本: 为什么最难不过二叉树的算法出现在面试题中都会被应聘者抱怨?