一亩三分地论坛

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

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

Facebook Intern 电面面经

[复制链接] |试试Instant~ |关注本帖
zpinthehouse 发表于 2016-11-13 01:06:07 | 显示全部楼层 |阅读模式

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

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

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

x
前天电面的。。面试官是中国小哥。。
第一题有点像Leetcode325 Maximum Size Subarray Sum Equals k,只需要判断是否存在,返回boolean,用一个set做就可以,我一上来傻乎乎的写了map。。
第二题decode ways,出了个小bug,该i+1的写成了i..然后followup是如果给的value不连续,比如a:78, b:539, ..., 怎么办。。我说可以backtracking,然后简单说了一下怎么搞。。
希望不管过没过能早一点出消息,有一个一般般的offer感恩节左右就得decide了。。

评分

1

查看全部评分

gaoyikai90 发表于 2016-11-13 07:43:58 | 显示全部楼层
第二题follow up还可以用dp,每次判断一个新的string的时候,例如判断123456, 可以遍历26个字母对应的每个number, 看该number能否作为这个String的结尾,如果可以,就可以写dp[i] += dp[i-L], 由于String每次前进一位只要遍历26次,所以复杂度还是O(n)。 这个我觉得可行吧
回复 支持 1 反对 0

使用道具 举报

angryR 发表于 2016-11-15 10:34:03 | 显示全部楼层
gaoyikai90 发表于 2016-11-13 07:43
第二题follow up还可以用dp,每次判断一个新的string的时候,例如判断123456, 可以遍历26个字母对应的每个 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
a = 3, b = 250000000
so you can't forward check a~z.
DP works, but it is O(n * (max len of the string for a number))
回复 支持 1 反对 0

使用道具 举报

wangyuesong2 发表于 2016-11-13 01:56:44 | 显示全部楼层
value不连续也可以用用dp吧?就是效率变成oN2了?
回复 支持 反对

使用道具 举报

 楼主| zpinthehouse 发表于 2016-11-15 01:00:00 | 显示全部楼层
gaoyikai90 发表于 2016-11-13 07:43
第二题follow up还可以用dp,每次判断一个新的string的时候,例如判断123456, 可以遍历26个字母对应的每个 ...

恩。。好像这样是对的。。
回复 支持 反对

使用道具 举报

jtzgz 发表于 2016-11-15 02:33:49 | 显示全部楼层
什么叫value不连续啊?
回复 支持 反对

使用道具 举报

oio14644 发表于 2016-11-15 06:07:32 | 显示全部楼层
jtzgz 发表于 2016-11-15 02:33. From 1point 3acres bbs
什么叫value不连续啊?

我也想知道,谢谢
回复 支持 反对

使用道具 举报

oio14644 发表于 2016-11-16 05:22:13 | 显示全部楼层
不连续 怎么理解?
回复 支持 反对

使用道具 举报

 楼主| zpinthehouse 发表于 2016-11-16 06:52:32 | 显示全部楼层
jtzgz 发表于 2016-11-15 02:33
什么叫value不连续啊?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是比如a:38, b:476, c:19280, d:2238, e:1,...
回复 支持 反对

使用道具 举报

oio14644 发表于 2016-11-16 09:48:38 | 显示全部楼层
zpinthehouse 发表于 2016-11-16 06:52
就是比如a:38, b:476, c:19280, d:2238, e:1,...

还是没明白,原题不是input 就一个string 吗?
public class Solution {
    public int numDecodings(String s) {
        .鏈枃鍘熷垱鑷1point3acres璁哄潧
    }
}
a:38 不连续怎么个解读? 是string 中间有非数字吗? 1&10 这样吗?
回复 支持 反对

使用道具 举报

 楼主| zpinthehouse 发表于 2016-11-16 10:16:58 | 显示全部楼层
oio14644 发表于 2016-11-16 09:48
还是没明白,原题不是input 就一个string 吗?
public class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    public int numDecodings(St ...

额。。就是说以前输入string12,可以是L,或者AB,现在没有这么明显的关系了。。不过楼上有位同学说是一样的,也可以DP来做。。我当时直接说backtracking了。。这个应该是面试官看时间还剩一点但是不多了随便问的吧我感觉。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-16 15:09:59 | 显示全部楼层
楼主收到二面通知了吗?
回复 支持 反对

使用道具 举报

oio14644 发表于 2016-11-16 17:12:16 | 显示全部楼层
这题不可以想预处理一下字符串吗? 去掉非法字符,只留下数字,然后再decode?
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-16 22:40:51 | 显示全部楼层
第一题只用返回boolean是说只用找到一个subarray sums larger than k 就可以了吗
回复 支持 反对

使用道具 举报

jtzgz 发表于 2016-11-17 06:04:22 | 显示全部楼层
还是不懂什么叫不连续的value。。可以加oio14644  私聊么?
回复 支持 反对

使用道具 举报

jimmyshie123 发表于 2016-11-17 12:02:58 | 显示全部楼层
楼主这是一面嘛
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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