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 | |
