Berkeley biostat应该是biostat里最非传统,最偏ml的超棒项目了!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 6845|回复: 35
收起左侧

Facebook Onsite

[复制链接] |试试Instant~
我的人缘0
anthonyivan 发表于 2016-10-12 08:51:29 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩

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

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

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

x
新鲜的Facebook Onsite面经,目测是要跪了

第一轮 Coding
input是一个array,要求生成一个树,有以下三个属性
1)二叉树
2)Min Heap,表示node的每个子节点的值都大于或者等于这个node的值
3)做inorder traversal的时候要保持array的顺序
. 牛人云集,一亩三分地
举个例子input是 5, 2, 10, 7. 一亩-三分-地,独家发布
       2. 1point3acres
      / \
    5   10
           \.1point3acres网
            7

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

第二轮 System Design. From 1point 3acres bbs
Design Facebook Search System
要求实现friends search和post search
.本文原创自1point3acres论坛
post search我说可以用inverted index,但是friends search就没有思路了。
然后厚着脸皮说没有相关经验,然后就扯到search的web service还有typeahead ui怎么实现了

第三轮 Coding. 1point3acres
面试官找不到房间,迟到了一会,就做了一到题目Insert Interval,但也是写的磕磕盼盼的
. Waral 博客有更多文章,
第四轮 Career
讲了讲工作经验,project
问了一个dot product问题,怎么存vector,vector特别大该怎么处理等等. Waral 博客有更多文章,
. 围观我们@1point 3 acres
第五轮 System Design
Design Instagram
主要扯了一下feed的pull vs push两种方法,还问了photo storage该怎么整,又是不会。。。. 1point3acres

评分

参与人数 1大米 +60 收起 理由
candy_shmily + 60

查看全部评分


上一篇:BB onsite
下一篇:刚结束的Google Onsite。。。
我的人缘0
aifer 发表于 2016-10-13 02:51:18 | 显示全部楼层
本楼: 【顶】   100% (4)
 
 
0% (0)   【踩】
全局: 顶  99% (158)
 
 
0% (1)  踩
西法的洛 发表于 2016-10-12 13:23
之前sb了。。改一下。

void addNode(TreeNode root, int val) {        if (root == null) return new ...
. 留学申请论坛-一亩三分地
你这个太麻烦,用递归最好做。代码如下。
        public TreeNode addNode(TreeNode root, int val) {. From 1point 3acres bbs
                if(root == null || root.val > val) {
                        TreeNode newNode = new TreeNode(val);
                        newNode.left = root;
                        return newNode;
                }.留学论坛-一亩-三分地
                root.right = addNode(root.right, val);
                return root;
        }
回复

使用道具 举报

我的人缘0
 楼主| anthonyivan 发表于 2016-10-12 08:53:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
例子写错了,应该是
      2. visit 1point3acres for more.
    /    \
   5     7. Waral 博客有更多文章,
        /  
     10
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-12 09:11:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (350)
 
 
38% (215)  踩
第一题应该是类似这个解法吧?  http://www.geeksforgeeks.org/construct-binary-tree-from-inorder-traversal/
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-12 10:16:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-12 10:55:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
第一题简单写了一下,欢迎指正。

class Solution {    TreeNode buildTree(int[] inorder, int start, int end) {
        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) {. Waral 博客有更多文章,
        int min = Integer.MAX_VALUE;
        int minIdx = -1;
        for (int i = start, i <= end; i++) {
            if (min > inorder) {
                min = inorder;. visit 1point3acres for more.
                minIdx = i;
            }
        }. visit 1point3acres for more.
        return minIdx;
    }-google 1point3acres

    void addNode(TreeNode root, int val) {
        if (val > root.val) {. 1point3acres
            if (root.right != null) root = root.right;
            else root.right = new TreeNode(val);
        } else {
            TreeNode node = new TreeNode(val);
            node.left = root;
        }
    }
}. 1point 3acres 论坛



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

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-12 10:59:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
chestnut9919 发表于 2016-10-12 10:16
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。
. 1point3acres
Leetcode 311
https://leetcode.com/problems/sparse-matrix-multiplication/
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-12 11:19:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
西法的洛 发表于 2016-10-12 10:59
Leetcode 311-google 1point3acres
https://leetcode.com/problems/sparse-matrix-multiplication/

原来是这道题啊!谢谢!

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| anthonyivan 发表于 2016-10-12 11:43:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
chestnut9919 发表于 2016-10-12 10:16
楼主能详细说说dot product吗?好像是fb高频题,但每个人都是一语带过至今不知道啥题。。

就是给两个vector:
{x1, x2, x3, x4}
{y1, y2, y3, y4}. 围观我们@1point 3 acres

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

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

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

回复

使用道具 举报

我的人缘0
 楼主| anthonyivan 发表于 2016-10-12 11:44:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
顺道想问一下大家,这两个system design有什么好的思路。
回复

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-12 11:49:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
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}. 围观我们@1point 3 acres
*
{y1,
y2,
y3,
y4
}
(row = 1, col = 4) * (row = 4, col = 1) 这种?

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-12 12:00:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
请问楼主,第一题add node,新的val在array里是最后一个吗?能说一下思路吗?
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-12 12:03:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
如果只能在array后面加新的数字的话,是不是每次都要重建一次树了?要是跟array没关系的话,能加的地方很多啊
回复

使用道具 举报

我的人缘0
bbsbbstry 发表于 2016-10-12 12:05:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (117)
 
 
7% (10)  踩
想问下addNode被加进去的val除了满足minheap以外其他还有什么条件?
回复

使用道具 举报

我的人缘0
bbsbbstry 发表于 2016-10-12 12:06:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (117)
 
 
7% (10)  踩
是保持原来的inorder不变吗?还是新的这个val相当于放在数组最后要满足新的inorder?
回复

使用道具 举报

我的人缘0
aifer 发表于 2016-10-12 12:13:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (158)
 
 
0% (1)  踩
anthonyivan 发表于 2016-10-12 08:53-google 1point3acres
例子写错了,应该是
      2
    /    \

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

使用道具 举报

我的人缘0
minggr 发表于 2016-10-12 12:28:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
西法的洛 发表于 2016-10-12 10:55
第一题简单写了一下,欢迎指正。
.本文原创自1point3acres论坛
class Solution {    TreeNode buildTree(int[] inorder, int start, i ...

没看懂你的AddNode(). From 1point 3acres bbs

比如5, 2, 10, 7,  add 20,应该是
           2
         /    \
       5      7
             /   \
           10    20
回复

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-12 12:59:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
minggr 发表于 2016-10-12 12:28. Waral 博客有更多文章,
没看懂你的AddNode()

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

如果加入的值比root大,分两种情况
1. 存在右儿子
2. 不存在右儿子. more info on 1point3acres

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

使用道具 举报

我的人缘0
minggr 发表于 2016-10-12 13:01:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
我来写一个AddNode,大家看看对不对

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

现在要添加4,步骤如下
假设有parent指针.本文原创自1point3acres论坛

1) 找到原树的最后一个结点,即7
2) 沿parent往上走,找到第一个比new value 4小的结点,即结点2
3) 新结点4的left指向7. 留学申请论坛-一亩三分地
4) 结点2的right指向4

新tree如下

       2
     /   \
    5   4
        /
      7
     /
     10
  1. TreeNode *AddNode(TreeNode *root, int val)
  2. {   
    . more info on 1point3acres
  3.     TreeNode *last_node = get_last_node_by_in_order_traversal(root);

  4.     TreeNode *new_node = new TreeNode(val);-google 1point3acres
  5. . from: 1point3acres
  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;
  13.     }
  14.    
  15.     if (parent == NULL) {
  16.         new_node->left = root;
  17.         root = new_node;. visit 1point3acres for more.
  18.     } else if (prev == NULL) {
  19.         parent->right = new_node;
  20.     } else {
  21.         new_node->left = prev;. more info on 1point3acres
  22.         parent->right = new_node;
  23.     }
  24.    
  25.     return root;
  26. }
复制代码
回复

使用道具 举报

我的人缘0
西法的洛 发表于 2016-10-12 13:12:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (163)
 
 
2% (4)  踩
minggr 发表于 2016-10-12 13:01
我来写一个AddNode,大家看看对不对

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

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

使用道具 举报

我的人缘0
minggr 发表于 2016-10-12 13:17:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
西法的洛 发表于 2016-10-12 13:12
你这个办法可以做,但是个人觉得没必要get_last_node_by_inorder_traversal。但是你的问题是多了很多额外 ...

找到最后这个结点,然后从这往上走,才能保证最后生成的树的inorder traversal顺序和数组顺序是一样的

5 2 10 7, add 4
新树的inorder traversal得是5 2 10 7 4
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-26 22:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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