《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

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

脸书电面

[复制链接] |试试Instant~ |关注本帖
multicia 发表于 2017-9-16 06:19:55 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚结束电面,两道原题,印度小哥,口音并不重,自我介绍聊项目15分钟,第二题写完后一直在问test case,并让手动模拟,有个test case没想到,但代码没问题,不知道会不会受影响,最后面了55分种。

1 325,只需判断有没有
2 158

求昂赛!


补充内容 (2017-9-16 10:43):
recruiter说要再约时间加面。。。

补充内容 (2017-10-8 23:18):. 鍥磋鎴戜滑@1point 3 acres
拿到onsite,感谢国人大哥。加面就一道题, 给了一个n*n的矩阵,每一行都是排序的,但列不是,求中位数。拿到题也是很懵,列不是排序并不知道怎么二分,大家有好的想法吗

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| multicia 发表于 2017-10-9 12:16:22 | 显示全部楼层
AnthonyNeu 发表于 2017-10-9 10:57. visit 1point3acres.com for more.
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。

之后就可以不断的从堆pop,然 ...

我电面时写的是这一种解法,这样space是O(n), 不知道这道题考点是不是在于空间复杂度。把整个矩阵排序的话也是n^2 lgn, 不过存数组需要n^2 的space。
回复 支持 1 反对 0

使用道具 举报

ojjccc 发表于 2017-9-16 06:39:35 | 显示全部楼层
158有哪些test case啊!一直都没看懂158和157想干嘛
回复 支持 反对

使用道具 举报

 楼主| multicia 发表于 2017-9-16 06:49:05 | 显示全部楼层
ojjccc 发表于 2017-9-16 06:39
158有哪些test case啊!一直都没看懂158和157想干嘛

158要保留上次调用后剩余的cache, 调用时要先读cache里的数据。test case就是多考虑文件读完之后的情况就OK了
回复 支持 反对

使用道具 举报

cutehuazai 发表于 2017-9-16 09:16:00 来自手机 | 显示全部楼层
楼主是哪个case没想到?
回复 支持 反对

使用道具 举报

 楼主| multicia 发表于 2017-9-16 10:42:17 | 显示全部楼层
cutehuazai 发表于 2017-9-16 09:16
楼主是哪个case没想到?

其实就是一个很普通的case,比如file 是2,read(4) 返回2就OK的,我之前给他了一个连续call几次然后最后返回一个小于文件size的例子,并没意识到这个,当时也是脑抽
回复 支持 反对

使用道具 举报

AnthonyNeu 发表于 2017-10-9 10:57:14 | 显示全部楼层
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。

之后就可以不断的从堆pop,然后把pop出来的那个点的同一行下一个放入堆里面,直到pop出n^2 / 2个元素就是中位数了。

补充内容 (2017-10-9 10:57):
不是每一列的开头,是每一行的开头
回复 支持 反对

使用道具 举报

lalasparrow 发表于 2017-10-9 11:36:15 | 显示全部楼层
AnthonyNeu 发表于 2017-10-9 10:57
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。

之后就可以不断的从堆pop,然 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉是不是可以在pop出来的那个点的同一行binary search,搜索堆现在peek的元素,这样是不是能省一些时间?
回复 支持 反对

使用道具 举报

AnthonyNeu 发表于 2017-10-9 11:54:24 | 显示全部楼层
lalasparrow 发表于 2017-10-9 11:36. 1point3acres.com/bbs
感觉是不是可以在pop出来的那个点的同一行binary search,搜索堆现在peek的元素,这样是不是能省一些时间 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这样可以快一点,最好的话可以直接log n到这一行的结束,最坏是n log n
回复 支持 反对

使用道具 举报

lalasparrow 发表于 2017-10-9 12:28:36 | 显示全部楼层
AnthonyNeu 发表于 2017-10-9 11:54. From 1point 3acres bbs
这样可以快一点,最好的话可以直接log n到这一行的结束,最坏是n log n

最好的话n/2 *logn,最差是n/2 * nlogn ???
不知道这样算对不对..
回复 支持 反对

使用道具 举报

jisong_L 发表于 2017-10-13 08:16:19 | 显示全部楼层
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left,最大的为right,然后每次求mid = (right + left) /  进行二分搜索。一共要进行log(right - left) 次。每次选出一个数后对每个列进行二分查找,找到比它小的数目,这样一次是 K*logN, 所以一共是 K*logN*log(right - left).
进一步想缩小开始选取的left和right的话,把每个行看成由[start, end]的interval。按照扫描线,先从左往右,只关心end的点,扫到 k/2 + 1个end的点结束,这个是搜索的上界(right)。然后从右往左,只关心start的点,扫到第k/2 + 1个start的点结束,这是搜索的下届(left

补充内容 (2017-10-13 08:17):
次选出一个数后对每个列进行二分查找 -> 次选出一个数后对每个行进行二分查找
回复 支持 反对

使用道具 举报

yanchao 发表于 2017-10-30 13:00:55 来自手机 | 显示全部楼层
jisong_L 发表于 2017-10-13 08:16
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left,最大的为right,然后每次求mid = (right + l ...

为什么第二种方式就能缩小范围?不是很明白,可以详细讲解一下吗?
回复 支持 反对

使用道具 举报

fredxue 发表于 2017-10-31 03:07:52 | 显示全部楼层
jisong_L 发表于 2017-10-13 08:16
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left,最大的为right,然后每次求mid = (right + l ...

列没排序,怎么对列二分?
回复 支持 反对

使用道具 举报

siranjoy119 发表于 2017-10-31 11:00:18 | 显示全部楼层
http://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/
回复 支持 反对

使用道具 举报

jisong_L 发表于 2017-10-31 13:02:23 | 显示全部楼层
fredxue 发表于 2017-10-31 03:07. Waral 鍗氬鏈夋洿澶氭枃绔,
列没排序,怎么对列二分?

每次选出一个数后对每个列进行二分查找,找到比它小的数目,这样一次是 K*logN 改成 .1point3acres缃
每次选出一个数后对每个行进行二分查找,找到比它小的数目,这样一次是 K*logN。
回复 支持 反对

使用道具 举报

jisong_L 发表于 2017-10-31 13:05:47 | 显示全部楼层
yanchao 发表于 2017-10-30 13:00
为什么第二种方式就能缩小范围?不是很明白,可以详细讲解一下吗?

因为第二种方法起始的right - lef的值t比第一种方法小,这样就会快些了。
回复 支持 反对

使用道具 举报

yanchao 发表于 2017-10-31 23:12:44 | 显示全部楼层
jisong_L 发表于 2017-10-31 13:05
因为第二种方法起始的right - lef的值t比第一种方法小,这样就会快些了。

我就是问第二种方法的right - left为什么会小。假如每一行都是一样,长度比较长,一样的话第二种方法的right-left就比较大了啊。
回复 支持 反对

使用道具 举报

jisong_L 发表于 2017-11-1 10:22:36 | 显示全部楼层
yanchao 发表于 2017-10-31 23:12
我就是问第二种方法的right - left为什么会小。假如每一行都是一样,长度比较长,一样的话第二种方法的ri ...

You are right. It's up to the inputs.
回复 支持 反对

使用道具 举报

adrianliu729 发表于 2017-11-5 11:38:59 | 显示全部楼层
这题n*n是偶数的话应该返回什么为median?
回复 支持 反对

使用道具 举报

iwantanintern 发表于 2017-11-5 12:30:22 | 显示全部楼层
158真的是很奇怪的一道题
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 19:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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