$4 AMC Theatres® Movie Ticket - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

$4 AMC Theatres® Movie Ticket

$4 AMC Theatres® Movie Ticket# Fashion - 美丽时尚

w*a2010-05-21 07:05

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，有些关键问题
我让他写下来了。应该不影响吧。我跟他说了是电话线路问题。

r*a2010-05-21 07:05

2 楼

http://www.kgbdeals.com/?id=261

f*t2010-05-21 07:05

3 楼

先顶再看

j*o2010-05-21 07:05

4 楼

thanks!

w*x2010-05-21 07:05

5 楼

bless....
一周没收到拒信楼主就过啦~~
楼主怎么不是两个面试一起的吗？？

l*D2010-05-21 07:05

6 楼

貌似只有纽约能用？

j*y2010-05-21 07:05

7 楼

bless
F 家这么恐怖阿，楼主答的挺好的阿

why

【在 w****a 的大作中提到】

: 10分钟面经系列，这次是T家。
: 上次FB二面终于如期收到拒信，move on了。T家的一面希望大家bless啊。
: 刚开始给我一分钟时间问了我两个behavior问题，一个是我现在在做什么，一个是why
: T家。
: 然后就开collabedit了，就写了一道题。题很简单，板上的XDJM们相信都能秒杀。
: 给一个多叉树和一个节点，求出这个节点所有path下来的数字的和。比如给出树和节点
: 4
: 4
: / \
: 2 1

j*y2010-05-21 07:05

8 楼

这里的多叉是怎么存的阿
struct Node
{
int val;
vector child
}
吗 ?

why

【在 w****a 的大作中提到】

w*a2010-05-21 07:05

9 楼

对，就这么存

【在 j*****y 的大作中提到】

: 这里的多叉是怎么存的阿
: struct Node
: {
: int val;
: vector child
: }
: 吗 ?
:
: why

w*a2010-05-21 07:05

10 楼

感谢bless，F家已经正式收到拒信啦。move on

【在 w****x 的大作中提到】

: bless....
: 一周没收到拒信楼主就过啦~~
: 楼主怎么不是两个面试一起的吗？？

w*x2010-05-21 07:05

11 楼

我说的是T家

【在 w****a 的大作中提到】

: 感谢bless，F家已经正式收到拒信啦。move on

w*a2010-05-21 07:05

12 楼

希望能过哈哈多谢多谢！！

【在 w****x 的大作中提到】

:
: 我说的是T家

j*y2010-05-21 07:05

13 楼

4
/ \
1 2
/ \
1 3
是 41 + 421 + 423 吗?

why

【在 w****a 的大作中提到】

w*a2010-05-21 07:05

14 楼

是，路径都加起来

【在 j*****y 的大作中提到】

: 4
: / \
: 1 2
: / \
: 1 3
: 是 41 + 421 + 423 吗?
:
: why

j*y2010-05-21 07:05

15 楼

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*a2010-05-21 07:05

16 楼

我一开始也是这么写的，不过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*e2010-05-21 07:05

17 楼

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*52010-05-21 07:05

18 楼

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*e2010-05-21 07:05

19 楼

哦，不过一样的

【在 M********5 的大作中提到】

: lz好像说的是多叉树

w*a2010-05-21 07:05

20 楼

是多叉树，不过就是这个做法

【在 p****e 的大作中提到】

j*y2010-05-21 07:05

21 楼

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*22010-05-21 07:05

22 楼

DFS就可以了。

w*x2010-05-21 07:05

23 楼

不愧是DFS大牛啊

【在 p*****2 的大作中提到】

: DFS就可以了。

l*b2010-05-21 07:05

24 楼

bless

c*s2010-05-21 07:05

25 楼

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 的大作中提到】

g*r2010-05-21 07:05

26 楼

这个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*p2010-05-21 07:05

27 楼

有点不太清楚多线程下引用会有什么问题，能解释一下吗

why

【在 w****a 的大作中提到】

w*a2010-05-21 07:05

28 楼

同时写一个变量，不加锁会有问题的

【在 p*****p 的大作中提到】

: 有点不太清楚多线程下引用会有什么问题，能解释一下吗
:
: why

p*22010-05-21 07:05

29 楼

scala应该没有问题吧？

【在 w****a 的大作中提到】

: 同时写一个变量，不加锁会有问题的

h*i2010-05-21 07:05

30 楼

scala 应该有同样的问题

【在 p*****2 的大作中提到】

:
: scala应该没有问题吧？

p*22010-05-21 07:05

31 楼

为什么？

【在 h***i 的大作中提到】

: scala 应该有同样的问题

p*e2010-05-21 07:05

32 楼

scala有什么特殊机制避免冲突情况?

【在 p*****2 的大作中提到】

:
: 为什么？

p*22010-05-21 07:05

33 楼

scala不需要用锁。

【在 p****e 的大作中提到】

: scala有什么特殊机制避免冲突情况?

p*22010-05-21 07:05

34 楼

这题刚刚收录到leetcode里。我做了一下放到博客了，不过这题是道简单题，没什么太
大的意思。
http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html

l*u2010-05-21 07:05

35 楼

bless

why

【在 w****a 的大作中提到】

h*i2010-05-21 07:05

36 楼

你写一个。准备用immutable，那个sum累加值怎么办？

【在 p*****2 的大作中提到】

: 这题刚刚收录到leetcode里。我做了一下放到博客了，不过这题是道简单题，没什么太
: 大的意思。
: http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html

p*e2010-05-21 07:05

37 楼

那多线程怎办

【在 p*****2 的大作中提到】

: 这题刚刚收录到leetcode里。我做了一下放到博客了，不过这题是道简单题，没什么太
: 大的意思。
: http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html

w*a2010-05-21 07:05

38 楼

我觉得要是有一个网站专门收录经典follow up的就好了。

【在 p*****2 的大作中提到】

: 这题刚刚收录到leetcode里。我做了一下放到博客了，不过这题是道简单题，没什么太
: 大的意思。
: http://blog.sina.com.cn/s/blog_b9285de20101iv6l.html

p*22010-05-21 07:05

39 楼

actor

【在 p****e 的大作中提到】

: 那多线程怎办

p*22010-05-21 07:05

40 楼

immutable的话不能改变变量，可以用常量来传递。

【在 h***i 的大作中提到】

: 你写一个。准备用immutable，那个sum累加值怎么办？

L*r2010-05-21 07:05

41 楼

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*32010-05-21 07:05

42 楼

BF也是刚on site T家·~~~~真希望他能成功拿到~~FLAG是五岳~~T家是黄山啊~~
太TM难了~特别是纽约的T家~
BLESS My baby~~
同时bless 楼主~~

w*a2010-05-21 07:05

43 楼

FLAG是五岳 T家是黄山啊
好说法

j*x2010-05-21 07:05

44 楼

t倒不一定比gf好，只是难进罢了。。。
难进也只是坑少，我知道有人fail所有其他公司，最后进了T

【在 p**********3 的大作中提到】

: BF也是刚on site T家·~~~~真希望他能成功拿到~~FLAG是五岳~~T家是黄山啊~~
: 太TM难了~特别是纽约的T家~
: BLESS My baby~~
: 同时bless 楼主~~

x*02010-05-21 07:05

45 楼

mark