入职后感觉很空虚

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2566|回复: 20
收起左侧

脸书电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
multicia 发表于 2017-9-16 06:19:55 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩

2017(7-9月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | fresh 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):. Waral 博客有更多文章,
拿到onsite,感谢国人大哥。加面就一道题, 给了一个n*n的矩阵,每一行都是排序的,但列不是,求中位数。拿到题也是很懵,列不是排序并不知道怎么二分,大家有好的想法吗

评分

参与人数 3大米 +11 收起 理由
lalasparrow + 5 感谢分享!
edyyy + 3 感谢分享!
ojjccc + 3 感谢分享!

查看全部评分


上一篇:亚麻新鲜面经,两个小时前刚面完
下一篇:画桥第一轮店面

本帖被以下淘专辑推荐:

我的人缘0
siranjoy119 发表于 2017-10-31 11:00:18 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  93% (76)
 
 
6% (5)  踩
http://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/
回复

使用道具 举报

我的人缘0
 楼主| multicia 发表于 2017-10-9 12:16:22 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
AnthonyNeu 发表于 2017-10-9 10:57
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。

之后就可以不断的从堆pop,然 ...
. 一亩-三分-地,独家发布
我电面时写的是这一种解法,这样space是O(n), 不知道这道题考点是不是在于空间复杂度。把整个矩阵排序的话也是n^2 lgn, 不过存数组需要n^2 的space。
回复

使用道具 举报

我的人缘0
ojjccc 发表于 2017-9-16 06:39:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
158有哪些test case啊!一直都没看懂158和157想干嘛
回复

使用道具 举报

我的人缘0
 楼主| multicia 发表于 2017-9-16 06:49:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
ojjccc 发表于 2017-9-16 06:39
158有哪些test case啊!一直都没看懂158和157想干嘛

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

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-9-16 09:16:00 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (100)
 
 
13% (16)  踩
楼主是哪个case没想到?
回复

使用道具 举报

我的人缘0
 楼主| multicia 发表于 2017-9-16 10:42:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
cutehuazai 发表于 2017-9-16 09:16.1point3acres网
楼主是哪个case没想到?

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

使用道具 举报

我的人缘0
AnthonyNeu 发表于 2017-10-9 10:57:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (79)
 
 
1% (1)  踩
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。

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

补充内容 (2017-10-9 10:57):. visit 1point3acres for more.
不是每一列的开头,是每一行的开头
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
lalasparrow 发表于 2017-10-9 11:36:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (36)
 
 
2% (1)  踩
AnthonyNeu 发表于 2017-10-9 10:57
只想到一个n^2 log n的方法,大致就是把每一列的开头放到一个最小堆里面。
. visit 1point3acres for more.
之后就可以不断的从堆pop,然 ...
.1point3acres网
感觉是不是可以在pop出来的那个点的同一行binary search,搜索堆现在peek的元素,这样是不是能省一些时间?
回复

使用道具 举报

我的人缘0
AnthonyNeu 发表于 2017-10-9 11:54:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (79)
 
 
1% (1)  踩
lalasparrow 发表于 2017-10-9 11:36
感觉是不是可以在pop出来的那个点的同一行binary search,搜索堆现在peek的元素,这样是不是能省一些时间 ...

这样可以快一点,最好的话可以直接log n到这一行的结束,最坏是n log n
回复

使用道具 举报

我的人缘0
lalasparrow 发表于 2017-10-9 12:28:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (36)
 
 
2% (1)  踩
AnthonyNeu 发表于 2017-10-9 11:54
这样可以快一点,最好的话可以直接log n到这一行的结束,最坏是n log n

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

使用道具 举报

我的人缘0
jisong_L 发表于 2017-10-13 08:16:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (134)
 
 
5% (8)  踩
如果有 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):
次选出一个数后对每个列进行二分查找 -> 次选出一个数后对每个行进行二分查找
回复

使用道具 举报

我的人缘0
yanchao 发表于 2017-10-30 13:00:55 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (41)
 
 
4% (2)  踩
jisong_L 发表于 2017-10-13 08:16
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left,最大的为right,然后每次求mid = (right + l ...
-google 1point3acres
为什么第二种方式就能缩小范围?不是很明白,可以详细讲解一下吗?
回复

使用道具 举报

我的人缘0
fredxue 发表于 2017-10-31 03:07:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (9)
 
 
18% (2)  踩
jisong_L 发表于 2017-10-13 08:16. 1point3acres
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left,最大的为right,然后每次求mid = (right + l ...

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

使用道具 举报

我的人缘0
jisong_L 发表于 2017-10-31 13:02:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (134)
 
 
5% (8)  踩
fredxue 发表于 2017-10-31 03:07
列没排序,怎么对列二分?
. 牛人云集,一亩三分地
每次选出一个数后对每个列进行二分查找,找到比它小的数目,这样一次是 K*logN 改成
每次选出一个数后对每个行进行二分查找,找到比它小的数目,这样一次是 K*logN。
回复

使用道具 举报

我的人缘0
jisong_L 发表于 2017-10-31 13:05:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (134)
 
 
5% (8)  踩
yanchao 发表于 2017-10-30 13:00.本文原创自1point3acres论坛
为什么第二种方式就能缩小范围?不是很明白,可以详细讲解一下吗?

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

使用道具 举报

我的人缘0
yanchao 发表于 2017-10-31 23:12:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (41)
 
 
4% (2)  踩
jisong_L 发表于 2017-10-31 13:05
因为第二种方法起始的right - lef的值t比第一种方法小,这样就会快些了。

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

使用道具 举报

我的人缘0
jisong_L 发表于 2017-11-1 10:22:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (134)
 
 
5% (8)  踩
yanchao 发表于 2017-10-31 23:12
我就是问第二种方法的right - left为什么会小。假如每一行都是一样,长度比较长,一样的话第二种方法的ri ...

You are right. It's up to the inputs.
回复

使用道具 举报

我的人缘0
adrianliu729 发表于 2017-11-5 11:38:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (176)
 
 
11% (23)  踩
这题n*n是偶数的话应该返回什么为median?
回复

使用道具 举报

我的人缘0
iwantanintern 发表于 2017-11-5 12:30:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  73% (53)
 
 
26% (19)  踩
158真的是很奇怪的一道题
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-19 15:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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