一亩三分地论坛

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

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

Facebook 二面面经,求bless

[复制链接] |试试Instant~ |关注本帖
familysize 发表于 2015-12-2 09:42:47 | 显示全部楼层 |阅读模式

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

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

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

x
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
周一刚面了FB二面,感觉不太乐观,不过还没有收到拒信,发个面经求bless吧!

看名字可能是越南人小哥,英语一般,人也并不是很热情,infrastructure组的,做Messaging. 1point 3acres 璁哄潧
一来先花了过多时间介绍自己的工作,还问我的简历,总共搞了15分钟左右吧,我都虚到时候做不完题

终于开始coding了:
两个sparse array A和B,同样长度,里面大部分是0,求所有A*B的sum
当时就震惊了,什么鸟题……花这么多时间刷题……
写完了他说ok,那么你要怎么优化?如果AB很长,而且大部分是0,有效信息只有很小一部分,怎么搞
我说HashMap,他说OK,请implement 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
写完了他说可不可以再优化,我说可以只loop A,B中最短的这样time已经很不错了

他说好,然后开始说Hashmap的size可能产生问题,我没意识到有什么问题,但他用他有限的英语巴拉巴拉说了一通hashmap有什么问题。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
他说你如果不用hashmap那怎么做。那时候时间已经不多了,我墨迹墨迹最后也就提出一个list<list>,但我说这样time不太行,他没有做任何评论。


然后就随便聊了一下他的工作中的challenge啊之类的。
总体来说感觉跪了,希望有什么神一样的转机吧……求bless

总体感觉大家除了平时刷题也要多思考吧,而且要对O()非常熟悉,光顾着刷题,遇到这种没有节操的题脑子要做好快速应对的准备。大家加油吧。
. 1point 3acres 璁哄潧
这是一面面经
http://www.1point3acres.com/bbs/thread-148454-1-1.html


补充内容 (2015-12-2 10:05):
哦哦,补充一下,忘了说,他第一个问题问完以后是问我用什么data structure来存这两个array,以便进行同样的Operation。我说的HashMap就是在Key存入array中非零数值的index,而在value存入这个数。
2015fallcser 发表于 2015-12-2 09:48:51 | 显示全部楼层
https://leetcode.com/problems/sparse-matrix-multiplication/. visit 1point3acres.com for more.
这道鸟题 LOL. 鍥磋鎴戜滑@1point 3 acres

回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-2 09:52:06 | 显示全部楼层
2015fallcser 发表于 2015-12-2 09:48
https://leetcode.com/problems/sparse-matrix-multiplication/.鐣欏璁哄潧-涓浜-涓夊垎鍦
这道鸟题 LOL
. visit 1point3acres.com for more.
但这道是matrix,解法相似么?
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-12-2 09:55:18 | 显示全部楼层
familysize 发表于 2015-12-2 09:52
但这道是matrix,解法相似么?

感觉你面的题目是他的子问题啊  . from: 1point3acres.com/bbs
优化点就在dot product上
回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-2 10:02:43 | 显示全部楼层
2015fallcser 发表于 2015-12-2 09:55
感觉你面的题目是他的子问题啊  
优化点就在dot product上

求指点啊……我说的这两个方法都已经是只存入非零的index和value了,只有双方的index match的时候才做乘法。
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-12-2 10:31:19 | 显示全部楼层
familysize 发表于 2015-12-2 10:02. 鍥磋鎴戜滑@1point 3 acres
求指点啊……我说的这两个方法都已经是只存入非零的index和value了,只有双方的index match的时候才做乘 ...

我具体也不知道hashmap的size有啥问题。。。
但是我感觉用个list of tuple啥的就能实现了

看了你的补充  我感觉他想问应该是io efficiency之类的 -google 1point3acres
在内存有限的情况下  你可能根本没办法把两个array都搞进来  hashtable更塞不下
所以可能是吧数组做一些拆分  每个array其实都能写好多page
然后再取交集 也就是只留下两边都非0的
回复 支持 反对

使用道具 举报

zjh08177 发表于 2015-12-3 04:03:33 | 显示全部楼层
求问楼主,这里两个array A B的乘积, A*B 是怎么定义的啊?
A[a1,a2,a3]  B[b1,b2,b3] A*B=[a1b1, a2b2, a3b3] 这样?
回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-3 04:08:09 来自手机 | 显示全部楼层
zjh08177 发表于 2015-12-3 04:03
求问楼主,这里两个array A B的乘积, A*B 是怎么定义的啊?. visit 1point3acres.com for more.
A[a1,a2,a3]  B A*B=[a1b1, a2b2, a3b3] 这样 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
只需要把你目前的结果所有数求和就行了哈,return int
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-3 05:09:49 | 显示全部楼层
楼主, 能说说如何用hashmap嘛?  感觉是不是应该用两个list来存所有非0得数字,然后相乘?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 05:50:08 | 显示全部楼层
请问楼主啊,这题我其实一直感觉没get到点。
面试官要求的是什么呢?
我觉得都不用hashMap来存啊,你直接扫一遍较短的那个array,每个非零元素对应的index去另外那个Array里看是否也为非零,如果是就直接加到输出里面,难道不是嘛? interviewer还要求怎么优化呢?
回复 支持 反对

使用道具 举报

gschengcong 发表于 2015-12-3 06:18:45 | 显示全部楼层
楼主可否把每个array的非零元素都全部弄到最前面来,比如用i++遍历array A,int count = 0, 然后每遇到非零元素就执行A[count++] = A[i]; 然后得到Array A和B的分别非零的区间,然后再进行乘操作?

还是重点在乘操作那里,不是很明白。。
回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-3 06:58:09 | 显示全部楼层
hyliu0000 发表于 2015-12-3 05:09. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主, 能说说如何用hashmap嘛?  感觉是不是应该用两个list来存所有非0得数字,然后相乘?

储存的话一定是只储存非零的数值。但如果要完成相乘的任务的话必须要原来在array中的index匹配才可以,所以说只要同时储存数值与其在原array中的index就好了。但hashmap在检测A,B中各个元素是否匹配是最快的,你只需要检验mapA的每一个key是否也存在在B中就行了。
回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-3 07:01:44 | 显示全部楼层
小A要当码农 发表于 2015-12-3 05:50-google 1point3acres
请问楼主啊,这题我其实一直感觉没get到点。
面试官要求的是什么呢?
我觉得都不用hashMap来存啊,你 ...

其实主要目的是完成这个multiplication,最开始的input就是这两个array,但明显这样遍历耗时间。他就说能不能将input用不同的data structure储存,但能够更快的完成同样的multiplication。我觉得他并不需要我们考虑怎么把之前的array变成新的DS。
回复 支持 反对

使用道具 举报

 楼主| familysize 发表于 2015-12-3 07:02:32 | 显示全部楼层
gschengcong 发表于 2015-12-3 06:18
楼主可否把每个array的非零元素都全部弄到最前面来,比如用i++遍历array A,int count = 0, 然后每遇到非零 ...

重点应该在multiplication。Index必须匹配才能相乘
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-3 07:37:57 | 显示全部楼层
familysize 发表于 2015-12-3 06:58
储存的话一定是只储存非零的数值。但如果要完成相乘的任务的话必须要原来在array中的index匹配才可以,所 ...

楼主,你的意思是只能相同index的elem相乘?.鏈枃鍘熷垱鑷1point3acres璁哄潧
A = [a1, a2, a3] B = [b1, b2, b3];
最后结果是 result = a1*b1 + a2*b2  + a3*b3 ?

如果是这样的话, 不是扫一遍就出结果了吗? 还是说我理解错了?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 10:58:43 | 显示全部楼层
familysize 发表于 2015-12-3 06:58
储存的话一定是只储存非零的数值。但如果要完成相乘的任务的话必须要原来在array中的index匹配才可以,所 ...

谢谢楼主解释,可是你就算用HashMap存的话,也得loop一遍吧,这样也是O(N)啊,和Array有什么不同呢?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 11:09:57 | 显示全部楼层
familysize 发表于 2015-12-3 07:02
重点应该在multiplication。Index必须匹配才能相乘

楼主你的意思是用HashMap的Key来存非零元素的Index,Value来存非零元素的值?Interviewer的意思是这一步初始化不算时间损耗?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-3 11:37:53 | 显示全部楼层
1. 如果是两个一维数组multiple,不需要其他数据结构,对着其中一个扫一遍就行
2. 如果是matrix,那么需要搞个Map或者ListofList(这个比较tricky可以理解成ListofTuple)
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 11:59:43 | 显示全部楼层
yjfox 发表于 2015-12-3 11:37
1. 如果是两个一维数组multiple,不需要其他数据结构,对着其中一个扫一遍就行
2. 如果是matrix,那么需要 ...

如果是两个matrix,为什么不能也是扫一遍呢?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-3 12:10:03 | 显示全部楼层
小A要当码农 发表于 2015-12-3 11:59
如果是两个matrix,为什么不能也是扫一遍呢?

可以直接扫,但是因为很多0,这些计算是没必要的,如果不做处理就无法利用sparse这个特点
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 23:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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