May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5146|回复: 35
收起左侧

Facebook Onsite

[复制链接] |试试Instant~ |关注本帖
anthonyivan 发表于 2016-10-12 08:51:29 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 猎头 - Onsite |Other在职跳槽

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

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

x
新鲜的Facebook Onsite面经,目测是要跪了. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第一轮 Coding
input是一个array,要求生成一个树,有以下三个属性
1)二叉树
2)Min Heap,表示node的每个子节点的值都大于或者等于这个node的值
3)做inorder traversal的时候要保持array的顺序. Waral 鍗氬鏈夋洿澶氭枃绔,

举个例子input是 5, 2, 10, 7
       2
      / \
    5   10
           \
            7

follow up 是一个addNode的函数,输入是root node,还有个int value,保持原有的属性,返回root

第二轮 System Design
Design Facebook Search System
要求实现friends search和post search.鐣欏璁哄潧-涓浜-涓夊垎鍦

post search我说可以用inverted index,但是friends search就没有思路了。
然后厚着脸皮说没有相关经验,然后就扯到search的web service还有typeahead ui怎么实现了

第三轮 Coding
面试官找不到房间,迟到了一会,就做了一到题目Insert Interval,但也是写的磕磕盼盼的

第四轮 Career
讲了讲工作经验,project
问了一个dot product问题,怎么存vector,vector特别大该怎么处理等等

第五轮 System Design
Design Instagram. more info on 1point3acres.com
主要扯了一下feed的pull vs push两种方法,还问了photo storage该怎么整,又是不会。。。

评分

1

查看全部评分

aifer 发表于 2016-10-13 02:51:18 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
西法的洛 发表于 2016-10-12 13:23
之前sb了。。改一下。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

void addNode(TreeNode root, int val) {        if (root == null) return new ...
. 1point3acres.com/bbs
你这个太麻烦,用递归最好做。代码如下。
        public TreeNode addNode(TreeNode root, int val) {
                if(root == null || root.val > val) {
                        TreeNode newNode = new TreeNode(val);. visit 1point3acres.com for more.
                        newNode.left = root;
                        return newNode;
                }
                root.right = addNode(root.right, val);
                return root;
        }
回复 支持 3 反对 0

使用道具 举报

 楼主| anthonyivan 发表于 2016-10-12 08:53:13 | 显示全部楼层
关注一亩三分地微博:
Warald
例子写错了,应该是
      2
    /    \. From 1point 3acres bbs
   5     7
        /  
     10
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-12 09:11:51 | 显示全部楼层
第一题应该是类似这个解法吧?  http://www.geeksforgeeks.org/construct-binary-tree-from-inorder-traversal/
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-12 10:16:53 | 显示全部楼层
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 10:55:09 | 显示全部楼层
第一题简单写了一下,欢迎指正。
. 1point 3acres 璁哄潧
class Solution {    TreeNode buildTree(int[] inorder, int start, int end) {. From 1point 3acres bbs
        if (start > end) return null;
        int idx = findMin(inorder, int start, int end);
        TreeNode node = new TreeNode(inorder[idx]);
        if (start == end) return node;
        node.left = buildTree(inorder, start, idx - 1);
        node.right = buildTree(inorder, idx + 1, end);
        return node;
    }

    int findMin(int[] inorder, int start, int end) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        int min = Integer.MAX_VALUE;
        int minIdx = -1;
        for (int i = start, i <= end; i++) {
            if (min > inorder) {
                min = inorder;
                minIdx = i;
            }
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        return minIdx;
    }
. Waral 鍗氬鏈夋洿澶氭枃绔,
    void addNode(TreeNode root, int val) {
        if (val > root.val) {
            if (root.right != null) root = root.right;
            else root.right = new TreeNode(val);
        } else {
            TreeNode node = new TreeNode(val);
            node.left = root;.1point3acres缃
        }
. visit 1point3acres.com for more.    }
}
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


补充内容 (2016-10-12 13:07):
不好意思 写出了个bug,每次要记录下pre,对于 else 里面改成:TreeNode node = new TreeNode(val); pre.right = node; node.left = root;
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 10:59:05 | 显示全部楼层
chestnut9919 发表于 2016-10-12 10:16
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。

Leetcode 311
https://leetcode.com/problems/sparse-matrix-multiplication/
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-12 11:19:14 | 显示全部楼层
西法的洛 发表于 2016-10-12 10:59
Leetcode 311
https://leetcode.com/problems/sparse-matrix-multiplication/
. more info on 1point3acres.com
原来是这道题啊!谢谢!
回复 支持 反对

使用道具 举报

 楼主| anthonyivan 发表于 2016-10-12 11:43:29 | 显示全部楼层
chestnut9919 发表于 2016-10-12 10:16
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。

就是给两个vector:
{x1, x2, x3, x4}
{y1, y2, y3, y4}

然后计算x1 * y1 + x2 * y2 + x3 * y3 + x4 * y4

但是在两个vector中,有很多是0,问用什么样的数据结构存储这些vector,然后写个函数计算dot product。

followup就是其中一个vector特别大,怎么办。两个都特别大怎么办。

回复 支持 反对

使用道具 举报

 楼主| anthonyivan 发表于 2016-10-12 11:44:56 | 显示全部楼层
顺道想问一下大家,这两个system design有什么好的思路。
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 11:49:38 | 显示全部楼层
anthonyivan 发表于 2016-10-12 11:43
就是给两个vector:
{x1, x2, x3, x4}
{y1, y2, y3, y4}

请问楼主你这个就是dot product还是matrix multiplication呀?
如果是dot product 那么两个vector的维数应该相同吧?这样如何存在不同维数的情况?
还是你给的例子其实是:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{x1, x2, x3, x4}
*
{y1,
y2,
y3,. from: 1point3acres.com/bbs
y4
}
(row = 1, col = 4) * (row = 4, col = 1) 这种?
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-12 12:00:41 | 显示全部楼层
请问楼主,第一题add node,新的val在array里是最后一个吗?能说一下思路吗?
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-12 12:03:30 | 显示全部楼层
如果只能在array后面加新的数字的话,是不是每次都要重建一次树了?要是跟array没关系的话,能加的地方很多啊
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-10-12 12:05:38 | 显示全部楼层
想问下addNode被加进去的val除了满足minheap以外其他还有什么条件?
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-10-12 12:06:52 | 显示全部楼层
是保持原来的inorder不变吗?还是新的这个val相当于放在数组最后要满足新的inorder?
回复 支持 反对

使用道具 举报

aifer 发表于 2016-10-12 12:13:13 | 显示全部楼层
anthonyivan 发表于 2016-10-12 08:53
例子写错了,应该是. 1point 3acres 璁哄潧
      2. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    /    \

你这个不能保证Inorder出来的是原数组的顺序啊
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 12:28:47 | 显示全部楼层
西法的洛 发表于 2016-10-12 10:55
第一题简单写了一下,欢迎指正。
.1point3acres缃
class Solution {    TreeNode buildTree(int[] inorder, int start, i ...

没看懂你的AddNode()
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如5, 2, 10, 7,  add 20,应该是
           2
         /    \
       5      7
             /   \. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
           10    20
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 12:59:17 | 显示全部楼层
minggr 发表于 2016-10-12 12:28
没看懂你的AddNode()

比如5, 2, 10, 7,  add 20,应该是

如果加入的值比root大,分两种情况
1. 存在右儿子. 鍥磋鎴戜滑@1point 3 acres
2. 不存在右儿子

如果是1,那么继续找右儿子的右儿子,再比较
如果是2,那么直接把加入的值放在root的右儿子上。
所以对于你给出的例子,我的代码是通过的。因为5,2,10,7 构建出来的树,此时node(7)是没有右儿子的,你加入20,那么就可以把20赋在7的右儿子上。
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 13:01:47 | 显示全部楼层
我来写一个AddNode,大家看看对不对.1point3acres缃
. From 1point 3acres bbs
比如原数组是5 2 10 7, tree如下
       2
     /   \
    5   7. from: 1point3acres.com/bbs
        /. 1point 3acres 璁哄潧
       10

现在要添加4,步骤如下
假设有parent指针
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1) 找到原树的最后一个结点,即7
2) 沿parent往上走,找到第一个比new value 4小的结点,即结点2
3) 新结点4的left指向7
4) 结点2的right指向4
. more info on 1point3acres.com
新tree如下. 1point3acres.com/bbs

       2. 鍥磋鎴戜滑@1point 3 acres
     /   \
    5   4
        /-google 1point3acres
      7. 1point3acres.com/bbs
     /.鐣欏璁哄潧-涓浜-涓夊垎鍦
     10
  1. TreeNode *AddNode(TreeNode *root, int val)
  2. {   . 1point 3acres 璁哄潧
  3.     TreeNode *last_node = get_last_node_by_in_order_traversal(root);. 1point 3acres 璁哄潧

  4.     TreeNode *new_node = new TreeNode(val);.1point3acres缃
  5. . Waral 鍗氬鏈夋洿澶氭枃绔,
  6.     TreeNode *parent = last_node;
  7.     TreeNode *prev = NULL;

  8.     while (parent) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.         if (parent->val < val)
  10.             break;
  11.         prev = parent;
  12.         parent = parent->parent;.1point3acres缃
  13.     }
  14.    
  15.     if (parent == NULL) {
  16.         new_node->left = root;
  17.         root = new_node;-google 1point3acres
  18.     } else if (prev == NULL) {
  19.         parent->right = new_node;
  20.     } else {.1point3acres缃
  21.         new_node->left = prev;
  22.         parent->right = new_node;
  23.     }. 鍥磋鎴戜滑@1point 3 acres
  24.    
  25.     return root;
  26. }
复制代码
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 13:12:20 | 显示全部楼层
minggr 发表于 2016-10-12 13:01
我来写一个AddNode,大家看看对不对

比如原数组是5 2 10 7, tree如下

你这个办法可以做,但是个人觉得没必要get_last_node_by_inorder_traversal。但是你的问题是多了很多额外操作。
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 13:17:39 | 显示全部楼层
西法的洛 发表于 2016-10-12 13:12
你这个办法可以做,但是个人觉得没必要get_last_node_by_inorder_traversal。但是你的问题是多了很多额外 ...

找到最后这个结点,然后从这往上走,才能保证最后生成的树的inorder traversal顺序和数组顺序是一样的
. From 1point 3acres bbs
5 2 10 7, add 4
新树的inorder traversal得是5 2 10 7 4
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 04:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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