传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 9204|回复: 42
收起左侧

fb面经 两轮phone+onsite

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
去年12月电面的,然后上上周去seattle参加university day之后被要求加面 ==
第一轮电面很简单:

1. 3sum
2. phone letter combinations
只要打印出所有组合就行,我写了dfs的解法,然后问时间复杂度
3. print binary tree path. 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
当时是圣诞节前的周五,打电话的是个白人小哥,感觉心情特别好,我说什么他都回应“cool"
然后新年第一天给了onsite的通知


onsite:
1.第一轮基本是behavior, 很general的问题,比如why facebook, 你感兴趣的部门/产品之类的。聊到最后剩了几分钟说来点coding吧,问了search in rotated sorted array, leetcode原题
2. find celebrity. 之前看面经的时候看到过,当时不知道这题是干什么的就没在意,被问到的时候后悔也来不及了。。。先写了O(n^2)的算法,然后被要求优化,各种不熟练,估计是栽到这轮了. 1point 3acres 璁哄潧
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].
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璁哄潧

评分

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/. more info on 1point3acres.com

评分

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):. 1point 3acres 璁哄潧
也没有design?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

zcy1848 发表于 2015-1-27 06:08:39 | 显示全部楼层
如果要call multiple times,是不是要把dictionary每个单词的各个排列都加到trie中?这个加的时间复杂度就非常高了,不过每次call function时间复杂度就是O(n)
回复 支持 反对

使用道具 举报

夏至 发表于 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. more info on 1point3acres.com
请问下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开始遍历查找. visit 1point3acres.com for more.

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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果要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要整死我

请问你面的哪个?
回复 支持 反对

使用道具 举报

蓝田十三点 发表于 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都怎么准备?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-27 00:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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