一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2289|回复: 16
收起左侧

Facebook 10/11 on campus面筋

[复制链接] |试试Instant~ |关注本帖
sf3 发表于 2016-10-14 12:49:02 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一上来就做题,非常直接
-google 1point3acres45分钟, 两道都是面经题:

第一题: validBST, 让写recursive的第二题,多叉树,找最深节点的最低公共父节点(很多面经有,要是不懂我再解释)

求保佑,求大米. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

3

查看全部评分

 楼主| sf3 发表于 2016-10-17 10:43:42 | 显示全部楼层
enzy 发表于 2016-10-15 17:31
没找到第二题的面经,求详解或者链接~~~感谢,感谢,祝好运。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那返回他自己。. 1point3acres.com/bbs
        1. 1point3acres.com/bbs
      / | \
    2  3  4
   /
  5              5最深,最低公共父节点是2, return 2.

        1
      / | \
    2  3  4
   / \
  5  6         5,6最深,最低公共父节点是2, return 2

        1
      / | \
    2  3  4
   /          \
  5           6   5,6最深,最低公共父节点是1, return 1
回复 支持 1 反对 0

使用道具 举报

minggr 发表于 2016-10-14 12:51:49 | 显示全部楼层
第二题实在是太高频了 。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-14 12:53:23 | 显示全部楼层
坐等楼主的onsite面经~~~~
回复 支持 反对

使用道具 举报

头像被屏蔽
enzy 发表于 2016-10-15 17:31:40 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-10-15 18:12:57 | 显示全部楼层
求第二题详细~ 谢谢
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-15 23:59:54 | 显示全部楼层
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-10-17 10:43:53 | 显示全部楼层
jacky841102 发表于 2016-10-15 18:12.鏈枃鍘熷垱鑷1point3acres璁哄潧
求第二题详细~ 谢谢

给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那返回他自己。. 1point3acres.com/bbs
        1
      / | \
    2  3  4
   /
  5              5最深,最低公共父节点是2, return 2.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        1. Waral 鍗氬鏈夋洿澶氭枃绔,
      / | \. 1point3acres.com/bbs
    2  3  4
   / \
  5  6         5,6最深,最低公共父节点是2, return 2

        1. From 1point 3acres bbs
      / | \
    2  3  4
   /          \
  5           6   5,6最深,最低公共父节点是1, return 1
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-10-17 10:46:01 | 显示全部楼层
Badger96 发表于 2016-10-15 23:59
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!

不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次高度,worst case will be O(n^2).
回复 支持 反对

使用道具 举报

1451427216 发表于 2016-10-17 11:08:09 | 显示全部楼层
sf3 发表于 2016-10-17 10:46. Waral 鍗氬鏈夋洿澶氭枃绔,
不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次 ...
. from: 1point3acres.com/bbs
是不是把二叉树的left,right 改成for 循环遍历children就可以了?楼主能贴下code吗。谢谢
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-10-17 12:13:14 | 显示全部楼层
1451427216 发表于 2016-10-17 11:08
是不是把二叉树的left,right 改成for 循环遍历children就可以了?楼主能贴下code吗。谢谢
. visit 1point3acres.com for more.
是的。就是两个child变成N个child。我也没有code,之前以为这题不会考,就没写。。
回复 支持 反对

使用道具 举报

y111d 发表于 2016-10-17 12:40:52 | 显示全部楼层
多叉树遍历完了,最后怎么确定公共祖先呢? 是不是分,两个节点在不同的 child 上=> 返回 root, 在相同的 child 上=>去那个child 的分支上寻找?
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-17 13:04:52 | 显示全部楼层
sf3 发表于 2016-10-17 10:46
不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次 ...
-google 1point3acres
谢谢!请问一下为什么最好top down计算深度?用bottom up计算会如何呢?然后就是找出最深的nodes后,可以用LCA of two nodes的方法来for loop两两相比得出最后的node吗?比如LCA(A, B)=X, 再LCA(X, C) = Y, 这样做可以吗?还是有更好的方法呢,感激不尽!
回复 支持 反对

使用道具 举报

芥末青豆 发表于 2016-10-25 00:29:56 | 显示全部楼层
感谢楼主分享,明天也要on-campus了
回复 支持 反对

使用道具 举报

xihesongruihua 发表于 2016-10-25 01:05:45 | 显示全部楼层
大神啊,拜一拜
回复 支持 反对

使用道具 举报

芥末青豆 发表于 2016-10-28 00:37:11 | 显示全部楼层
sf3 发表于 2016-10-17 10:43
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那 ...
. 1point 3acres 璁哄潧
楼主打的好工整,赞!
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-31 06:30:56 | 显示全部楼层
第二题, recursive O(n) solution:
  1. #include <vector>
  2. #include <unordered_map>
  3. #include <unordered_set>
  4. #include <map>. From 1point 3acres bbs
  5. #include <set>
  6. #include <queue>
  7. #include <cmath>
  8. #include <algorithm>-google 1point3acres
  9. #include <numeric>. Waral 鍗氬鏈夋洿澶氭枃绔,
  10. #include <string>
  11. #include <list>
  12. #include <iostream>. From 1point 3acres bbs

  13. using namespace std;

  14. struct TreeNode 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15. {
  16.     TreeNode(int i) : label(i) {}. Waral 鍗氬鏈夋洿澶氭枃绔,
  17.     int label;. From 1point 3acres bbs
  18.     vector<TreeNode *> childrens;
  19. };

  20. class Solution
  21. {
  22.   public:. 1point 3acres 璁哄潧
  23.     TreeNode *root;
  24.     Solution() {}-google 1point3acres

  25.     int getParents()
  26.     {
    . visit 1point3acres.com for more.
  27.         int depth = 0;
  28.         auto tmp = getParents(root, depth);
  29.         return tmp->label;
  30.     }

  31.     TreeNode *getParents(TreeNode *root, int &depth)
  32.     {
  33.         if (root->childrens.empty())
  34.         {
  35.             depth = 1;. more info on 1point3acres.com
  36.             return root;
  37.         }
  38.         vector<int> depths;
  39.         vector<TreeNode *> roots;
  40.         for (auto &v : root->childrens)
  41.         {
  42.             int depthtmp = 0;
  43.             roots.push_back(getParents(v, depthtmp));.1point3acres缃
  44.             depths.push_back(depthtmp);
  45.         }
  46.         int maxV = getMax(depths);
  47.         depth = maxV + 1;
  48.         auto count = countMax(depths, maxV);
  49.         if (count.size() == 1)
  50.         {
  51.             return roots[count[0]];
  52.         }
  53.         else
  54.         {
  55.             return root;
  56.         }
  57.     }

  58.     int getMax(vector<int> depths)
  59.     {
  60.         int ret = 0;
  61.         for (auto &v : depths)
  62.         {
  63.             ret = max(ret, v);
  64.         }
  65.         return ret;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  66.     }. from: 1point3acres.com/bbs

  67.     vector<int> countMax(vector<int> depths, int maxV)
  68.     {
  69.         vector<int> ret;
  70.         for (int i = 0; i < depths.size(); i++)
  71.         {
  72.             if (depths[i] == maxV)
  73.                 ret.push_back(i);
  74.         }
  75.         return ret;-google 1point3acres
  76.     }
  77. };. 鍥磋鎴戜滑@1point 3 acres

  78. int main()
  79. {
  80.     TreeNode *root = new TreeNode(1);
  81.     root->childrens.push_back(new TreeNode(2));
  82.     root->childrens.push_back(new TreeNode(3));
  83.     root->childrens.push_back(new TreeNode(4));
  84.     root->childrens[0]->childrens.push_back(new TreeNode(5));
  85.     // root->childrens[0]->childrens.push_back(new TreeNode(6));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  86.     root->childrens[2]->childrens.push_back(new TreeNode(6));

  87.     Solution sl;
  88.     sl.root = root;
  89.     cout << sl.getParents() << endl;
  90.     return 0;
  91. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-18 12:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表