Google second phone interview - 未名空间MITBBS历史存档

Google second phone interview# JobHunting - 待字闺中

i*62012-02-14 08:02

1 楼

1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
1
/ \
2 -> 3
/ \ / \
4->5->6->7
2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
经由二维的整数数组给出。
都要求说思路，然后doc上面coding.

h*l2012-02-14 08:02

2 楼

1.bfs，存level和pre ptr把
2.cc150上面的题

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

r*n2012-02-14 08:02

3 楼

1用deque就是了

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

: 1.bfs，存level和pre ptr把
: 2.cc150上面的题

h*l2012-02-14 08:02

4 楼

还是要记下每层头尾把

【在 r*******n 的大作中提到】

: 1用deque就是了

r*n2012-02-14 08:02

5 楼

不用...头上蹦出来, 尾巴插child

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

: 还是要记下每层头尾把

g*e2012-02-14 08:02

6 楼

my sol. for 1
use two queues,
push root to q1,
pop q1, connect all nodes in q1. push all its children to q2.
pop q2, connect all nodes in q2. push all their children to q1.
then two queues do this in turn.

d*o2012-02-14 08:02

7 楼

第一题用先广遍历，然后把每一个node都放到一个vector里面去。
接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
有人可以不用多余空间的方法吗？

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

l*a2012-02-14 08:02

8 楼

有啊
不需要o(N)空间
以前有人发过

【在 d****o 的大作中提到】

: 第一题用先广遍历，然后把每一个node都放到一个vector里面去。
: 接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
: 有人可以不用多余空间的方法吗？

r*n2012-02-14 08:02

9 楼

treewidth也是worst case O(n)啊...

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

: 有啊
: 不需要o(N)空间
: 以前有人发过

d*o2012-02-14 08:02

10 楼

顶这个，不过你这个方法还是需要traversal所有的节点。
写一下，看看有没有问题。
void sib(node* root)
{
if(root&&root->left&&root->right)
{
root->left->next = root->right;
if(root->next)
{
root->right->next = root->next->left;
}
sib(root->left);
sib(root->right);
}
}

q*c2012-02-14 08:02

11 楼

Bingo!

l*a2012-02-14 08:02

12 楼

没有任何一个方法不需要traverse所有的节电吧？

【在 d****o 的大作中提到】

: 顶这个，不过你这个方法还是需要traversal所有的节点。
: 写一下，看看有没有问题。
: void sib(node* root)
: {
: if(root&&root->left&&root->right)
: {
: root->left->next = root->right;
: if(root->next)
: {
: root->right->next = root->next->left;

a*g2012-02-14 08:02

13 楼

I used exactly the same solution in MS interview. and the interviewer asked
me to come up a solution with O(1) space

【在 d****o 的大作中提到】

: 第一题用先广遍历，然后把每一个node都放到一个vector里面去。
: 接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
: 有人可以不用多余空间的方法吗？

c*n2012-02-14 08:02

14 楼

For the first question:
// Assumption: all node's sibling property is null before calling
// the function.
void linkSibling(Node root){
if (root == null) return;
if (root.left != null){
root.left.sibling = root.right;
}
if (root.right != null ){
root.right.sibling = root.sibling == null ? null : root.sibling.left;
}
linkSibling(root.left);
linkSibling(root.right);
}

z*n2012-02-14 08:02

15 楼

第一题和leecode上的“Populating next right pointers in each node”类似，
http://www.leetcode.com/2010/03/first-on-site-technical-intervi

a*s2012-02-14 08:02

16 楼

mark

l*a2012-02-14 08:02

17 楼

还是用了recursion
开销很大啊

【在 z*****n 的大作中提到】

: 第一题和leecode上的“Populating next right pointers in each node”类似，
: http://www.leetcode.com/2010/03/first-on-site-technical-intervi

d*o2012-02-14 08:02

18 楼

他是不是就想要我上面写的recursion版本？不过recursion也需要stack，需要O(n)
space啊？
你过了没有？

asked

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

: I used exactly the same solution in MS interview. and the interviewer asked
: me to come up a solution with O(1) space

i*62012-02-14 08:02

19 楼

1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
1
/ \
2 -> 3
/ \ / \
4->5->6->7
2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
经由二维的整数数组给出。
都要求说思路，然后doc上面coding.

h*l2012-02-14 08:02

20 楼

1.bfs，存level和pre ptr把
2.cc150上面的题

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

r*n2012-02-14 08:02

21 楼

1用deque就是了

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

: 1.bfs，存level和pre ptr把
: 2.cc150上面的题

h*l2012-02-14 08:02

22 楼

还是要记下每层头尾把

【在 r*******n 的大作中提到】

: 1用deque就是了

r*n2012-02-14 08:02

23 楼

不用...头上蹦出来, 尾巴插child

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

: 还是要记下每层头尾把

g*e2012-02-14 08:02

24 楼

my sol. for 1
use two queues,
push root to q1,
pop q1, connect all nodes in q1. push all its children to q2.
pop q2, connect all nodes in q2. push all their children to q1.
then two queues do this in turn.

d*o2012-02-14 08:02

25 楼

第一题用先广遍历，然后把每一个node都放到一个vector里面去。
接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
有人可以不用多余空间的方法吗？

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

l*a2012-02-14 08:02

26 楼

有啊
不需要o(N)空间
以前有人发过

【在 d****o 的大作中提到】

: 第一题用先广遍历，然后把每一个node都放到一个vector里面去。
: 接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
: 有人可以不用多余空间的方法吗？

r*n2012-02-14 08:02

27 楼

treewidth也是worst case O(n)啊...

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

: 有啊
: 不需要o(N)空间
: 以前有人发过

d*o2012-02-14 08:02

28 楼

顶这个，不过你这个方法还是需要traversal所有的节点。
写一下，看看有没有问题。
void sib(node* root)
{
if(root&&root->left&&root->right)
{
root->left->next = root->right;
if(root->next)
{
root->right->next = root->next->left;
}
sib(root->left);
sib(root->right);
}
}

【在 q********c 的大作中提到】

: Bingo!

q*c2012-02-14 08:02

29 楼

Bingo!

l*a2012-02-14 08:02

30 楼

没有任何一个方法不需要traverse所有的节电吧？

【在 d****o 的大作中提到】

: 顶这个，不过你这个方法还是需要traversal所有的节点。
: 写一下，看看有没有问题。
: void sib(node* root)
: {
: if(root&&root->left&&root->right)
: {
: root->left->next = root->right;
: if(root->next)
: {
: root->right->next = root->next->left;

a*g2012-02-14 08:02

31 楼

I used exactly the same solution in MS interview. and the interviewer asked
me to come up a solution with O(1) space

【在 d****o 的大作中提到】

: 第一题用先广遍历，然后把每一个node都放到一个vector里面去。
: 接着把vector里面的node每一个连到下一个（判断一下是否是最右节点）
: 有人可以不用多余空间的方法吗？

c*n2012-02-14 08:02

32 楼

For the first question:
// Assumption: all node's sibling property is null before calling
// the function.
void linkSibling(Node root){
if (root == null) return;
if (root.left != null){
root.left.sibling = root.right;
}
if (root.right != null ){
root.right.sibling = root.sibling == null ? null : root.sibling.left;
}
linkSibling(root.left);
linkSibling(root.right);
}

z*n2012-02-14 08:02

33 楼

第一题和leecode上的“Populating next right pointers in each node”类似，
http://www.leetcode.com/2010/03/first-on-site-technical-intervi

a*s2012-02-14 08:02

34 楼

mark

l*a2012-02-14 08:02

35 楼

还是用了recursion
开销很大啊

【在 z*****n 的大作中提到】

: 第一题和leecode上的“Populating next right pointers in each node”类似，
: http://www.leetcode.com/2010/03/first-on-site-technical-intervi

d*o2012-02-14 08:02

36 楼

他是不是就想要我上面写的recursion版本？不过recursion也需要stack，需要O(n)
space啊？
你过了没有？

asked

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

: I used exactly the same solution in MS interview. and the interviewer asked
: me to come up a solution with O(1) space

j*22012-02-14 08:02

37 楼

should be O(log n) space ba. The recursion depth is log n for a perfect tree
ba?

【在 d****o 的大作中提到】

: 他是不是就想要我上面写的recursion版本？不过recursion也需要stack，需要O(n)
: space啊？
: 你过了没有？
:
: asked

n*i2012-02-14 08:02

38 楼

第一题 O（1）空间可以实现。思路是：
要想link 第 n+1 行 node 的 next right，需要从第 n 行 node 的第一个下手。
假设 Node *n 是第n行第一个node
while(n && n->nextRight){
n->left->nextRight = n->right;
n->right->nextRight = n->nextRight->left;
n = n->nextRight;
}
n->left->nextRight = n->right;
n->right->nextRight = 0;
这样就可以把第n+1 行连起来。这里利用的是当你连第n+1行时，第n行已经连好。

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

n*i2012-02-14 08:02

39 楼

第一题 O（1）空间可以实现。思路是：
要想link 第 n+1 行 node 的 next right，需要从第 n 行 node 的第一个下手。
假设 Node *n 是第n行第一个node
while(n && n->nextRight){
n->left->nextRight = n->right;
n->right->nextRight = n->nextRight->left;
n = n->nextRight;
}
n->left->nextRight = n->right;
n->right->nextRight = 0;
这样就可以把第n+1 行连起来。这里利用的是当你连第n+1行时，第n行已经连好。

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

: 1.perfect binary tree, 给每一个node加一个sabling的pointer,比如
: 1
: / \
: 2 -> 3
: / \ / \
: 4->5->6->7
: 2.实现画图里面的油漆桶功能（那个点下去可以把一块图染成一种颜色的），假设图已
: 经由二维的整数数组给出。
: 都要求说思路，然后doc上面coding.

a*y2012-02-14 08:02

40 楼

不是类似，就是一样的题

【在 z*****n 的大作中提到】

: 第一题和leecode上的“Populating next right pointers in each node”类似，
: http://www.leetcode.com/2010/03/first-on-site-technical-intervi