一亩三分地论坛

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

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

FaceBook Aug29电话面试

[复制链接] |试试Instant~ |关注本帖
kingsering 发表于 2016-8-30 02:32:01 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
刚电话面试Facebook完毕,电面题目是设计一个data structure来存储spare vector并做dot product。

一开始我的思路是用hashmap, key存index,value存non-zero vector element。乘积的时候,遍历size小的那hashmap的每一个key, 然后查找他的key是否在另一个中能找到,如果找到就做乘积。小哥问了时间复杂度,然后说hashmap在这里会有什么问题,这块儿我没很清楚的回答出来,我的回答大概就是hashing会有overhead。他的意思是hashmap空间上还有多余的overhead。这里不是很明白。。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后问我还有没有别的data structure,然后说可以不考虑乘积的时间复杂度,然后我的solution就是用一个vector<pair<int,int>> pair.first 是index,pair.second是value,做的dot product的时候,因为pair.first是sorted,所以查找可以用二分查找,而且运算的时候,要iterate size小的那个vector<pair<int,int>>,时间复杂度是 O(sizeA*log(sizeB)),(sizeA < sizeB). 同时迅速敲好了binary search的代码以及压缩vector的代码,接着又被问,可不可以再优化时间复杂度,因为时间不多了,面试官说,可以用while loop,然后同时遍历两个vector<pair<int,int>>,如果是交集,就做乘积,否则就continue,这样时间复杂度是O(max(sizeA,sizeB)).因为时间不够,所以没有当场写代码,面试官也说不用写了。现在把代码写一下,代码大概就是:
int i = 0,j = 0;. from: 1point3acres.com/bbs
int sum = 0;
while(i < sizeA && j  < sizeB)
{
      if(A[i].first == B[j].first)  sum +=  A[i].second * B[j].second //do product
      else if(A[i].first < B[j].first) i++;   //因为都是排好序的,所以如果A[i].first小,i往前移动
      else j++;  //同理
}

祝大家面试好运,有如神助。也保佑自己电话面试通过。

评分

2

查看全部评分

gaocan1992 发表于 2016-8-30 02:46:46 | 显示全部楼层
这好像是lc311 Sparse Matrix Multiplication
回复 支持 反对

使用道具 举报

 楼主| kingsering 发表于 2016-8-30 02:52:13 | 显示全部楼层
gaocan1992 发表于 2016-8-30 02:46. Waral 鍗氬鏈夋洿澶氭枃绔,
这好像是lc311 Sparse Matrix Multiplication

相似,但是仔细想想,LC131的核心在于如何order for loop的次序,让运算最快,当然你也可以设计new data structure 去做乘积。但因为是2D的,所以你就不太可能用类似这个面试官说的算法去用two pointer做查找及乘积。
回复 支持 反对

使用道具 举报

hychin 发表于 2016-8-30 03:04:11 | 显示全部楼层
代码没写出来估计悬了
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-8-30 09:05:35 | 显示全部楼层
这是存稀疏矩阵然后做稀疏矩阵间的乘法吗?  如果只是存稀疏向量, 链表不就行了
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-8-30 09:07:56 | 显示全部楼层
我觉得  如果是稀疏矩阵  应该用 链表的链表来存

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sjph 发表于 2016-8-30 11:13:20 | 显示全部楼层
谢谢楼主分享!感觉这道题是空间和时间的取舍,对于java,若能用数组,可以实现二分查找,但消耗空间,若用链表,省空间,但成了线性时间复杂度。
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-8-30 11:21:43 | 显示全部楼层
sjph 发表于 2016-8-29 20:13
谢谢楼主分享!感觉这道题是空间和时间的取舍,对于java,若能用数组,可以实现二分查找,但消耗空间,若用 ...

为什么用链表能省空间呢?不都是要存index和value吗?
回复 支持 反对

使用道具 举报

aboriginal 发表于 2016-8-30 11:38:33 | 显示全部楼层
相当于两个sorted list求交集,如果size差别不大的话,可以用类似merge sort的方法,复杂度O(n +)

补充内容 (2016-8-30 11:39):
O(n + m)
回复 支持 反对

使用道具 举报

 楼主| kingsering 发表于 2016-8-31 05:28:37 | 显示全部楼层
AndrewFish 发表于 2016-8-30 09:05
这是存稀疏矩阵然后做稀疏矩阵间的乘法吗?  如果只是存稀疏向量, 链表不就行了

只是稀疏向量。
回复 支持 反对

使用道具 举报

keepworkinghard 发表于 2016-8-31 05:55:42 | 显示全部楼层
. 1point 3acres 璁哄潧
lz面的是2017 new grad的职位么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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