一亩三分地论坛

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

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

上周完成的脸书onsite

[复制链接] |试试Instant~ |关注本帖
lfzh123 发表于 2016-7-27 05:15:25 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Other在职跳槽

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

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

x
上周刚刚结束的脸书onsite,不算午饭,一共5轮,因为签了NDA,就不细说了,这里和大家聊聊一些看起来挺有意思的算法题和设计题

1. 聊一聊现在的工作,有没有failed project什么之类的。买股票1,删除在单链表的节点。
2. 有一个无限流的interval输入,要找出cover range。这个用什么数据结构比较好呢?
3. 设计一个系统,大概有1b的active user,大家都会post,每个post,都有名字和时间戳。然后还有一个search的功能,输入是一个或多个keyword(words之间是OR关系),要求返回相关的post。这个问题牵扯到如何存,如果做search word。大概的结构是什么样子的,还有要估算出每个function都需要多少机器呢。估算做的不完整,我只算出来了存post需要多少个机器,然后没有时间了。三哥说架构没有问题,good direction,算出来多少机器那一步不错。
4. 工作的调度,是个面经题,有些变种,只要求出给定tasks的工作总时间,在小哥提示下做了优化到O(n). Follow up是如何schedule这些工作,这样最后的工作总时间最少。我说了一种greedy的算法,就是相同task相隔约长约好。但是不太对,小哥说其实是一旦数量最多的task cooldown时间到了,就schedule这个task。问了我大概怎么实现,就结束了。. 1point3acres.com/bbs
5. 找出数组中第M大的数。quick sort也可以解决,average run time O(N), worst case O(N^2)。如果数组特别大呢,不想sort呢。可以用一个M size的pq,这样的话就是O(N*logM). 倒叙输出单链表,有两种方法,问了下tradeoff。然后完成单链表反转。

之前说是只有4轮,但是不知道为啥变成了5轮,好累啊。第一轮和最后一轮面的最好。第二轮国人大哥问的挺难的,没有完成code。但是他说他们team也是花了几个月完成的。。希望国人大哥抬一手啊,三哥千万不要黑我啊。. Waral 鍗氬鏈夋洿澶氭枃绔,

赞赞RP, 求offer


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-7-30 07:14):
接到HR电话,已经悲剧了。。没有detail,只是technical方面的。5轮interview是因为有一轮是training他们面试官的。。估计不算分

评分

3

查看全部评分

frederickyl 发表于 2016-7-27 13:52:04 | 显示全部楼层
2. 用TreeSet<Interval> 存储non-overlapped的intervals, 此时是有序的。当添加一个interval时,需要merge或者split来保持这个特性,复杂度为log级别, 因为可以用TreeSet的floor和ceiling函数先找到插入位置。cover range就是这个TreeSet.
回复 支持 2 反对 0

使用道具 举报

mdyuki1016 发表于 2016-7-27 06:54:50 | 显示全部楼层
三哥说架构没有问题,good direction,算出来多少机器那一步不错。  求教楼主,如何计算需要多少机器这种题, 有什么原则吗?
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-27 07:06:27 | 显示全部楼层
mdyuki1016 发表于 2016-7-27 06:54
三哥说架构没有问题,good direction,算出来多少机器那一步不错。  求教楼主,如何计算需要多少机器这种题, ...

1b active user,大概每个人每天写2个post,每个post大概50Byte,那每秒有多大的write 流量,如果写到disk里,需要多少个server.基本都是估算。
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-7-27 07:06:44 | 显示全部楼层
2. 有一个无限流的interval输入,要找出cover range。这个用什么数据结构比较好呢?.鐣欏

能给个例子吗? interval 是排序好的吗?
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-7-27 07:13:09 | 显示全部楼层
1b active user,大概每个人每天写2个post,每个post大概50Byte,那每秒有多大的write 流量,如果写到disk里,需要多少个server.基本都是估算。 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
总共产生 100G的内容/每天
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-27 07:56:09 | 显示全部楼层
mdyuki1016 发表于 2016-7-27 07:06
. from: 1point3acres.com/bbs 2. 有一个无限流的interval输入,要找出cover range。这个用什么数据结构比较好呢?.鐣欏

能给个例子吗? ...

不停有interval进来啊,所有需要一个适合的data structure,按大小排序,而且需要merge
回复 支持 反对

使用道具 举报

peter_sqliu 发表于 2016-7-27 13:58:42 | 显示全部楼层
感觉lz很有戏啊,等lz报offer
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-28 02:31:47 | 显示全部楼层
frederickyl 发表于 2016-7-27 13:52
2. 用TreeSet 存储non-overlapped的intervals, 此时是有序的。当添加一个interval时,需要merge或者split来 ...

这个方法 每次加入新的 interval 的最坏复杂度应该是 O(n*logn)吧

补充内容 (2016-7-28 02:46):
更正一下, 最坏情况应该是 O(n), 因为有可能需要遍历所有的 Interval
回复 支持 反对

使用道具 举报

zzh730 发表于 2016-7-28 04:27:52 | 显示全部楼层
第二轮类似这个题 Leetcode 352. Data Stream as Disjoint Intervals?
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-28 04:52:18 | 显示全部楼层
zzh730 发表于 2016-7-28 04:27
第二轮类似这个题 Leetcode 352. Data Stream as Disjoint Intervals?

LC 352每次进来的都是integer,这里进来的都是interval,不过也可以当做start = end的interval
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-28 04:54:24 | 显示全部楼层
peter_sqliu 发表于 2016-7-27 13:58
-google 1point3acres感觉lz很有戏啊,等lz报offer

关键是第二轮没有写完。。不报太大的希望了。明年接着再战
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-28 04:54:38 | 显示全部楼层
hyj143 发表于 2016-7-28 02:31
这个方法 每次加入新的 interval 的最坏复杂度应该是 O(n*logn)吧. more info on 1point3acres.com

补充内容 (2016-7-28 02:46):

为什么是o(n)
回复 支持 反对

使用道具 举报

frederickyl 发表于 2016-7-28 12:45:38 | 显示全部楼层
hyj143 发表于 2016-7-28 02:31
这个方法 每次加入新的 interval 的最坏复杂度应该是 O(n*logn)吧
. From 1point 3acres bbs
补充内容 (2016-7-28 02:46):

考虑amortized复杂度,即使最坏情况发生的话... fb一个team忙几个月就为这个?什么应用场景?
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-28 22:41:52 | 显示全部楼层
frederickyl 发表于 2016-7-28 12:45. Waral 鍗氬鏈夋洿澶氭枃绔,
考虑amortized复杂度,即使最坏情况发生的话... fb一个team忙几个月就为这个?什么应用场景?

大哥说要统计每个人上facebook的时间吧
回复 支持 反对

使用道具 举报

zzh730 发表于 2016-7-29 03:59:40 | 显示全部楼层
lfzh123 发表于 2016-7-28 04:52
LC 352每次进来的都是integer,这里进来的都是interval,不过也可以当做start = end的interval

没注意是interval=,=
好难啊这题,楼主当时什么思路
回复 支持 反对

使用道具 举报

chm34 发表于 2016-8-3 07:41:55 | 显示全部楼层
frederickyl 发表于 2016-7-27 13:52
2. 用TreeSet 存储non-overlapped的intervals, 此时是有序的。当添加一个interval时,需要merge或者split来 ...

插入操作复杂度worst case应该是O(nlgn)吧?如果这里的新插入的interval跨度很大,可以包含了当前TreesSet里中间好多的interval, 那么需要对这些interval做删除操作,单次删除操作复杂度为O(lgn)的。比如set里存的是[1,2],[3,4],[5,6],...[99,100], 新插入的interval是[1,100], 那么需要删除原来里的所有的interval, 总时间应该是nlgn?小弟愚钝,请层主明示. 1point 3acres 璁哄潧

补充内容 (2016-8-3 07:57):
或者是说只插入,不删除?最后求cover range的时候再merge?
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-3 09:51:03 | 显示全部楼层
Interval tree,   就可以了吧,  不停往里插入, update 相关 overlap
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-8-3 12:35:34 | 显示全部楼层
第五题不是有O(N)的算法么,不需要quicksort
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-8-4 07:34:25 | 显示全部楼层
pawprinter 发表于 2016-8-3 12:35
第五题不是有O(N)的算法么,不需要quicksort

什么算法啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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