问个amazon面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个amazon面试题

问个amazon面试题# JobHunting - 待字闺中

B*12011-09-15 07:09

1 楼

What is Full binary tree and complete binary tree. And code to find if a
given tree is so.. (Phone interview, interviewer was very supportive. As I
couldn't finish coding, asked me to send offline, and did so).
问题很弱，但是怎么验证full binary tree和complete binary tree才是最快呢。
谢谢。

c*l2011-09-15 07:09

2 楼

full binary 比较好验证吧递归的写就行
complete 这个有点麻烦可能是查层数？

l*d2011-09-15 07:09

3 楼

full 应该是dfs，每个node递归的时候都查一下是不是2 children，不是就return
false退出。
complete应该用bfs吧，每一层都记下当前的level。等找到第一个leaf的时候，后面就
改用dfs，如果层数超出了leaf两层就return false退出。

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

: full binary 比较好验证吧递归的写就行
: complete 这个有点麻烦可能是查层数？

g*y2011-09-15 07:09

4 楼

complete = full && nodeNumber = 2^height - 1

B*12011-09-15 07:09

5 楼

isn't it
full = complete && nodeNumber = 2^height - 1
?
from wiki:
A full binary tree (sometimes proper binary tree or 2-tree or strictly
binary tree) is a tree in which every node other than the leaves has two
children.
A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible.[2]

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

: complete = full && nodeNumber = 2^height - 1

g*y2011-09-15 07:09

6 楼

http://xlinux.nist.gov/dads//HTML/completeBinaryTree.html

c*62011-09-15 07:09

7 楼

full:
i>对于当前层节点，看是不是都有2个孩子
ii> 如果不是，看下一层有没有孩子，
i> 如果没有，返回true
ii> 如果有，返回false
iii> 如果是，接着遍历下一层节点，跳到i继续

d*d2011-09-15 07:09

8 楼

bool checkfull(Node * root){
if( root == 0)
return true;
if( root->left == 0 && root->right == 0)
return true;
if( root->left == 0 || root->right == 0)
return false;
return (checkfull(root->left) && checkfull(root->right));
}

【在 B*******1 的大作中提到】

: What is Full binary tree and complete binary tree. And code to find if a
: given tree is so.. (Phone interview, interviewer was very supportive. As I
: couldn't finish coding, asked me to send offline, and did so).
: 问题很弱，但是怎么验证full binary tree和complete binary tree才是最快呢。
: 谢谢。

r*n2011-09-15 07:09

9 楼

//A full binary tree (sometimes proper binary tree or 2-tree or strictly
binary tree) is a tree in which every node other than the leaves has two
children.
bool isFull(Node *s){

if(!s->L && !s->R)
return true;

if(!s->R || !s->L)
return false;

return isFull(s->L) && isFull(s->R);
}
//A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible.[2]
int minHeight(Node *s){
if (!s)
return 0;
return 1 + min(minHeight(s->L), minHeight(s->R));
}
int maxHeight(Node *s){
if (!s)
return 0;
return 1 + max(maxHeight(s->L), maxHeight(s->R));
}
bool isComplete(Node *s){
if(!s)
return true;
int in1 = maxHeight(s);
int in2 = minHeight(s)
return (in1==in2 || in1==in2+1);
}

B*12011-09-15 07:09

10 楼

complete binary tree那里你怎么保证最底层的node都是在左边，而不是在右边或者分
散的呢？

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

: //A full binary tree (sometimes proper binary tree or 2-tree or strictly
: binary tree) is a tree in which every node other than the leaves has two
: children.
: bool isFull(Node *s){
:
: if(!s->L && !s->R)
: return true;
:
: if(!s->R || !s->L)
: return false;

j*x2011-09-15 07:09

11 楼

a tree of a size of 1 is complete
a tree is complete if satisfies all of the following:
1. both his left and right sub-trees are complete
2. suppose the height of the right sub-tree is h_s and the right is h_r.
2.1 if h_s == h_r, then the leaves of the left sub-tree must fill the level
completely
2.2 if h_s - 1 == h_r, then the leaves of the right sub-tree must fill the
level completely

【在 B*******1 的大作中提到】

: complete binary tree那里你怎么保证最底层的node都是在左边，而不是在右边或者分
: 散的呢？

D*g2011-09-15 07:09

12 楼

A solution with bfs, node on a complete b-tree should have continuous index
if appropriately indexed:
Boolean isCompleteBinaryTree(Node root) {
If (root == NULL) return true;
Queue> bfs = new Queue>();
Bfs.put(new Entry(root, 0));
Int currentNodeIdx = -1;
While (!bfs.empty()) {
Entry e = bfs.poll();
If (e.getValue() != ++ currentNodeIdx) {
Return false; // Node index is not continuous.
}
Node n = e.getKey();
If (n.left != null) {
Bfs.add(new Entry(n.left, e.getValue() * 2 + 1));
}
If (n.right != null) {
Bfs.add(new Entry(n.right, e.getValue() * 2 + 2));
}
}
Return true;
}

level

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

: a tree of a size of 1 is complete
: a tree is complete if satisfies all of the following:
: 1. both his left and right sub-trees are complete
: 2. suppose the height of the right sub-tree is h_s and the right is h_r.
: 2.1 if h_s == h_r, then the leaves of the left sub-tree must fill the level
: completely
: 2.2 if h_s - 1 == h_r, then the leaves of the right sub-tree must fill the
: level completely

W*22011-09-15 07:09

13 楼

level
按照你的算法是不是这样？
CheckComplete(Node *root){
if (root==0)
return true;
if(Height(root.left)==Height(root.right))
return (CheckFull(root.left))
if(Height(root.left)==Height(root.right)+1)
return (CheckFull(root.right))
return (CheckComplete(root.left)&&CheckComplete(root.right))
}

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

l*s2011-09-15 07:09

14 楼

Amazon jobs
http://jobguiding.com/it-jobs/it-companies/amazon.html

【在 B*******1 的大作中提到】

c*w2011-09-15 07:09

15 楼

好像有问题唉.
Case:
if(Height(root.left)==Height(root.right))
return (CheckFull(root.left))
O
/ \
O O
/ \ \
O O O
仅仅CheckFull(root.left) 似乎还不够, 因为root.right可能不是complete的.

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

:
: level
: 按照你的算法是不是这样？
: CheckComplete(Node *root){
: if (root==0)
: return true;
: if(Height(root.left)==Height(root.right))
: return (CheckFull(root.left))
: if(Height(root.left)==Height(root.right)+1)
: return (CheckFull(root.right))

j*x2011-09-15 07:09

16 楼

建议手写bst相关算法10遍以上然后会比较好理解其中的递归问题

【在 B*******1 的大作中提到】