一亩三分地论坛

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

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

facebook Onsite

[复制链接] |试试Instant~ |关注本帖
yulijiayou 发表于 2016-10-10 01:04:44 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 网上海投 - Onsite |Pass在职跳槽

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

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

x
给大家打打气,分享新鲜面经 Facebook。

共5轮,
1,  fibonacci 但是问的很细, recursion - 》 memoization -》 compression,而且输出和输入范围要考虑到。. 鍥磋鎴戜滑@1point 3 acres
然后问了个有意思的题, 说有两个 date object 形式为  MM/DD/YYYY, 要计算 date diff 以 MM/DD的形式输出, 这题看着挺简单,不过edge case还是挺多。
解法基本是先算day diff, 然后carry over 到 month diff。 需要两个api, daysInMonth 和 date class 的 ++ operator override, 细想还挺好玩。

2. 说有起始时间 和 终止时间, 再加上一堆时间段, 找出所有空闲时间段。 简单题,不过不要一开始就做,有很多陷阱,比如是不是都在同一天, 输入会不会合法 比如起始在终止之后。 时间段overlap是不是要预处理,总之抓住机会尽量表现。

3. system design 游戏点卡,有的卖的慢,有的卖的快, 怎么scale,用什么storage,写什么API。

4. 这个稍微难, 说有一堆task,每个有不同时间完成, 然后有一堆worker, 说如何分配 task to worker,完成时间最短, task是独立的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看起来像背包, DP . 1point3acres.com/bbs
task:  2,2,3,7, 1
worker: 2. 1point 3acres 璁哄潧
. more info on 1point3acres.com
解(2,2,3) (1, 7)

5 Manger 瞎侃。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

2

查看全部评分

 楼主| yulijiayou 发表于 2016-10-26 11:58:34 | 显示全部楼层
谁问我系统设计来着。

这破地方不能回信,贴着了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴



你最好有自己的模版 或者套路. more info on 1point3acres.com
比如一上来不要钻到细节里, 先把你的系统高度概括一下, 比如模块有哪些,相互依赖如何,数据怎么流。
然后不同的解决方案优缺点如何,怎么比较。
还是要靠积累吧。

最后千万不要跟着他走, 而是你要drive整个过程,或者不要胆怯,把你的想法说的有理有据就ok


比如说这个垃圾bbs, 既然回不了信,你干嘛可以收信。
回复 支持 1 反对 0

使用道具 举报

喜马拉雅疯子 发表于 2016-10-10 05:48:58 | 显示全部楼层
求问LZ分配任务的题是怎么做的。
我的思路是用一个min heap保存每个worker拥有的任务的时间总数。然后将tasks按照倒序排列。从耗时最大的task开始遍历, 每次将遍历倒的task加入min heap 最顶部的那个worker。这样就保证每次都将目前未分配的任务中耗时最多的任务分配给工作时间最短的worker。达到平衡
回复 支持 1 反对 0

使用道具 举报

dhldxy 发表于 2016-10-10 01:24:02 | 显示全部楼层
楼主这个system design是怎么答的呢,能简单说说思路吗?
回复 支持 反对

使用道具 举报

 楼主| yulijiayou 发表于 2016-10-10 01:42:05 | 显示全部楼层

RE: mock

sasssssssssssssss
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-10-10 02:05:04 | 显示全部楼层
楼主是new grad吗?
回复 支持 反对

使用道具 举报

 楼主| yulijiayou 发表于 2016-10-10 03:07:43 | 显示全部楼层
顺便问问 如何删帖? 用户体验太差
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-10 03:55:02 | 显示全部楼层
求问楼主电面题目~~>.<
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-10 04:03:17 | 显示全部楼层
task:  2,2,3,7, 1 这里的数字表示的是每个task要用的时间吗
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-10 05:36:11 | 显示全部楼层
话说想请教下第四题用dp是怎么做的?我咋觉得把task从大到小排个序然后每次处理新task的时候让当前工作量最小的worker去做就可以了呢?
回复 支持 反对

使用道具 举报

喜马拉雅疯子 发表于 2016-10-10 05:49:23 | 显示全部楼层
yxyxyx 发表于 2016-10-10 05:36
话说想请教下第四题用dp是怎么做的?我咋觉得把task从大到小排个序然后每次处理新task的时候让当前工作量最 ...

我也是这么想的
回复 支持 反对

使用道具 举报

frankman 发表于 2016-10-10 08:12:51 | 显示全部楼层
第4题跟这个题一样吧?LEETCODE  410 https://leetcode.com/problems/split-array-largest-sum/
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-10-10 08:36:01 | 显示全部楼层
frankman 发表于 2016-10-10 08:12
第4题跟这个题一样吧?LEETCODE  410 https://leetcode.com/problems/split-array-largest-sum/

不一样吧,这个split不能改变原数组的顺序的
回复 支持 反对

使用道具 举报

LumiG 发表于 2016-10-10 15:29:55 | 显示全部楼层

这个不对吧,这样没有最优子问题,并不能贪心。。。

比如task序列  9 8 7 4 4,贪心分出来就是 (9,4,4) (8,7) 是15,然而最优解是(9,7) (8,4,4)。。。-google 1point3acres

所以得把所有的状态空间弄出来,做dp,不能只选一条路做贪心。。

补充内容 (2016-10-10 15:31):
写错了,那个反例的值是17,最优解是16
回复 支持 反对

使用道具 举报

zhuhai_ZFC 发表于 2016-10-10 21:38:48 | 显示全部楼层
楼主已经工作多久了?
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-10-10 21:42:58 | 显示全部楼层
LumiG 发表于 2016-10-10 15:29
这个不对吧,这样没有最优子问题,并不能贪心。。。

比如task序列  9 8 7 4 4,贪心分出来就是 (9,4,4 ...

用dp的话你纪录的状态是什么呢?
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-10 22:13:29 | 显示全部楼层
LumiG 发表于 2016-10-10 03:29
这个不对吧,这样没有最优子问题,并不能贪心。。。
-google 1point3acres
比如task序列  9 8 7 4 4,贪心分出来就是 (9,4,4 ...

恩就是感觉上找不到一个合适的状态转移方程。。。
回复 支持 反对

使用道具 举报

喜马拉雅疯子 发表于 2016-10-11 01:07:18 | 显示全部楼层
LumiG 发表于 2016-10-10 15:29
这个不对吧,这样没有最优子问题,并不能贪心。。。

比如task序列  9 8 7 4 4,贪心分出来就是 (9,4,4 ...

嗯对。贪心法是错的。但是dp的转移方程想不出来啊。
回复 支持 反对

使用道具 举报

LumiG 发表于 2016-10-11 03:47:49 | 显示全部楼层
喜马拉雅疯子 发表于 2016-10-11 01:07
嗯对。贪心法是错的。但是dp的转移方程想不出来啊。
.1point3acres缃
这是个NPC问题吧… 状态空间是指数的,也没有重复状态,没有最优子问题。。。所以直接搜索就行了…

dp的话觉得可以像背包问题那样,就当装sum/2的东西,可以稍微剪掉一些状态…

补充内容 (2016-10-11 03:52):
不对,我傻逼了,这相当于一个01背包问题,正常dp就可以了……多项式复杂度。。。等于是一个数组,如果和是sum,每个数字可以取或者不取,求最接近sum/2的取法…
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-11 04:02:55 | 显示全部楼层
LumiG 发表于 2016-10-10 15:47
这是个NPC问题吧… 状态空间是指数的,也没有重复状态,没有最优子问题。。。所以直接搜索就行了…

dp ...

哦所以相当于是如果有k个worker,对每一个worker的工作量都进行一次01背包计算,标准是最接近sum/k,然后对一个worker找到答案之后把它处理的job删掉,让下一个worker从剩下的jobs里进行下一轮01背包,最后算一下每个worker的工作量的最大值?
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-10-11 05:09:16 | 显示全部楼层
LumiG 发表于 2016-10-11 03:47
这是个NPC问题吧… 状态空间是指数的,也没有重复状态,没有最优子问题。。。所以直接搜索就行了…

dp ...

如果是两个worker应该简单很多,但现在是k个worker。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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