谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5389|回复: 18
收起左侧

Facebook 10/11 on campus面筋

[复制链接] |试试Instant~ |关注本帖
我的人缘0
sf3 发表于 2016-10-14 12:49:02 | 显示全部楼层 |阅读模式
  此人我要顶:
 
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 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
sf3 发表于 2016-10-17 10:43
给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那 ...

       1-google 1point3acres
      / | \
    2  3  4
   /
  5              5最深,最低公共父节点是2, return 2.

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

参考leetcode里边的描述
回复 支持 1 反对 0

使用道具 举报

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

给一个tree,每个node 有很多children,找到所有最深的nodes 的common ancestor, 比如只有一个点最深,那返回他自己。.1point3acres网
        1
      / | \ 来源一亩.三分地论坛.
    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

使用道具 举报

我的人缘0
minggr 发表于 2016-10-14 12:51:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题实在是太高频了 。。。
回复 支持 反对

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-14 12:53:23 | 显示全部楼层
  此人我要顶:
 
38% (4) 【我投】
  此人我要踩:
 
62% (9) 【我投】
坐等楼主的onsite面经~~~~
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
jacky841102 发表于 2016-10-15 18:12:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求第二题详细~ 谢谢
回复 支持 反对

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-15 23:59:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 10:43:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jacky841102 发表于 2016-10-15 18:12
. 一亩-三分-地,独家发布求第二题详细~ 谢谢

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

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

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

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 10:46:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Badger96 发表于 2016-10-15 23:59
求解释第二题怎么做,跟一般的二叉树做法有什么不同呢,感谢!

不同就是用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% (暂未有人投票) 【我投】
sf3 发表于 2016-10-17 10:46
不同就是用for loop遍历children. 最好top down计算高度,bottom up找出candidate. 如果每个node都算一次 ...

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

使用道具 举报

我的人缘0
 楼主| sf3 发表于 2016-10-17 12:13:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
1451427216 发表于 2016-10-17 11:08
是不是把二叉树的left,right 改成for 循环遍历children就可以了?楼主能贴下code吗。谢谢

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

使用道具 举报

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

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-17 13:04:52 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
感谢楼主分享,明天也要on-campus了
回复 支持 反对

使用道具 举报

我的人缘0
xihesongruihua 发表于 2016-10-25 01:05:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
大神啊,拜一拜
回复 支持 反对

使用道具 举报

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

楼主打的好工整,赞!
回复 支持 反对

使用道具 举报

我的人缘0
keytion 发表于 2016-10-31 06:30:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题, recursive O(n) solution:
  1. #include <vector>. 围观我们@1point 3 acres
  2. #include <unordered_map>
  3. #include <unordered_set>. from: 1point3acres
  4. #include <map>. 留学申请论坛-一亩三分地
  5. #include <set>
  6. #include <queue>
  7. #include <cmath>. 牛人云集,一亩三分地
  8. #include <algorithm>
  9. #include <numeric>-google 1point3acres
  10. #include <string>
  11. #include <list>
  12. #include <iostream>. 围观我们@1point 3 acres

  13. using namespace std;.留学论坛-一亩-三分地
  14. .本文原创自1point3acres论坛
  15. struct TreeNode
  16. {
  17.     TreeNode(int i) : label(i) {}
  18.     int label;
  19.     vector<TreeNode *> childrens;
  20. };

  21. class Solution. visit 1point3acres for more.
  22. {
  23.   public:
  24.     TreeNode *root;
  25.     Solution() {}

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

  32.     TreeNode *getParents(TreeNode *root, int &depth)
  33.     {
  34.         if (root->childrens.empty())
  35.         {
  36.             depth = 1;.留学论坛-一亩-三分地
  37.             return root;
  38.         }
  39.         vector<int> depths;
  40.         vector<TreeNode *> roots;
  41.         for (auto &v : root->childrens)
  42.         {
  43.             int depthtmp = 0;
  44.             roots.push_back(getParents(v, depthtmp));
  45.             depths.push_back(depthtmp);
  46.         }
  47.         int maxV = getMax(depths);
  48.         depth = maxV + 1;
  49.         auto count = countMax(depths, maxV);
  50.         if (count.size() == 1)
  51.         {. 1point 3acres 论坛
  52.             return roots[count[0]];
  53.         }
  54.         else
  55.         {
  56.             return root;. visit 1point3acres for more.
  57.         }
  58.     }
  59. . 留学申请论坛-一亩三分地
  60.     int getMax(vector<int> depths)
  61.     {
  62.         int ret = 0;
  63.         for (auto &v : depths). 1point3acres
  64.         {
  65.             ret = max(ret, v);
  66.         }. From 1point 3acres bbs
  67.         return ret;
  68.     }

  69.     vector<int> countMax(vector<int> depths, int maxV). 留学申请论坛-一亩三分地
  70.     {
  71.         vector<int> ret;. Waral 博客有更多文章,
  72.         for (int i = 0; i < depths.size(); i++)
  73.         {
  74.             if (depths[i] == maxV). visit 1point3acres for more.
  75.                 ret.push_back(i);. 一亩-三分-地,独家发布
  76.         }
  77.         return ret;. 1point3acres
  78.     }
    . 1point3acres
  79. };

  80. int main()
  81. {
  82.     TreeNode *root = new TreeNode(1);.本文原创自1point3acres论坛
  83.     root->childrens.push_back(new TreeNode(2));
  84.     root->childrens.push_back(new TreeNode(3));
  85.     root->childrens.push_back(new TreeNode(4));
  86.     root->childrens[0]->childrens.push_back(new TreeNode(5));.1point3acres网
  87.     // root->childrens[0]->childrens.push_back(new TreeNode(6));
  88.     root->childrens[2]->childrens.push_back(new TreeNode(6));

  89.     Solution sl;
  90.     sl.root = root;. 牛人云集,一亩三分地
  91.     cout << sl.getParents() << endl;
  92.     return 0;
  93. }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
英伦十六世纪 发表于 2017-2-1 11:26:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
on campus是在白板上做题吗?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-25 21:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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