一亩三分地论坛

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

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

fb两轮电面面经

[复制链接] |试试Instant~ |关注本帖
8wy172250 发表于 2015-1-9 02:40:19 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass

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

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

x
    是的,你没有看错,的确就是两轮。发面经为接下来的onsite攒RP,希望一切顺利。

    第一轮的问题是:给一个int矩阵,0代表empty,1代表obstacle,find whether there's a path between 2 nodes.  我这道题上来直接就用了dfs,而且写的磕磕绊绊,大概半小时才完全写好,导致整轮只做了一道题。后来想想这道题用bfs 或者 bidirectional bfs会更好。follow up是当图变得极大时,dfs会有什么问题。还有当我们有一个计算机集群的时候,可以如何加速算法。面试之后两天都没有消息,我就知道不妙。一周之后通知被加了一轮电面。. from: 1point3acres.com/bbs

    第二轮的问题:Given a string list,find all pairs of strings which can be combined to be a palindrome. eg: cigar + tragic -> cigartragic, none + xenon -> nonexenon。如果有n个词,每个词长度m,用HashSet可以用O(nm)做出来。第二道是find distance between two nodes in a binary tree。做到这道题的时候只剩十分钟左右了,做的险象环生,还好最后做出来了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


补充内容 (2015-1-11 07:44):
第二问第一题时间复杂度错了,应该是O(nm^2)。

评分

3

查看全部评分

 楼主| 8wy172250 发表于 2015-1-11 02:13:48 | 显示全部楼层
lklk1986fa 发表于 2015-1-10 17:15
soga, 不过感觉每个单词拆分之后遍历查是不是palindrome应该是O(m^2),然后看看reverse的substring是否 ...

嗯 有道理
回复 支持 1 反对 0

使用道具 举报

ndhuanhuan 发表于 2015-1-9 02:45:52 | 显示全部楼层
电面是在shared doc上写吗? 除了coding还是否问了其它问题?
回复 支持 反对

使用道具 举报

 楼主| 8wy172250 发表于 2015-1-9 02:49:17 | 显示全部楼层
ndhuanhuan 发表于 2015-1-9 02:45
电面是在shared doc上写吗? 除了coding还是否问了其它问题?

在collabedit.com上写的。其他问题就是些项目经历,实习的时候做过些什么之类的。
回复 支持 反对

使用道具 举报

kwang75 发表于 2015-1-9 03:28:23 | 显示全部楼层
lz给力。十分钟做最后一题其实会挺紧张的。
回复 支持 反对

使用道具 举报

lklk1986fa 发表于 2015-1-9 03:47:07 | 显示全部楼层
第二题第一问如何O(mn)呢?
回复 支持 反对

使用道具 举报

smith 发表于 2015-1-9 06:27:40 | 显示全部楼层
同问,楼主第二题第一问怎么做的呢?
回复 支持 反对

使用道具 举报

smith 发表于 2015-1-9 06:27:46 | 显示全部楼层
同问,楼主第二题第一问怎么做的呢?
回复 支持 反对

使用道具 举报

dtcxzch 发表于 2015-1-10 10:17:06 | 显示全部楼层
同问第二面第一题O(mn)解法
回复 支持 反对

使用道具 举报

 楼主| 8wy172250 发表于 2015-1-10 12:45:32 | 显示全部楼层
lklk1986fa 发表于 2015-1-9 03:47
第二题第一问如何O(mn)呢?

把所有的词丢进hashset。然后对每一个word, for each i in [0, word.length()), 将word拆成两个substring [0, i] and [i + 1, word.length()),如果一个词是palindrome而另一个词在set里,说明可以combine成palindrome,然后就可以返回这个pair了。
回复 支持 反对

使用道具 举报

lklk1986fa 发表于 2015-1-10 17:15:22 | 显示全部楼层
8wy172250 发表于 2015-1-10 12:45. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
把所有的词丢进hashset。然后对每一个word, for each i in [0, word.length()), 将word拆成两个substring ...

soga, 不过感觉每个单词拆分之后遍历查是不是palindrome应该是O(m^2),然后看看reverse的substring是否在hashset里
回复 支持 反对

使用道具 举报

dtcxzch 发表于 2015-1-11 09:02:36 | 显示全部楼层
lklk1986fa 发表于 2015-1-10 04:15
soga, 不过感觉每个单词拆分之后遍历查是不是palindrome应该是O(m^2),然后看看reverse的substring是否 ...

对啊 我也觉得总的时间复杂度是O(n*m^2)
回复 支持 反对

使用道具 举报

brainrpi 发表于 2015-1-11 11:55:48 | 显示全部楼层
求问LZ第二轮第二题是BST吗?有木有父指针?能否用额外空间,比如先把path存起来?都没有好难做啊
回复 支持 反对

使用道具 举报

z3581640 发表于 2015-2-13 00:28:57 | 显示全部楼层
第一题是否可以这样,一边在List里向前走, 一边 往hashset里面插入,没遇到一个词, 假设 reverse = Reverse(word); 分别查找 set里 reverse 和 reverse.substring(1); 存在的话就是palindrome, 同时基于 palindrome 的特性, 那么把这个 combine reverse 一下, 又是上一个词的 palindrome, 这样时间是 O(m * n)

另外的话, 如果用 prefix tree 做的话, 可以 比 O(m*n) 再小一点, 因为可以不用reverse, 按着prefix走, 只要不同就可以返回了. Waral 鍗氬鏈夋洿澶氭枃绔,

第二题 求 两个 node 之间的path, 觉得是不是先求一下 lowest common ancester, 这样 是O(N) 的时间复杂度,然后 从 公共祖先求到两个点的距离,这是lg(n)的时间复杂度, 所以总体是O(N)的时间复杂度

然后 obstacle 那个题, 因为是int型, 觉得是否 用 dp数组更好一些, 如果是图特别大, 就把图拆开, 分别在几个机器上计算, 然后 把他们的边界 的一位数组 进行比较, 就可以得出是否走的通

不知大家有没有好的思路,谢谢啦
回复 支持 反对

使用道具 举报

李宗基 发表于 2015-3-29 11:57:37 | 显示全部楼层
z3581640 发表于 2015-2-13 00:28
第一题是否可以这样,一边在List里向前走, 一边 往hashset里面插入,没遇到一个词, 假设 reverse = Rever ...

你第一题的思路是错的
回复 支持 反对

使用道具 举报

z3581640 发表于 2015-4-3 05:27:59 | 显示全部楼层
李宗基 发表于 2015-3-29 11:57. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你第一题的思路是错的

多谢多谢,前些天跟朋友讨论过,思路不对,忘了update了,哈哈
回复 支持 反对

使用道具 举报

youto 发表于 2015-10-15 03:13:51 | 显示全部楼层
第二题的第一个问题貌似还要考虑 {abc, ba}的情况,应该 把abc返过来拆分一下,判断substring[0,len-i] 和substring[len-i]. 鍥磋鎴戜滑@1point 3 acres

请问lz,题目要求是包含duplicate words还是unique word了吗?
回复 支持 反对

使用道具 举报

reality 发表于 2015-11-16 10:38:25 | 显示全部楼层
同问第二轮第一题。不是很懂这个解法。望指教。
回复 支持 反对

使用道具 举报

yanggao1119 发表于 2016-2-18 15:27:45 | 显示全部楼层
用hashset够吗?感觉这个不是要返回一个boolean,而是要把pair找出来,hashset存partial string,不太够的感觉。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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