x****r
发帖数: 99 | 1 刚刚面完FB第二轮technical面试，估计悲剧了：（
没考任何复杂的算法，面试就盯着一个reverse print链表的复杂度，和n种不同的方法
问O(N)的常
数系数问题，具体到了recursive call里面每次function call的开销多少byte。。
唉，，等待拒信中 ：/ |
f****4
发帖数: 1359 | |
x****r
发帖数: 99 | 3 基本上就是先让我5分钟写了两个链表反向打印的程序，
一个我用了stack，一个用了recursive
然后他问两种的worst case space complexity是多少，我说O(N),然后他就问具体是多
少n，然
后我就和他说了什么stack实现啊，还有function call的overhead什么的然后他就一直
在问
function call每次要用掉多少stack的空间？（有code ptr, parameter等等）
然后他就问那怎么找space是constant的解法（扫描n遍，naive的方法）
然后又问怎么找small o(N2) Time, Small o(N) Space的方法
我就和他说了一个divede and conquer
反正就是围着这个破题狂问，烦死了。。
【在 f****4 的大作中提到】
: 能再具体一点么？
|
k**********i
发帖数: 177 | 4 我也很悲剧。。。好几天了 等待拒信中。。。
【在 x****r 的大作中提到】
: 刚刚面完FB第二轮technical面试，估计悲剧了：（
: 没考任何复杂的算法，面试就盯着一个reverse print链表的复杂度，和n种不同的方法
: 问O(N)的常
: 数系数问题，具体到了recursive call里面每次function call的开销多少byte。。
: 唉，，等待拒信中 ：/
|
s****t
发帖数: 36 | 5 我也是啊，头两轮facebook都面得好好啊，都是第二天就联系，第三轮写的bug有点多
，是个中国姐姐，估计也是黄了啊。上次google的也是这样啊，头两轮都不错，第三轮
就死在一个台湾哥哥手里，哎，悲啊，amazon两轮店面完了，自我感觉面得不错，但是
两个星了也没消息~三轮店面的真的好难熬啊 |
s****t
发帖数: 36 | 6 我也是啊，头两轮facebook都面得好好啊，都是第二天就联系，第三轮写的bug有点多
，是个中国姐姐，估计也是黄了啊。上次google的也是这样啊，头两轮都不错，第三轮
就死在一个台湾哥哥手里，哎，悲啊，amazon两轮店面完了，自我感觉面得不错，但是
两个星了也没消息~三轮店面的真的好难熬啊 |
x****r
发帖数: 99 | 7 恩，，第三面是杀手啊~~~~ ：/
【在 s****t 的大作中提到】
: 我也是啊，头两轮facebook都面得好好啊，都是第二天就联系，第三轮写的bug有点多
: ，是个中国姐姐，估计也是黄了啊。上次google的也是这样啊，头两轮都不错，第三轮
: 就死在一个台湾哥哥手里，哎，悲啊，amazon两轮店面完了，自我感觉面得不错，但是
: 两个星了也没消息~三轮店面的真的好难熬啊
|
x****r
发帖数: 99 | 8 follow up, 再一轮tech interview，，，折磨人无极限啊！ |
l*****a
发帖数: 14598 | 9 there is a classical interview question to let u reverse the
singly linked list.
that is also work for this issue.
i think u missed this solution which will scan twice but no
stack/function call cost
【在 x****r 的大作中提到】
: 刚刚面完FB第二轮technical面试，估计悲剧了：（
: 没考任何复杂的算法，面试就盯着一个reverse print链表的复杂度，和n种不同的方法
: 问O(N)的常
: 数系数问题，具体到了recursive call里面每次function call的开销多少byte。。
: 唉，，等待拒信中 ：/
|
h****r
发帖数: 2056 | 10 Agree. A variation of the classic reversing singly linked list issue.
【在 l*****a 的大作中提到】
: there is a classical interview question to let u reverse the
: singly linked list.
: that is also work for this issue.
: i think u missed this solution which will scan twice but no
: stack/function call cost
|
|
|
x****r
发帖数: 99 | 11 Hmm, how does that one work exactly, I do know by naive approach(scanning
it n times) you could use O(N^2) time with constant space to do it.
Yea, ur right about there're many alternate solutions out there, but the
interviewer wasn't asking me for all of those, instead he picked a few of
them and ask me to analyze and break them down in the very detailed way.
【在 l*****a 的大作中提到】
: there is a classical interview question to let u reverse the
: singly linked list.
: that is also work for this issue.
: i think u missed this solution which will scan twice but no
: stack/function call cost
|
h***o
发帖数: 30 | 12 I guess.
First you reverse the link list in a loop.
Then reverse the link list back and print the key in a second loop.
This uses O(n) time, O(1) space.
【在 x****r 的大作中提到】
: Hmm, how does that one work exactly, I do know by naive approach(scanning
: it n times) you could use O(N^2) time with constant space to do it.
: Yea, ur right about there're many alternate solutions out there, but the
: interviewer wasn't asking me for all of those, instead he picked a few of
: them and ask me to analyze and break them down in the very detailed way.
|
x****r
发帖数: 99 | 13 Yuup, I did mention that one, he said that's OK, but how about you are not
allowed to change it.
Anyways, it'd been quite annoying to torture me with this single problem,
instead of asking about anything else I've prepared for :/
【在 h***o 的大作中提到】
: I guess.
: First you reverse the link list in a loop.
: Then reverse the link list back and print the key in a second loop.
: This uses O(n) time, O(1) space.
|
x****r
发帖数: 99 | 14 Yuup, I did mention that one, he said that's OK, but how about you are not
allowed to change it.
Anyways, it'd been quite annoying to torture me with this single problem,
instead of asking about anything else I've prepared for :/
【在 h***o 的大作中提到】
: I guess.
: First you reverse the link list in a loop.
: Then reverse the link list back and print the key in a second loop.
: This uses O(n) time, O(1) space.
|
r****o
发帖数: 1950 | 15 存到一个stack里面再pop出来也可以，不过空间O(n)
【在 x****r 的大作中提到】
: Yuup, I did mention that one, he said that's OK, but how about you are not
: allowed to change it.
: Anyways, it'd been quite annoying to torture me with this single problem,
: instead of asking about anything else I've prepared for :/
|
x****r
发帖数: 99 | 16 恩，，我一开始就给了一个stack的解和一个recursive的
【在 r****o 的大作中提到】
: 存到一个stack里面再pop出来也可以，不过空间O(n)
|
s*******t
发帖数: 248 | 17 每次function call 开销多少byte如何来计算呢？
【在 x****r 的大作中提到】
: 刚刚面完FB第二轮technical面试，估计悲剧了：（
: 没考任何复杂的算法，面试就盯着一个reverse print链表的复杂度，和n种不同的方法
: 问O(N)的常
: 数系数问题，具体到了recursive call里面每次function call的开销多少byte。。
: 唉，，等待拒信中 ：/
|
l*****a
发帖数: 14598 | 18 其实你这个stack跟recursive几乎就是一回事
【在 x****r 的大作中提到】
: 恩，，我一开始就给了一个stack的解和一个recursive的
|
x****r
发帖数: 99 | 19 我也不清楚，但是他就是这样问的，我就和他说比如你要知道call你的function的地址
，那就是一个
word，然后有参数，还有base指针，然后他就叫我估计大小，然后问这样的话如果是O(
n)的算法，那
你得出的系数是多少这样。
【在 s*******t 的大作中提到】
: 每次function call 开销多少byte如何来计算呢？
|
x****r
发帖数: 99 | 20 原理是一样，但是实际用的空间不太一样呀，和stack的实现有关
【在 l*****a 的大作中提到】
: 其实你这个stack跟recursive几乎就是一回事
|
