一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 777|回复: 22
收起左侧

脸家面经

[复制链接] |试试Instant~ |关注本帖
e5399014 发表于 2017-12-2 12:39:51 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
11月9号两轮背靠背
第一轮,两个interval array的交集, 先用2 pointer做的,follow up,改binary search,code都写出来了,complexity分析错了,因此导致后面加面。
第二轮,破庙忒神的变种,里口山灵衣,分析分析space和time。
11月17号收到HR回复要加面
12月1号加面一轮.鐣欏璁哄潧-涓浜-涓夊垎鍦
移灵,给一个interval array和一个target interval,求前者覆盖后者最小的区间集,跌跌爬爬经提示写完,估计没戏了。. From 1point 3acres bbs

本帖被以下淘专辑推荐:

dunan00001 发表于 2017-12-2 14:18:18 | 显示全部楼层
加面题 能详细解释下吗?
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-2 14:40:10 | 显示全部楼层
interval你怎么做binary search??
回复 支持 反对

使用道具 举报

get_bits 发表于 2017-12-2 17:18:10 来自手机 | 显示全部楼层
马克一下 谢谢楼主!
回复 支持 反对

使用道具 举报

 楼主| e5399014 发表于 2017-12-3 04:30:17 | 显示全部楼层
dunan00001 发表于 2017-12-2 14:18
加面题 能详细解释下吗?
-google 1point3acres
比如,给[(1,3), (3,5), (3,6),(3,8)] 和 (2, 7), 则输出 [(1,3), (3,8)],基本思路跟里口肆武有点像
回复 支持 反对

使用道具 举报

 楼主| e5399014 发表于 2017-12-3 04:33:44 | 显示全部楼层
hychin 发表于 2017-12-2 14:40
interval你怎么做binary search??

follow up是一个array小另一个很大,那么就scan小的array,然后在大的里二分查找interval start,找到了再求交集
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-3 06:23:34 | 显示全部楼层
e5399014 发表于 2017-12-3 04:33
follow up是一个array小另一个很大,那么就scan小的array,然后在大的里二分查找interval start,找到了 ...

这个最坏的复杂度还是O(m+n)吧,比如[1,2] [2,3],[3,4],[4,5] 另外一个[1,5],cover住A里面所有的,那你还是要A走一遍啊
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-3 06:24:52 | 显示全部楼层
对了,另外这个interval array每一个内部是不overlap并且sort的吗?
回复 支持 反对

使用道具 举报

 楼主| e5399014 发表于 2017-12-3 10:48:22 | 显示全部楼层
hychin 发表于 2017-12-3 06:23
这个最坏的复杂度还是O(m+n)吧,比如[1,2] [2,3],[3,4],[4,5] 另外一个[1,5],cover住A里面所有的,那 ...

你是对的,我当时举了这个例子之后,脑子打岔,说复杂度是O(mn)了。。。
回复 支持 反对

使用道具 举报

 楼主| e5399014 发表于 2017-12-3 10:48:42 | 显示全部楼层
hychin 发表于 2017-12-3 06:24
对了,另外这个interval array每一个内部是不overlap并且sort的吗?

sort,但是可能有overlap
回复 支持 反对

使用道具 举报

douch 发表于 前天 06:20 | 显示全部楼层
lz好人啊 不过第二轮 “破庙忒神的变种” 是什么东东?
回复 支持 反对

使用道具 举报

iwantanintern 发表于 前天 06:49 | 显示全部楼层
为什么输出[(1,3) (3,8)]啊
回复 支持 反对

使用道具 举报

goshining 发表于 前天 06:59 | 显示全部楼层
douch 发表于 2017-12-13 06:20
lz好人啊 不过第二轮 “破庙忒神的变种” 是什么东东?

里特口 思诗留吧 字数字数
回复 支持 反对

使用道具 举报

douch 发表于 前天 07:03 | 显示全部楼层
goshining 发表于 2017-12-13 06:59
里特口 思诗留吧 字数字数

哥们谢谢啦 难怪人说来这里才知道自己中文不行 😄
回复 支持 反对

使用道具 举报

douch 发表于 前天 07:08 | 显示全部楼层
第一轮的交集的, 比如在list1 有个interval [1, 4], list2中有个interval [2, 5]交集是[2, 4]?
回复 支持 反对

使用道具 举报

iwantanintern 发表于 前天 07:56 | 显示全部楼层
iwantanintern 发表于 2017-12-13 06:49
为什么输出[(1,3) (3,8)]啊
.鏈枃鍘熷垱鑷1point3acres璁哄潧
啊不好意思没看到这是加面题
回复 支持 反对

使用道具 举报

iwantanintern 发表于 前天 08:08 | 显示全部楼层

比如list1有[(1,6),(2,7)], list2 [(2,4) (3,9)] 这种情况return什么呢??很confused
还有intersection的定义 是必需大的包小的比如 [1,8] [4,6] 还是 [1,6] [4,8] return [4,6]?. more info on 1point3acres.com
非常感谢楼主的分享!
回复 支持 反对

使用道具 举报

iwantanintern 发表于 前天 08:09 | 显示全部楼层
如果一个array可以有overlap  那就既要inter-array search又要intra-array search?
回复 支持 反对

使用道具 举报

iwantanintern 发表于 前天 08:37 | 显示全部楼层
hychin 发表于 2017-12-3 06:23. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个最坏的复杂度还是O(m+n)吧,比如[1,2] [2,3],[3,4],[4,5] 另外一个[1,5],cover住A里面所有的,那 ...

可以解释下为啥是m+n不是mn吗
回复 支持 反对

使用道具 举报

dajianshi23 发表于 前天 09:06 | 显示全部楼层
请问,破庙忒神 是什么意思?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-15 14:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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