一亩三分地论坛

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

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

Facebook Intern 二面

[复制链接] |试试Instant~ |关注本帖
hanchen999 发表于 2015-10-10 23:00:19 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
在板上看了不少面经,回馈下
这周四下午二面的,出了三道题
. 1point3acres.com/bbs
1 找两个字符串中长度为N以上的共同子串。。LZ脑抽没答好。。。其实遍历一下就行
2leetcode原题tree right next pointer
3可能LZ两题反差比较大所以加了个第三题leetcode原题 最大子数组. 1point3acres.com/bbs

一面地址:http://www.1point3acres.com/bbs/thread-141847-1-1.html
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
昨天HR写信约周一给我打电话,只求人品不要电话据我。。。。


补充内容 (2015-10-13 04:47):
多谢各位的支持,顺利拿到OFFER

评分

3

查看全部评分

huoshankou 发表于 2015-12-1 12:24:54 | 显示全部楼层
第一题还是不太明白。他要求N 或者 N以上的。你的set只装长度为N的子串?那长度为N + 1, N + 2, N + 3, ...呢?
回复 支持 1 反对 0

使用道具 举报

sonicgu 发表于 2015-10-10 23:08:11 | 显示全部楼层
lz问一下第一题,意思是两个string,然后找他们共有的长度为N以上的substring吗
回复 支持 反对

使用道具 举报

 楼主| hanchen999 发表于 2015-10-10 23:13:47 | 显示全部楼层
是的。。弄个set搞下就好。。其实就是找长度为N的,N以上包含长度为N的。。。
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-10-10 23:17:00 | 显示全部楼层
hanchen999 发表于 2015-10-10 23:13
是的。。弄个set搞下就好。。其实就是找长度为N的,N以上包含长度为N的。。。

好的,谢谢,祝顺利
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-11 01:09:10 | 显示全部楼层
LZ放心,约电话就是给offer了。
回复 支持 反对

使用道具 举报

clarkleng 发表于 2015-10-11 01:27:55 | 显示全部楼层
电话就offer 了,放心
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-10-11 01:28:35 | 显示全部楼层
facebook实习没有onsite吗?
回复 支持 反对

使用道具 举报

 楼主| hanchen999 发表于 2015-10-11 01:40:00 来自手机 | 显示全部楼层
借ls几位大神的吉言了,fb实习如果人多情况下好像两轮都可以screen
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-11 02:30:30 | 显示全部楼层
楼主第一题为什么遍历就行。。?
每个STR的SUB STR有很多个啊?一个个弄出来?
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-11 02:38:26 | 显示全部楼层
楼主,您说的是不是从第一个STR1开始,里面每个起点挖出一个长度为N的SUBTR,然后去第二个STR2里面找么。。
回复 支持 反对

使用道具 举报

 楼主| hanchen999 发表于 2015-10-11 02:52:17 来自手机 | 显示全部楼层
弄个set装起来就行,然后把str2的所有长度为n的substr遍历一下
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-11 03:33:29 | 显示全部楼层
hanchen999 发表于 2015-10-11 02:52
弄个set装起来就行,然后把str2的所有长度为n的substr遍历一下

谢谢您,刚才和人讨论了一下,貌似这题有可能用DP做也行,我想想
回复 支持 反对

使用道具 举报

 楼主| hanchen999 发表于 2015-10-11 03:45:41 | 显示全部楼层
DP确实可行,当时觉得这是第一题,就没往那个方向想。不dp我觉得复杂度应该是N*str.length(), dp估计能降到str.length()吧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-10-11 03:51):
回头想了下还是set快一些,如果dp怕是str1.length() * str2.length(), 不dp是N * str1.length() + N * str2.length().
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-10-11 04:55:55 | 显示全部楼层
hanchen999 发表于 2015-10-11 03:45
DP确实可行,当时觉得这是第一题,就没往那个方向想。不dp我觉得复杂度应该是N*str.length(), dp估计能降到 ...

我理解的DP是先从S1中找到N个substring, 其中n1与S1共有,下一步则是借助n1长度为N的substring,推得与之相关的(N+1)长的substring,假设有n2个。

这样下去的话,其实也是找len(s1)^(len(s1l-N) + k*len(s2) ---与用set在数量级上差不多,但是要过滤的结果少了很多。
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-11 11:53:37 | 显示全部楼层
hanchen999 发表于 2015-10-11 03:45. 鍥磋鎴戜滑@1point 3 acres
DP确实可行,当时觉得这是第一题,就没往那个方向想。不dp我觉得复杂度应该是N*str.length(), dp估计能降到 ...

Set的复杂度应该是len1^3 + len^3吧,应该需要求N, N+1...len1长度的substring.
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-1 12:37:32 | 显示全部楼层
longest common substring. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
大伙为啥这么纠结
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-12-3 05:19:35 | 显示全部楼层
huoshankou 发表于 2015-12-1 12:24
第一题还是不太明白。他要求N 或者 N以上的。你的set只装长度为N的子串?那长度为N + 1, N + 2, N + 3, . ...

同不明白,求解释
回复 支持 反对

使用道具 举报

 楼主| hanchen999 发表于 2015-12-3 05:35:36 | 显示全部楼层
N + 1以上包含N, 就是比如规定长度是2, 两个字符串都包含abc, 在发现abc之前你就会看见ab然后直接返回false...
回复 支持 反对

使用道具 举报

huoshankou 发表于 2015-12-4 03:03:11 | 显示全部楼层
hanchen999 发表于 2015-12-3 05:35.1point3acres缃
N + 1以上包含N, 就是比如规定长度是2, 两个字符串都包含abc, 在发现abc之前你就会看见ab然后直接返回fa ...

所以这个题只是返回能不能找到, 不是让你返回所有的长度大于等于N的共同子串喽。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 21:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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