一亩三分地论坛

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

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

FB 面经

[复制链接] |试试Instant~ |关注本帖
天下人 发表于 2016-5-14 19:06:11 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Facebook - 网上海投 - Onsite |Other在职跳槽

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

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

x



.鐣欏璁哄潧-涓浜-涓夊垎鍦
Jedi:
  go through背景
  light coding: clone a graph

Ninjia:
 给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行
时间为5. 写一个函数输入task序列和interval, 输出运行时间。
 followup: 写一个调度函数,输入task序列和interval,输出task最优执行序列

Pirate:
  设计一个大型在线多人视频系统,支持FB的scale

NinJia:
  Best Time to Buy and Sell Stock
  followup: 返回买入和卖出时间的Index
  Search in Rotated Sorted Array

. from: 1point3acres.com/bbs Pirate:
  设计一个系统。输入为FB用户的status流, 每个status的组成为多个tags, 用户可通
过 tag1 and tag2 or tag3之类的查询语句, 查出满足这些条件的status list.

Pirate:
  设计一个google maps 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

Ninjia:
  leetcode Move Zeros变种
  leetcode Subsets变种

Pirate:
  设计shortURL 系统

评分

4

查看全部评分

andrewpiggy 发表于 2016-5-18 04:02:52 | 显示全部楼层
感觉直接用贪心就行了吧?
. Waral 鍗氬鏈夋洿澶氭枃绔,1. 对于序列ABBABBC,得出每个task的次数,A:2, B:4, C:1;
2. 每一轮都挑剩下次数最多的task:. 1point 3acres 璁哄潧
    a. 如果该task还没过cool down,则挑选下一个;
    b. 如果都挑完还没有,则根据之前挑的cool down时间最短的先cool down再执行
回复 支持 0 反对 1

使用道具 举报

luomiao1904 发表于 2016-5-15 05:40:43 | 显示全部楼层
请问这是几次面试啊?一次的话会有这么多设计题吗
回复 支持 反对

使用道具 举报

WSNNSW 发表于 2016-5-15 07:32:37 | 显示全部楼层
感谢分享,感觉应该是加面的,网上其他的面经一般就两个Pirate。
回复 支持 反对

使用道具 举报

youto 发表于 2016-5-15 07:38:49 | 显示全部楼层
而且也多了一轮coding,难道包括了店面?
回复 支持 反对

使用道具 举报

justin 发表于 2016-5-15 09:30:29 | 显示全部楼层
四道设计题…………………………

不过看了下楼主是在职跳槽的就解释得通了。new grad基本不会有system design的经验。
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-5-16 13:03:43 | 显示全部楼层
我觉得这些设计题都很经典啊, 讨论下:
Pirate:
  设计一个系统。输入为FB用户的status流, 每个status的组成为多个tags, 用户可通
过 tag1 and tag2 or tag3之类的查询语句, 查出满足这些条件的status list.. 鐗涗汉浜戦泦,涓
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-18 01:47:16 | 显示全部楼层
大家对于follow up有什么方法吗?
给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行
时间为5. 写一个函数输入task序列和interval, 输出运行时间。
 followup: 写一个调度函数,输入task序列和interval,输出task最优执行序列. . 1point 3acres 璁哄潧

谢谢
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-19 11:59:12 | 显示全部楼层
andrewpiggy 发表于 2016-5-18 04:02
感觉直接用贪心就行了吧?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴1. 对于序列ABBABBC,得出每个task的次数,A:2, B:4, C:1;
2. 每一轮都挑剩下 ...

如果我没理解错你的意思的话,我感觉这么做不是最优解啊。
比如ABBABBC,按照你说的前两次肯定都会放B那么最后就是BBXXX..后面我们不管,一开始的连续两个B已经导致要等3分钟了对吧。

按照我对题意的理解就是要尽可能少的存在相同字母在一起的情况,那么对于ABBABBC这个input,最优的结果就是没有任何相同字母在一起,比如:BABABCB
具体算法大概就是先把最多的字母放进去,然后不断插入剩下的字母
回复 支持 反对

使用道具 举报

andrewpiggy 发表于 2016-5-19 22:25:13 | 显示全部楼层
handsomecool 发表于 2016-5-19 11:59
如果我没理解错你的意思的话,我感觉这么做不是最优解啊。
比如ABBABBC,按照你说的前两次肯定都会放B那 ...

Hmmm,我的判断里面,“如果都挑完还没有,则根据之前挑的cool down时间最短的先cool down再执行”,所以不会出现BB的情况,因为A此时是不需要cool down的,所以应该是BAC.
回复 支持 反对

使用道具 举报

cdwzfly 发表于 2016-5-20 00:05:50 | 显示全部楼层
好棒的面经啊!!!
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-20 01:33:06 | 显示全部楼层
andrewpiggy 发表于 2016-5-19 22:25
Hmmm,我的判断里面,“如果都挑完还没有,则根据之前挑的cool down时间最短的先cool down再执行”,所以 ...

我找到原题了,原来我完全理解错了题意,并不是只要相同字母不在一起最好。
恩。。。现在我感觉你说的OK了,不好意思;)
回复 支持 反对

使用道具 举报

Yang778899 发表于 2016-5-20 13:40:58 | 显示全部楼层
handsomecool 发表于 2016-5-20 01:33
. from: 1point3acres.com/bbs 我找到原题了,原来我完全理解错了题意,并不是只要相同字母不在一起最好。
恩。。。现在我感觉你说的OK ...

具体怎么做呢?能给个链接么
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-20 13:51:07 | 显示全部楼层
Yang778899 发表于 2016-5-20 13:40
具体怎么做呢?能给个链接么

我是看到另一个帖子里把题目讲的比较清楚,并没看到解法。但我觉得 andrewpiggy 描述的做法可行。
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-20 23:55:14 | 显示全部楼层
andrewpiggy 发表于 2016-5-18 04:02
感觉直接用贪心就行了吧?
1. 对于序列ABBABBC,得出每个task的次数,A:2, B:4, C:1;
2. 每一轮都挑剩下 ...

"如果都挑完还没有,则根据之前挑的cool down时间最短的先cool down再执行"
你是说每个task的cool down时间不一样吗?
好像都是一个int
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-21 02:35:04 | 显示全部楼层
tcomein2009 发表于 2016-5-20 23:55
"如果都挑完还没有,则根据之前挑的cool down时间最短的先cool down再执行"
你是说每个task的cool down ...

cool down时间一样,只是到了具体某个时刻,某个task剩余的冷却时间不一样,比如冷却时间是2个单位时间,然后这么排ABC_, 那么在第四个位置,A已经完成了冷却,B的冷却时间剩下1个单位时间,C的冷却时间才开始所以剩下2个单位时间
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-21 06:13:01 | 显示全部楼层
handsomecool 发表于 2016-5-21 02:35
cool down时间一样,只是到了具体某个时刻,某个task剩余的冷却时间不一样,比如冷却时间是2个单位时间, ...

对没错
紫薯紫薯
回复 支持 反对

使用道具 举报

zhuhai_ZFC 发表于 2016-9-1 09:14:20 | 显示全部楼层
其实我觉得,任务调度的那题就是LC358, 只是LC358是只要没法在排下去了就返回false,而这里没法排下去了就插一个空格,然后等间隔足够之后又可以继续排了
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-29 02:02:50 | 显示全部楼层
tcomein2009 发表于 2016-5-18 01:47
大家对于follow up有什么方法吗?
给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则 ...
.1point3acres缃
原来这就是TASK那题,感觉FOLLOWUP是不是很像LEETCODE那倒K DISTANCE APART
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-29 02:09:06 | 显示全部楼层
andrewpiggy 发表于 2016-5-18 04:02
感觉直接用贪心就行了吧?
1. 对于序列ABBABBC,得出每个task的次数,A:2, B:4, C:1;
2. 每一轮都挑剩下 ...

感觉就是LC原题, REORDER K DISTANCE APART,只是那个保证可以排列出来,这个可能会选到最后大家都在COOL DOWN ,那么就要干等一轮
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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