一亩三分地论坛

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

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

fb面经 两轮phone+onsite

[复制链接] |试试Instant~ |关注本帖
skyangel317 发表于 2015-1-27 03:28:21 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Other

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

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

x
去年12月电面的,然后上上周去seattle参加university day之后被要求加面 ==. Waral 鍗氬鏈夋洿澶氭枃绔,
第一轮电面很简单:
. more info on 1point3acres.com
1. 3sum
2. phone letter combinations
只要打印出所有组合就行,我写了dfs的解法,然后问时间复杂度. visit 1point3acres.com for more.
3. print binary tree path. from: 1point3acres.com/bbs

当时是圣诞节前的周五,打电话的是个白人小哥,感觉心情特别好,我说什么他都回应“cool"
然后新年第一天给了onsite的通知


onsite:
1.第一轮基本是behavior, 很general的问题,比如why facebook, 你感兴趣的部门/产品之类的。聊到最后剩了几分钟说来点coding吧,问了search in rotated sorted array, leetcode原题
2. find celebrity. 之前看面经的时候看到过,当时不知道这题是干什么的就没在意,被问到的时候后悔也来不及了。。。先写了O(n^2)的算法,然后被要求优化,各种不熟练,估计是栽到这轮了. 1point3acres.com/bbs
3. 给一个double array, 返回一个新的array, 每个元素是原来的array除它之外所有元素的乘积。先写了用除法的,然后问不用除法怎么做
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
加面一轮:
Find all words [A-Z] in a dictionary (about 1M words) that are made of a subset (in any order) of the chars in the input parameter [A-Z].
. visit 1point3acres.com for more.ex: input "ACRAT" (10 to 20 chars, up to 30 worst case)
matching words: "A", "CAR", "ACA", "ART", "RAC"
non-matching words: "BAR", "AAA".鐣欏璁哄潧-涓浜-涓夊垎鍦


一上来就做题,function会被call multiple times, 问怎么优化。回答用trie,然后没想起来怎么做,在他提示下才想到思路,感觉答得不好。. 1point3acres.com/bbs
. from: 1point3acres.com/bbs

评分

6

查看全部评分

本帖被以下淘专辑推荐:

cjlm007 发表于 2015-2-16 09:01:38 | 显示全部楼层
第二轮经典celebrity题,stack做,O(n):
http://www.fgdsb.com/2015/01/03/the-celebrity-problem/

第三轮就是exclusive product: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
http://www.fgdsb.com/2015/01/13/get-prod-array-without-div/

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

jill_8668 发表于 2016-2-21 06:17:20 | 显示全部楼层
skipper 发表于 2015-1-27 04:09
Good luck.
加面的那个题目只要统计下字符串中每个字符出现次数,遍历dict里面的每个word,比较相应字符串 ...

按照你这个思路, 是不是不需要用trie? 我也认为不需要用trie.为啥大家都说要用trie???
回复 支持 1 反对 0

使用道具 举报

likeulb 发表于 2016-2-22 14:22:20 | 显示全部楼层
jill_8668 发表于 2016-2-21 06:17
按照你这个思路, 是不是不需要用trie? 我也认为不需要用trie.为啥大家都说要用trie???

他的优化是当这个function要call很多次的时候,如果每次给一个input, 建一个map, 再把Dictionary里每个Word遍历一遍看是不是可以用这个map里的char,就不是很有效。我觉得,当要call很多次时,把dictionary里的所有Word建成一个trie tree, 然后每次对一个input string,从root走这个tree,看有哪些word可以走到
回复 支持 1 反对 0

使用道具 举报

gzy13245 发表于 2015-1-28 20:08:57 | 显示全部楼层
第三题不用除法怎么做啊?
回复 支持 1 反对 0

使用道具 举报

skipper 发表于 2015-1-27 04:09:49 | 显示全部楼层
Good luck.
加面的那个题目只要统计下字符串中每个字符出现次数,遍历dict里面的每个word,比较相应字符串中A-Z出现的次数就行
算法复杂度是O(total words length)
回复 支持 反对

使用道具 举报

YY大帝 发表于 2015-1-27 04:58:38 | 显示全部楼层
请问下lz这个phone letter combinations的dfs时间复杂度是多少,是O(所有组合个数)?
回复 支持 反对

使用道具 举报

NdrZmansN 发表于 2015-1-27 05:04:03 | 显示全部楼层
怎么现在这么多新题....
回复 支持 反对

使用道具 举报

蓝田十三点 发表于 2015-1-27 05:07:34 | 显示全部楼层
谢谢分享,祝offer!
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-1-27 05:12:22 | 显示全部楼层
祝offer!
LZ 最后加面优化怎么做了?

补充内容 (2015-1-27 05:12):
也没有design?
回复 支持 反对

使用道具 举报

海拔2纳米 发表于 2015-1-27 05:42:10 | 显示全部楼层
skipper 发表于 2015-1-27 04:09
Good luck.
. From 1point 3acres bbs加面的那个题目只要统计下字符串中每个字符出现次数,遍历dict里面的每个word,比较相应字符串 ...

这题我onsite也面到了,面试官是想让我给dict写成一个trie
回复 支持 反对

使用道具 举报

头像被屏蔽
zcy1848 发表于 2015-1-27 06:08:39 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

夏至 发表于 2015-1-27 08:11:05 | 显示全部楼层
第二题是什么意思啊? 楼主能解释下吗? 没见过
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-1-27 12:17:08 | 显示全部楼层
skipper 发表于 2015-1-27 04:09
Good luck.
加面的那个题目只要统计下字符串中每个字符出现次数,遍历dict里面的每个word,比较相应字符串 ...

谢谢~
没错,先是用一个数组存下input中所有字母出现的次数,然后根据dict建一个trie, 但是貌似不需要遍历其中的每个word。比如"BAR", 发现“B"不在input里面就不用继续查了
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-1-27 12:20:08 | 显示全部楼层
YY大帝 发表于 2015-1-27 04:58
请问下lz这个phone letter combinations的dfs时间复杂度是多少,是O(所有组合个数)?

对的,假设每个数字对应k个字母,然后输入字符串长度n,时间复杂度就是O(k^n)
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-1-27 12:52:52 | 显示全部楼层
houqingniao 发表于 2015-1-27 05:12
祝offer!
LZ 最后加面优化怎么做了?

优化算法就是根据字典建一个trie,统计input里面所有字母的出现次数,然后从root开始遍历查找

onsite就是三道算法题,没有design
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-1-27 12:53:08 | 显示全部楼层
houqingniao 发表于 2015-1-27 05:12
祝offer!
LZ 最后加面优化怎么做了?

优化算法就是根据字典建一个trie,统计input里面所有字母的出现次数,然后从root开始遍历查找

onsite就是三道算法题,没有design
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-1-27 12:57:05 | 显示全部楼层
zcy1848 发表于 2015-1-27 06:08-google 1point3acres
如果要call multiple times,是不是要把dictionary每个单词的各个排列都加到trie中?这个加的时间复杂度就 ...

每个单词只要按顺序加到trie里面就可以了,当时剩下的时间不够了,面试官说假设trie已经建好了,只让我写了search的部分
回复 支持 反对

使用道具 举报

天空的一点 发表于 2015-2-1 13:19:42 | 显示全部楼层
前几天刚刚电面了,而且电面的问题竟然是lz onsite的问题。。。难道Facebook要整死我
回复 支持 反对

使用道具 举报

qjx026 发表于 2015-2-6 03:45:14 | 显示全部楼层
天空的一点 发表于 2015-2-1 13:19
前几天刚刚电面了,而且电面的问题竟然是lz onsite的问题。。。难道Facebook要整死我
-google 1point3acres
请问你面的哪个?
回复 支持 反对

使用道具 举报

蓝田十三点 发表于 2015-2-6 04:10:37 | 显示全部楼层
楼主你好,刚和HR电话安排onsite的时候HR说onsite大概是两轮coding,一轮system design,一轮behavior,可我是NCG哇,我还特意问了下一定会有system design吗,她说是的。请教楼主安排onsite的时候是个什么情况,hr也有说会有system design的事吗
回复 支持 反对

使用道具 举报

 楼主| skyangel317 发表于 2015-2-6 08:51:05 | 显示全部楼层
蓝田十三点 发表于 2015-2-6 04:10
楼主你好,刚和HR电话安排onsite的时候HR说onsite大概是两轮coding,一轮system design,一轮behavior,可 ...

当时hr给我安排面试的时候就是三轮,说是两轮coding, 一轮behavior+coding, 没有安排面system design。不过我是master,可能不用面design。或者你的背景比较强,他们要考察一下==
回复 支持 反对

使用道具 举报

seahope 发表于 2015-2-6 15:50:46 | 显示全部楼层
大家system design都怎么准备?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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