要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
系统
6分钟前
系统
7分钟前
系统
13分钟前
系统
16分钟前
系统
16分钟前
系统
17分钟前
系统
21分钟前
系统
22分钟前
系统
54分钟前
全站
Warald 说: MemorialDay大礼包之七:【新功能】每日答题,答对了有大米奖励!加上每日登陆和每日签到,每天可以拿3颗大米!
55分钟前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】高级模式发帖,图片框里添加“大图片上传”,upto20张X10M
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
1小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之五:【新功能】小喇叭可以点击“发布”,可以在全局、板块或者帖子里发
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
Warald 说: MemorialDay大礼包之四:【新功能】主题列表页显示图片,欢迎上图
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
系统
2小时前
全站
2小时前
系统
2小时前
系统
2小时前
系统
3小时前
系统
3小时前
系统
3小时前
系统
3小时前
全站
Warald 说: MemorialDay大礼包之二:【新功能】论坛开启用户全局威望值,每楼右上方均可投票。
3小时前
全站
Warald 说: MemorialDay大礼包之一:【新功能】发帖后,可以邀请朋友参与讨论(自动功能)
3小时前
查看: 4950|回复: 34
收起左侧

Facebook 二面面经,求bless

[复制链接] |试试Instant~ |关注本帖
我的人缘0
familysize 发表于 2015-12-2 09:42:47 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x

周一刚面了FB二面,感觉不太乐观,不过还没有收到拒信,发个面经求bless吧!
. From 1point 3acres bbs
看名字可能是越南人小哥,英语一般,人也并不是很热情,infrastructure组的,做Messaging
一来先花了过多时间介绍自己的工作,还问我的简历,总共搞了15分钟左右吧,我都虚到时候做不完题
. 围观我们@1point 3 acres
终于开始coding了: 来源一亩.三分地论坛.
两个sparse array A和B,同样长度,里面大部分是0,求所有A*B的sum
当时就震惊了,什么鸟题……花这么多时间刷题…… 来源一亩.三分地论坛.
写完了他说ok,那么你要怎么优化?如果AB很长,而且大部分是0,有效信息只有很小一部分,怎么搞. 1point 3acres 论坛
我说HashMap,他说OK,请implement
写完了他说可不可以再优化,我说可以只loop A,B中最短的这样time已经很不错了

他说好,然后开始说Hashmap的size可能产生问题,我没意识到有什么问题,但他用他有限的英语巴拉巴拉说了一通hashmap有什么问题。
他说你如果不用hashmap那怎么做。那时候时间已经不多了,我墨迹墨迹最后也就提出一个list<list>,但我说这样time不太行,他没有做任何评论。

. 1point 3acres 论坛
然后就随便聊了一下他的工作中的challenge啊之类的。-google 1point3acres
总体来说感觉跪了,希望有什么神一样的转机吧……求bless.留学论坛-一亩-三分地

总体感觉大家除了平时刷题也要多思考吧,而且要对O()非常熟悉,光顾着刷题,遇到这种没有节操的题脑子要做好快速应对的准备。大家加油吧。

这是一面面经. more info on 1point3acres
http://www.1point3acres.com/bbs/thread-148454-1-1.html


补充内容 (2015-12-2 10:05):
哦哦,补充一下,忘了说,他第一个问题问完以后是问我用什么data structure来存这两个array,以便进行同样的Operation。我说的HashMap就是在Key存入array中非零数值的index,而在value存入这个数。

上一篇:FB 二面
下一篇:Uber电面,已跪
我的人缘0
2015fallcser 发表于 2015-12-2 09:48:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
https://leetcode.com/problems/sparse-matrix-multiplication/
这道鸟题 LOL

回复 支持 反对

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-2 09:52:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
2015fallcser 发表于 2015-12-2 09:48
https://leetcode.com/problems/sparse-matrix-multiplication/
这道鸟题 LOL

但这道是matrix,解法相似么?
回复 支持 反对

使用道具 举报

我的人缘0
2015fallcser 发表于 2015-12-2 09:55:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
familysize 发表于 2015-12-2 09:52. 围观我们@1point 3 acres
但这道是matrix,解法相似么?

感觉你面的题目是他的子问题啊  . 一亩-三分-地,独家发布
优化点就在dot product上
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-2 10:02:43 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
2015fallcser 发表于 2015-12-2 09:55
感觉你面的题目是他的子问题啊  
优化点就在dot product上

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

使用道具 举报

我的人缘0
2015fallcser 发表于 2015-12-2 10:31:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
familysize 发表于 2015-12-2 10:02
求指点啊……我说的这两个方法都已经是只存入非零的index和value了,只有双方的index match的时候才做乘 ...
. 牛人云集,一亩三分地
我具体也不知道hashmap的size有啥问题。。。
但是我感觉用个list of tuple啥的就能实现了

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

使用道具 举报

我的人缘0
zjh08177 发表于 2015-12-3 04:03:33 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
求问楼主,这里两个array A B的乘积, A*B 是怎么定义的啊?
A[a1,a2,a3]  B[b1,b2,b3] A*B=[a1b1, a2b2, a3b3] 这样?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-3 04:08:09 来自手机 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
zjh08177 发表于 2015-12-3 04:03. more info on 1point3acres
求问楼主,这里两个array A B的乘积, A*B 是怎么定义的啊?
A[a1,a2,a3]  B A*B=[a1b1, a2b2, a3b3] 这样 ...

只需要把你目前的结果所有数求和就行了哈,return int
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
hyliu0000 发表于 2015-12-3 05:09:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主, 能说说如何用hashmap嘛?  感觉是不是应该用两个list来存所有非0得数字,然后相乘?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-3 06:58:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
hyliu0000 发表于 2015-12-3 05:09
楼主, 能说说如何用hashmap嘛?  感觉是不是应该用两个list来存所有非0得数字,然后相乘?

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

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-3 07:01:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
小A要当码农 发表于 2015-12-3 05:50
请问楼主啊,这题我其实一直感觉没get到点。
面试官要求的是什么呢? . 牛人云集,一亩三分地
我觉得都不用hashMap来存啊,你 ...

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

使用道具 举报

我的人缘0
 楼主| familysize 发表于 2015-12-3 07:02:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
gschengcong 发表于 2015-12-3 06:18
楼主可否把每个array的非零元素都全部弄到最前面来,比如用i++遍历array A,int count = 0, 然后每遇到非零 ...

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

使用道具 举报

我的人缘0
hyliu0000 发表于 2015-12-3 07:37:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
familysize 发表于 2015-12-3 06:58
储存的话一定是只储存非零的数值。但如果要完成相乘的任务的话必须要原来在array中的index匹配才可以,所 ...

楼主,你的意思是只能相同index的elem相乘?. visit 1point3acres for more.
A = [a1, a2, a3] B = [b1, b2, b3];. 一亩-三分-地,独家发布
最后结果是 result = a1*b1 + a2*b2  + a3*b3 ?

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

使用道具 举报

我的人缘0
小A要当码农 发表于 2015-12-3 10:58:43 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
familysize 发表于 2015-12-3 06:58
储存的话一定是只储存非零的数值。但如果要完成相乘的任务的话必须要原来在array中的index匹配才可以,所 ...

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

使用道具 举报

我的人缘0
小A要当码农 发表于 2015-12-3 11:09:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
familysize 发表于 2015-12-3 07:02. 1point3acres
重点应该在multiplication。Index必须匹配才能相乘

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

使用道具 举报

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

使用道具 举报

我的人缘0
小A要当码农 发表于 2015-12-3 11:59:43 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
yjfox 发表于 2015-12-3 11:37
1. 如果是两个一维数组multiple,不需要其他数据结构,对着其中一个扫一遍就行. 留学申请论坛-一亩三分地
2. 如果是matrix,那么需要 ...

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

使用道具 举报

我的人缘0
yjfox 发表于 2015-12-3 12:10:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
小A要当码农 发表于 2015-12-3 11:59
如果是两个matrix,为什么不能也是扫一遍呢?
. Waral 博客有更多文章,
可以直接扫,但是因为很多0,这些计算是没必要的,如果不做处理就无法利用sparse这个特点
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 16:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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