一亩三分地论坛

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

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

Facebook 二面面经

[复制链接] |试试Instant~ |关注本帖
songty11 发表于 2016-1-30 01:54:26 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

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

Given a tree, find the smallest subtree that contains all of the tree's deepest nodes.
                  a
               /  |  \
             b   c   d
           /   \       |
         e      f      g
       /       /  \
      h      i     j
depth of tree: 4
deepest nodes:[h,i,j]
least common ancestor of [h,i,j]: b
return: b

我问面试官这个树的定义呢,我要不要写一写,面试官说不用了,你就随意写吧,我可以【猜】啊!
我就找到leetcode上面哪个lowest common ancestor of binary tree,一通瞎改了改改成了多叉树版本的,这时候我是直接使用了 h,i,j 这几个节点假设是输入的。
然后面试官一直沉默,我说,我觉得这能跑通(我其实一点都不觉得),面试官说哦那你这几个点是什么鬼,我说咦这不是输入么?哦这不是输入啊!那我再写个BFS先找到最深的点吧,然后又写了个BFS,全程面试官不说话,就看着我一个人干着急,然后,时间竟飞也似的到了40分钟,我就跟面试官说,这个您还在么,面试官说我看着呢,我说要不我给您讲讲我这个代码的意思?面试官说好啊,我就讲讲讲(我也不知道对不对),面试官听完说cool,我心想cool毛啊一点都不cool啊,我这写的都是什么乱泥。
然后面试官说那你讲讲时间复杂度,我说BFS肯定是O(n),下面用了递归,每个节点访问一遍,也是O(n),所以总的就是O(n) 咯(其实我根本不知道是不是),面试官说行吧make sense,来问我问题吧...
. From 1point 3acres bbs. more info on 1point3acres.com
最后告诉我recruiter会在这周或者下周联系我。现在并无消息。
世间事大抵如此...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-1-30 07:28):. 1point 3acres 璁哄潧
太特么刺激了...刚刚收到一封邮件以 Thanks for interviewing with us at Facebook开头的...还以为是拒信,都吓出心脏病了...结果一看发现是 Facebook Interview Survey...感觉已经再承受不住这样的暴击了...
-google 1point3acres
补充内容 (2016-1-31 15:56):
万万没想到居然过了...运气真好只投了一家公司,拿了一个面试...就过了...感谢一亩三分地....

补充内容 (2016-2-6 04:44):
面经总结在这里——
http://www.1point3acres.com/bbs/ ... choption%5B3046%...

评分

11

查看全部评分

本帖被以下淘专辑推荐:

 楼主| songty11 发表于 2016-2-6 04:46:24 | 显示全部楼层
raccoon 发表于 2016-2-6 03:01
恭喜楼主!!楼主是第二天就收到recruiter的邮件约电话了是吗..昨天面了二面,等待的好忐忑,刚也被那个sur ...

我是周四下午面试,周五下午都到survey...然后周日凌晨1点多收到HR的congratulation...
回复 支持 1 反对 0

使用道具 举报

坐北朝南的学渣 发表于 2016-2-1 07:42:38 | 显示全部楼层
楼主厉害!!楼主准备的万无一失,虽然碰到了新题但能力还是在的,所以过了也是必然的~~
回复 支持 1 反对 0

使用道具 举报

xutopia 发表于 2016-1-30 02:53:40 | 显示全部楼层
就是算height。如果所有subtree height都一样,那就返回root,否则返回height最高那个subtree所返回的答案。
回复 支持 1 反对 0

使用道具 举报

 楼主| songty11 发表于 2016-1-30 02:20:29 | 显示全部楼层
我把代码也贴出来吧,不过不保证任何的正确性...
  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});. more info on 1point3acres.com
  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.       }. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.     }-google 1point3acres
  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). from: 1point3acres.com/bbs
  40.         total++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.     total += p.first;
  42.     if(p.first == node.size())
  43.       return p;
  44.   }

  45.   return {total,total==node.size()?root:NULL};
  46.   -google 1point3acres
  47. }
  48. TreeNode * SmallestTree(TreeNode *root,int depth)
  49. {
  50.   vector<TreeNode *> node = BFS(root,depth);
  51.   return DFS(root,node).second;
  52. }
复制代码
回复 支持 反对

使用道具 举报

mzhqlh 发表于 2016-1-30 03:06:15 | 显示全部楼层
这个也是面经里的题: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):. 1point3acres.com/bbs
以及“当前子树最深节点的lowest common ancestor"
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2016-1-30 03:40:26 | 显示全部楼层
试着用Java写了写
  1. import java.io.*;
  2. import java.util.*;

  3. class TreeNode {
  4.     int val;
  5.     ArrayList<TreeNode> children;
  6.     TreeNode(int val) {
  7.         this.val = val;
  8.         children = new ArrayList<>();
  9.     }
  10. }
  11. . 鍥磋鎴戜滑@1point 3 acres
  12. class TreeNodeWrapper {
  13.     TreeNode node;
  14.     int maxDepth;
  15.     TreeNodeWrapper(TreeNode node, int maxDepth) {
  16.         this.node = node;
  17.         this.maxDepth = maxDepth;
  18.     }
  19. }

  20. class Solution {
  21.     public TreeNode find(TreeNode root) {
  22.         if (root == null || root.children.isEmpty()) {
  23.             return root;
  24.         }
  25.         return helper(root).node;
  26.     }. 鍥磋鎴戜滑@1point 3 acres
  27.    
  28.     public TreeNodeWrapper helper(TreeNode root) {
  29.         if (root.children.isEmpty()) {
  30.             return new TreeNodeWrapper(root, 1);
  31.         }
  32.         
  33.         int maxDepth = Integer.MIN_VALUE;
  34.         int size = root.children.size();
  35.         TreeNodeWrapper r = new TreeNodeWrapper(root, maxDepth);
  36.         
  37.         for (int i = 0; i < size; i++) {
  38.             TreeNodeWrapper wrapper = helper(root.children.get(i));
  39.             if (wrapper.maxDepth > maxDepth) {
  40.                 maxDepth = wrapper.maxDepth;
  41.                 r.node = (maxDepth == 1? root: wrapper.node);. 1point3acres.com/bbs
  42.                 r.maxDepth = wrapper.maxDepth + 1;
  43.             } else if (wrapper.maxDepth == maxDepth) {. 1point 3acres 璁哄潧
  44.                 r.node = root;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45.             }        
  46.         }
  47.         return r;
  48.     }
  49. }
复制代码
回复 支持 反对

使用道具 举报

Howie 发表于 2016-1-31 05:39:23 | 显示全部楼层
昨天onsite前还打了份楼主的文档对着题目过了一次
patpat.看来楼主整理漏了一个题  因为那个帖子是实习onsite而你只筛选了实习电面嘛 太倒霉了=-=
回复 支持 反对

使用道具 举报

 楼主| songty11 发表于 2016-1-31 05:57:12 | 显示全部楼层
Howie 发表于 2016-1-31 05:39
昨天onsite前还打了份楼主的文档对着题目过了一次
patpat.看来楼主整理漏了一个题  因为那个帖子是实习ons ...
.1point3acres缃
嗯哼~那你onsite怎么样 有结果了么...
回复 支持 反对

使用道具 举报

Howie 发表于 2016-1-31 06:02:38 | 显示全部楼层
songty11 发表于 2016-1-31 05:57
嗯哼~那你onsite怎么样 有结果了么...

当然没木有。。昨天面完的。。今天周末呢,hr说估计下周末之前才有
回复 支持 反对

使用道具 举报

 楼主| songty11 发表于 2016-1-31 06:33:31 | 显示全部楼层
Howie 发表于 2016-1-31 06:02
当然没木有。。昨天面完的。。今天周末呢,hr说估计下周末之前才有

额...我身边朋友拒信不断...吓得我心神不宁...死也不让我死干脆...
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-31 08:23:29 | 显示全部楼层
如果没见过 第一次就能给出这个解法不容易
回复 支持 反对

使用道具 举报

可可米汐 发表于 2016-2-1 03:15:26 | 显示全部楼层
楼主,能给分面经汇总给我么。。。积分不够

补充内容 (2016-2-1 03:16):.1point3acres缃
xiaoxiao.t@hotmail.com
回复 支持 反对

使用道具 举报

raccoon 发表于 2016-2-6 03:01:00 | 显示全部楼层
恭喜楼主!!楼主是第二天就收到recruiter的邮件约电话了是吗..昨天面了二面,等待的好忐忑,刚也被那个survey吓到...
回复 支持 反对

使用道具 举报

duanj99 发表于 2016-2-6 03:22:01 | 显示全部楼层
嗯嗯,先恭喜了。然后,请问可以把整理的面经啥的发一份么,哈哈哈哈
回复 支持 反对

使用道具 举报

 楼主| songty11 发表于 2016-2-6 04:44:11 | 显示全部楼层
duanj99 发表于 2016-2-6 03:22
嗯嗯,先恭喜了。然后,请问可以把整理的面经啥的发一份么,哈哈哈哈

http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-6 05:11:14 | 显示全部楼层
DFS 的同时记录可以达到最底层的节点 同时记录这个节点的depth。 map<int, set<int>> trace_map

第1个int表示节点所在的depth set存这个depth中所有能到最低点的节点
. 鍥磋鎴戜滑@1point 3 acres
trace_map建好后,所有能到最底层的节点都找出来了 而且是按层级从低到高放在trace_map中的 如果 set的元素不止一个 那这个不是最低点. visit 1point3acres.com for more.
. from: 1point3acres.com/bbs
按顺序找到的第一个 set之后一个元素的 那个key 就是你要返回的节点. From 1point 3acres bbs

补充内容 (2016-2-6 05:12):
对照楼主给的例子 很好理解
回复 支持 反对

使用道具 举报

huangnjsu 发表于 2016-2-17 13:32:46 | 显示全部楼层
楼主!我阅读权限不够,周五要面FB了,能不能发我一份你的总结,十分感谢!huangnjsu@gmail.com
回复 支持 反对

使用道具 举报

YJ_Li 发表于 2016-2-18 07:23:24 | 显示全部楼层
楼主面经资料汇总能发 yijin.li.jack@gmail.com, 权限不够进不去,感谢
回复 支持 反对

使用道具 举报

YJ_Li 发表于 2016-2-18 07:25:11 | 显示全部楼层
电面的时候能查leetcode 或在网上找其他资料吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 17:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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