UT Austin CS MS 18Fall入學感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 5554|回复: 18
收起左侧

Facebook 10/11 on campus面筋

[复制链接] |试试Instant~ |关注本帖
我的人缘0
sf3 发表于 2016-10-14 12:49:02 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩

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

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

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

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

第一题: validBST, 让写recursive的第二题,多叉树,找最深节点的最低公共父节点(很多面经有,要是不懂我再解释)
. 留学申请论坛-一亩三分地
求保佑,求大米

评分

参与人数 3大米 +58 收起 理由
whdawn + 50
1451427216 + 3 感谢分享!
leixiang5 + 5 欢迎来介绍你知道的情况

查看全部评分


上一篇:10.13 Dropbox 电面
下一篇:FB CMU oncampus 面经

本帖被以下淘专辑推荐:

我的人缘0
WhatsFLAG 发表于 2017-2-1 23:53:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  88% (32)
 
 
11% (4)  踩
sf3 发表于 2016-10-17 10:43
给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那 ...

       1. 留学申请论坛-一亩三分地
      / | \. 留学申请论坛-一亩三分地
    2  3  4
   /-google 1point3acres
  5              5最深,最低公共父节点是2, return 2.

这里是不是返回5更合理一些呢?因为假如只有一个node应该返回它本身,所以本身也可以算作父亲节点?仿照二叉树的LCA,那里边节点本身也被考虑成为父亲节点的范畴,

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


参考leetcode里边的描述
回复

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 10:43:42 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
enzy 发表于 2016-10-15 17:31
没找到第二题的面经,求详解或者链接~~~感谢,感谢,祝好运。

给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那返回他自己。
        1
      / | \
    2  3  4
   /
  5              5最深,最低公共父节点是2, return 2.

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

        1
. 1point 3acres 论坛      / | \. 牛人云集,一亩三分地
    2  3  4
   /          \
  5           6   5,6最深,最低公共父节点是1, return 1
回复

使用道具 举报

我的人缘0
minggr 发表于 2016-10-14 12:51:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
第二题实在是太高频了 。。。
回复

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-14 12:53:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (196)
 
 
17% (41)  踩
坐等楼主的onsite面经~~~~

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

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

使用道具 举报

我的人缘0
jacky841102 发表于 2016-10-15 18:12:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
求第二题详细~ 谢谢
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-15 23:59:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!
回复

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 10:43:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
jacky841102 发表于 2016-10-15 18:12
求第二题详细~ 谢谢

给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那返回他自己。. 围观我们@1point 3 acres
        1
      / | \
    2  3  4
   /
  5              5最深,最低公共父节点是2, return 2.

        1
      / | \. Waral 博客有更多文章,
    2  3  4
   / \
  5  6         5,6最深,最低公共父节点是2, return 2

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

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 10:46:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
Badger96 发表于 2016-10-15 23:59. 1point 3acres 论坛
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!

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

使用道具 举报

我的人缘0
1451427216 发表于 2016-10-17 11:08:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (61)
 
 
3% (2)  踩
sf3 发表于 2016-10-17 10:46
不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次 ...

是不是把二叉树的left,right 改成for 循环遍历children就可以了?楼主能贴下code吗。谢谢

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 12:13:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
1451427216 发表于 2016-10-17 11:08. 1point 3acres 论坛
是不是把二叉树的left,right 改成for 循环遍历children就可以了?楼主能贴下code吗。谢谢

是的。就是两个child变成N个child。我也没有code,之前以为这题不会考,就没写。。
回复

使用道具 举报

我的人缘0
y111d 发表于 2016-10-17 12:40:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (50)
 
 
3% (2)  踩
多叉树遍历完了,最后怎么确定公共祖先呢? 是不是分,两个节点在不同的 child 上=> 返回 root, 在相同的 child 上=>去那个child 的分支上寻找?
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-17 13:04:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
sf3 发表于 2016-10-17 10:46
. 牛人云集,一亩三分地不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次 ...

谢谢!请问一下为什么最好top down计算深度?用bottom up计算会如何呢?然后就是找出最深的nodes后,可以用LCA of two nodes的方法来for loop两两相比得出最后的node吗?比如LCA(A, B)=X, 再LCA(X, C) = Y, 这样做可以吗?还是有更好的方法呢,感激不尽!
回复

使用道具 举报

我的人缘0
芥末青豆 发表于 2016-10-25 00:29:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (170)
 
 
1% (2)  踩
感谢楼主分享,明天也要on-campus了
回复

使用道具 举报

我的人缘0
xihesongruihua 发表于 2016-10-25 01:05:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
大神啊,拜一拜
回复

使用道具 举报

我的人缘0
芥末青豆 发表于 2016-10-28 00:37:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (170)
 
 
1% (2)  踩
sf3 发表于 2016-10-17 10:43
给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那 ...

楼主打的好工整,赞!
回复

使用道具 举报

我的人缘0
keytion 发表于 2016-10-31 06:30:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
第二题, recursive O(n) solution:
  1. #include <vector>
    . 一亩-三分-地,独家发布
  2. #include <unordered_map>
  3. #include <unordered_set>
  4. #include <map>
  5. #include <set>. From 1point 3acres bbs
  6. #include <queue>
  7. #include <cmath>. 1point3acres
  8. #include <algorithm>
  9. #include <numeric>
  10. #include <string>
  11. #include <list>
  12. #include <iostream>

  13. using namespace std;

  14. struct TreeNode
  15. {
  16.     TreeNode(int i) : label(i) {}
  17.     int label;
  18.     vector<TreeNode *> childrens;
  19. };

  20. class Solution
  21. {
  22.   public:
  23.     TreeNode *root; 来源一亩.三分地论坛.
  24.     Solution() {}

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

  31.     TreeNode *getParents(TreeNode *root, int &depth)
  32.     {. From 1point 3acres bbs
  33.         if (root->childrens.empty()). 1point3acres
  34.         {
  35.             depth = 1;. 1point 3acres 论坛
  36.             return root;. more info on 1point3acres
  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));. visit 1point3acres for more.
  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.         {. more info on 1point3acres
  51.             return roots[count[0]];
  52.         }
  53.         else
  54.         {
  55.             return root;
  56.         }. 1point 3acres 论坛
  57.     }

  58.     int getMax(vector<int> depths)
  59.     {. 牛人云集,一亩三分地
  60.         int ret = 0;
  61.         for (auto &v : depths). 一亩-三分-地,独家发布
  62.         {
  63.             ret = max(ret, v);
    .本文原创自1point3acres论坛
  64.         }. more info on 1point3acres
  65.         return ret;. 留学申请论坛-一亩三分地
  66.     }

  67.     vector<int> countMax(vector<int> depths, int maxV)
  68.     {. From 1point 3acres bbs
  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;
  76.     }
  77. };

  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));.1point3acres网
  85.     // root->childrens[0]->childrens.push_back(new TreeNode(6));
  86.     root->childrens[2]->childrens.push_back(new TreeNode(6));.本文原创自1point3acres论坛

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

使用道具 举报

我的人缘0
英伦十六世纪 发表于 2017-2-1 11:26:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (22)
 
 
8% (2)  踩
on campus是在白板上做题吗?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-19 16:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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