140有必要pp么 - 未名空间MITBBS历史存档

a*n2017-02-23 08:02

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~

S*32017-02-23 08:02

2 楼

今日早盘沪深两市双双低开，沪指开在3617点，下跌29点，跌幅0.04%；深成指开在
12390点，下跌62点，跌幅0.37%，两市集合竞价成交92.7亿。两市低开随后震荡走高，
10.40分附近券商板块启动，带动沪指强势翻红。盘中数字电影、环保、充电桩等表现
强势，截至收盘沪指报收于3662点，上涨15点，板块上券商、文化传媒、多元金融等板
块涨幅居前，航空运输、港口、汽车制造概念等板块跌幅居前。
早盘沪指低开随后震荡走高，券商板块重新启动带动沪指反弹，而昨日强势的银行板块
早盘则呈现低开低走的走势，从银行券商这一来一回之间我们发现资金成流出状态，不
排除有获利盘获利了结。成交量方面早盘量能明显出现萎缩，说明投资者在操作山并不
积极。综合来看财富龙认为虽然临近尾盘权重板块强势拉升，但是由于近期沪指连续上
涨盘中积累较大的获利盘，因此不排除主力资金借助银行券商的拉升出货，因此在操作
上不要被早盘的反弹所诱惑，控制仓位保持一定的清醒。

d*n2017-02-23 08:02

3 楼

公司好像默认是regular process。要pp要么要找mgr。要么自己出。值得pp么？还是可
以先submit regular。如果mgr同意再追加pp？

f*n2017-02-23 08:02

4 楼

thanks and bless

s*y2017-02-23 08:02

5 楼

从小我爸妈就教育我：能用钱摆平的事，都不算大事。
几十年后，当我面临相同境地的时候，我毫不犹豫的选择了自己出钱pp……

【在 d******n 的大作中提到】

: 公司好像默认是regular process。要pp要么要找mgr。要么自己出。值得pp么？还是可
: 以先submit regular。如果mgr同意再追加pp？

s*n2017-02-23 08:02

6 楼

多谢LZ！麻烦问下，是总共面了4轮，每轮都有coding吗？

P*r2017-02-23 08:02

7 楼

着急跳槽当然自己出钱都要pp.不急的话，慢慢来也无所谓。

【在 d******n 的大作中提到】

: 公司好像默认是regular process。要pp要么要找mgr。要么自己出。值得pp么？还是可
: 以先submit regular。如果mgr同意再追加pp？

a*n2017-02-23 08:02

8 楼

一共六轮吧，如果中间吃饭那个也算。有三轮做题，我贴了两轮的，另外一轮的题目
是一个多线程的设计题，我忘了所以没贴。
其他几轮有manager面试，还有一些架构设计之类的。

w*32017-02-23 08:02

9 楼

如果工作一周以上才能赚到PP的钱，并且不急，那就等等。
如果3天就可以赚到这个钱，那就PP吧。

【在 d******n 的大作中提到】

: 公司好像默认是regular process。要pp要么要找mgr。要么自己出。值得pp么？还是可
: 以先submit regular。如果mgr同意再追加pp？

t*t2017-02-23 08:02

10 楼

难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。

a*m2017-02-23 08:02

11 楼

以前有140么？如果没有的话俺脚着pp还是值得的，如果有的话就不用着急了。

l*a2017-02-23 08:02

12 楼

算sqrt是要整数,还是小数也要?

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

c*32017-02-23 08:02

13 楼

如果不是缺这$1225，有140也PP啊，别像某些倒霉的XD，熬了8个月10个月，最后还是
忍不住花钱PP了....

【在 a********m 的大作中提到】

: 以前有140么？如果没有的话俺脚着pp还是值得的，如果有的话就不用着急了。

l*a2017-02-23 08:02

14 楼

人家也许就是想让你解释呢

【在 t***t 的大作中提到】

: 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。

d*n2017-02-23 08:02

15 楼

谢谢大家都回复。 Mgr是中国人，还是很帮忙的。说approval了. 可以公司support pp

【在 c******3 的大作中提到】

: 如果不是缺这$1225，有140也PP啊，别像某些倒霉的XD，熬了8个月10个月，最后还是
: 忍不住花钱PP了....

g*g2017-02-23 08:02

16 楼

以我的经验。运气加表达。

h*32017-02-23 08:02

17 楼

KMP算法实际用途很小。本质上，如果真的要进行大规模字符串的查询，一般都用index
的办法，suffix array之类的办法。真的上大规模匹配之后，KMP和直接一个一个匹配
没多大本质区别，五十步和百步的区别，解决不了问题本质。

【在 t***t 的大作中提到】

: 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。

c*02017-02-23 08:02

18 楼

最后一题全排列的，LZ 是怎么用swap 递归的？我不是很清楚LZ的思路，能不能让
我学习一下~~
还有算 sqrt（）是要精确到小数点么？牛顿法完全木有听过。。。膜拜LZ ！！

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

e*a2017-02-23 08:02

19 楼

what is your focus area in software domain?

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

f*82017-02-23 08:02

20 楼

其实现在的面试都挺傻逼的，在一个真正的不是闹着玩的项目里，算法战多大比例呀？
GOOGLE一下就有了，需求分析，设计，文档，测试，人员配备，协调等等，才是一个老
年工程
是应该真正做的，也没法GOOGLE到，算法考考NEW GRAD还可以。楼主看着像有多年经验
的人，应该也算是某个DOMAIN，比如PERFORMANCE， BACKEND，DATA，I18N等其中一个
方面的专家了，L一点都不CARE这些，只问算法？
当然存在即是合理，谁也没办法，

【在 e***a 的大作中提到】

: what is your focus area in software domain?

P*H2017-02-23 08:02

21 楼

sqrt()在leetcode上必须用牛顿，binary search解法会time out。

l*a2017-02-23 08:02

22 楼

不信
BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么

【在 P**H 的大作中提到】

: sqrt()在leetcode上必须用牛顿，binary search解法会time out。

j*x2017-02-23 08:02

23 楼

乱说了吧 :)
@lz, 不懂为什么一开始就上牛顿迭代,KMP? 策略上也该让面试官先提到再说啊

【在 P**H 的大作中提到】

: sqrt()在leetcode上必须用牛顿，binary search解法会time out。

a*n2017-02-23 08:02

24 楼

//hand
确实是完全不关心过去的项目经历，问也只是象征性的让说上几句自己做过的东西，呵
呵。

【在 f***8 的大作中提到】

: 其实现在的面试都挺傻逼的，在一个真正的不是闹着玩的项目里，算法战多大比例呀？
: GOOGLE一下就有了，需求分析，设计，文档，测试，人员配备，协调等等，才是一个老
: 年工程
: 是应该真正做的，也没法GOOGLE到，算法考考NEW GRAD还可以。楼主看着像有多年经验
: 的人，应该也算是某个DOMAIN，比如PERFORMANCE， BACKEND，DATA，I18N等其中一个
: 方面的专家了，L一点都不CARE这些，只问算法？
: 当然存在即是合理，谁也没办法，

a*n2017-02-23 08:02

25 楼

google一下就有了啊，全排列：
http://www.cnblogs.com/dragonpig/archive/2010/01/21/1653680.htm

【在 c******0 的大作中提到】

: 最后一题全排列的，LZ 是怎么用swap 递归的？我不是很清楚LZ的思路，能不能让
: 我学习一下~~
: 还有算 sqrt（）是要精确到小数点么？牛顿法完全木有听过。。。膜拜LZ ！！

S*l2017-02-23 08:02

26 楼

活该！！
当你面试别人时候，特别是中国人的时候，为什么不大把大把地让国人过关？？？
现在马共抱怨裸印的统治，活该！！！

a*n2017-02-23 08:02

27 楼

我同意，问sqrt太蛋疼了。牛顿法算是一种迭代的思想，和计算机还是能扯上点关系的。

【在 l*****a 的大作中提到】

: 不信
: BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么

P*H2017-02-23 08:02

28 楼

我的错。我用double算的太精确了，所以time out。后来只算int解就好了。
另外，计算机本来就是数学的一个很小的子集。求sqrt()，暴力O(n)是一种，binary
search是一种，牛顿也是一种。比较下来，牛顿收敛更快。但不能说谁更数学，谁更计
算机。或者说优化解的是数学的，笨方法，或者暴力解更“计算机”一些。
算法就是先证明了这个方法时候是正确，比别的方法更加优化;然后用if，for去实现这
个已经证明过的方法。
定义问题因人而异。严格的说面试官未必就全是对的，至少是有争议的。但最重要的一
点，人为刀俎，面试就按面试官的来。

【在 l*****a 的大作中提到】

: 不信
: BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么

l*a2017-02-23 08:02

29 楼

计算机的课程学过牛顿?
还有那个fibonacci数列的lgn solution.也是同样问题。

【在 P**H 的大作中提到】

: 我的错。我用double算的太精确了，所以time out。后来只算int解就好了。
: 另外，计算机本来就是数学的一个很小的子集。求sqrt()，暴力O(n)是一种，binary
: search是一种，牛顿也是一种。比较下来，牛顿收敛更快。但不能说谁更数学，谁更计
: 算机。或者说优化解的是数学的，笨方法，或者暴力解更“计算机”一些。
: 算法就是先证明了这个方法时候是正确，比别的方法更加优化;然后用if，for去实现这
: 个已经证明过的方法。
: 定义问题因人而异。严格的说面试官未必就全是对的，至少是有争议的。但最重要的一
: 点，人为刀俎，面试就按面试官的来。

m*s2017-02-23 08:02

30 楼

Bless

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

T*u2017-02-23 08:02

31 楼

sqrt用binary search也行吧

【在 l*****a 的大作中提到】

: 算sqrt是要整数,还是小数也要?

A*c2017-02-23 08:02

32 楼

多谢lz。

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

A*c2017-02-23 08:02

33 楼

btw, 我觉得lz小看面试官了，他要是问strstr的话必然知道KMP。
这毕竟是他挑的题。你想他一个题面了那么多人，肯定有N个人曾经写过KMP，看都看会
了。
我觉得能把KMP解释清楚的人的个数远远小于能写出来的人个数。
他应该是在求解释。

【在 a*******n 的大作中提到】

: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。

b*f2017-02-23 08:02

34 楼

Mark