Facebook Phone Interview

(招工季节从7-9月到了10-12月)

一小时前FB电话面试，扯了20分钟简历才说：想要写点代码吗？ 。。。

Iterator for in-order traversal of binary tree.  开始以为是iterative traverse in-order binary tree...还暗喜了一会。。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

3px">很久都没有理解题目，，后面边理解边写边改的。写完面试官说有个Bug，我找了半天说没找到，给个提示。。还好他说是他看错了。。

求Onsite！！！ 邮箱里面已经塞满了拒信。

我用c++实现了一个，大家看看有么有bug吧。。

1. #include <iostream>
   
2. #include <stack>
   
3. using namespace std;
   
4. 
   
5. struct Tree{
   
6.     int val;
   
7.     Tree *left, *right;
   
8.     Tree(int mval):val(mval), left(NULL), right(NULL){}
   
9. };
   
10. 
    
11. class TreeIterator{
    
12. public:
    
13.     TreeIterator(Tree *root){
    
14.         flag = true;
    
15.         if(root == NULL){
    
16.             cur = NULL;
    
17.             cout<<"invalid root point"<<endl;
    
18.         }else{
    
19.             while(root){
    
20.                 st.push(root);
    
21.                 root = root->left;
    
22.             }
    
23.             cur = st.top();
    
24.         }
    
25.     }
    
26.     int value(){
    
27.         if(cur == NULL){
    
28.             cout<<"invalid operation"<<endl;
    
29.             return -1;
    
30.         }else{
    
31.             cout<<cur->val<<endl;
    
32.             return cur->val;
    
33.         }
    
34.     }
    
35.     void next(){
    
36.         if(cur == NULL){
    
37.             cout<<"No next point"<<endl;
    
38.             return;
    
39.         }else{
    
40.             if(cur->right){
    
41.                 st.pop();
    
42.                 cur = cur->right;
    
43.                 st.push(cur);
    
44.                 while(cur->left){
    
45.                     cur = cur->left;
    
46.                     st.push(cur);
    
47.                 }
    
48.             }else{
    
49.                 st.pop();
    
50.                 cur = st.empty()?NULL:st.top();
    
51.             }
    
52.         }
    
53.     }
    
54.     bool hasNext(){
    
55.         return cur != NULL;
    
56.     }
    
57. private:
    
58.     stack<Tree* > st;
    
59.     Tree* cur;
    
60.     bool flag;
    
61. };
    
62. 
    
63. int main(){
    
64.     Tree *t1 = new Tree(1);
    
65.     Tree *t2 = new Tree(2);
    
66.     Tree *t3 = new Tree(3);
    
67.     Tree *t4 = new Tree(4);
    
68.     Tree *t5 = new Tree(5);
    
69.     Tree *t6 = new Tree(6);
    
70.     Tree *t7 = new Tree(7);
    
71.     t1->left = t2, t1->right = t3;
    
72.     t2->left = t4, t2->right = t5;
    
73.     t3->left = t6, t3->right = t7;
    
74.     TreeIterator tit(t1);
    
75.     while(tit.hasNext()){
    
76.         tit.value();
    
77.         tit.next();
    
78.     }
    
79. }
    
80. 
    
81. /*
    
82.                 1
    
83.                /\
    
84.               2 3
    
85.              /\ /\
    
86.             4 56 7
    
87.             */
    

复制代码

1. import java.util.Stack;
   
2. public class IteratorOfInOrder {       
   
3.         private TreeNode curr;
   
4.         private Stack<TreeNode> nodes = new Stack<TreeNode>();       
   
5.        
   
6.         public IteratorOfInOrder(TreeNode root){
   
7.                 TreeNode nd = root;
   
8.                 while(nd != null){
   
9.                         nodes.push(nd);
   
10.                         nd = nd.left;
    
11.                 }               
    
12.         }
    
13.        
    
14.         public int value(){                       
    
15.                 return curr.val;               
    
16.         }
    
17. 
    
18.         public void next(){
    
19.                 if(!nodes.isEmpty()){
    
20.                         curr = nodes.pop();                       
    
21.                 }else{
    
22.                         curr = null;
    
23.                 }
    
24.                
    
25.                 if(curr != null) {
    
26.                         TreeNode nd = curr;
    
27.                         if(nd.right != null) {
    
28.                                 nd = nd.right;
    
29.                                 while(nd != null) {
    
30.                                         nodes.push(nd);
    
31.                                         nd = nd.left;
    
32.                                 }
    
33.                         }                       
    
34.                 }
    
35.         }
    
36.        
    
37.         public boolean hasNext(){
    
38.                 return !nodes.isEmpty();
    
39.         }
    
40. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题用iterative version 的 inorder? 可以自己开个stack吗 还是说用morris?

rettyye3 发表于 2014-11-8 08:24
这题用iterative version 的 inorder? 可以自己开个stack吗 还是说用morris?

实现那个类的方法。

22691482 发表于 2014-11-8 08:39
实现那个类的方法。

哦, 我的意思是能不能自己给这个class加个private的stack, 或者这Node的结构有没有parent?

祝早日拿到onsite!

楼主怎么做的啊，没想明白。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

hno3 发表于 2014-11-8 10:01
楼主怎么做的啊，没想明白。。。

可以参考： CC150 4.5

构造函数那里就是把根传进去，然后跑到最左边。 （即in-order的第一个要遍历的元素）