一亩三分地论坛

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

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

facebook 新鲜11.16 onsite面经+代码

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

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

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

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

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

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

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


题目:. 1point3acres.com/bbs
求一颗任意树(不一定是二叉树)所有最深叶子节点(数量可以是大于等于1的任意值,取决于树的结构)的最深公共前驱节点。
例子:
屏幕快照 2015-11-17 下午7.33.27.png 屏幕快照 2015-11-17 下午7.33.55.png

如图的树中,返回的都是红色的节点。

面试结束回去后,我自己又写了一遍代码,自己写了几个test case,都是对的。但无奈临场表现实在太差,悲剧。

我后来写的代码,求大家指导:
/*Problem: Give the common ancestor of all the deepest nodes of a tree.
*Author: Chunnan
*Data: 2015/11/16
**/

#include <vector> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
#include <iostream>
using namespace std;

//Tree node definition
struct TreeNode {
    int val;
    vector<TreeNode*> neighbors;
    TreeNode(int x):val(x) {}
};

class Solution {
public:
    //dfs helper function. Return depth of the subtree with "node" to be its root
    //Also return "sub_res" as the common ancestor of all the deepest nodes of the sub tree.
    int helper(TreeNode *node, TreeNode* &sub_res) {
        TreeNode* sr;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        //when node is leaf, itself is the deepest node and its ancestor is NULL(because it has no parent
        if(node->neighbors.empty()) {
            sub_res=NULL;
            return 0;
        }
        int max_dep=0;
        //count the number of neighbors with largest depth
        int count=1;
        //traverse all neighbors of current node
        for(auto i:node->neighbors) {. 1point3acres.com/bbs
            TreeNode* sr1;
            int sub_dep=helper(i, sr1)+1;
            if(sub_dep>max_dep) {.1point3acres缃
                max_dep=sub_dep;
                count=1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                //sr==NULL means that neighbor is a leaf. So "node" should be it's common ancester if this is the only neighbor "node" has.
                if(sr1==NULL) sr=node;
                else sr=sr1;
            }
            else if(sub_dep==max_dep) count++;
        }
        if(count==1) sub_res=sr;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        else sub_res=node;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        return max_dep;
    }
    TreeNode* findCommonAncestorOfDeepest(TreeNode* root) {
        if(!root) return NULL;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        TreeNode *res;
        int depth=helper(root, res);. 1point 3acres 璁哄潧
        return res;
    }

};
//test
int main() {
    Solution solution;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    vector<TreeNode*> data;
    for(int i=0; i<10; i++) {
        data.push_back(new TreeNode(i+1));
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    data[0]->neighbors.push_back(data[1]);
    data[0]->neighbors.push_back(data[2]);
    data[0]->neighbors.push_back(data[3]);
    data[1]->neighbors.push_back(data[4]);
    data[1]->neighbors.push_back(data[5]);
    data[3]->neighbors.push_back(data[6]);
    data[4]->neighbors.push_back(data[7]);
    data[5]->neighbors.push_back(data[8]);
    data[5]->neighbors.push_back(data[9]);
    //data[7]->neighbors.push_back(new TreeNode(11));
    //data[8]->neighbors.push_back(new TreeNode(12));
    TreeNode* root=data[0];
    TreeNode* res=solution.findCommonAncestorOfDeepest(root);
    std::cout<<res->val;
    return 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}. Waral 鍗氬鏈夋洿澶氭枃绔,




补充内容 (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就行了
回复 支持 2 反对 0

使用道具 举报

akluffy 发表于 2015-11-19 03:43:48 | 显示全部楼层
楼主,我有几个问题想问你。
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:. more info on 1point3acres.com
  3.     int val;
  4.     int longestPath;. 鍥磋鎴戜滑@1point 3 acres
  5.     vector<TreeNode*> children;
  6.     TreeNode(int x) : val(x), longestPath(0), children(vector<TreeNode*>(0)) {}
  7. };. From 1point 3acres bbs

  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() {
  14.     TreeNode *root = new TreeNode(1);. 1point3acres.com/bbs
  15.     root->children.push_back(new TreeNode(2));
  16.     root->children.push_back(new TreeNode(3));
  17.     root->children.push_back(new TreeNode(4));. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.     root->children.push_back(new TreeNode(5));
  19. . from: 1point3acres.com/bbs
  20.     root->children[0]->children.push_back(new TreeNode(6));
  21.     root->children[0]->children.push_back(new TreeNode(7));
  22.     root->children[0]->children.push_back(new TreeNode(8));
  23. .1point3acres缃
  24.     root->children[1]->children.push_back(new TreeNode(9));
  25.     root->children[1]->children.push_back(new TreeNode(10));

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

  28.     return root;
  29. }

  30. TreeNode* findCommonAncestorOfDeepest(TreeNode *root) {
  31.     if(!root || root->children.empty()) return NULL;. more info on 1point3acres.com
  32.     int curLongestPath = 0, countOfLongestLength = 0;
  33.     TreeNode *node = NULL;
  34.     for(auto kid : root->children) {
  35.         TreeNode *temp = findCommonAncestorOfDeepest(kid);
  36.         if(temp == NULL) continue;-google 1point3acres
  37.         else if(temp->longestPath > curLongestPath) {
  38.             curLongestPath = temp->longestPath;
  39.             node = temp;
  40.             countOfLongestLength = 1;
  41.         } else if(temp->longestPath == curLongestPath) countOfLongestLength++;. more info on 1point3acres.com
  42.     }
  43.     if(countOfLongestLength > 1) {. 1point3acres.com/bbs
  44.         root->longestPath = node->longestPath + 1;. 1point3acres.com/bbs
  45.         return root;
  46.     } else if(countOfLongestLength == 1) {
  47.         node->longestPath++;
  48.         return node;
  49.     } else if(countOfLongestLength == 0) {
  50.         root->longestPath = 2;
  51.         return root;. more info on 1point3acres.com
  52.     }
  53. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


  54. int main(){

  55.     TreeNode* root = generate();
  56.     TreeNode* result = findCommonAncestorOfDeepest(root);

  57.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;-google 1point3acres
  58. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  59.     root->children[0]->children[0]->children.push_back(new TreeNode(13)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  60.     cout << "add node 13 to node 6" << endl;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  61.     result = findCommonAncestorOfDeepest(root);
  62.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  63.     cout << "add node 14 to node 13" << endl;
  64.     root->children[0]->children[0]->children[0]->children.push_back(new TreeNode(14));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  65.     result = findCommonAncestorOfDeepest(root);
  66.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;
  67. . Waral 鍗氬鏈夋洿澶氭枃绔,
  68.     cout << "add node 15 to node 12" << endl;
  69.     root->children[3]->children[0]->children.push_back(new TreeNode(15));
  70.     result = findCommonAncestorOfDeepest(root);
  71.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;
  72. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  73.     cout << "add node 16 to node 15" << endl;
  74.     root->children[3]->children[0]->children[0]->children.push_back(new TreeNode(16));
  75.     result = findCommonAncestorOfDeepest(root);
  76.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;

  77.     cout << "add node 17 to node 16" << endl;
  78.     root->children[3]->children[0]->children[0]->children[0]->children.push_back(new TreeNode(17));
  79.     result = findCommonAncestorOfDeepest(root);
  80.     cout << "CAD node : " << result-> val << "   MaxDepth : " << result->longestPath << endl;. from: 1point3acres.com/bbs

  81.     cout << endl << "Pre-Oreder traversal : ";
  82.     printTree(root);. visit 1point3acres.com for more.
  83.     cout << endl;

  84.     return 0;
  85. }
复制代码

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

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做. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鍥磋鎴戜滑@1point 3 acres
用bfs一层一层的来,每个节点需要纪录它的父节点。. 1point 3acres 璁哄潧

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

使用道具 举报

haifengc 发表于 2015-11-18 12:02:45 | 显示全部楼层
haifengc 发表于 2015-11-18 12:02
我根据这题可以用bfs做
. Waral 鍗氬鏈夋洿澶氭枃绔,
用bfs一层一层的来,每个节点需要纪录它的父节点。

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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. . more info on 1point3acres.com
  6. class Solution(object):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.         def LCA(self, root):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                 result = self.helper(root). more info on 1point3acres.com
  9.                 return result[0]

  10.         def helper(self, root):
  11.                 if not root:
  12.                         return (root, 0)
  13.                 left = self.helper(root.left)
  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]:.1point3acres缃
  20.                         return (right[0], right[1]+1)
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

头像被屏蔽
shqyking 发表于 2015-11-18 14:22:30 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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:22:57 | 显示全部楼层
gorilazz 发表于 2015-11-18 12:48.1point3acres缃
这题感觉比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
还有你这代码有一个bug。 你用我的第二张图跑一下看看。
. 1point 3acres 璁哄潧
那这就和leetcode上LCA的parent定义不一样了。那上面如果q在p的子树里,那p就是common ancestor,而不是p的parent。. 1point 3acres 璁哄潧
而且按照你这么定义,如果是只有一个节点的树,应该返回什么呢?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-19 05:19:34 | 显示全部楼层

多谢你的启发,照着你的思路写了java代,新创一个返回类的方法很好. more info on 1point3acres.com
class TreeNode{
        int val;
        ArrayList<TreeNode> children;
        public TreeNode(int val){
                this.val = val;
                children = new ArrayList<>();. from: 1point3acres.com/bbs
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}
class Result{
        TreeNode node;. Waral 鍗氬鏈夋洿澶氭枃绔,
        int maxDepth;
        public Result(TreeNode node, int maxDepth){
                this.node = node;
                this.maxDepth = maxDepth;
        }
}
public class LowestCommonAncestorForAnyTree{
        public static TreeNode find(TreeNode root){
        if(root == null || root.children.isEmpty()) return root;
                return helper(root).node;. 1point3acres.com/bbs
        }
        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++){
                        Result tmp = helper(root.children.get(i).node);
                        if(tmp.maxDepth > maxDepth){
                                maxDepth = tmp.maxDepth;
                                r.node = tmp.node;
                                r.maxDepth = tmp.maxDepth + 1;
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        else if(tmp.maxDepth == maxDepth){
                                r.node = root;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                        }       
                }
                return r;
        }
        public static void main(String[] args){
                TreeNode n1 = new TreeNode(1);
                TreeNode n2 = new TreeNode(2);
. Waral 鍗氬鏈夋洿澶氭枃绔,                TreeNode n3 = new TreeNode(3);
                TreeNode n4 = new TreeNode(4);
                TreeNode n5 = new TreeNode(5);. 1point 3acres 璁哄潧
                TreeNode n6 = new TreeNode(6);
                TreeNode n7 = new TreeNode(7);. visit 1point3acres.com for more.
                TreeNode n8 = new TreeNode(8);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                TreeNode n9 = new TreeNode(9);
                TreeNode n10 = new TreeNode(10);
                n1.children.add(n2);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                n1.children.add(n3);
                n1.children.add(n4);
                n2.children.add(n5);. from: 1point3acres.com/bbs
                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);. 1point3acres.com/bbs

        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zsycn 发表于 2015-11-19 09:13:17 | 显示全部楼层
akluffy 发表于 2015-11-19 03:43
楼主,我有几个问题想问你。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. 您面的是intern还是fulltime呢?
2. 这个题是属于你面试的开场热身题,还 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
分析得很好。把难点全都罗列出来了。赞一个。楼主是leetcode题没有举一反三,没想到可以返回两个变量。在我上面的事后诸葛亮代码里,我是用C++ 的引用变量来达到同时返回depth和子结果节点的效果的。
. more info on 1point3acres.com
我面的intern. 就这一道题,不是follow up,直接多叉树以及要求达到所有条件。当时楼主看到多叉树的时候菊花一紧,分析算法复杂度时因为不是二叉树内心纠结了好久,说话都吞吞吐吐了。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-19 09:26:17 | 显示全部楼层
zsycn 发表于 2015-11-19 09:13. 1point 3acres 璁哄潧
分析得很好。把难点全都罗列出来了。赞一个。楼主是leetcode题没有举一反三,没想到可以返回两个变量。在 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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