f*****w
发帖数: 2602 | 1 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
第一次
居然是大牛Andrew Ng的学生；
为什么要FB
如果来了FB 最想做的事情 project 会是什么
然后问了个简历上的问题
然后 两个技术问题 很简单的
1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
地卡了很
久 最后给了一个不是很好的答案(O(lgn*lgn))。 他最后告诉我了更好的方法, 这个方
法确实比
我的好很多,lgN时间O(1)空间 就可以了。
我以为我挂了，但是有了第二次
这次好一些
1) 为什么FB
2) 简历上的好几个问题
3) 技术问题是找一个binary tree的叶子的最少depth。 我很stupid地给了个递归方法
。他说
不行啊， 要是很不balance的话，效率会很低。 我又很stupid的说那我会randomize每
次递归
的时候是左子树还是右子树，这样average 复杂度会低一些。
他忍无可忍了，说他expect something like BFS
我当时真想抽自己， 然后写了个BFS， 还被挑了个bug。
这时候才25分钟，他居然跟我说让我问他问题了开始... 不知道是不是表示他没有耐心了
这下估计是真挂了，然后我就问了些他现在做的project，工作氛围 诸如此类 后来
就结束了。
感觉跟其他人比起来很非典型...
希望还能有第三次电面... |
g**e
发帖数: 6127 | 2 i think you are doing fine.
stupid
【在 f*****w 的大作中提到】
: 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
: 第一次
: 居然是大牛Andrew Ng的学生；
: 为什么要FB
: 如果来了FB 最想做的事情 project 会是什么
: 然后问了个简历上的问题
: 然后 两个技术问题 很简单的
: 1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
: 2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
: 地卡了很
|
d*******l
发帖数: 338 | 3 lz面的是fb的summer intern吗？据说summer的已经截止了啊。。
另外对于你第一面的第二个问题，是不是可以用这样的解法
node * find(node *root, node *upper_bound, int x)
{
if(root == NULL) return upper_bound;
if(root->value <= x) return find(root->right, upper_bound, x);
else return find(root->left, root, x);
}
最开始的时候uppder_bound传入一个值为无穷大的哨兵节点就行。
这个复杂度是log的无疑，bst应该不用考虑退化的情况吧？至于空间，如果考虑尾递归
的优化应该可以说是O(1)的 |
g*********s
发帖数: 1782 | 4 你说的尾递归是怎么回事？
【在 d*******l 的大作中提到】
: lz面的是fb的summer intern吗？据说summer的已经截止了啊。。
: 另外对于你第一面的第二个问题，是不是可以用这样的解法
: node * find(node *root, node *upper_bound, int x)
: {
: if(root == NULL) return upper_bound;
: if(root->value <= x) return find(root->right, upper_bound, x);
: else return find(root->left, root, x);
: }
: 最开始的时候uppder_bound传入一个值为无穷大的哨兵节点就行。
: 这个复杂度是log的无疑，bst应该不用考虑退化的情况吧？至于空间，如果考虑尾递归
|
f*****w
发帖数: 2602 | 5
full time的position 不是inern
你的想法是正确的 递归的时候记住当前最大的值
【在 d*******l 的大作中提到】
: lz面的是fb的summer intern吗？据说summer的已经截止了啊。。
: 另外对于你第一面的第二个问题，是不是可以用这样的解法
: node * find(node *root, node *upper_bound, int x)
: {
: if(root == NULL) return upper_bound;
: if(root->value <= x) return find(root->right, upper_bound, x);
: else return find(root->left, root, x);
: }
: 最开始的时候uppder_bound传入一个值为无穷大的哨兵节点就行。
: 这个复杂度是log的无疑，bst应该不用考虑退化的情况吧？至于空间，如果考虑尾递归
|
g*********s
发帖数: 1782 | 6 我觉得你表现一般。为什么觉得第二次比第一次好些？
但对于FB这种热门公司来说，面试是否成功，很大程度看面试官的性格和心情。另外你
的背景似乎和他
们需求吻合？这样会有加分。
【在 f*****w 的大作中提到】
:
: full time的position 不是inern
: 你的想法是正确的 递归的时候记住当前最大的值
|
g*********s
发帖数: 1782 | 7 O(1)是通过尾递归吗？我估计这里的O(1)忽略了递归开销吧。
【在 f*****w 的大作中提到】
:
: full time的position 不是inern
: 你的想法是正确的 递归的时候记住当前最大的值
|
g**u
发帖数: 583 | 8
就是说
尾递归可以改成iterative solution，因为程序只有一条执行路径。
借用ls的思路， 改写iterative solution:
node * find(node * root, node * upper, int val)
{
if(!root)
return upper;
while(root)
{
if(root->value<=val)
root=root->right;
else
{
upper=root;
root=root->left;
}
}
return upper;
}
【在 g*********s 的大作中提到】
: 你说的尾递归是怎么回事？
|
g*********s
发帖数: 1782 | 9 写错了吧。
【在 g**u 的大作中提到】
:
: 就是说
: 尾递归可以改成iterative solution，因为程序只有一条执行路径。
: 借用ls的思路， 改写iterative solution:
: node * find(node * root, node * upper, int val)
: {
: if(!root)
: return upper;
: while(root)
: {
|
g**u
发帖数: 583 | 10
恩，搞反了， 已经改好了
【在 g*********s 的大作中提到】
: 写错了吧。
|
|
|
n*******l
发帖数: 19 | 11 感觉你第一次能过是侥幸，第二次估计就死了，FB的电面每轮大都三道technical
question，面试官如果人品一般的话，你表现不完美就意味着你要挂，特别nice的能让
你到下一轮，你自己都想抽自己了你还想让面试官让你过？move on 吧
stupid
【在 f*****w 的大作中提到】
: 还不知道接下来结果怎么样 不过还是趁有空先回馈一下版面
: 第一次
: 居然是大牛Andrew Ng的学生；
: 为什么要FB
: 如果来了FB 最想做的事情 project 会是什么
: 然后问了个简历上的问题
: 然后 两个技术问题 很简单的
: 1. 实现一个strstr() 我说我可写不出KMP， 他说没事没事 就写个普通的就好
: 2. 给定一个没有通往父节点的连接的BST, 找到大于x的最小的那个节点。 我很stupid
: 地卡了很
|
d*******l
发帖数: 338 | 12 差不多就是这个意思，我对尾递归也是一知半解。其实用递归的方法很少有人会考虑栈
上的空间，这里提到尾递归是因为很多编译器会对尾递归进行优化，这样就能比较严格
的认为空间是O(1)
【在 g**u 的大作中提到】
:
: 恩，搞反了， 已经改好了
|
g*********s
发帖数: 1782 | 13 Node* upper_bound(Node* root, int t)
{
Node* x = root;
Node* upper = NULL;
while ( x != NULL ) {
if ( x->data <= t ) {
x = x->right;
}
else {
upper = x;
x = x->left;
}
}
return upper;
}
【在 g**u 的大作中提到】
:
: 恩，搞反了， 已经改好了
|
g*********s
发帖数: 1782 | 14 btw, i think the complexity O(lgN) requires the bst balanced.
【在 g*********s 的大作中提到】
: Node* upper_bound(Node* root, int t)
: {
: Node* x = root;
: Node* upper = NULL;
: while ( x != NULL ) {
: if ( x->data <= t ) {
: x = x->right;
: }
: else {
: upper = x;
|
f*****w
发帖数: 2602 | 15 大家有没有谁知道 FB 一般几次电面？ 还有大概怎么个评价法？ |
