a*******n
发帖数: 112 | 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~ |
f******n
发帖数: 640 | |
s****n
发帖数: 147 | 3 多谢LZ！麻烦问下，是总共面了4轮，每轮都有coding吗？ |
a*******n
发帖数: 112 | 4 一共六轮吧，如果中间吃饭那个也算。有三轮做题，我贴了两轮的，另外一轮的题目
是一个多线程的设计题，我忘了所以没贴。
其他几轮有manager面试，还有一些架构设计之类的。 |
t***t
发帖数: 6066 | 5 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。 |
l*****a
发帖数: 14598 | 6 算sqrt是要整数,还是小数也要?
【在 a*******n 的大作中提到】
: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
|
l*****a
发帖数: 14598 | 7 人家也许就是想让你解释呢
【在 t***t 的大作中提到】
: 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。
|
g*****g
发帖数: 212 | |
h********3
发帖数: 2075 | 9 KMP算法实际用途很小。本质上，如果真的要进行大规模字符串的查询，一般都用index
的办法，suffix array之类的办法。真的上大规模匹配之后，KMP和直接一个一个匹配
没多大本质区别，五十步和百步的区别，解决不了问题本质。
【在 t***t 的大作中提到】
: 难道米国鬼子都不学KMP算法？上回狗家一个题也是。我说用KMP，他不懂。
|
c******0
发帖数: 260 | 10 最后一题 全排列的，LZ 是怎么用swap 递归的？ 我不是很清楚LZ的思路， 能不能让
我学习一下~~
还有算 sqrt（） 是要精确到小数点么？ 牛顿法完全木有听过。。。膜拜LZ ！！
【在 a*******n 的大作中提到】
: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
|
|
|
e***a
发帖数: 1661 | 11 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***8
发帖数: 510 | 12 其实现在的面试都挺傻逼的，在一个真正的不是闹着玩的项目里，算法战多大比例呀？
GOOGLE一下就有了，需求分析，设计，文档，测试，人员配备，协调等等，才是一个老
年工程
是应该真正做的，也没法GOOGLE到，算法考考NEW GRAD还可以。楼主看着像有多年经验
的人，应该也算是某个DOMAIN，比如PERFORMANCE， BACKEND，DATA，I18N等其中一个
方面的专家了，L一点都不CARE这些，只问算法？
当然存在即是合理，谁也没办法，
【在 e***a 的大作中提到】
: what is your focus area in software domain?
|
P**H
发帖数: 1897 | 13 sqrt()在leetcode上必须用牛顿，binary search解法会time out。 |
l*****a
发帖数: 14598 | 14 不信
BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么
【在 P**H 的大作中提到】
: sqrt()在leetcode上必须用牛顿，binary search解法会time out。
|
j***x
发帖数: 3 | 15 乱说了吧 :)
@lz, 不懂为什么一开始就上牛顿迭代,KMP? 策略上也该让面试官先提到再说啊
【在 P**H 的大作中提到】
: sqrt()在leetcode上必须用牛顿，binary search解法会time out。
|
a*******n
发帖数: 112 | 16 //hand
确实是完全不关心过去的项目经历，问也只是象征性的让说上几句自己做过的东西，呵
呵。
【在 f***8 的大作中提到】
: 其实现在的面试都挺傻逼的，在一个真正的不是闹着玩的项目里，算法战多大比例呀？
: GOOGLE一下就有了，需求分析，设计，文档，测试，人员配备，协调等等，才是一个老
: 年工程
: 是应该真正做的，也没法GOOGLE到，算法考考NEW GRAD还可以。楼主看着像有多年经验
: 的人，应该也算是某个DOMAIN，比如PERFORMANCE， BACKEND，DATA，I18N等其中一个
: 方面的专家了，L一点都不CARE这些，只问算法？
: 当然存在即是合理，谁也没办法，
|
a*******n
发帖数: 112 | 17 google一下就有了啊，全排列：
http://www.cnblogs.com/dragonpig/archive/2010/01/21/1653680.htm
【在 c******0 的大作中提到】
: 最后一题 全排列的，LZ 是怎么用swap 递归的？ 我不是很清楚LZ的思路， 能不能让
: 我学习一下~~
: 还有算 sqrt（） 是要精确到小数点么？ 牛顿法完全木有听过。。。膜拜LZ ！！
|
S*******l
发帖数: 125 | 18 活该 ！！
当你面试别人时候， 特别是中国人的时候， 为什么不大把大把地让国人过关？？？
现在马共抱怨裸印的统治， 活该 ！！！ |
a*******n
发帖数: 112 | 19 我同意，问sqrt太蛋疼了。牛顿法算是一种迭代的思想，和计算机还是能扯上点关系的。
【在 l*****a 的大作中提到】
: 不信
: BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么
|
P**H
发帖数: 1897 | 20 我的错。我用double算的太精确了，所以time out。后来只算int解就好了。
另外，计算机本来就是数学的一个很小的子集。求sqrt()，暴力O(n)是一种，binary
search是一种，牛顿也是一种。比较下来，牛顿收敛更快。但不能说谁更数学，谁更计
算机。或者说优化解的是数学的，笨方法，或者暴力解更“计算机”一些。
算法就是先证明了这个方法时候是正确，比别的方法更加优化;然后用if，for去实现这
个已经证明过的方法。
定义问题因人而异。严格的说面试官未必就全是对的，至少是有争议的。但最重要的一
点，人为刀俎，面试就按面试官的来。
【在 l*****a 的大作中提到】
: 不信
: BTW 我同意面世官的观点,牛顿跟计算机根本没关系,用这个的话想不出来要考察什么
|
|
|
l*****a
发帖数: 14598 | 21 计算机的课程学过牛顿?
还有那个fibonacci数列的lgn solution.也是同样问题。
【在 P**H 的大作中提到】
: 我的错。我用double算的太精确了，所以time out。后来只算int解就好了。
: 另外，计算机本来就是数学的一个很小的子集。求sqrt()，暴力O(n)是一种，binary
: search是一种，牛顿也是一种。比较下来，牛顿收敛更快。但不能说谁更数学，谁更计
: 算机。或者说优化解的是数学的，笨方法，或者暴力解更“计算机”一些。
: 算法就是先证明了这个方法时候是正确，比别的方法更加优化;然后用if，for去实现这
: 个已经证明过的方法。
: 定义问题因人而异。严格的说面试官未必就全是对的，至少是有争议的。但最重要的一
: 点，人为刀俎，面试就按面试官的来。
|
m******s
发帖数: 1469 | 22 Bless
【在 a*******n 的大作中提到】
: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
|
T*****u
发帖数: 7103 | 23 sqrt用binary search也行吧
【在 l*****a 的大作中提到】
: 算sqrt是要整数,还是小数也要?
|
A*********c
发帖数: 430 | 24 多谢lz。
【在 a*******n 的大作中提到】
: 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
: 就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
: 吧。
: - 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: 一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
: 栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
: 要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
: 还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
: 一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
|
A*********c
发帖数: 430 | 25 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****f
发帖数: 138 | |
