一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3123|回复: 18
收起左侧

FB 跪经

[复制链接] |试试Instant~ |关注本帖
bunnyNova 发表于 2016-10-20 06:08:06 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Fail在职跳槽

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

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

x
10号onsite 正常的四轮 2轮 coding + 1轮 design + 1轮聊天/coding
整体来说,coding难度不大,但会很抠细节,以及很多follow up, System Design比较有压力

Coding题
1. vector dot product
sparse怎么处理?一个很长一个很短怎么优化
2. build itinerary,先是输出一个解就好,follow up是在所有解中间输出字母表序最小的
leetcode原题,我隐约记得有个比较好的方法但忘记了,只能用普通的dfs backtracking
3. add binary,我觉得主要跪在这里,我很傻X的每加一个数都insert到stringbuilder的最前面
但忽略了stringbuilder/buffer这种东西是array base的 所以插入的时间消耗是很大的,当面试官
问我你这个解法input很大的时候不是线性时间你觉得问题在哪里?我没有第一时间想到这点。
其实直接append 最后reverse就好。
4. group anagram, follow up是如果考虑所有字符 甚至汉字日文韩文klingon 怎么办

Design
design memcache, 跟distributed system 0关系,问的很细,hash怎么设计,collision怎么办. visit 1point3acres.com for more.
每个node怎么设计,free之后的list怎么保存,插入是first fit还是best fit等等。

Manager聊天
比较正常的套路,就是project啊 人际关系啊 当你老板让你做你不愿意做的事情怎么办之类的。

上周五ref我的哥们说hr管他要ref letter了以为有戏(其实我也不知道这个是不是hr觉得还行才会去要)但周一还是告诉我跪了。不过也正常,面完就知道9成跪,因为答题过程中还是有不少瑕疵。感觉FB的面试难度真的不高,但是要求完成度很高,有点差错都会Good Game Well Played了...

.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-10-20 06:53):
1. vector dot product就是 A{a1, a2, a3...} B{b1, b2, b3...} product = a1 * b1 + a2 * b2... an * bn
如果vector很稀疏,那么这么算就很浪费,所以第一步优化是只看非0的,记录成一个pair {aindex, aval} 再算

补充内容 (2016-10-20 06:55):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这样当某个index 在两个vector里都非0我们再进行计算。再一步优化是其中一个vector非零很多另一个很少,可以对非零很多的vector pair进行binary search找对应的index

补充内容 (2016-10-20 06:56):. From 1point 3acres bbs
2. 332. Reconstruct Itinerary

评分

2

查看全部评分

luckylady 发表于 2016-10-20 06:22:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
谢谢LZ,能再具体说下 第一题和第二题的条件是什么吗
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-20 06:51:09 | 显示全部楼层
关注一亩三分地微博:
Warald
luckylady 发表于 2016-10-20 06:22
谢谢LZ,能再具体说下 第一题和第二题的条件是什么吗

具体的内容补充在帖子里了
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-20 06:51:28 | 显示全部楼层
有人问就补充一下1,2题细节:
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-20 09:30:49 | 显示全部楼层
"group anagram, follow up是如果考虑所有字符 甚至汉字日文韩文klingon 怎么办."

这个该怎么办?面试官有要求怎么找anagram的方法吗?一般的sort他能满意吗?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-20 10:25:03 | 显示全部楼层
dot product的输入是什么?两个array吗?
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-25 04:34:52 | 显示全部楼层
想请教一下楼主,hash遇到collision该怎么答,value存成linkedlist吗?谢谢~
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-10-25 10:36:41 | 显示全部楼层
这个 system design 有难度啊,没做过caching 的话怎么会知道这么多细节
回复 支持 反对

使用道具 举报

datrick 发表于 2016-10-26 05:44:18 | 显示全部楼层
请问,这个cache的application是什么?是很底层的cache吗?直接做内存管理而不用OS吗
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-26 08:19:57 | 显示全部楼层
Badger96 发表于 2016-10-25 04:34
想请教一下楼主,hash遇到collision该怎么答,value存成linkedlist吗?谢谢~

这是比较正常的思路吧,我也是这么说的
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-26 08:21:00 | 显示全部楼层
datrick 发表于 2016-10-26 05:44
请问,这个cache的application是什么?是很底层的cache吗?直接做内存管理而不用OS吗

.鐣欏璁哄潧-涓浜-涓夊垎鍦应该是memcached,不需要你考虑太多os的东西 不过他也问了不少相关的,可能和我的底层背景有关
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-26 08:21:44 | 显示全部楼层
iPhD 发表于 2016-10-20 09:30
"group anagram, follow up是如果考虑所有字符 甚至汉字日文韩文klingon 怎么办."

这个该怎么办?面试 ...

sort或者count吧 反正面试官点头了
回复 支持 反对

使用道具 举报

 楼主| bunnyNova 发表于 2016-10-26 08:22:15 | 显示全部楼层
chestnut9919 发表于 2016-10-20 10:25
dot product的输入是什么?两个array吗?

最开始是两个array,然后变成两个pair array只有非0元素和index构成的pair
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-26 09:29:47 | 显示全部楼层
第四题 follow up楼主有何高见?我的想法就是对unicode定义comparator,不确定~~
回复 支持 反对

使用道具 举报

finerve 发表于 2016-10-26 09:52:49 | 显示全部楼层
fb不是可以把一轮system design换成算法题么? lz你没换,还是改成必须的了??
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-31 11:17:45 | 显示全部楼层
感谢分享~~~!  请问 4. group anagram, follow up是如果考虑所有字符 甚至汉字日文韩文klingon 怎么办 这个follow up 怎么做?  如果用string表示的话 还是可以直接sort呀 感觉code并没有变化
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-11-1 05:36:26 | 显示全部楼层
何打发123 发表于 2016-10-31 11:17
感谢分享~~~!  请问 4. group anagram, follow up是如果考虑所有字符 甚至汉字日文韩文klingon 怎么办 这 ...

trick 在于 unicode take 1 to 4 bytes, 而java charAt() 返回长为2 bytes 的char, 这里要用codepoint 来表征字符. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-11-1 05:37):
就是说有的诡异字符可能会在String里占用两个位置, 要handle这种情况

补充内容 (2016-11-1 06:46):
不严谨了, 应该说utf8占用1-4个byte,unicode和utf8还是不一样的
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-1 05:53:34 | 显示全部楼层
zhaoweigg 发表于 2016-11-1 05:36
trick 在于 unicode take 1 to 4 bytes, 而java charAt() 返回长为2 bytes 的char, 这里要用codepoint  ...

厉害了我的哥。。。。受教了! 看来这里是考ascii 和Unicode的区别~~>.<
回复 支持 反对

使用道具 举报

XCQ 发表于 2016-11-10 16:10:43 | 显示全部楼层
楼主你说design memcache和distributed system没关系??? 是就设计成了sharded hashtable吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-22 20:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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