一亩三分地论坛

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

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

Facebook电面

[复制链接] |试试Instant~ |关注本帖
西法的洛 发表于 2016-10-19 10:56:23 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
报一个今天上午FB的面经,求onsite

一个印度小哥,在纽约site
第一题 whether there is a subarray's sum equals to k, 其实就是lc maximum subarray那道题目的简化版本, 当时脑子抽了,直接写了个hashset的O(n) space, O(n) time的解法,小哥人问我怎么reduce complexity,然后又写了个sliding window的正常解法,这回constant space,这里也是紧张了,应该先跟面试官确认是不是想让我写之前那个很烂的方法,然后确定人家想让你写啥,你再去写,要不然白耽误时间了。(这里写for loop时候里面忘记i++了,算是一个bug,小哥提示我有bug,让我看看,我改正了,不知道这样ok不)

第二题 其实是第一题的follow up,whether there is a submatrix's sum equals to k,脑子里直接想了个不好的解法,怕时间不够,就说了一下想法,面试官问了一下复杂度,答O(m^2*N^2) 他就说你写吧,然后以为应该可以了,然后快速写完(这里又有个bug,一个减号写成了加号,小哥说你这个代码有问题吗,我说我看看啊,然后改正)。写完了之后终于松了一口气,小哥说你这个复杂度能不能reduce,我说我看看啊,想了一下,没出声,小哥说结合你上道题目想想,怎么把二维转换成一维呢(这里多谢小哥给hint),然后我就讲了一下,复杂度变为O(m^2 * n) 小哥说可以了,问问题吧。. 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
中午面完到现在一直没消息,求个onsite。
其实这次面试,问题还是很多,lc的原题,没有第一时间想出最优解,而且写出了bug,然后最后follow up尽管思路说出来了,写出来的不是最优解,最后其实复杂度是O(Min(m ^ 2 * n, n^2 * m)) 根据这两个数的大小来选择压缩行还是列。所以就算挂了,也是需要再提升了。
. 1point 3acres 璁哄潧

补充内容 (2016-10-19 11:03):
第一题都是正数。

补充内容 (2016-10-20 00:36):
Update 一下,刚刚接到recruiter 电话,拿到onsite了。

评分

3

查看全部评分

 楼主| 西法的洛 发表于 2016-10-19 14:00:52 | 显示全部楼层
youto 发表于 2016-10-19 13:06
能说说是如何压缩的嘛?不太明白,谢谢

1 2 3
4 5 6
7 8 9

3 * 3 matrix, if we compress by rows, then it can be. 1point 3acres 璁哄潧
compress 1 row
1: 1, 2, 3
2: 4, 5, 6
3: 7, 8 ,9

compress 2 rows. from: 1point3acres.com/bbs
1: 5, 7, 9
2: 11, 13, 15

compress 3 rows 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1: 12, 15, 18

For each m * n matrix, if we compress it by rows, it can be compressed by 1 row, 2 rows, 3 rows, ..., m - 1 rows, m rows. That is to say, there are  m + m -1 + m -2 + ... + 2 + 1 = m * (m + 1) / 2 = O(m^2) ways. For each way, we can reuse the linear solution of previous problem. Therefore, the time complexity is O(m ^ 2 * n). Or compressed by columns, it should be O(n ^ 2 * m). It depends which one is smaller...

gei wo dian da mi he rp...

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

iPhD 发表于 2016-10-19 11:02:55 | 显示全部楼层
第一题全是正数吗?不然没法用2 pointers
回复 支持 反对

使用道具 举报

湾区留下来 发表于 2016-10-19 11:26:03 | 显示全部楼层
唉 我第一反应也是 HashTable + 2 pass

第二题我第一反应是没思路 看了楼主写的才想到了暴力的 O(M^2*N^2)  然后又看了楼主的提示才想到可以暴力O(M^2), 然后two pointer  O(N)

下周也要电面了 要跪 要跪啊

楼主比我强太多了 一定会有onsite的!
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-10-19 11:34:55 | 显示全部楼层
求问楼主第二题hint之后的解法,第一题有对input是正数限制么?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-10-19 11:36:43 | 显示全部楼层
写了一下第一题
bool check(vector<int>& nums, int k)
{
        if (nums.empty())return false;
        int sum = 0;
        int j = 0;
        for (int i = 0; i < nums.size(); i++)
        {
                sum += nums[i];
                while (sum > k)
                {
                        if (j == i)break;
                        sum -= nums[j++];
                }. from: 1point3acres.com/bbs
                if (sum == k)return true;
        }
        return false;
.鏈枃鍘熷垱鑷1point3acres璁哄潧}
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 11:39:02 | 显示全部楼层
mingzhou1987 发表于 2016-10-19 11:34
求问楼主第二题hint之后的解法,第一题有对input是正数限制么?

第一个问题 看补充。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二个问题 压缩行或者列。二维变一维。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-10-19 12:27:30 | 显示全部楼层
感觉楼主答得很好啊。。肯定没问题的。
. more info on 1point3acres.com
问一下楼主,第二问的submatrix是怎么定义的?是指压缩成一维后连续的一段,还是二维中连续的一块就行,比如说中间的一小块巨型是submatrix吗?
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 12:58:13 | 显示全部楼层
Mark6 发表于 2016-10-19 12:27
感觉楼主答得很好啊。。肯定没问题的。

问一下楼主,第二问的submatrix是怎么定义的?是指压缩成一维后 ...

1 2 3
4 5 6. From 1point 3acres bbs
7 8 9
10 11 12

4 * 3 矩阵, exist(24) true , 4,5,7,8这个chunk
exist(15) true, 6,9 这个chunk. more info on 1point3acres.com
exist(100) false
exist(24) true, 5, 8, 11这个chunk
回复 支持 反对

使用道具 举报

youto 发表于 2016-10-19 13:06:07 | 显示全部楼层
能说说是如何压缩的嘛?不太明白,谢谢
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-10-19 13:16:00 | 显示全部楼层
西法的洛 发表于 2016-10-19 12:58.鐣欏璁哄潧-涓浜-涓夊垎鍦
1 2 3
4 5 6
7 8 9

很清楚,谢谢楼主!
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-19 13:54:11 | 显示全部楼层
这个不用看了...肯定onsite~~..楼主想好时间飞吧..哈!
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 14:02:14 | 显示全部楼层
leixiang5 发表于 2016-10-19 13:54. From 1point 3acres bbs
这个不用看了...肯定onsite~~..楼主想好时间飞吧..哈!

回复 支持 反对

使用道具 举报

RedAlice 发表于 2016-10-19 14:19:56 | 显示全部楼层
面我的人说一周后给消息 是不是已经挂了
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 14:21:13 | 显示全部楼层
RedAlice 发表于 2016-10-19 14:19
面我的人说一周后给消息 是不是已经挂了
. From 1point 3acres bbs
你问我 我也不知道啊。。。不过不是说fb都很效率的么
回复 支持 反对

使用道具 举报

RedAlice 发表于 2016-10-19 14:30:00 | 显示全部楼层
西法的洛 发表于 2016-10-19 14:21
你问我 我也不知道啊。。。不过不是说fb都很效率的么

我是这样的 第一题hash他说桶不够大 让给时间复杂度 我卡了一下……最后还是说出来了
然后第二题有一个bug和一个多余的操作指出以后改掉了,他是边写边说的最后有个排序的部分他就没让我写
不知道会怎样
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 14:32:06 | 显示全部楼层
RedAlice 发表于 2016-10-19 14:30
我是这样的 第一题hash他说桶不够大 让给时间复杂度 我卡了一下……最后还是说出来了. 鍥磋鎴戜滑@1point 3 acres
然后第二题有一个b ...

具体什么题啊,你什么解法啊。这个你都要说说,这样才能帮你分析。
回复 支持 反对

使用道具 举报

shuangzimian 发表于 2016-10-19 14:41:04 | 显示全部楼层
西法的洛 发表于 2016-10-19 14:00. more info on 1point3acres.com
1 2 3
4 5 6
7 8 9

不知道有没有理解对楼主的方法。
需要O(m^2*n)才能得到所有的compress的可能性,每个都需要O(n)来解决,感觉仍旧是O(m^2*n^2)。
回复 支持 反对

使用道具 举报

 楼主| 西法的洛 发表于 2016-10-19 14:42:23 | 显示全部楼层
shuangzimian 发表于 2016-10-19 14:41
不知道有没有理解对楼主的方法。. From 1point 3acres bbs
需要O(m^2*n)才能得到所有的compress的可能性,每个都需要O(n)来解决, ...

没理解对。

所有的可能性只需O(m ^ 2)
回复 支持 反对

使用道具 举报

lovelyDayDay 发表于 2016-10-19 14:52:45 | 显示全部楼层
第一题是Maximum Size Subarray Sum Equals k简化版,第二题是Range Sum Query 2D啊lz - -!!!!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 05:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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