一亩三分地论坛

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

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

Facebook intern 第一轮电面

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-11-7 09:01:43 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
今天上午面的,发下帖子攒人品,求二面



是一位印度小哥,迟到了十分钟。人很好,我有好几次听不清他的话请他重复,他也没有不耐烦。.1point3acres缃
题目是给两个巨型的向量(矩阵),有很多很多的零,求他们的dot product。
一开始忘了这个概念,他给我举了个例子,就是所有下标相同的元素相乘,最后求和。

这下就明白了,就先遍历两个矩阵,然后保存它们的非零元素,最后找相同的相乘就行了。他问了下我打算怎样储存非零元素,我说把二维坐标转换成一维坐标,然后我就用hash开始写,写了差不多了,他又问不用hash的话怎样储存。我跟他说用arraylist,这样size是changeble的,他对这个很满意,不过还好没让我比较下hash和arraylist。。。接下来他又说,给你两个list,写一下相乘的程序。
我大致写了下,就是以小的list中的元素依次去大的list中去遍历寻找。他问了我下时间复杂度,然后我想了下跟他说可以用binary search 优化,因为list中的一维坐标是递增的,他又问了下复杂度,然后简单说了些关于fb的问题就结束了。

. from: 1point3acres.com/bbs 感觉这次运气真的很好,题不难,而且他也没有让我跑testcase,只是把大体框架都写了。不过感觉电面时真的很紧张,真怕遇到一些偏僻的题脑袋短路。最后希望能有二面

评分

1

查看全部评分

oio14644 发表于 2015-11-7 10:20:39 | 显示全部楼层
他说的是矩阵还是向量,我记得高中数学,只有向量有dot product,而且两个向量是不是默认长度一样?谢谢
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-11-7 10:28:34 | 显示全部楼层
oio14644 发表于 2015-11-7 10:20
他说的是矩阵还是向量,我记得高中数学,只有向量有dot product,而且两个向量是不是默认长度一样?谢谢

一开始说的就是向量dot product,肯定是相等才能进行。后来才说进行两个n*n矩阵相乘的话怎样扩展
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 10:49:13 | 显示全部楼层
You have 2 sparse vectors (large number of 0’s). First tell me a way to represent and store them, and then find the dot product. 你的题是这个吗?
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-11-7 11:05:02 | 显示全部楼层
oio14644 发表于 2015-11-7 10:49
You have 2 sparse vectors (large number of 0’s). First tell me a way to represent and store them, a ...

一开始是只有两个向量,但说了下思路就扩展到很多个向量了,但还是求每两个对应的dot product,这点我也没弄太清楚他什么意思,后来他说直接理解成两个n*n矩阵相乘,下标相同的元素相乘求和,怎样进行。
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 11:14:12 | 显示全部楼层
jy_121 发表于 2015-11-7 11:05
一开始是只有两个向量,但说了下思路就扩展到很多个向量了,但还是求每两个对应的dot product,这点我也 ...

谢谢, 希望你能拿到二面. From 1point 3acres bbs

补充内容 (2015-11-7 11:18): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我跟他说用arraylist,这样size是changeble的; 你指的是 List<List<Integer>> 内层list 放index和value对吗? 这个感觉跟hashmap 非常像了,优势在哪里呢?
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-11-7 11:39:57 | 显示全部楼层
oio14644 发表于 2015-11-7 11:14. 1point3acres.com/bbs
谢谢, 希望你能拿到二面
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-11-7 11:18):
. 1point3acres.com/bbs
List<Integer>,只放index,这个index是由x,y转来的,取值时再转为x,y访问
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 11:52:07 | 显示全部楼层
jy_121 发表于 2015-11-7 11:39
List,只放index,这个index是由x,y转来的,取值时再转为x,y访问

请问怎么从二维x,y转到一个index,有公式吗?谢谢
回复 支持 反对

使用道具 举报

xiaohl0913 发表于 2015-11-7 12:03:28 | 显示全部楼层
Sparse Matrix一般用CSR (Compressed row Storage)存
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-11-7 12:19:53 | 显示全部楼层
oio14644 发表于 2015-11-7 11:52
. from: 1point3acres.com/bbs 请问怎么从二维x,y转到一个index,有公式吗?谢谢
. more info on 1point3acres.com
这看你自己怎么设定了啊,只要还能恢复回去就行。 一般就是 x * 列数 + y, 还原回去对应求商或求余就行了。你把元素都标上号自己算下就知道了。
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-11-7 12:34:20 | 显示全部楼层
jy_121 发表于 2015-11-7 12:19. 鍥磋鎴戜滑@1point 3 acres
这看你自己怎么设定了啊,只要还能恢复回去就行。 一般就是 x * 列数 + y, 还原回去对应求商或求余就行 ...

非常感谢
回复 支持 反对

使用道具 举报

liqingfd 发表于 2015-11-7 13:52:32 | 显示全部楼层
请问你是通过什么渠道申请的fb呀 是内推吗
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-11-7 14:23:54 | 显示全部楼层
liqingfd 发表于 2015-11-7 13:52
请问你是通过什么渠道申请的fb呀 是内推吗

是找人内推的
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-3 16:41:23 | 显示全部楼层
你是1面后挂的么?
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2016-3-4 01:22:00 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-3 16:41
你是1面后挂的么?

2面后挂的
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-4 02:21:32 | 显示全部楼层

http://www.cnblogs.com/jcliBlogger/p/5015959.html. more info on 1point3acres.com
你一面的就是leetcode这道题么
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2016-3-4 02:40:52 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-4 02:21
http://www.cnblogs.com/jcliBlogger/p/5015959.html
你一面的就是leetcode这道题么

先问了稀疏向量点乘,然后问矩阵的follow up。记不太清了,说的是矩阵非常大,不能像这样直接计算,因为内存不够放不下
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-5 17:08:16 | 显示全部楼层
jy_121 发表于 2016-3-4 02:40
先问了稀疏向量点乘,然后问矩阵的follow up。记不太清了,说的是矩阵非常大,不能像这样直接计算,因为 ...

能方便私信下,你2面的题么,非常感谢啊
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2016-3-6 04:07:25 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-5 17:08
能方便私信下,你2面的题么,非常感谢啊

number of islands,Binary Tree Maximum Path Sum
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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