一亩三分地论坛

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

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

FB 8/19 面经

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

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

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

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

x


两轮design, 两轮 coding
design 答得不好, 问得很细,
. Waral 鍗氬鏈夋洿澶氭枃绔,
coding 有一轮不好:

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

     1
  2   3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
     5  6    return 3.

       1  
    2   3
4      5 6   retrun 1.
先用 recursive  , 很快写出来了, 要求用 iterative 。 时间不够了。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
有什么比较好的办法 ?
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

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

使用道具 举报

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) {-google 1point3acres
                if(root == null)        return -1;
                // <node -> parent node>
                Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();. 1point 3acres 璁哄潧

                TreeNode head = null, tail = null;        // the head and tail node in a level. 鍥磋鎴戜滑@1point 3 acres
                Queue<TreeNode> que = new LinkedList<TreeNode>();
. Waral 鍗氬鏈夋洿澶氭枃绔,                que.offer(root);
                map.put(root, null);
                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) {. visit 1point3acres.com for more.
                                        map.put(curr.left, curr);
                                        que.offer(curr.left);
                                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                if(curr.right != null) {
                                        map.put(curr.right, curr);
                                        que.offer(curr.right);
                                }
                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }

                while(head != tail){
                        head = map.get(head);
                        tail = map.get(tail);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }
                return head.val;
        }
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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,两个深 ...

返回深度3节点本身
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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){
  2.     if(!root){
  3.         depth = 0;
  4.         return NULL;
  5.     }
  6.    
  7.     int ldepth, rdepth;
  8.     TreeNode * left = dfs(root->left, ldepth);
  9.     TreeNode * right = dfs(root->right, rdepth);
  10.     depth = 1 + max(ldepth, rdepth);
  11.    
  12.     if(ldepth == rdepth) return root;
  13.     else if(ldepth < rdepth) return right;. From 1point 3acres bbs
  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
这个貌似get到了, 贴一个我的代码, 是这么个意思吗?

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

zhuhai_ZFC 发表于 2016-8-31 02:05:43 | 显示全部楼层
感觉这个可以DFS解。返回值为当前子树上最深叶子节点的深度,和当前子树上的最深叶子节点的lca。-google 1point3acres
  1. private static class Solution {
  2.         private class ReturnVal {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.             public int depth;   //The depth of the deepest leaves on the current subtree
  4.             public TreeNode lca;//The lca of the deepest leaves on the current subtree

  5.             public ReturnVal(int d, TreeNode n) {
  6.                 depth = d;
  7.                 lca = n;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.         }

  10.         public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
  11.             ReturnVal res = find(root, 0);
  12.             return res.lca;
  13.         }
    .鏈枃鍘熷垱鑷1point3acres璁哄潧

  14.         private ReturnVal find(TreeNode root, int depth) {
  15.             if(root == null) {
  16.                 return new ReturnVal(-1, null);
  17.             } else {
  18.                 ReturnVal lRes = find(root.left, depth+1);
  19.                 ReturnVal rRes = find(root.right, depth+1);
  20. -google 1point3acres
  21.                 if(lRes.depth == rRes.depth) {
  22.                     return new ReturnVal(lRes.depth==-1?depth:lRes.depth, root);
  23.                 } else {
  24.                     return new ReturnVal(Math.max(rRes.depth, lRes.depth), rRes.depth>lRes.depth?rRes.lca:lRes.lca);
  25.                 }. 1point 3acres 璁哄潧
  26.             }
  27.         }
  28.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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