一亩三分地论坛

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

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

FB onsite

[复制链接] |试试Instant~ |关注本帖
a9887688zboy 发表于 2016-11-18 15:59:43 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
再来写个跪经。
十一月初onsite的, 4个工作日就收到拒信了,面的确实不好。
1. readN given read 4K II. 注意这里遇到一个follow up:optimize when N is larger than 4K。 有个假设: 如果可以调用的API 改变成 int read4K (char[] buf,  int start). 默认 buf 足够长, start 为上次读完之后的下一个空index. 这里readN 就可以直接用read 4K里面的buf.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. 在一个array 里面找到 sum最大,长度为 k 的 subarray, 返回sum。 这题太简单应该没算分,但是还让我写了。 第二个 题 找 sum最大,每个长度都是k 的三个subarray。 三个subarray不能有overlap。 举个栗子 1,2,1,2,6,7,5,1。k = 2。 这个里面找到的就应该是[1,2], 1,[2,6],[7,5],1 同样返回和。 楼猪这题傻逼的写了个 N^3的解法。铁定跪了。回学校问了下大神,大神说dp, 我也明白dp怎么写了,O(N)。

3. behavior 面试, 最后出了一个 LC115. 楼猪又没有一下用dp写出来,写了个recursion的解法。。然后follow up 是 lc 115 里面s 是一个一个字母给出,每给出一个字母,打印出 有几个 distinct subsequence。 这时候问了一个hint想出dp了。。可是没啥时间了,说了下思路。. 1point 3acres 璁哄潧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
三轮都面的不是太好,第一题follow up交流也不是很好。 不出意料跪了。还是dp有点弱。 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
helloc93 发表于 2016-11-18 16:16:03 | 显示全部楼层
摸摸 楼主面的好难
回复 支持 反对

使用道具 举报

jia0804 发表于 2016-11-18 16:19:14 | 显示全部楼层
楼主这题。。感觉就是FB面经里最难的了。最近FB bar越来越高了,不一定是楼主面的不好,headcount少了吧
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-11-18 16:48:47 | 显示全部楼层
好难好难。。。不怪楼主,实在难
第一题楼主的意思是read4k(buf, start)可以用readN的buf的意思吗(看楼主写的意思好像是反的不过反的好像说不通啊)? start是读的起始位置
解法大概是假设n是4k*i + j大小,前面i下就直接读到buf里,或者读没了直接返回。最后一下读到cache里?下次读的时候先把cache读出来再继续
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-11-18 19:15:27 | 显示全部楼层
谢谢分享!请问能不能解释一下第二题,为什么例子不是[1,2],1,2,[6,7],[5,1] 因为6+7才是最大的不是么?这个每选一个subarray,top 3 sum 都会不一样,怎么选呢?
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-18 23:45:58 | 显示全部楼层
wangyuesong2 发表于 2016-11-18 16:48
好难好难。。。不怪楼主,实在难. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题楼主的意思是read4k(buf, start)可以用readN的buf的意思 ...

正解!我还担心我表述不大清楚
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-18 23:48:41 | 显示全部楼层
Xochitl 发表于 2016-11-18 19:15
谢谢分享!请问能不能解释一下第二题,为什么例子不是[1,2],1,2,[6,7],[5,1] 因为6+7才是最大的不是么?这 ...

要的是三个 subarray 的和最大,按照你的解法,算出来的和是3+13+6 = 22. 应该算出来的是 3+8+12 = 23. 是有点绕。 我一开始也是想着怎么避免你说的这种情况,有点想傻了
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-11-19 01:29:13 | 显示全部楼层
谢谢解释,那这个是第一道题有点儿误导…然后把思维定式了,摸摸楼主
回复 支持 反对

使用道具 举报

xiangjn_alex 发表于 2016-11-19 02:00:58 | 显示全部楼层
求问楼主 第二题 O(n)是怎么做的哇 可以说说嘛~
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-19 09:52:04 | 显示全部楼层
xiangjn_alex 发表于 2016-11-19 02:00
求问楼主 第二题 O(n)是怎么做的哇 可以说说嘛~

先搞一个 sum array,再来一个 3*n 的矩阵dp, dp[j] = Math.max(dp[j - 1], dp[j - k] +sum[j+1] - [j+1-k])

没仔细想,大概是这样。有错请指出哈~

补充内容 (2016-11-19 10:12):
这个现实有点问题 dp[j]
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-19 10:13:02 | 显示全部楼层
  1. dp[i][j] = Math.max(dp[i][j - 1], dp[i][j - k] +sum[j + 1] - sum[j + 1 - k]);
复制代码
回复 支持 反对

使用道具 举报

此用户无名 发表于 2016-11-19 10:14:38 | 显示全部楼层
哪个office面的?普通university recruiting的话这题目很难啊。楼主别难过了
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-19 10:16:29 | 显示全部楼层
此用户无名 发表于 2016-11-19 10:14.鏈枃鍘熷垱鑷1point3acres璁哄潧
哪个office面的?普通university recruiting的话这题目很难啊。楼主别难过了
-google 1point3acres
就是Uday 总部
回复 支持 反对

使用道具 举报

firemanysome 发表于 2016-11-23 11:18:23 | 显示全部楼层
楼主 第二个 题 找 sum最大,每个长度都是k 的三个subarray。 三个subarray不能有overlap。 举个栗子 1,2,1,2,6,7,5,1。k = 2。 这个里面找到的就应该是[1,2], 1,[2,6],[7,5],1 同样返回和。如果输入是[1,2,1], 2。结果是什么?谢谢
回复 支持 反对

使用道具 举报

notbad 发表于 2016-11-23 13:18:26 | 显示全部楼层
第二题不可以直接贪心吗?从左到右,先找一个,然后再找一个,然后再找,如果存在肯定可以找到。如果找不到,也能说明肯定不存在。
回复 支持 反对

使用道具 举报

notbad 发表于 2016-11-23 13:19:40 | 显示全部楼层
忽略我,看错题目了。。。
回复 支持 反对

使用道具 举报

 楼主| a9887688zboy 发表于 2016-11-24 01:03:32 | 显示全部楼层
firemanysome 发表于 2016-11-23 11:18
楼主 第二个 题 找 sum最大,每个长度都是k 的三个subarray。 三个subarray不能有overlap。 举个栗子 1,2,1 ...

1,2,1,2 k = 2 应该不是一个合法的输入。k= 2 这种情况起码要6个数字 才是合法输入
回复 支持 反对

使用道具 举报

Raymomd 发表于 2016-11-27 00:50:35 | 显示全部楼层
题目中要求的是三个subarray,但是楼主贴的代码里的转换方程好像和 i 无关,是求所有不重叠subarray的最大和吧, 楼楼这一点怎么做到啊
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-11-27 06:40:09 | 显示全部楼层
lz能说下电面的题目吗?
回复 支持 反对

使用道具 举报

treeguard 发表于 2016-11-29 09:57:38 | 显示全部楼层
说一下我对第二题的想法, 可以先简化为两个subarray 两个subarray 明显简单了 dp1[i]表示nums[0..i] one subarray的最大值 dp2[i] 表示nums[0...i] 的two subarray的sum最大值 dp2[i] = max(dp2[i-1], dp[i-k]+sum(i-k,i)) 有了dp2 就可以方便的求出三个了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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