140有必要pp么# EB23 - 劳工卡
a*n
1 楼
上周面的,从早9点到晚5点,说好大概一周以内给消息,结果什么消息也没有,是不是
就是婉拒了?也罢,既然没有签什么nondisclosure agreement,我就贡献几道面试题
吧。
- 一个双向链表,带头尾指针,每个节点可能都有父节点和子节点,每个父子节点又是
一个链表。要求把它拍扁,顺序随意。
一开始说了一个类似DFS的算法,他说我的空间复杂度是O(N),我说递归的方法如果堆
栈空间也算的话确实是O(N),但他咬定我临时放节点的地方也是O(N),楞说我存节点需
要分配额外空间,我就很纳闷,这节点都已经是双向链表了,里面有next/prev,为毛
还需要分配O(N)的空间来存这些节点?坚持跟他讨论半天,把节点定义什么都给出来,
一点一点说明白,才证明是他理解有问题,幸好还算坚持,不然就被他带沟里去了。
当然这个算法有更好的解,既然不要求顺序,而且有头尾指针,每次把父子链表接到尾
巴后面就可以了。连递归都省了。
- 算sqrt()
我提出用牛顿法,刚画完坐标系就说不让用。原话是“newton's method is for
mathematics, please use computer science“。于是我只好说,不用数学的方法,那
你大概就只能从2到 n/2 一个一个数去试了,看结果和除数哪个更接近,在选择数的时
候也许还可以用折半的方法,但不管这样算出来的误差会挺大。他就说无所谓,把步长
改成小于1,比如0.001,然后再从1.001, 1.002, 1.003 ...这样挨个试就可以了。最
后让分析了一下这样的算法复杂度。
- 字符串匹配
接下来两轮很狗血,问我字符串匹配,我先说了一个暴力方法,然后就说可以用KMP算
法来做,但两个面试官似乎没有听说过KMP算法。于是花了将近半个多小时,解释了很
久,给了好几个例子,最后他俩似乎明白了。我又给出了一个没有KMP那么复杂,但是
也可行的一种办法,最后就算过去了。
感受:也许是我表达能力有问题,但是临时向两个没听说过KMP算法的人解释KMP,真不
是一件容易的事情。
- 全排列
这个按理说是很简单的,很快就写出来一个用swap递归的方法,结果,还是上面这两个
面试官,似乎也从没见过用这种方法。于是又一点一点解释,直到把每一层调用的参数
和局部变量以及排列的情况都列出来到时间了才算结束。
感受:作为一个面试过很多人,也被别人面试过很多的人,我还是能分清楚面试官想考
考你什么,和面试官没见过这个东西时的表情的。所以面对这样的面试,真不知道他们
会给出什么评价。
最后祝大家马年马上都有大offer~
就是婉拒了?也罢,既然没有签什么nondisclosure agreement,我就贡献几道面试题
吧。
- 一个双向链表,带头尾指针,每个节点可能都有父节点和子节点,每个父子节点又是
一个链表。要求把它拍扁,顺序随意。
一开始说了一个类似DFS的算法,他说我的空间复杂度是O(N),我说递归的方法如果堆
栈空间也算的话确实是O(N),但他咬定我临时放节点的地方也是O(N),楞说我存节点需
要分配额外空间,我就很纳闷,这节点都已经是双向链表了,里面有next/prev,为毛
还需要分配O(N)的空间来存这些节点?坚持跟他讨论半天,把节点定义什么都给出来,
一点一点说明白,才证明是他理解有问题,幸好还算坚持,不然就被他带沟里去了。
当然这个算法有更好的解,既然不要求顺序,而且有头尾指针,每次把父子链表接到尾
巴后面就可以了。连递归都省了。
- 算sqrt()
我提出用牛顿法,刚画完坐标系就说不让用。原话是“newton's method is for
mathematics, please use computer science“。于是我只好说,不用数学的方法,那
你大概就只能从2到 n/2 一个一个数去试了,看结果和除数哪个更接近,在选择数的时
候也许还可以用折半的方法,但不管这样算出来的误差会挺大。他就说无所谓,把步长
改成小于1,比如0.001,然后再从1.001, 1.002, 1.003 ...这样挨个试就可以了。最
后让分析了一下这样的算法复杂度。
- 字符串匹配
接下来两轮很狗血,问我字符串匹配,我先说了一个暴力方法,然后就说可以用KMP算
法来做,但两个面试官似乎没有听说过KMP算法。于是花了将近半个多小时,解释了很
久,给了好几个例子,最后他俩似乎明白了。我又给出了一个没有KMP那么复杂,但是
也可行的一种办法,最后就算过去了。
感受:也许是我表达能力有问题,但是临时向两个没听说过KMP算法的人解释KMP,真不
是一件容易的事情。
- 全排列
这个按理说是很简单的,很快就写出来一个用swap递归的方法,结果,还是上面这两个
面试官,似乎也从没见过用这种方法。于是又一点一点解释,直到把每一层调用的参数
和局部变量以及排列的情况都列出来到时间了才算结束。
感受:作为一个面试过很多人,也被别人面试过很多的人,我还是能分清楚面试官想考
考你什么,和面试官没见过这个东西时的表情的。所以面对这样的面试,真不知道他们
会给出什么评价。
最后祝大家马年马上都有大offer~