一道面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试题

一道面试题# JobHunting - 待字闺中

R*s2010-01-12 08:01

1 楼

家常丑菜又来了。。。健康又快捷哈
羊肉萝卜汤：
带骨羊肉两大块，过水，切成小块，萝卜也切小块，一起扔
电高压锅煮， 15分钟，出锅的时候加盐，胡椒，香菜。
熏火鸡脖子：
昨天本来想买火鸡腿的，只找到脖子。蒸锅先蒸上，这时候可
以做别的菜，最后出锅加点Jalapeno和蒜炒一下就好了。
香菇白菜：
香菇泡一下，　白菜洗干净，　扯一半，　下锅，　加点水煮下下。
微波红薯：
红薯扔微波炉高温6分钟，完事。

c*y2010-01-12 08:01

2 楼

Given a binary tree
struct node{
struct node* leftChild;
struct node* rightChild;
struct node* nextRight;
}
The nextRight points to the right node to the current node in the same
level. Ask you populate the nextRight pointers in each node.
大家怎么做这道题.

s*l2010-01-12 08:01

3 楼

不错不错，学习了

m*f2010-01-12 08:01

4 楼

记得以前有个分level打印二叉树的题目么，这两道题本质上是一样的

d*e2010-01-12 08:01

5 楼

###此帖已应当事人要求删除###

a*g2010-01-12 08:01

6 楼

BFS

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

: Given a binary tree
: struct node{
: struct node* leftChild;
: struct node* rightChild;
: struct node* nextRight;
: }
: The nextRight points to the right node to the current node in the same
: level. Ask you populate the nextRight pointers in each node.
: 大家怎么做这道题.

s*i2010-01-12 08:01

7 楼

赞，你家的伙食总是很丰盛

c*y2010-01-12 08:01

8 楼

对，就是每个node从queue里面dequeue出来后它的nextRight指向queue的peek。
我现在在想，能否有recursion的方法？想了下想不出来。

【在 m*****f 的大作中提到】

: 记得以前有个分level打印二叉树的题目么，这两道题本质上是一样的

s*i2010-01-12 08:01

9 楼

熏火鸡脖子色泽诱人，令人食指大动！
为什么叫“熏”，买的是熏过的吗？

b*j2010-01-12 08:01

10 楼

可以使用任何方式遍历一遍这棵树，iterative or recurise
在遍历过程中，对每一个节点x
if (x->leftChild and x->rightChild) {
x->leftChild->nextRight = x->rightChild;
x->rightChild->nextRight = 0;
}

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

c*u2010-01-12 08:01

11 楼

赞啊！你买的火鸡脖子本来就是熟的么？

【在 R*****s 的大作中提到】

: 家常丑菜又来了。。。健康又快捷哈
: 羊肉萝卜汤：
: 带骨羊肉两大块，过水，切成小块，萝卜也切小块，一起扔
: 电高压锅煮， 15分钟，出锅的时候加盐，胡椒，香菜。
: 熏火鸡脖子：
: 昨天本来想买火鸡腿的，只找到脖子。蒸锅先蒸上，这时候可
: 以做别的菜，最后出锅加点Jalapeno和蒜炒一下就好了。
: 香菇白菜：
: 香菇泡一下，　白菜洗干净，　扯一半，　下锅，　加点水煮下下。
: 微波红薯：

c*y2010-01-12 08:01

12 楼

这个主要看如何理解这道题，如果认为nextRight是指向同一parent点下的右边点，你
可以这么做。
如果是指同一level的右边点，那么只能用bfs了。

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

: 可以使用任何方式遍历一遍这棵树，iterative or recurise
: 在遍历过程中，对每一个节点x
: if (x->leftChild and x->rightChild) {
: x->leftChild->nextRight = x->rightChild;
: x->rightChild->nextRight = 0;
: }

R*s2010-01-12 08:01

13 楼

哈哈，　是挺粗的，　不过味道不错，　比鸭脖子好啃　：）

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

: ###此帖已应当事人要求删除###

b*j2010-01-12 08:01

14 楼

I see, then BFS!

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

: 这个主要看如何理解这道题，如果认为nextRight是指向同一parent点下的右边点，你
: 可以这么做。
: 如果是指同一level的右边点，那么只能用bfs了。

R*s2010-01-12 08:01

15 楼

嗯，　熏过的，　我们这里超市老卖熏火鸡翅膀啊火鸡腿啊啥的。。
蒸一下就可以吃。。。

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

: 熏火鸡脖子色泽诱人，令人食指大动！
: 为什么叫“熏”，买的是熏过的吗？

b*e2010-01-12 08:01

16 楼

这题水深了. 你的研究客户心理. 明显不是BFS. 对于平衡树来讲, BFS的space
complexity
是O(n)的. DFS一般是O(log(n))的. 一般树都比较平衡, 否则比较傻逼. 这个分三步:
第一步, 如果有parent pointer, 就就这么做:
void linkNext(node * current) {
if (!current) {
return;
}
if (current->nextRight) {
return;
}
node * parent = current->parent;
if (!parent) {
current->nextRight = NULL;
} else if (current == parent->leftChild && parent->rightChild) {
current->nextRight = parent->rightChild;
} else {
node

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

: 对，就是每个node从queue里面dequeue出来后它的nextRight指向queue的peek。
: 我现在在想，能否有recursion的方法？想了下想不出来。

a*l2010-01-12 08:01

17 楼

版大威武！

【在 R*****s 的大作中提到】

v*t2010-01-12 08:01

18 楼

其实从上往下，遍历一层链的过程中链接下一层链，这样就不需要parent指针了。因为
在生成下一层链的时候，当前的这个节点就是下一层的parent。

步:

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

: 这题水深了. 你的研究客户心理. 明显不是BFS. 对于平衡树来讲, BFS的space
: complexity
: 是O(n)的. DFS一般是O(log(n))的. 一般树都比较平衡, 否则比较傻逼. 这个分三步:
: 第一步, 如果有parent pointer, 就就这么做:
: void linkNext(node * current) {
: if (!current) {
: return;
: }
: if (current->nextRight) {
: return;

R*s2010-01-12 08:01

19 楼

不晓得啊，　熏过的，　我一般是要蒸一下，　至少蒸15分钟吧，
完了直接就能吃，　我一般回下锅，　加点蒜啥的炒炒更香～

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

: 赞啊！你买的火鸡脖子本来就是熟的么？

b*e2010-01-12 08:01

20 楼

没说到点上。
其实这题的意思是用nextRight来代替queue, 不要新空间。就像用parent来代替栈一
样。

【在 v*****t 的大作中提到】

: 其实从上往下，遍历一层链的过程中链接下一层链，这样就不需要parent指针了。因为
: 在生成下一层链的时候，当前的这个节点就是下一层的parent。
:
: 步:

l*32010-01-12 08:01

21 楼

先顶下，看着真好吃。。。

g*y2010-01-12 08:01

22 楼

在一层上遍历完了一条链(由nextRight串起来的链)生成下一层新的一条链，然后再遍历新的链继续生成新的链。。。这不就相当于是用nextRight代替queue嘛
当然，没有你表述的那么清晰，呵呵
有了queue就不需要stack了，所以不需要用到parent了嘛

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

: 没说到点上。
: 其实这题的意思是用nextRight来代替queue, 不要新空间。就像用parent来代替栈一
: 样。

R*s2010-01-12 08:01

23 楼

细细，　比特厨的差远了，　没办法，　这不是一下能赶上来的。。。

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

: 先顶下，看着真好吃。。。

m*f2010-01-12 08:01

24 楼

一针见血啊, 明白了

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

: 没说到点上。
: 其实这题的意思是用nextRight来代替queue, 不要新空间。就像用parent来代替栈一
: 样。

s*i2010-01-12 08:01

25 楼

不错，方便多了

【在 R*****s 的大作中提到】

: 嗯，　熏过的，　我们这里超市老卖熏火鸡翅膀啊火鸡腿啊啥的。。
: 蒸一下就可以吃。。。

b*e2010-01-12 08:01

26 楼

其实这个题我真的遇到过。说起来都容易，现场写code不好写。尤其是白板上。

【在 m*****f 的大作中提到】

: 一针见血啊, 明白了

F*t2010-01-12 08:01

27 楼

吔
熏火鸡脖子很好吃的
能解解吃不到精武鸭脖子的馋
就是不辣

k*e2010-01-12 08:01

28 楼

大牛怎么最近开始用中文了
有没有机会refer我一下：）

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

: 其实这个题我真的遇到过。说起来都容易，现场写code不好写。尤其是白板上。

s*i2010-01-12 08:01

29 楼

关于微波红薯，你是切成小段后转的？
我妈通常是挑细长的小番薯，洗好，不用擦很干，放微波炉盒子里（盖子搭在上面就好
，不要盖紧），高火3分钟后翻面再3分钟，基本上就好了。外婆让我2分钟2分钟......
转，嗬嗬。如果是比较粗壮的，就对剖后转。

b*j2010-01-12 08:01

30 楼

好主意, 原题没有说清楚需要空间O(1)，时间O(n)，把这个算法实现了一下，没有运行
过：
void check(Node *p, Node* &last, Node* &first) {
if (p) {
if (last)
last->nextRight = p;
else
first = p;
last = p;
}
}
void link_next_right(Node *root) {
if (root)
root->nextRight = NULL;
for (Node *first=root, *next_first=NULL;
first;
first=next_first, next_first=NULL) {
Node *last = NULL;
for (Node *p=first; p; p=p->nextRight) {
check(p->leftChild, last, next_first);
check(p->ri

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

: 在一层上遍历完了一条链(由nextRight串起来的链)生成下一层新的一条链，然后再遍历新的链继续生成新的链。。。这不就相当于是用nextRight代替queue嘛
: 当然，没有你表述的那么清晰，呵呵
: 有了queue就不需要stack了，所以不需要用到parent了嘛

l*t2010-01-12 08:01

31 楼

羊肉萝卜香菜最配了。

h*e2010-01-12 08:01

32 楼

should the rightmost one in a level point to NULL, or to the leftmost one in
the next level?

l*t2010-01-12 08:01

33 楼

题外话：不确定这周哪天李小龙诞辰70周年。

b*j2010-01-12 08:01

34 楼

NULL, if it were the leftmost one in the next level, the code could be furth
er simplified.

in

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

: should the rightmost one in a level point to NULL, or to the leftmost one in
: the next level?

b*x2010-01-12 08:01

35 楼

嗯嗯去买火鸡脖子～～
香菇油菜？
我们家今晚才是香菇白菜呵呵

l*22010-01-12 08:01

36 楼

变叔家的伙食总是这么好
版大你家都是你下厨吧，你老婆也太幸福了，
我认识的人里面，我发现湖北男人和上海男人家庭下厨比例最高

l*22010-01-12 08:01

37 楼

你这是超级特厨，我觉得家常菜最好吃的，你每次上菜都让人特有胃口

【在 R*****s 的大作中提到】

: 细细，　比特厨的差远了，　没办法，　这不是一下能赶上来的。。。