《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 6036|回复: 35
收起左侧

Facebook Onsite

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

2016(10-12月) 码农类 硕士 全职@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
      / \
    5   10
           \
            7
. from: 1point3acres.com/bbs
follow up 是一个addNode的函数,输入是root node,还有个int value,保持原有的属性,返回root. more info on 1point3acres.com

第二轮 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特别大该怎么处理等等. Waral 鍗氬鏈夋洿澶氭枃绔,

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

评分

1

查看全部评分

aifer 发表于 2016-10-13 02:51:18 | 显示全部楼层
西法的洛 发表于 2016-10-12 13:23
之前sb了。。改一下。

void addNode(TreeNode root, int val) {        if (root == null) return new ...
-google 1point3acres
你这个太麻烦,用递归最好做。代码如下。
        public TreeNode addNode(TreeNode root, int val) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if(root == null || root.val > val) {
                        TreeNode newNode = new TreeNode(val);
                        newNode.left = root;
                        return newNode;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
                root.right = addNode(root.right, val);
                return root;.1point3acres缃
        }
回复 支持 3 反对 0

使用道具 举报

 楼主| anthonyivan 发表于 2016-10-12 08:53:13 | 显示全部楼层
例子写错了,应该是
      2
    /    \
   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 | 显示全部楼层
第一题简单写了一下,欢迎指正。

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;. Waral 鍗氬鏈夋洿澶氭枃绔,
        node.left = buildTree(inorder, start, idx - 1);
        node.right = buildTree(inorder, idx + 1, end);
        return node;
    }

    int findMin(int[] inorder, int start, int end) {. visit 1point3acres.com for more.
        int min = Integer.MAX_VALUE;
        int minIdx = -1;.1point3acres缃
        for (int i = start, i <= end; i++) {
            if (min > inorder) {
                min = inorder;. visit 1point3acres.com for more.
                minIdx = i;
            }
        }
        return minIdx;
    }

    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;
        }
    }
. 1point 3acres 璁哄潧}.1point3acres缃



补充内容 (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/

原来是这道题啊!谢谢!
回复 支持 反对

使用道具 举报

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

就是给两个vector:. visit 1point3acres.com for more.
{x1, x2, x3, x4}
{y1, y2, y3, y4}

然后计算x1 * y1 + x2 * y2 + x3 * y3 + x4 * y4
. From 1point 3acres bbs
但是在两个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}
.1point3acres缃
请问楼主你这个就是dot product还是matrix multiplication呀?
如果是dot product 那么两个vector的维数应该相同吧?这样如何存在不同维数的情况?.鐣欏璁哄潧-涓浜-涓夊垎鍦
还是你给的例子其实是:
{x1, x2, x3, x4}
*
{y1,
y2,
y3,
y4. 1point 3acres 璁哄潧
}
(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
例子写错了,应该是
      2
    /    \
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你这个不能保证Inorder出来的是原数组的顺序啊
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-12 12:28:47 | 显示全部楼层
西法的洛 发表于 2016-10-12 10:55
第一题简单写了一下,欢迎指正。

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. 存在右儿子
2. 不存在右儿子

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

使用道具 举报

minggr 发表于 2016-10-12 13:01:47 | 显示全部楼层
我来写一个AddNode,大家看看对不对
.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如原数组是5 2 10 7, tree如下
       2
     /   \
    5   7
        /. more info on 1point3acres.com
       10

现在要添加4,步骤如下. 鍥磋鎴戜滑@1point 3 acres
假设有parent指针. visit 1point3acres.com for more.

1) 找到原树的最后一个结点,即7
2) 沿parent往上走,找到第一个比new value 4小的结点,即结点2
3) 新结点4的left指向7
4) 结点2的right指向4
. 鍥磋鎴戜滑@1point 3 acres
新tree如下

       2
     /   \
    5   4
        /
      7
     /
     10
  1. TreeNode *AddNode(TreeNode *root, int val)
  2. {   
  3.     TreeNode *last_node = get_last_node_by_in_order_traversal(root);. from: 1point3acres.com/bbs

  4.     TreeNode *new_node = new TreeNode(val);

  5.     TreeNode *parent = last_node;
  6.     TreeNode *prev = NULL;

  7.     while (parent) {
  8.         if (parent->val < val)
  9.             break;
  10.         prev = parent;
  11.         parent = parent->parent;
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.     }
  13.    
  14.     if (parent == NULL) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.         new_node->left = root;
  16.         root = new_node;
  17.     } else if (prev == NULL) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.         parent->right = new_node;
  19.     } else {
  20.         new_node->left = prev;
  21.         parent->right = new_node;
  22.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.    
  24.     return root;
  25. }
复制代码
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-12 13:12:20 | 显示全部楼层
minggr 发表于 2016-10-12 13:01
我来写一个AddNode,大家看看对不对
. Waral 鍗氬鏈夋洿澶氭枃绔,
比如原数组是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顺序和数组顺序是一样的

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 06:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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