Facebook 二面面经

昨天面完的，被开了一个天大的玩笑，面试前把地里所有的面经都看了一遍，并且做了一遍，还整理成了文档，leetcode上facebook标签的都重新写了遍最优解，心想着这下万无一失了。
结果面试碰到个【没见过的题】，真是给跪了...
面试官是个欧洲白人小哥，自从把题目打出来后，就再没说过话，就看着我这边一边胡言乱语一边敲代码...
然而我感觉写的就是一团乱泥啊！
下面是题目

Given a tree, find the smallest subtree that contains all of the tree's deepest nodes.
                  a
               /  |  \
             b   c   d
           /   

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

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

，都吓出心脏病了...结果一看发现是 Facebook Interview Survey...感觉已经再承受不住这样的暴击了...

补充内容 (2016-1-31 15:56):
万万没想到居然过了...运气真好只投了一家公司，拿了一个面试...就过了...感谢一亩三分地....

补充内容 (2016-2-6 04:44):
面经总结在这里——

raccoon 发表于 2016-2-6 03:01
恭喜楼主！！楼主是第二天就收到recruiter的邮件约电话了是吗..昨天面了二面，等待的好忐忑，刚也被那个sur ...

我是周四下午面试，周五下午都到survey...然后周日凌晨1点多收到HR的congratulation...

楼主厉害！！楼主准备的万无一失，虽然碰到了新题但能力还是在的，所以过了也是必然的~~

就是算height。如果所有subtree height都一样，那就返回root，否则返回height最高那个subtree所返回的答案。

我把代码也贴出来吧，不过不保证任何的正确性...

1. vector<TreeNode*> BFS(TreeNode *root,int depth)
   
2. {
   
3.   if(!root)
   
4.     return {};
   
5.   queue<pair<TreeNode *,int>> Q;
   
6.   Q.push({root,1});
   
7.   vector<TreeNode *> res;
   
8.   while(!Q.empty())
   
9.   {
   
10.     auto node = Q.front();
    
11.     Q.pop();
    
12.     if(adj[node].size()==0)
    
13.     {
    
14.       if(node.second ==depth)
    
15.       {
    
16.         res.push_back(node);
    
17.       }
    
18.     }
    
19.     else
    
20.     {
    
21.       for(auto n: adj[node])
    
22.       {
    
23.         Q.push({n,node.second+1});
    
24.       }
    
25.     }
    
26.   }
    
27.   return res;
    
28.    
    
29. }
    
30. pair<int,TreeNode *> DFS(TreeNode *root,vector<TreeNode *> node)
    
31. {
    
32.   if(!root)
    
33.     return{0,NULL};
    
34.   int total = 0;
    
35.   for(auto n: adj[root])
    
36.   {
    
37.     auto  p = DFS(n,node);
    
38.     for(auto deep: node)
    
39.       if(root==deep)
    
40.         total++;
    
41.     total += p.first;
    
42.     if(p.first == node.size())
    
43.       return p;
    
44.   }
    
45. 
    
46.   return {total,total==node.size()?root:NULL};
    
47.   
    
48. }
    
49. TreeNode * SmallestTree(TreeNode *root,int depth)
    
50. {
    
51.   vector<TreeNode *> node = BFS(root,depth);
    
52.   return DFS(root,node).second;
    
53. }

复制代码

这个也是面经里的题：http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148413&pid=2068421&page=1&extra=page%3D1%26filter%3Dsortid%26sortid%3D311#pid2068421

需要同时返回height,以及当前子树的最深节点（用引用可能会方便点）....第一次见确实挺难的....

补充内容 (2016-1-30 03:10):
以及“当前子树最深节点的lowest common ancestor"

昨天onsite前还打了份楼主的文档对着题目过了一次
patpat.看来楼主整理漏了一个题  因为那个帖子是实习onsite而你只筛选了实习电面嘛 太倒霉了=-=

Howie 发表于 2016-1-31 05:39
昨天onsite前还打了份楼主的文档对着题目过了一次
patpat.看来楼主整理漏了一个题  因为那个帖子是实习ons ...

嗯哼~那你onsite怎么样 有结果了么...

songty11 发表于 2016-1-31 05:57
嗯哼~那你onsite怎么样 有结果了么...

当然没木有。。昨天面完的。。今天周末呢，hr说估计下周末之前才有

Howie 发表于 2016-1-31 06:02
当然没木有。。昨天面完的。。今天周末呢，hr说估计下周末之前才有

额...我身边朋友拒信不断...吓得我心神不宁...死也不让我死干脆...

如果没见过 第一次就能给出这个解法不容易