一亩三分地论坛

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

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

facebook Onsite 11月19

[复制链接] |试试Instant~ |关注本帖
haifengc 发表于 2015-11-25 13:02:21 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Facebook - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
(1) coding
  • point coverd by most intervals
  • 2D (covered by the most rectangles)
(2) system design
  • privacy design
(3) system design

  • machine learning system design
(3) PhD research
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  • talk about research and intern experience
  • gate and wall, find the minimum distance between position from any gate 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
(4) coding

  • search in rotated array
  • BST to doubly linked list


. From 1point 3acres bbs
应该是挂在了第二和第三轮的sysmte design
. 鍥磋鎴戜滑@1point 3 acres



补充内容 (2016-4-2 00:30):. From 1point 3acres bbs
总共5轮,两轮coding,两轮design,一轮phd research

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zilchist 发表于 2015-11-25 21:41:19 | 显示全部楼层
多谢楼主分享,第二三轮的题目能具体说说吗?
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-26 02:46:55 | 显示全部楼层
zilchist 发表于 2015-11-25 21:41
多谢楼主分享,第二三轮的题目能具体说说吗?

第二轮:对每一个post,那些人能看,哪些人不能看,比如,有的是public,所有人都能看,有的是friends only,有的是family only等等
第三轮,我也不太懂,没有搞过machine learning相关的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

anyjlucky 发表于 2015-11-26 06:44:18 | 显示全部楼层
谢谢分享!
covered by most rectangle 怎么做啊?楼主你电面做了几道题拿到的onsite啊?
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-26 06:57:36 | 显示全部楼层
anyjlucky 发表于 2015-11-26 06:44
谢谢分享!
covered by most rectangle 怎么做啊?楼主你电面做了几道题拿到的onsite啊?

电面做两道题
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
covered by most rectangle,
. visit 1point3acres.com for more.
我当时是这么做的
按照2n 个y把y划分成2n-1个区间,每个区间在做一位的算法(covered by most intervers)
时间复杂度 n^2log(n)


回复 支持 反对

使用道具 举报

lishusha 发表于 2015-11-27 10:44:50 | 显示全部楼层
lz可以具体说一个第一个coding的问题吗?
point coverd by most intervals.鐣欏璁哄潧-涓浜-涓夊垎鍦
2D (covered by the most rectangles)
requirement是什麽啊?
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-27 11:37:21 | 显示全部楼层
lishusha 发表于 2015-11-27 10:44. 1point 3acres 璁哄潧
lz可以具体说一个第一个coding的问题吗?
point coverd by most intervals
2D (covered by the most rec ...

给n个区间,一个点被最多的区间覆盖的点,这个点可能有多个,任意返回一个

给n个长方形,一个点被最多长方形覆盖的点,这个点可能有多个,任意返回一个
回复 支持 反对

使用道具 举报

idunknow 发表于 2015-11-28 09:31:10 | 显示全部楼层
你是system design 一轮答了两道题是把?
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 09:32:56 | 显示全部楼层
idunknow 发表于 2015-11-28 09:31
你是system design 一轮答了两道题是把?

不是,

是有两轮system design,每轮45分钟
回复 支持 反对

使用道具 举报

lishusha 发表于 2015-11-28 11:37:45 | 显示全部楼层
haifengc 发表于 2015-11-27 11:37. more info on 1point3acres.com
给n个区间,一个点被最多的区间覆盖的点,这个点可能有多个,任意返回一个

给n个长方形,一个点被最多 ...

谢谢啊~第一个区间的我就想到brute force来递归解。每次O(N^2)的每两两区间的intersection,又生成一个intervals,然后递归。。。。。lz有什么更好的办法吗?
上代码:
public class Util
        {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                public static List<Interval> FindMostCoveredInterval(List<Interval> intervals)
                {. Waral 鍗氬鏈夋洿澶氭枃绔,
                        List<Interval> results = new List<Interval>();
                        if (intervals == null || intervals.Count == 0)
                        {
                                return results;
                        }
                        results = FindMostCoveredIntervalHelper(intervals);
                       
                        return results;
                }
.1point3acres缃
                private static List<Interval> FindMostCoveredIntervalHelper(List<Interval> intervals)
                {
                        if (intervals.Count <= 1)
                        {
                                return intervals;-google 1point3acres
                        }

                        HashSet<Interval> results = new HashSet<Interval>();
                        for (int i = 0; i < intervals.Count; i++)
                        {
                                Interval first = intervals;
                                for (int j = i + 1; j < intervals.Count; j++)
                                {
                                        Interval second = intervals[j];

                                        //Find intersaction for first and second;
                                        int low = Math.Max(first.Low, second.Low);
                                        int high = Math.Min(first.High, second.High);
                                        if (low <= high)
                                        {
                                                Interval intersect = new Interval(low, high);
                                                results.Add(intersect);-google 1point3acres
                                        }
                                }
                        }
                        if (results.Count == 0)
                        {
                                return intervals;
                        }

                        return FindMostCoveredInterval(results.ToList());. 1point3acres.com/bbs
                }
        }
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 11:45:36 | 显示全部楼层
lishusha 发表于 2015-11-28 11:37
谢谢啊~第一个区间的我就想到brute force来递归解。每次O(N^2)的每两两区间的intersection,又生成一个i ...

请参考leetcode meeting room II
回复 支持 反对

使用道具 举报

lishusha 发表于 2015-11-28 11:57:45 | 显示全部楼层
haifengc 发表于 2015-11-28 11:45
请参考leetcode meeting room II

现在就去看看!!谢谢呀~~~
回复 支持 反对

使用道具 举报

returning 发表于 2015-11-28 14:53:55 | 显示全部楼层
lishusha 发表于 2015-11-28 11:37
谢谢啊~第一个区间的我就想到brute force来递归解。每次O(N^2)的每两两区间的intersection,又生成一个i ...

1, 给n个区间,一个点被最多的区间覆盖的点,这个点可能有多个,任意返回一个
这个明显有O(n)办法,我们把区间的开始和结束都当做一个点,对2N个点排序,每遇到一个左边括号,当前的intersection数目加1,每遇到一个右边括号,当前intersection数目减一。但是有些细节需要注意,如果两个点重合,应该谁在前?

2,给n个长方形,一个点被最多长方形覆盖的点,这个点可能有多个,任意返回一个
这个题很复杂,开始只能想到N^3做法,对两个长方形,如果相交,找出4个交点,依次查询这4个交点是否在剩余的N-2个点内部,这样就能求出最大了。
但是,因为有了1,似乎可以用1来优化,先把所有长方形投影到x轴,得到N个interval,用和1类似的办法,但是增加存储空间,存储一个set,维护当前的相交的interval编号。比如,我们扫描到一个新的左边界,那么我们就应该可以知道当前有几个长方形的投影是相交的,每当扫描到一个右边界,就知道应该从这个set里面删除一个interval。所以,当遇到一个左边界时候,就去对这些长方形的y轴也用同样方法处理,看看有几个相交的。大概思路如此。做起来肯定很复杂。

楼主,这两道题让你多久做出来锕。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

idunknow 发表于 2015-11-28 15:03:38 | 显示全部楼层
haifengc 发表于 2015-11-28 09:32.鏈枃鍘熷垱鑷1point3acres璁哄潧
不是,

是有两轮system design,每轮45分钟
. Waral 鍗氬鏈夋洿澶氭枃绔,
what? fb不就一轮design么?
回复 支持 反对

使用道具 举报

idunknow 发表于 2015-11-28 15:04:27 | 显示全部楼层
idunknow 发表于 2015-11-28 15:03. visit 1point3acres.com for more.
what? fb不就一轮design么?
-google 1point3acres
哦 看到了 你应该是和manager那轮问了design
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 15:10:45 | 显示全部楼层
idunknow 发表于 2015-11-28 15:04
哦 看到了 你应该是和manager那轮问了design

两轮单独的design
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 15:12:32 | 显示全部楼层
returning 发表于 2015-11-28 14:53
1, 给n个区间,一个点被最多的区间覆盖的点,这个点可能有多个,任意返回一个
这个明显有O(n)办法,我们 ...

很好。第一个nlogn 第二个n^2logn
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 15:19:39 | 显示全部楼层
上面打错了。总共5轮,两轮coding,两轮design,一轮phd research
回复 支持 反对

使用道具 举报

 楼主| haifengc 发表于 2015-11-28 15:20:49 | 显示全部楼层
总共5轮,两轮coding,两轮design,一轮phd research
回复 支持 反对

使用道具 举报

yanggao1119 发表于 2016-2-23 16:15:39 | 显示全部楼层
haifengc 发表于 2015-11-28 15:12
很好。第一个nlogn 第二个n^2logn

楼主,为什么是 n^2logn 呢? sort x 轴的时间是nlogn,对每个点copy x 轴的 rectangle id,时间是m * n, where m is the number of points.. from: 1point3acres.com/bbs

sort y轴时间nlogn,copy y轴的rectangle id,和x轴的rectangle id取交集,时间是m * n,

所以好像总的complexity是 nlogn + mn 啊。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

不知这样理解有什么错吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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