一亩三分地论坛

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

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

报FB 实习offer

[复制链接] |试试Instant~ |关注本帖
dnalwqer 发表于 2016-2-2 03:19:34 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Facebook - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
报个onsite面经,发帖攒人品!~ 刚收到offer,估计从了

1. 给一个数组。要你变成二叉树,必须满足条件:1. 满足minHeap性质 2. 树的中序遍历和数组顺序一致

2. followup: 给定了上述生成的树,要插入一个新节点,同样要满足上述条件。
followup:如果要插入很多节点,有没有方法提速?

有没有FB群呀。。。求小伙伴!另外LZ还有一个Hulu,在国内的时候知道hulu很屌,求问各位该怎么选?.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

9

查看全部评分

本帖被以下淘专辑推荐:

duduhaha 发表于 2016-2-2 14:36:35 | 显示全部楼层
写了一下这题和follow up,请指正。
Node generateTree(int[] a, int left ,int right) {. from: 1point3acres.com/bbs
        if (left > right)
            return null;

        int min = a[left], index = left;

        for (int i = left + 1; i <= right; i++)
            if (a[i] < min) {
                min = a[i];
                index = i;. visit 1point3acres.com for more.
            }

         Node root = new Node(a[min]);
         root.left = generateTree(a, left, index - 1);
         root.right = generateTree(a, index + 1, right);
         return root;
      }

      Node addNode(Node root, int val) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        Node inserted = new Node(val);
        if (val <= root.data) {
            inserted.left = root;
            return inserted;
        }

        Node curr = root.right, prev = root;
. 1point 3acres 璁哄潧
        while (curr != null) {
            if (val <= curr.data) {
                inserted.left = curr;
                prev.right = inserted;
                return root;
            } else {
                prev = curr;
                curr = curr.right;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,

        prev.right = inserted;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        return root;
      }
回复 支持 5 反对 0

使用道具 举报

seusofthd 发表于 2016-2-2 12:08:00 | 显示全部楼层
cnc155 发表于 2016-2-2 07:12
怎么在插入很多节点是提速呢

如果是一次性插入很多元素的话,可以先把这些元素建成一棵树,然后再merge这两棵树
回复 支持 3 反对 0

使用道具 举报

duduhaha 发表于 2016-2-2 06:26:38 | 显示全部楼层
这题应该用递归分治吧。遍历一遍找到最小值做为root, 然后递归处理左右两部分,然后链接到root上
回复 支持 2 反对 0

使用道具 举报

1370786136.1.3 发表于 2016-2-2 04:58:59 | 显示全部楼层
LZ, 不知道我的思路对不对:

先sort数组, 得到的数组为树的前序遍历;根据前序和中序数组重构该树。

另外求问follow up I & II 解法~
回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-2 03:36:36 | 显示全部楼层
恭喜lz,
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴你第1题怎么做的
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-2 03:36:54 | 显示全部楼层
就是要实现一个类似flatten linkedlist那样的BST吧
回复 支持 反对

使用道具 举报

wcyz666 发表于 2016-2-2 04:31:38 | 显示全部楼层
恭喜强哥!不要犹豫直接从了FB吧!
回复 支持 反对

使用道具 举报

dummyshooter 发表于 2016-2-2 06:35:45 | 显示全部楼层
请问HR是rollock吗?
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-2-2 06:38:15 | 显示全部楼层
Follow up 里插入一个节点维持性质啥意思?min heap可以维护, 但相比原来数组多了一个元素啊
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-2 06:55:03 | 显示全部楼层
lz, 第一题是要保证 minHeap的性质, 然后要求树的先序,还是中序?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
要是中序的话,第一个节点是左子树的最左节点,也就是min value, 然后这个如果也是数组的第一个的话。是不是直接把数组拍个序, 然后每一个都是前一个节点的右子节点就可以了?
回复 支持 反对

使用道具 举报

cnc155 发表于 2016-2-2 07:12:18 | 显示全部楼层
怎么在插入很多节点是提速呢
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 09:38:19 | 显示全部楼层
duduhaha 发表于 2016-2-2 06:26
这题应该用递归分治吧。遍历一遍找到最小值做为root, 然后递归处理左右两部分,然后链接到root上

对哒。。。。。。。。
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 09:39:01 | 显示全部楼层
guixi107 发表于 2016-2-2 06:55
lz, 第一题是要保证 minHeap的性质, 然后要求树的先序,还是中序?

要是中序的话,第一个节点是左子树 ...

不用排序其实
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 09:40:39 | 显示全部楼层
duduhaha 发表于 2016-2-2 06:38
Follow up 里插入一个节点维持性质啥意思?min heap可以维护, 但相比原来数组多了一个元素啊

followup就等于在数组最后加了一个数,然后在这棵树上加一个节点,满足那两个性质。
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 09:40:49 | 显示全部楼层
dummyshooter 发表于 2016-2-2 06:35
请问HR是rollock吗?
.1point3acres缃
不是诶。。。~
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 09:42:35 | 显示全部楼层
1370786136.1.3 发表于 2016-2-2 04:58
LZ, 不知道我的思路对不对:. 鍥磋鎴戜滑@1point 3 acres

先sort数组, 得到的数组为树的前序遍历;根据前序和中序数组重构该树。

可以感觉,但是其实可以不用排序。直接分治递归就好。
回复 支持 反对

使用道具 举报

Huangxin 发表于 2016-2-2 11:20:24 | 显示全部楼层
dnalwqer 发表于 2016-2-2 09:40
followup就等于在数组最后加了一个数,然后在这棵树上加一个节点,满足那两个性质。

楼主的意思是插入的那个点后,中序遍历对应的数组,那个点一定是最后一个么?还是说这个点的值是任意的,这个点可能插入到任何位置,然后再相应的调整它的子树
回复 支持 反对

使用道具 举报

 楼主| dnalwqer 发表于 2016-2-2 11:40:08 | 显示全部楼层
Huangxin 发表于 2016-2-2 11:20. From 1point 3acres bbs
楼主的意思是插入的那个点后,中序遍历对应的数组,那个点一定是最后一个么?还是说这个点的值是任意的, ...

一定是最后一个
回复 支持 反对

使用道具 举报

Huangxin 发表于 2016-2-2 12:07:10 | 显示全部楼层
dnalwqer 发表于 2016-2-2 11:40
一定是最后一个

那岂不是说直接找到给的树的最右节点,然后加到它的right就可以了?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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