一亩三分地论坛

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

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

facebook 面经 。。。看似简单的问题没答好

[复制链接] |试试Instant~ |关注本帖
junjunkate 发表于 2015-9-26 05:04:40 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 实习@Facebook - 校园招聘会 - 技术电面 |Other其他

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

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

x
1. project, why facebook2. calculate the dot product of two very large arrays with many 0 elements. Be as efficient as possible
3. ask question. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

感觉面试官放水了。。但是第二题还是答的不好。。。 大家对那个dot product有什么好的solution ?

.1point3acres缃

本帖被以下淘专辑推荐:

jobchaser 发表于 2015-9-26 05:43:18 | 显示全部楼层
求所有Non-zero index的交集?

用hashset O(N) 复杂度
回复 支持 反对

使用道具 举报

jobchaser 发表于 2015-9-26 05:43:26 | 显示全部楼层
求所有Non-zero index的交集?

用hashset O(N) 复杂度

补充内容 (2015-9-26 05:48):
居然发了两遍,见谅。。。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-26 06:36:12 | 显示全部楼层
可以用LinkedList或者hashmap表示array,只考虑非0的
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-9-26 08:46:21 | 显示全部楼层
jobchaser 发表于 2015-9-26 05:43
求所有Non-zero index的交集?

用hashset O(N) 复杂度
. Waral 鍗氬鏈夋洿澶氭枃绔,
能说的具体一点么?这个N是什么?

我的想法是对于A*B, A每行都提取一个hashmap (value -> col),B每列提取HashMap (row -> value),然后对每个A中non-zero的值去B中相乘,复杂度是O(number of non-zero elements in A * row of B)。不过其实也可以是反过来的。. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2015-9-26 08:58):
明白你的意思了 我想错了
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-9-28 01:32:41 | 显示全部楼层
什么是dot product?
回复 支持 反对

使用道具 举报

 楼主| junjunkate 发表于 2015-9-28 11:35:09 | 显示全部楼层
oio14644 发表于 2015-9-28 01:32
什么是dot product?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是指给两个vectors, 例如{0,3,2} 和{1,3,5}。 那么dot product 就是 0*1+3*3+2*5 = 19 。 那么如果每个vector 有millions of elements, 怎样优化 可以让 running time 比 o(n) 小

补充内容 (2015-9-28 11:36):
另外一个特点是 每个vector都有好多0
回复 支持 反对

使用道具 举报

 楼主| junjunkate 发表于 2015-9-28 11:37:43 | 显示全部楼层
wenqiang88 发表于 2015-9-26 06:36
可以用LinkedList或者hashmap表示array,只考虑非0的

但是历遍一次linkedlist 也是O(n) 呀。。如何让他比 o(n) 要小呢
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-28 12:06:55 | 显示全部楼层
junjunkate 发表于 2015-9-28 11:37
但是历遍一次linkedlist 也是O(n) 呀。。如何让他比 o(n) 要小呢

首先是遍历array是必须的,我觉得面试官的意思是如何预处理完array后变得更efficient
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-9-28 12:36:34 | 显示全部楼层
wenqiang88 发表于 2015-9-28 12:06
首先是遍历array是必须的,我觉得面试官的意思是如何预处理完array后变得更efficient

可是遍历的时候不就是可以累加非零项乘积了么?所以这题不是肯定O(N)复杂度嘛?. visit 1point3acres.com for more.
是我理解的有问题吗?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-9-28 12:37:40 | 显示全部楼层
求问楼主,实习对于简历的要求高么?找人内推的话,过简历关难不?谢谢
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-28 19:45:27 | 显示全部楼层
小A要当码农 发表于 2015-9-28 12:36
可是遍历的时候不就是可以累加非零项乘积了么?所以这题不是肯定O(N)复杂度嘛? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
是我理解的有问题吗?

是这个意思
回复 支持 反对

使用道具 举报

354886 发表于 2015-9-28 21:03:16 | 显示全部楼层
感觉是快速傅立叶变换。
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-9-28 21:52:23 | 显示全部楼层
同学面过这个题
A,B化简成list of tuples. visit 1point3acres.com for more.
(non-zero index, non-zero value)
然后two pointer扫就行
这个题应该还有一个follow up是如果A中有10000个non-zero, B中只有100个non-zero,这个时候就是binary search

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

will_ym 发表于 2015-9-29 09:06:06 | 显示全部楼层
kurtwang 发表于 2015-9-28 21:52
同学面过这个题
A,B化简成list of tuples
(non-zero index, non-zero value)

大侠能不能展开说一下啊 不太明白为啥用binary search啊
如果A*B的话 A的tuple可以是(col, row, value) 按照col排序,B可以是(row, col, value)按照排序
我能想到的扫的方法就是把A的每个col=k的tuple和B的每个row=k的tuple都要乘一下
没想出来哪里用binary search啊。。。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-29 10:12:57 | 显示全部楼层
will_ym 发表于 2015-9-29 09:06
大侠能不能展开说一下啊 不太明白为啥用binary search啊
如果A*B的话 A的tuple可以是(col, row, value)  ...

用binary search找一个index是不是也在另一个index里
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-9-29 10:14:18 | 显示全部楼层
will_ym 发表于 2015-9-29 09:06. 鍥磋鎴戜滑@1point 3 acres
大侠能不能展开说一下啊 不太明白为啥用binary search啊
如果A*B的话 A的tuple可以是(col, row, value)  ...

follow up,就是A中的非零比B中的多很多,就现在A中找B[0],找到的话就再从A[index of B[0]:]中找B[1]依次类推
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-29 10:52:14 | 显示全部楼层
小A要当码农 发表于 2015-9-28 12:36
可是遍历的时候不就是可以累加非零项乘积了么?所以这题不是肯定O(N)复杂度嘛?
是我理解的有问题吗?

跟你完全一样的理解。。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
不知诸位所云。。。
回复 支持 反对

使用道具 举报

 楼主| junjunkate 发表于 2015-9-29 20:20:55 | 显示全部楼层
kurtwang 发表于 2015-9-28 21:52
同学面过这个题
A,B化简成list of tuples
(non-zero index, non-zero value)
. Waral 鍗氬鏈夋洿澶氭枃绔,
面试官给我的提示也是这个。。最后我按照这个提示把code写出来了。。。但问题是 简化成 <non-sero index, non-zero value>的过程 也是要o(n)的呀? 那岂不是还不如直接把两个arrays 扫一遍然后两个都非零的项都加起来?所以我当时有点感觉他面的问题有点坑
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-9-29 22:14:05 | 显示全部楼层
junjunkate 发表于 2015-9-29 20:20
面试官给我的提示也是这个。。最后我按照这个提示把code写出来了。。。但问题是 简化成 的过程 也是要o(n ...

请问lz是在给出hashmap的方法后,面试官让优化成binarysearch 的吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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