Facebook 10/11 on campus面筋

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

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

多叉树遍历完了，最后怎么确定公共祖先呢？ 是不是分，两个节点在不同的 child 上=> 返回 root， 在相同的 child 上=>去那个child 的分支上寻找？

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

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

感谢楼主分享，明天也要on-campus了

大神啊，拜一拜

sf3 发表于 2016-10-17 10:43
给一个tree，每个node 有很多children，找到所有最深的nodes 的common ancestor, 比如只有一个点最深，那 ...

楼主打的好工整，赞！

第二题， recursive O(n) solution:

1. #include <vector>
   
2. #include <unordered_map>
   
3. #include <unordered_set>
   
4. #include <map>
   
5. #include <set>
   
6. #include <queue>
   
7. #include <cmath>
   
8. #include <algorithm>
   
9. #include <numeric>
   
10. #include <string>
    
11. #include <list>
    
12. #include <iostream>
    
13. 
    
14. using namespace std;
    
15. 
    
16. struct TreeNode
    
17. {
    
18.     TreeNode(int i) : label(i) {}
    
19.     int label;
    
20.     vector<TreeNode *> childrens;
    
21. };
    
22. 
    
23. class Solution
    
24. {
    
25.   public:
    
26.     TreeNode *root;
    
27.     Solution() {}
    
28. 
    
29.     int getParents()
    
30.     {
    
31.         int depth = 0;
    
32.         auto tmp = getParents(root, depth);
    
33.         return tmp->label;
    
34.     }
    
35. 
    
36.     TreeNode *getParents(TreeNode *root, int &depth)
    
37.     {
    
38.         if (root->childrens.empty())
    
39.         {
    
40.             depth = 1;
    
41.             return root;
    
42.         }
    
43.         vector<int> depths;
    
44.         vector<TreeNode *> roots;
    
45.         for (auto &v : root->childrens)
    
46.         {
    
47.             int depthtmp = 0;
    
48.             roots.push_back(getParents(v, depthtmp));
    
49.             depths.push_back(depthtmp);
    
50.         }
    
51.         int maxV = getMax(depths);
    
52.         depth = maxV + 1;
    
53.         auto count = countMax(depths, maxV);
    
54.         if (count.size() == 1)
    
55.         {
    
56.             return roots[count[0]];
    
57.         }
    
58.         else
    
59.         {
    
60.             return root;
    
61.         }
    
62.     }
    
63. 
    
64.     int getMax(vector<int> depths)
    
65.     {
    
66.         int ret = 0;
    
67.         for (auto &v : depths)
    
68.         {
    
69.             ret = max(ret, v);
    
70.         }
    
71.         return ret;
    
72.     }
    
73. 
    
74.     vector<int> countMax(vector<int> depths, int maxV)
    
75.     {
    
76.         vector<int> ret;
    
77.         for (int i = 0; i < depths.size(); i++)
    
78.         {
    
79.             if (depths[i] == maxV)
    
80.                 ret.push_back(i);
    
81.         }
    
82.         return ret;
    
83.     }
    
84. };
    
85. 
    
86. int main()
    
87. {
    
88.     TreeNode *root = new TreeNode(1);
    
89.     root->childrens.push_back(new TreeNode(2));
    
90.     root->childrens.push_back(new TreeNode(3));
    
91.     root->childrens.push_back(new TreeNode(4));
    
92.     root->childrens[0]->childrens.push_back(new TreeNode(5));
    
93.     // root->childrens[0]->childrens.push_back(new TreeNode(6));
    
94.     root->childrens[2]->childrens.push_back(new TreeNode(6));
    
95. 
    
96.     Solution sl;
    
97.     sl.root = root;
    
98.     cout << sl.getParents() << endl;
    
99.     return 0;
    
100. }

复制代码

on campus是在白板上做题吗？

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

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