10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 14025|回复: 48
收起左侧

facebook 新鲜11.16 onsite面经+代码

[复制链接] |试试Instant~ |关注本帖
zsycn 发表于 2015-11-18 11:37:08 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - Onsite |Fail其他

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

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

x
F家效率很高,16号面试17号通知已跪。on site六人小分队已悲剧四人。这次on site给我的教训就是,刷题一定要在题目表象之下,领悟最基本的算法原理。临近on site的周末,为了刷到所谓“原题”,我基本进入了看题-》想思路-》想不出-》看discussion                             -》想出-》估摸估摸代码烦不烦-》不烦-》码之练手          -》记住关键思路. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                                                             -》烦-》看discussion

的模式,想赶在on site前把leetcode上有facebook tag的题都在复习一遍,没做过的看一下思路。


面试官是怀孕的印度姐姐。面的题目和leetcode有几分相似,但感觉更难些。我由于一个劲的想用leetcode 的common ancestor of a binary tree 套,就悲剧了。先是思路一致被否,然后没有想到在树的dfs中,同一层每个分支的子结果互相之间还可以加上代码逻辑的。之前做了太多backtracking的题目,注意力都集中在了处理dfs中单条path上。被打到软肋了。面得非常不好。
. more info on 1point3acres.com

题目:
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here to access restricted content

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-11-18 15:23):
另 hr 说的信息: we are continuously growing and want more intern. However lots of interns would get return offer, so we hire less new grad.

评分

6

查看全部评分

本帖被以下淘专辑推荐:

johnjavabean 发表于 2015-11-20 10:29:36 | 显示全部楼层
想到一个解法,先层序遍历,找到最深的节点,然后求最左边的节点和最右边的节点的LCA就行了
回复 支持 4 反对 1

使用道具 举报

akluffy 发表于 2015-11-19 03:43:48 | 显示全部楼层
楼主,我有几个问题想问你。. 1point 3acres 璁哄潧
1. 您面的是intern还是fulltime呢?
2. 这个题是属于你面试的开场热身题,还是属于比较靠后的follow up题?
3. 如果只有一个题,那面试官是一上来就把所有的要求全部列出来,还是说,一层层递进,比如先二叉树,然后再多叉树?

关于这题的思路与代码:
说实话,单纯从思路的角度而言,并不难,但是考虑到2个难点,要在20分钟之内写完,并且到bug free,我觉得基本上是不太可能的。
两个难道是什么呢?? 1. 我们要返回什么?不难看出来, 最后要返回一个node,所以TreeNode 肯定是需要返回的变量之一;另外一个条件是什么?最长路径或者说最大深度,嗯,所以说,每个node往上层返的时候都需要返回这2个变量,一个是当前以node为root的时候最深common节点,一个是深度deep。为什么说这是难点之一?大部分leetcode的树的题,基本上都是只需要返回一个变量的,这时候要返回两个变量?怎么办?最普遍的2个办法,一种是另外创建一个类,这个类里面包含一个node跟一个int类型的MAXdeep变量。第二种是就在TreeNode这个类里面加一个int类型的变量depth,(请注意,这个depth并不是表示所在的instance的node的深度,比如node5->deep = 5,并不是说node5的深度是5哦,只是完全用来满足 返回给父函数的时候传递的第二个变量罢了)。 所以说当对任意一个节点调用这个函数的时候,都将返回,commonAncestorOfDeepest的节点,以及这个节点所在路径的depth。

第二个难点在哪里?多叉树,而不是二叉树。或许你觉得多叉数,本质上与二叉树没有区别,嗯嗯嗯,不就是多了几个下一级的指针嘛?二叉树只有left, right。 多叉树则有N个,仅此而已。可是就因为需要用一个list来保存多叉树的指针,又会影响递归函数内的判断逻辑的复杂程度。说的更加直白一点,二叉树,你只需要比较一下left跟right就好了,而多叉树你需要写loop,以及count来遍历,所有的指针。

然后下面是我的完整的C++代码,加上libraries直接复制到编译器里面就能run
  1. class TreeNode {
  2. public:
  3.     int val;
  4.     int longestPath;
  5.     vector<TreeNode*> children;
  6.     TreeNode(int x) : val(x), longestPath(0), children(vector<TreeNode*>(0)) {}
  7. };

  8. void printTree(TreeNode *root) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.     if(!root) return;
  10.     cout << root->val << ", ";
  11.     for(auto i : root->children) printTree(i);
  12. }

  13. TreeNode* generate() {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.     TreeNode *root = new TreeNode(1);
  15.     root->children.push_back(new TreeNode(2));
  16.     root->children.push_back(new TreeNode(3));
  17.     root->children.push_back(new TreeNode(4));
  18.     root->children.push_back(new TreeNode(5));

  19.     root->children[0]->children.push_back(new TreeNode(6));
  20.     root->children[0]->children.push_back(new TreeNode(7));
  21.     root->children[0]->children.push_back(new TreeNode(8));

  22.     root->children[1]->children.push_back(new TreeNode(9));
  23.     root->children[1]->children.push_back(new TreeNode(10));

  24.     root->children[2]->children.push_back(new TreeNode(11));
  25.     root->children[3]->children.push_back(new TreeNode(12));

  26.     return root;
  27. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  28. TreeNode* findCommonAncestorOfDeepest(TreeNode *root) {
  29.     if(!root || root->children.empty()) return NULL;
  30.     int curLongestPath = 0, countOfLongestLength = 0;
  31.     TreeNode *node = NULL;
  32.     for(auto kid : root->children) {
  33.         TreeNode *temp = findCommonAncestorOfDeepest(kid);
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  34.         if(temp == NULL) continue;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.         else if(temp->longestPath > curLongestPath) {
  36.             curLongestPath = temp->longestPath;.1point3acres缃
  37.             node = temp;
  38.             countOfLongestLength = 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.         } else if(temp->longestPath == curLongestPath) countOfLongestLength++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  40.     }
  41.     if(countOfLongestLength > 1) {
  42.         root->longestPath = node->longestPath + 1;
  43.         return root;
  44.     } else if(countOfLongestLength == 1) {. visit 1point3acres.com for more.
  45.         node->longestPath++;
  46.         return node;
  47.     } else if(countOfLongestLength == 0) {.1point3acres缃
  48.         root->longestPath = 2;. 鍥磋鎴戜滑@1point 3 acres
  49.         return root;
  50.     }
  51. }. 鍥磋鎴戜滑@1point 3 acres
  52. . visit 1point3acres.com for more.

  53. int main(){
  54. . From 1point 3acres bbs
  55.     TreeNode* root = generate();
  56.     TreeNode* result = findCommonAncestorOfDeepest(root);

  57.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  58.     root->children[0]->children[0]->children.push_back(new TreeNode(13));
  59.     cout << "add node 13 to node 6" << endl;
  60.     result = findCommonAncestorOfDeepest(root);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  61.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  62.     cout << "add node 14 to node 13" << endl;
  63.     root->children[0]->children[0]->children[0]->children.push_back(new TreeNode(14));
  64.     result = findCommonAncestorOfDeepest(root);
  65.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  66.     cout << "add node 15 to node 12" << endl;
  67.     root->children[3]->children[0]->children.push_back(new TreeNode(15));. from: 1point3acres.com/bbs
  68.     result = findCommonAncestorOfDeepest(root);
  69.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  70.     cout << "add node 16 to node 15" << endl;
  71.     root->children[3]->children[0]->children[0]->children.push_back(new TreeNode(16));
  72.     result = findCommonAncestorOfDeepest(root);
  73.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;.1point3acres缃

  74.     cout << "add node 17 to node 16" << endl;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  75.     root->children[3]->children[0]->children[0]->children[0]->children.push_back(new TreeNode(17));
  76.     result = findCommonAncestorOfDeepest(root);
  77.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  78.     cout << endl << "Pre-Oreder traversal : ";
  79.     printTree(root);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  80.     cout << endl;. 1point3acres.com/bbs

  81.     return 0;
  82. }
复制代码

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

gorilazz 发表于 2015-11-18 12:48:06 | 显示全部楼层
这题感觉比leetcode的LCA还简单啊。。。代码如下,楼主帮忙看看。。。
  1. class TreeNode(object):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.         def __init__(self, value):
  3.                 self.val = value
  4.                 self.left, self.right = None, None

  5. class Solution(object):
  6.         def LCA(self, root):
  7.                 result = self.helper(root)
  8.                 return result[0]
  9. . 1point 3acres 璁哄潧
  10.         def helper(self, root):
  11.                 if not root:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                         return (root, 0)
  13.                 left = self.helper(root.left). 1point3acres.com/bbs
  14.                 right = self.helper(root.right)
  15.                 if left[1]==right[1]:
  16.                         return (root, left[1]+1)
  17.                 if left[1]>right[1]:
  18.                         return (left[0], left[1]+1)
  19.                 if left[1]<right[1]:
  20.                         return (right[0], right[1]+1)
复制代码
回复 支持 0 反对 1

使用道具 举报

akluffy 发表于 2015-11-19 03:44:27 | 显示全部楼层
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                               
登录/注册后可看大图

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| zsycn 发表于 2015-11-18 11:49:04 | 显示全部楼层
我认为的时间复杂度O(b^m), 空间复杂度O(m)。 b是分支系数,m是图的最大深度。后来想想这确实是道考察对dfs、递归以及树的结构理解的一道很赞的面试题。
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-18 12:02:06 | 显示全部楼层
我根据这题可以用bfs做

用bfs一层一层的来,每个节点需要纪录它的父节点。

. From 1point 3acres bbs到达最后一层的时候,
(1)如果只有一个节点,返回它的父节点. 1point3acres.com/bbs
(2)如果有多个节点,那么同时向上走(向父节点走),走到某个点,它们的父节点相同,那么这个相同的点就是需要返回的点
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-18 12:02:45 | 显示全部楼层
haifengc 发表于 2015-11-18 12:02
我根据这题可以用bfs做

用bfs一层一层的来,每个节点需要纪录它的父节点。

时间复杂度是 O(n)
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2015-11-18 12:12:03 | 显示全部楼层
写的很好,六人小分队中至今毫无音讯的出一个...楼主这道题有点难,我遇到估计也得扑. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

神罗天征 发表于 2015-11-18 12:16:42 | 显示全部楼层
楼主啊,我就是六人小分队中的一个啊
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-18 12:23:03 | 显示全部楼层
弱弱的问一下,什么是 六人小分队
回复 支持 反对

使用道具 举报

 楼主| zsycn 发表于 2015-11-18 13:14:35 | 显示全部楼层
gorilazz 发表于 2015-11-18 12:48 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这题感觉比leetcode的LCA还简单啊。。。代码如下,楼主帮忙看看。。。

方法是对的。就是不一定是二叉树。不过不是大问题,稍微改一下就好。
回复 支持 反对

使用道具 举报

shqyking 发表于 2015-11-18 14:22:30 | 显示全部楼层
FB应该headcount没有了或者超级少吧。。现在面Bar一定超级高
回复 支持 反对

使用道具 举报

 楼主| zsycn 发表于 2015-11-18 15:18:48 | 显示全部楼层
shqyking 发表于 2015-11-18 14:22
FB应该headcount没有了或者超级少吧。。现在面Bar一定超级高

FB HR 原话:we are continuously growing and want more intern. However lots of interns would get return offer, so we hire less new grad.
回复 支持 反对

使用道具 举报

shqyking 发表于 2015-11-18 15:20:33 | 显示全部楼层
zsycn 发表于 2015-11-18 15:18
FB HR 原话:we are continuously growing and want more intern. However lots of interns would get re ...

原来你是面intern... 我以为是fulltime. 我本来的意思是fulltime没啥headcount了。。。
回复 支持 反对

使用道具 举报

 楼主| zsycn 发表于 2015-11-18 15:22:57 | 显示全部楼层
gorilazz 发表于 2015-11-18 12:48
这题感觉比leetcode的LCA还简单啊。。。代码如下,楼主帮忙看看。。。

还有你这代码有一个bug。 你用我的第二张图跑一下看看。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2015-11-18 15:29:29 | 显示全部楼层
zsycn 发表于 2015-11-18 15:18
FB HR 原话:we are continuously growing and want more intern. However lots of interns would get re ...

哎,我也想起来了,这么说intern挂了onsite要难得多了
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-11-19 04:23:44 | 显示全部楼层
zsycn 发表于 2015-11-18 15:22. From 1point 3acres bbs
还有你这代码有一个bug。 你用我的第二张图跑一下看看。

那这就和leetcode上LCA的parent定义不一样了。那上面如果q在p的子树里,那p就是common ancestor,而不是p的parent。
而且按照你这么定义,如果是只有一个节点的树,应该返回什么呢?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-19 05:19:34 | 显示全部楼层
. from: 1point3acres.com/bbs
多谢你的启发,照着你的思路写了java代,新创一个返回类的方法很好
class TreeNode{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        int val;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        ArrayList<TreeNode> children;
.1point3acres缃        public TreeNode(int val){
                this.val = val;
                children = new ArrayList<>();
        }
}
class Result{
        TreeNode node;
        int maxDepth;. visit 1point3acres.com for more.
        public Result(TreeNode node, int maxDepth){. 1point3acres.com/bbs
                this.node = node;
                this.maxDepth = maxDepth;
        }
}. Waral 鍗氬鏈夋洿澶氭枃绔,
public class LowestCommonAncestorForAnyTree{
        public static TreeNode find(TreeNode root){
        if(root == null || root.children.isEmpty()) return root;
                return helper(root).node;
        }
        public static Result helper(TreeNode root){
                if(root.children.isEmpty()) return new Result(root, 1);
                int size = root.children.size();
                int maxDepth = Integer.MIN_VALUE;
                Result r = new Result(root, maxDepth);
                for(int i = 0; i < size; i++){. 鍥磋鎴戜滑@1point 3 acres
                        Result tmp = helper(root.children.get(i).node);
                        if(tmp.maxDepth > maxDepth){
                                maxDepth = tmp.maxDepth;
                                r.node = tmp.node;
                                r.maxDepth = tmp.maxDepth + 1;. 1point3acres.com/bbs
                        }
                        else if(tmp.maxDepth == maxDepth){
                                r.node = root;
                        }       
                }
                return r;
        }
        public static void main(String[] args){
                TreeNode n1 = new TreeNode(1);. Waral 鍗氬鏈夋洿澶氭枃绔,
                TreeNode n2 = new TreeNode(2);
                TreeNode n3 = new TreeNode(3);
                TreeNode n4 = new TreeNode(4);
                TreeNode n5 = new TreeNode(5);
                TreeNode n6 = new TreeNode(6);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                TreeNode n7 = new TreeNode(7);. Waral 鍗氬鏈夋洿澶氭枃绔,
                TreeNode n8 = new TreeNode(8);
                TreeNode n9 = new TreeNode(9);
                TreeNode n10 = new TreeNode(10);
                n1.children.add(n2);
                n1.children.add(n3);.1point3acres缃
                n1.children.add(n4);
                n2.children.add(n5);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                n2.children.add(n6);
                n4.children.add(n7);
                n5.children.add(n8);
                n5.children.add(n9);
                n6.children.add(n10);
                TreeNode res = find(n1);
                System.out.println(res.val);
. From 1point 3acres bbs
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zsycn 发表于 2015-11-19 09:13:17 | 显示全部楼层
akluffy 发表于 2015-11-19 03:43
楼主,我有几个问题想问你。
1. 您面的是intern还是fulltime呢?
2. 这个题是属于你面试的开场热身题,还 ...

分析得很好。把难点全都罗列出来了。赞一个。楼主是leetcode题没有举一反三,没想到可以返回两个变量。在我上面的事后诸葛亮代码里,我是用C++ 的引用变量来达到同时返回depth和子结果节点的效果的。

我面的intern. 就这一道题,不是follow up,直接多叉树以及要求达到所有条件。当时楼主看到多叉树的时候菊花一紧,分析算法复杂度时因为不是二叉树内心纠结了好久,说话都吞吞吐吐了。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-19 09:26:17 | 显示全部楼层
zsycn 发表于 2015-11-19 09:13. Waral 鍗氬鏈夋洿澶氭枃绔,
分析得很好。把难点全都罗列出来了。赞一个。楼主是leetcode题没有举一反三,没想到可以返回两个变量。在 ...

关于复杂的问题,想跟楼主讨论一下。 这道题,我觉得时间复杂度应该就是O(N)呀,N是所有node数目, 空间复杂度的话,也应该是O(N)吧?每个node都要调用一下递归函数。 不知道我的分析正确与否。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-23 19:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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