[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 11794|回复: 35
收起左侧

FB 8/19 面经

[复制链接] |试试Instant~ |关注本帖
lvvvvv 发表于 2016-8-19 11:45:02 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 博士 全职@Facebook - 内推 - Onsite  | Other | 在职跳槽

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

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

x


两轮design, 两轮 coding
design 答得不好, 问得很细,. 牛人云集,一亩三分地

coding 有一轮不好:. 一亩-三分-地,独家发布

给一个 二叉树 , 求最深节点的最小公共父节点。

     1
  2   3
     5  6    return 3.
. 1point 3acres 论坛
       1  
来源一亩.三分地论坛.     2   3
4      5 6   retrun 1.
先用 recursive  , 很快写出来了, 要求用 iterative 。 时间不够了。。。
. from: 1point3acres
有什么比较好的办法 ?

评分

2

查看全部评分

aifer 发表于 2016-10-12 05:45:14 | 显示全部楼层
minggr 发表于 2016-10-10 01:51
Iteration如下,就是post-order traversal的iterative版本

贴个自己的code.用的是level traversal,找出最深层的head和tail节点,用一个map来track 节点到父节点的映射。
如果head 和tail相等,说明最深层就一个节点,如果不等,分别从map里向parent节点搜索,知道发现一个公共的节点即为LCA。
public int lcaBFS(TreeNode root) {.1point3acres网
                if(root == null)        return -1;. 牛人云集,一亩三分地
                // <node -> parent node>
                Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
.1point3acres网
                TreeNode head = null, tail = null;        // the head and tail node in a level
                Queue<TreeNode> que = new LinkedList<TreeNode>();
                que.offer(root);
                map.put(root, null);. 1point3acres
                while(!que.isEmpty()) {
                        head = null; tail = null;
                        int sz = que.size();
                        while(sz-- > 0) {
                                TreeNode curr = que.poll();
                                if(head == null)        head = curr;. 留学申请论坛-一亩三分地
                                if(sz == 0)        tail = curr;
                                if(curr.left != null) {
                                        map.put(curr.left, curr);
                                        que.offer(curr.left);
                                }
. 留学申请论坛-一亩三分地                                if(curr.right != null) {
                                        map.put(curr.right, curr);
                                        que.offer(curr.right);. visit 1point3acres for more.
                                }
                        }
                }

                while(head != tail){
                        head = map.get(head);
                        tail = map.get(tail);
                }
                return head.val; 来源一亩.三分地论坛.
        }
回复 支持 4 反对 1

使用道具 举报

hychin 发表于 2016-8-19 12:16:21 | 显示全部楼层
recursive 直接DFS找最底层最左和最右边的点然后求这两个点的LCA即可,iteration就变成BFS找最后一层的第一个和最后一个,找出点后求LCA即可
回复 支持 4 反对 0

使用道具 举报

zzh730 发表于 2016-8-20 12:20:08 | 显示全部楼层
最近这个题很高频啊,其实dfs遍历,返回的时候返回lca和depth,每个node如果有大于一个子节点的depth相同就返回这个node,如果有一个子节点depth更深就返回个子节点lca,这个o(n)就可以了
回复 支持 2 反对 0

使用道具 举报

熊亮亮111 发表于 2016-8-19 12:53:26 | 显示全部楼层
DFS的话,最直接的办法还是iterative  post order traversal用hashmap存每个child node的深度和candidate。 hashmap可以变走边删除 space 也能做到O(h)  time 还是O(N)

BFS也可以 level order traversal 每个node 都带一个path info  比如向左是0  向右是1  最后一层的所有node的共同前缀就是lca 第一个例子 最后一层5 、6 就是010 011  共同前缀是01  也就是 3那个node 第二个例子最后一层是4 5 6  就是000 010 011  共同前缀是0  就是root 1 node
回复 支持 2 反对 0

使用道具 举报

cicean 发表于 2016-9-4 14:26:15 | 显示全部楼层
是BST 么? 还是BT
回复 支持 1 反对 0

使用道具 举报

ChrisGates23 发表于 2016-8-19 12:07:49 | 显示全部楼层
能说说design的题目吗
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-8-19 12:14:02 | 显示全部楼层
有一个比较naive的想法,先BFS(同时用map存节点映射到父节点)到最后一层,然后从最后一层开始往上找父节点直到只有一个父节点。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2016-8-19 12:15:56 | 显示全部楼层
iterative感觉可以用一个HashMap 得到最深节点到根节点的路径。然后K个最深节点求交点。
回复 支持 反对

使用道具 举报

 楼主| lvvvvv 发表于 2016-8-19 12:29:43 | 显示全部楼层
hychin 发表于 2016-8-19 12:16. from: 1point3acres
recursive 直接DFS找最底层最左和最右边的点然后求这两个点的LCA即可,iteration就变成BFS找最后一层的第一 ...

理论上是这样,
每一层记录一个leftmost, 一个 rightmost, 如果没有下层了, 再从 root 找 path ?-google 1point3acres
感觉应该有更好办法 。
回复 支持 反对

使用道具 举报

sitsit 发表于 2016-8-20 01:01:08 | 显示全部楼层
我的想法是: BFS,保存每一层的queue,queue的节点中保存该节点父亲节点在上一层中的位置。遍历完之后,对最后一个队列的头尾俩节点同时向上搜索父亲,直到父亲相同。有点绕,不知到说清楚没有
回复 支持 反对

使用道具 举报

cacofish 发表于 2016-8-20 04:35:19 | 显示全部楼层
为啥我觉得题目不太看得懂。如果只有一个节点深度3, 一个节点深度2,返回谁的LCA?如果一个深度3,两个深度2,返回哪两个的LCA
回复 支持 反对

使用道具 举报

sitsit 发表于 2016-8-20 11:14:38 来自手机 | 显示全部楼层
cacofish 发表于 2016-8-20 04:35
为啥我觉得题目不太看得懂。如果只有一个节点深度3, 一个节点深度2,返回谁的LCA?如果一个深度3,两个深 ...
. 1point 3acres 论坛
返回深度3节点本身
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-8-20 11:27:01 | 显示全部楼层
tree的recursion换成iteration处理,一般用stack都能解决吧(相当于手动用stack模拟recursion)。感觉这题可以是一个样的做法,换成post order访问,这样处理每个node的时候,左右孩子的信息都有了,而且最后一个处理的node一定是tree root。
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-8-21 01:19:17 | 显示全部楼层
楼主有空分享分享design题呀
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-8-21 04:06:56 | 显示全部楼层
这题好高频,前两天才看到有人面一样的
回复 支持 反对

使用道具 举报

Lilian1109 发表于 2016-8-23 03:16:05 | 显示全部楼层
zzh730 发表于 2016-8-20 12:20
最近这个题很高频啊,其实dfs遍历,返回的时候返回lca和depth,每个node如果有大于一个子节点的depth相同就 ...

这个貌似get到了, 贴一个我的代码, 是这么个意思吗?
  1. TreeNode* dfs(TreeNode * root, int & depth){.本文原创自1point3acres论坛
  2.     if(!root){. 牛人云集,一亩三分地
  3.         depth = 0;
  4.         return NULL;. Waral 博客有更多文章,
  5.     }
  6.    
  7.     int ldepth, rdepth;
  8.     TreeNode * left = dfs(root->left, ldepth);
  9.     TreeNode * right = dfs(root->right, rdepth);. more info on 1point3acres
  10.     depth = 1 + max(ldepth, rdepth);
  11.     -google 1point3acres
  12.     if(ldepth == rdepth) return root;
  13.     else if(ldepth < rdepth) return right;
  14.     else return right;
  15. }

  16. int commonAncestor(TreeNode * root){
  17.     int depth;
  18.     TreeNode* LCA = dfs(root, depth);
  19.     cout << "Tree depth:" << depth << endl;
  20.     return LCA->val;
  21. }
复制代码
回复 支持 反对

使用道具 举报

Lilian1109 发表于 2016-8-23 03:20:34 | 显示全部楼层
一个很naive的想法, 可不可以BFS找到deepest nodes, 同时把每一个node记录其parent。
每个 node向上返回一步, 把它们的parent用一个set来记录, 迭代, 当set的 size为1的时候就是他们的lowest common ancestor。
回复 支持 反对

使用道具 举报

zzh730 发表于 2016-8-23 06:19:54 | 显示全部楼层
Lilian1109 发表于 2016-8-23 03:16. From 1point 3acres bbs
这个貌似get到了, 贴一个我的代码, 是这么个意思吗?

是的,题里是多叉树,稍稍改下就好了
回复 支持 反对

使用道具 举报

lovelysier613 发表于 2016-8-24 08:25:01 | 显示全部楼层
Lilian1109 发表于 2016-8-23 03:16
这个貌似get到了, 贴一个我的代码, 是这么个意思吗?

这个代码写的很好!
如果不让用recursion,可以用一个stack来做post order travesal,顺便把左右子树的高度算出来比较,keep track这个左右子树一样高度最大值的父节点,即为所求。
回复 支持 反对

使用道具 举报

 楼主| lvvvvv 发表于 2016-8-31 01:04:58 | 显示全部楼层
chen6145 发表于 2016-8-21 01:19. visit 1point3acres for more.
楼主有空分享分享design题呀

design  pocketmon ,  google search suggestion.
回复 支持 反对

使用道具 举报

zhuhai_ZFC 发表于 2016-8-31 02:05:43 | 显示全部楼层
感觉这个可以DFS解。返回值为当前子树上最深叶子节点的深度,和当前子树上的最深叶子节点的lca。
  1. private static class Solution {
  2.         private class ReturnVal {.本文原创自1point3acres论坛
  3.             public int depth;   //The depth of the deepest leaves on the current subtree. 围观我们@1point 3 acres
  4.             public TreeNode lca;//The lca of the deepest leaves on the current subtree

  5.             public ReturnVal(int d, TreeNode n) {
  6.                 depth = d;. 1point3acres
  7.                 lca = n;
  8.             }.1point3acres网
  9.         }

  10.         public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
  11.             ReturnVal res = find(root, 0);
  12.             return res.lca;
  13.         }

  14.         private ReturnVal find(TreeNode root, int depth) {. from: 1point3acres
  15.             if(root == null) {
  16.                 return new ReturnVal(-1, null);
  17.             } else {
  18.                 ReturnVal lRes = find(root.left, depth+1);. from: 1point3acres
  19.                 ReturnVal rRes = find(root.right, depth+1);

  20.                 if(lRes.depth == rRes.depth) {
    .本文原创自1point3acres论坛
  21.                     return new ReturnVal(lRes.depth==-1?depth:lRes.depth, root);. visit 1point3acres for more.
  22.                 } else {
  23.                     return new ReturnVal(Math.max(rRes.depth, lRes.depth), rRes.depth>lRes.depth?rRes.lca:lRes.lca);
  24.                 }
  25.             }
  26.         }.1point3acres网
  27.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-24 19:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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