一亩三分地论坛

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

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

Facebook Fulltime电面

[复制链接] |试试Instant~ |关注本帖
StellaJiang 发表于 2016-8-19 03:44:24 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
朋友内推,10天后收到8.18号的面试安排面试小哥上来先介绍了一下自己,在messenger工作了2年半,然后转组开始做product framework(没听清具体在那个组)。
然后让我做自我介绍。
跟着做了三道题,最后让我问问题。前两题都是leetcode.

1. First Bad Version. leetcode 278. 问了时间空间复杂度

2. Valid Palindrome. leetcode 125. 问了时间空间复杂度。这题要求要in-place, 然后输入是char[],不过做法跟leetcode一样。做这题居然忘记了Character.toLowerCase()这个method。小哥人很好的提醒了一下。
3. Dot Product.
   A={a1, a2, a3,...}
   B={b1, b2, b3,...}
   dot_product = a1 * b1 + a2 * b2 + a3 * b3 +。。。
   如果数组很稀疏,例如. 1point 3acres 璁哄潧
   A={a1, ...., a300, ...., a5000}
   B={...., b100, ..., b300, ..., b1000, ...}. 1point 3acres 璁哄潧
  里面有很多0,用什么数据结构表示能节省空间。我开始说用hashmap,但是hashmap不能做有顺序的iteration。然后改用list和array,两个都可以。后面做题的时用的array。
  题目是:. From 1point 3acres bbs
  input A=[[1, a1], [300, a300], [5000, a5000]]
          B=[[100, b100], [300, b300], [1000, b1000]]. 鍥磋鎴戜滑@1point 3 acres
  求 dot product. 问了时间复杂度。
  Follow up:
  如果length(B) >>> length(A),即B非常长,怎么做能减少时间复杂度。对A里面的每个数,用binary search找B中相对应的值,这样时间复杂度是O(nlogm) (n = len(A), m =len(B)).时间不够没写代码, 就说了一下思路和复杂度。
   



补充内容 (2016-8-19 06:24):
第三题的输入就是稀疏数组的非0的数列出来了,A=[[1, a1], [300, a300], [5000, a5000]]的意思就是A中第1个数是a1,第300个是a300,第5000个是a5000,其他都是0.
-google 1point3acres
补充内容 (2016-8-23 06:06):
上周四的店面,今天拿到onsite通知

评分

2

查看全部评分

iPhD 发表于 2016-8-19 04:54:29 | 显示全部楼层
第3题的input那个形式什么意思?[1, a1], ... 输入是这种形式的?就把数组A遍历一遍,然后对于每个A里有的index,去B里binary search一遍?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-8-19 05:12:35 | 显示全部楼层
这个follow up有点奇怪啊,如果b比a长,算a和b的点乘, 不是只要在b上截取a的长度做点乘吗?
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-8-19 06:08:48 | 显示全部楼层
wtcupup 发表于 2016-8-19 05:12
这个follow up有点奇怪啊,如果b比a长,算a和b的点乘, 不是只要在b上截取a的长度做点乘吗?

应该是长度一样,但是A比B稀疏很多,input A和B是只有非0元素的一个list或者array。。
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-19 06:20:42 | 显示全部楼层
iPhD 发表于 2016-8-19 04:54. Waral 鍗氬鏈夋洿澶氭枃绔,
第3题的input那个形式什么意思?[1, a1], ... 输入是这种形式的?就把数组A遍历一遍,然后对于每个A里有的i ...
.1point3acres缃
1是index, a1是那个位置上的val
回复 支持 反对

使用道具 举报

whisperty 发表于 2016-8-19 06:44:26 | 显示全部楼层
wtcupup 发表于 2016-8-19 05:12
这个follow up有点奇怪啊,如果b比a长,算a和b的点乘, 不是只要在b上截取a的长度做点乘吗?

我觉得楼主说的是如果b中的非0位置比a多很多。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-19 11:39:11 | 显示全部楼层
你人品真好 全是原题最后一个也是面经的题
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-19 12:21:29 | 显示全部楼层
zyoppy008 发表于 2016-8-19 11:39
你人品真好 全是原题最后一个也是面经的题

运气确实不错,他出完这三道题后,我自己也被震惊了。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-19 12:45:29 | 显示全部楼层
StellaJiang 发表于 2016-8-19 12:21
运气确实不错,他出完这三道题后,我自己也被震惊了。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我今天才面的 两轮完全没见过的题
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-19 12:48:16 | 显示全部楼层
zyoppy008 发表于 2016-8-19 12:45
我今天才面的 两轮完全没见过的题

运气什么的果然重要啊。我也是今天面的,那你面的如何?
回复 支持 反对

使用道具 举报

zzh730 发表于 2016-8-19 12:50:02 | 显示全部楼层
sparse vector prodcut为什么不能用hashtable, 反正是求product,顺序无所谓啊
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-19 12:54:51 | 显示全部楼层
zzh730 发表于 2016-8-19 12:50
sparse vector prodcut为什么不能用hashtable, 反正是求product,顺序无所谓啊

我也觉得可以,但是面试小哥要一个可以顺序的iterative的,其实我觉得他只是为了要引出后面题目中input的结构。所以面试官是老大,他说不想要你只能想出另外一个来回答他。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-19 13:02:07 | 显示全部楼层
StellaJiang 发表于 2016-8-19 12:48
运气什么的果然重要啊。我也是今天面的,那你面的如何?

跪了,第二道题写了挺久的,最后写出来,结果不是最优,而且事后一想有bug
回复 支持 反对

使用道具 举报

zzh730 发表于 2016-8-19 13:06:54 | 显示全部楼层
StellaJiang 发表于 2016-8-19 12:54
我也觉得可以,但是面试小哥要一个可以顺序的iterative的,其实我觉得他只是为了要引出后面题目中input的 ...

哈哈楼主说的是,面试官必须是大爷
回复 支持 反对

使用道具 举报

wujingzhishui 发表于 2016-8-19 15:39:58 | 显示全部楼层
楼主自我介绍说的什么啊  new grad 感觉没太多可以展现的
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-20 05:11:56 | 显示全部楼层
wujingzhishui 发表于 2016-8-19 15:39
楼主自我介绍说的什么啊  new grad 感觉没太多可以展现的

就简单介绍了一下自己,然后说了一下实习时候做的项目,感觉面试官也没有期待你会说很多,说了两三分钟就开始做题了
回复 支持 反对

使用道具 举报

 楼主| StellaJiang 发表于 2016-8-20 05:15:38 | 显示全部楼层
zyoppy008 发表于 2016-8-19 13:02. more info on 1point3acres.com
跪了,第二道题写了挺久的,最后写出来,结果不是最优,而且事后一想有bug

pat pat。还有很多好公司等着你呢。不过你怎么能这么快知道自己挂了,不是才面完吗?我都还没有收到任何后续消息。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-20 05:28:08 | 显示全部楼层
StellaJiang 发表于 2016-8-20 05:15. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
pat pat。还有很多好公司等着你呢。不过你怎么能这么快知道自己挂了,不是才面完吗?我都还没有收到任何 ...

刚面完,5个小时之后就通知了
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-8-25 13:28:27 | 显示全部楼层
StellaJiang 发表于 2016-8-19 12:48
运气什么的果然重要啊。我也是今天面的,那你面的如何?

运气确实重要,还有女生一般会稍微照顾一点,当然这也是应该的
回复 支持 反对

使用道具 举报

stephaniede 发表于 2016-8-26 04:13:09 | 显示全部楼层
用Treemap也可以实现。建一个sparse vector class,遇到value是0的不要insert,不是0的value insert进去treemap, insert和get复杂度是log(n),treemap是有排序的,所以可以顺序loop key。followup的问题和使用binary tree 找到B里A对应的index值, 时间度一样,空间度是o(k),k是A和B里所有有效不为0的值。

祝LZ onsite顺利!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-8-25 13:14):
第三题是哪里的原题? 求解。。 我也就想到treemap和lz的binary search方法。有更好的吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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