w****a 发帖数: 710 | 1 10分钟面经系列,这次是T家。
上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。
刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why
T家。
然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。
给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点
4
4
/ \
2 1
\
3
答案就是413+42 = 455。
这个题倒没什么,拿到就问了他需不需要考虑big int的问题,他说不需要,int肯定够
用。那就放心写了。写完之后我怕有bug在纸上反复写各种test验证。他问我干啥,我
就说我在做“单元测试”。他就让我别在纸上画了直接在collabedit上写。我就把他给
的sample用函数流程走了一遍。。
随后就是一系列的follow up。我一开始给的解不是最优解(犯2了,啥也没想上来先用
了vector存所有路径下的数字,最后我逐个相加)。他也没说什么,因为代码本身没问
题,就是跟我说让我说出时间复杂度和空间复杂度。说空间复杂度的时候他就问我能不
能不用vector的,我当时心小凉了一把,立即改掉了,我加了个引用参数来存的sum,
每次sum+=xxx。在C++里用引用用惯了(后面才知道不是好习惯)。他没说什么,问我
现在的空间复杂度是多少,我说O(1),他说真的是O(1)么?我说是O(1)啊。他说如
果考虑递归的stack损耗呢?我说考虑堆栈消耗那就不是O(1)了,如果考虑这点,当这
个树很大的时候,还会stack overflow。他说提到stack overflow,你能说说函数调用
的栈空间耗费在哪里?我说参数压栈需要空间,局部变量要栈空间,栈指针也是。他说
那么如果现在我们考虑堆栈损耗,空间复杂度是多少。我说那就是O(n)了,n取决于递
归深度。然后又追着问我如何测量递归深度。我说在这个程序中递归深度就是当前节点
到最深叶子节点的depth。他说OK,又问了最后一个问题(我上面埋下的祸根)。他说
在并行开发情况下,用引用是会出问题的,让我把引用改掉。我只得立即改成传返回值
回去了。最后他终于说了句“现在看上去很不错了”。
面试题确实很简单,还好也没出bug,除了被他指出有两点需要improve的地方。关于引
用在并行环境下有问题这个真没想到。下次是要注意一下了。平时都是在单线程下编程
,这些地方很少注意到。希望能够拿到二面,求bless。
他最后还问我对概率熟不熟悉,我说我基本不熟悉。他说好那我就不问你了,这个也不
是必要的。当时松了口气哈哈。
PS.这次是打电话的,他说话我听得断断续续的,所以我说了很多sorry,有些关键问题
我让他写下来了。应该不影响吧。我跟他说了是电话线路问题。 |
f*******t 发帖数: 7549 | |
w****x 发帖数: 2483 | 3 bless....
一周没收到拒信楼主就过啦~~
楼主怎么不是两个面试一起的吗?? |
j*****y 发帖数: 1071 | 4 bless
F 家这么恐怖阿, 楼主答的挺好的阿
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
j*****y 发帖数: 1071 | 5 这里的多叉是怎么存的阿
struct Node
{
int val;
vector child
}
吗 ?
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
w****a 发帖数: 710 | 6 对,就这么存
【在 j*****y 的大作中提到】 : 这里的多叉是怎么存的阿 : struct Node : { : int val; : vector child : } : 吗 ? : : why
|
w****a 发帖数: 710 | 7 感谢bless,F家已经正式收到拒信啦。move on
【在 w****x 的大作中提到】 : bless.... : 一周没收到拒信楼主就过啦~~ : 楼主怎么不是两个面试一起的吗??
|
w****x 发帖数: 2483 | 8
我说的是T家
【在 w****a 的大作中提到】 : 感谢bless,F家已经正式收到拒信啦。move on
|
|
w****a 发帖数: 710 | 9 希望能过 哈哈 多谢多谢!!
【在 w****x 的大作中提到】 : : 我说的是T家
|
j*****y 发帖数: 1071 | 10 4
/ \
1 2
/ \
1 3
是 41 + 421 + 423 吗?
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
|
|
w****a 发帖数: 710 | 11 是,路径都加起来
【在 j*****y 的大作中提到】 : 4 : / \ : 1 2 : / \ : 1 3 : 是 41 + 421 + 423 吗? : : why
|
j*****y 发帖数: 1071 | 12 void sumOfNodes(TreeNode * root, vector &A, int &sum)
{
if(root->child.size() == 0)
{
int sub_sum = 0;
for(int i = 0; i < A.size() ; ++i)
{
sub_sum += 10 * sub_sum + A[i];
}
sub_sum += 10 * sub_sum + root->val;
sum += sub_sum;
return;
}
for(int i = 0; i < root->child.size(); ++i)
{
A.push_back(root->val);
int size = A.size();
sumOfNodes(root->child[i], A, sum)
A.resize(size);
}
return ;
}
【在 w****a 的大作中提到】 : 是,路径都加起来
|
w****a 发帖数: 710 | 13 我一开始也是这么写的,不过vector &A这玩意儿被鄙视啦,要让O(1)空间
【在 j*****y 的大作中提到】 : void sumOfNodes(TreeNode * root, vector &A, int &sum) : { : if(root->child.size() == 0) : { : int sub_sum = 0; : for(int i = 0; i < A.size() ; ++i) : { : sub_sum += 10 * sub_sum + A[i]; : } : sub_sum += 10 * sub_sum + root->val;
|
p****e 发帖数: 3548 | 14 int TreeSum(TreeNode * root, int prefix){
if(root) == NULL return 0;
prefix = prefix*10 + root->val;
if(root->left == NULL && root->right == NULL)
return prefix;
int sum = 0;
if(root->left)
sum = TreeSum(root->left, prefix);
if(root->right)
sum += TreeSum(root->right, prefix);
return sum;
}
【在 w****a 的大作中提到】 : 我一开始也是这么写的,不过vector &A这玩意儿被鄙视啦,要让O(1)空间
|
M********5 发帖数: 715 | 15 lz好像说的是多叉树
【在 p****e 的大作中提到】 : int TreeSum(TreeNode * root, int prefix){ : if(root) == NULL return 0; : prefix = prefix*10 + root->val; : if(root->left == NULL && root->right == NULL) : return prefix; : int sum = 0; : if(root->left) : sum = TreeSum(root->left, prefix); : if(root->right) : sum += TreeSum(root->right, prefix);
|
p****e 发帖数: 3548 | 16 哦, 不过一样的
【在 M********5 的大作中提到】 : lz好像说的是多叉树
|
w****a 发帖数: 710 | 17 是多叉树,不过就是这个做法
【在 p****e 的大作中提到】 : int TreeSum(TreeNode * root, int prefix){ : if(root) == NULL return 0; : prefix = prefix*10 + root->val; : if(root->left == NULL && root->right == NULL) : return prefix; : int sum = 0; : if(root->left) : sum = TreeSum(root->left, prefix); : if(root->right) : sum += TreeSum(root->right, prefix);
|
j*****y 发帖数: 1071 | 18 void sumOfNodes(TreeNode * root, int sub_sum, int &sum)
{
if(root->child.size() == 0)
{
sum += 10 * sub_sum + root->val;
return;
}
for(int i = 0; i < root->child.size(); ++i)
{
int tmp = 10 * sub_sum + root->val;
sumOfNodes(root->child[i], tmp, sum);
}
return ;
}
【在 w****a 的大作中提到】 : 是多叉树,不过就是这个做法
|
p*****2 发帖数: 21240 | |
w****x 发帖数: 2483 | 20
不愧是DFS大牛啊
【在 p*****2 的大作中提到】 : DFS就可以了。
|
|
|
l**b 发帖数: 457 | |
c***s 发帖数: 192 | 22 int sumTree(TreeNode *T, int x) {
int y = x * 10 + T->val, sum = 0;
if((T->child).size() == 0) return(y);
for(int i = 0; i < T->child.size(); i++)
sum += sumTree((T->child)[i], y);
return(sum);
}
int sumTree(TreeNode *T) {
if(!T) return(0);
return(sumTree(T, 0));
}
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
g********r 发帖数: 58 | 23 这个code行吗
int treesum(node n, prefix = 0)
if n == null return prefix
prefix = prefix*10 + n.val
sum = 0
for c in n.children:
sum += treesum(c, prefix)
return sum |
p*****p 发帖数: 379 | 24 有点不太清楚多线程下引用会有什么问题,能解释一下吗
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
w****a 发帖数: 710 | 25 同时写一个变量,不加锁会有问题的
【在 p*****p 的大作中提到】 : 有点不太清楚多线程下引用会有什么问题,能解释一下吗 : : why
|
p*****2 发帖数: 21240 | 26
scala应该没有问题吧?
【在 w****a 的大作中提到】 : 同时写一个变量,不加锁会有问题的
|
h***i 发帖数: 1970 | 27 scala 应该有同样的问题
【在 p*****2 的大作中提到】 : : scala应该没有问题吧?
|
p*****2 发帖数: 21240 | 28
为什么?
【在 h***i 的大作中提到】 : scala 应该有同样的问题
|
p****e 发帖数: 3548 | 29 scala有什么特殊机制避免冲突情况?
【在 p*****2 的大作中提到】 : : 为什么?
|
p*****2 发帖数: 21240 | 30
scala不需要用锁。
【在 p****e 的大作中提到】 : scala有什么特殊机制避免冲突情况?
|
|
|
p*****2 发帖数: 21240 | |
l*********u 发帖数: 19053 | 32 bless
why
【在 w****a 的大作中提到】 : 10分钟面经系列,这次是T家。 : 上次FB二面终于如期收到拒信,move on了。T家的一面希望大家bless啊。 : 刚开始给我一分钟时间问了我两个behavior问题,一个是我现在在做什么,一个是why : T家。 : 然后就开collabedit了,就写了一道题。题很简单,板上的XDJM们相信都能秒杀。 : 给一个多叉树和一个节点,求出这个节点所有path下来的数字的和。比如给出树和节点 : 4 : 4 : / \ : 2 1
|
h***i 发帖数: 1970 | 33 你写一个。准备用immutable,那个sum累加值怎么办?
【在 p*****2 的大作中提到】 : 这题刚刚收录到leetcode里。我做了一下放到博客了,不过这题是道简单题,没什么太 : 大的意思。 : http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html
|
p****e 发帖数: 3548 | 34 那多线程怎办
【在 p*****2 的大作中提到】 : 这题刚刚收录到leetcode里。我做了一下放到博客了,不过这题是道简单题,没什么太 : 大的意思。 : http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html
|
w****a 发帖数: 710 | 35 我觉得要是有一个网站专门收录经典follow up的就好了。
【在 p*****2 的大作中提到】 : 这题刚刚收录到leetcode里。我做了一下放到博客了,不过这题是道简单题,没什么太 : 大的意思。 : http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html
|
p*****2 发帖数: 21240 | 36
actor
【在 p****e 的大作中提到】 : 那多线程怎办
|
p*****2 发帖数: 21240 | 37
immutable的话不能改变变量,可以用常量来传递。
【在 h***i 的大作中提到】 : 你写一个。准备用immutable,那个sum累加值怎么办?
|
L*********r 发帖数: 9 | 38 int r = 0;
void dfs(NaryTreeNode node, int sum) {
if ( node == null )
r += sum;
sum = sum * 10 + node.val;
for ( NaryTreeNode child : node.children )
dfs( child, sum );
} |
p**********3 发帖数: 127 | 39 BF也是刚on site T家·~~~~真希望他能成功拿到~~FLAG是五岳~~T家是黄山啊~~
太TM难了~特别是纽约的T家~
BLESS My baby~~
同时bless 楼主~~ |
w****a 发帖数: 710 | |
|
|
j********x 发帖数: 2330 | 41 t倒不一定比gf好,只是难进罢了。。。
难进也只是坑少,我知道有人fail所有其他公司,最后进了T
【在 p**********3 的大作中提到】 : BF也是刚on site T家·~~~~真希望他能成功拿到~~FLAG是五岳~~T家是黄山啊~~ : 太TM难了~特别是纽约的T家~ : BLESS My baby~~ : 同时bless 楼主~~
|
x*****0 发帖数: 452 | |