要不要加入一亩三分地团队,和我们一起开发app和网站?
一亩三分地招summer intern

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

瞄准秋招
跟Shawn一起刷算法题

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 1126|回复: 18
收起左侧

[找工就业] 新鲜脸熟2面

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
ZealOt_zzz 发表于 2018-10-27 02:00:54 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩

2019(7-9月)-[18]CS硕士+< - 内推|Pittsburgh 码农类General实习@Facebookfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
这周二面的实习第二轮,放上来攒人品,求fb抬一手啊。。。

[hide=130
第一题,很简单,给一串航班的起点和终点,按顺序输出所有的航班。比如说[[北京,广州],[上海,北京],[深圳,上海]],要求输出[[深圳,上海],[上海,北京],[北京,广州]],直接拿哈希表存下来,然后找只有一个出度的点,顺着遍历就行了。
第二题,一个01矩阵,每一行所有的0在前,1在后,要求给出矩阵中最左边的1所在的列id。我先给了一种O(m logn)的方法,面试官说我这个方法在n大的时候可以,然后直接告诉我了O(m+n)的方法让我实现,不知道算不算黑点。[/hide]


评分

参与人数 4大米 +15 收起 理由
zjunnju + 3 给你点个赞!
fancz2002 + 5 欢迎来一亩三分地论坛!
kywang + 3 给你点个赞!
艾利克斯 + 4 给你点个赞!

查看全部评分


上一篇:求一个职位介绍FB - Data Scientist, Infrastructure Data Center - Intern
下一篇:Pinterest VS Airbnb
我的人缘0
太空牛仔 发表于 2018-10-28 02:17:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  78% (630)
 
 
21% (176)  踩
第二题有个很野的做法是二维二分,同时对i 和 j进行二分,需要注意的是在进入左上和右下之前要对当前行当前列进行二分,以免遗漏,时间应该是max(logm, logn) ^2,我自己想出来的,理论上来说应该是最优,可是咋没看到有人用。
回复

使用道具 举报

我的人缘0
艾利克斯 发表于 2018-10-27 02:28:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (30)
 
 
6% (2)  踩
第二题是对每一行做二分搜索吗?那面试官说的O(m+n)的方法思路是怎么样的啊?
回复

使用道具 举报

我的人缘0
Barbados 发表于 2018-10-27 02:36:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (63)
 
 
10% (7)  踩
O(m+n)是不是从右上往左下走,每次先往左走,遇到每行最左的1就往下走,遇到有1就拐向左走,然后循环?感觉不算是黑点,二分和这种各有优势。
回复

使用道具 举报

我的人缘0
gundamkeroro 发表于 2018-10-27 02:43:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (154)
 
 
10% (18)  踩
第二题lc上面一道题的马甲题 道理是一样在 左上走到右下
回复

使用道具 举报

我的人缘0
TTTynthia 发表于 2018-10-27 02:51:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (90)
 
 
8% (8)  踩
Barbados 发表于 2018-10-27 02:36
O(m+n)是不是从右上往左下走,每次先往左走,遇到每行最左的1就往下走,遇到有1就拐向左走,然后循环?感觉 ...

为什么这个方法的复杂度是(m+n)啊。。
回复

使用道具 举报

我的人缘0
Barbados 发表于 2018-10-27 02:56:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (63)
 
 
10% (7)  踩
TTTynthia 发表于 2018-10-26 10:51
为什么这个方法的复杂度是(m+n)啊。。

因为就是走了一个矩阵的长加宽的距离
回复

使用道具 举报

我的人缘0
laura9 发表于 2018-10-27 03:04:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (43)
 
 
0% (0)  踩
同第二题,没告诉我方法让我实现O(m+n)
回复

使用道具 举报

我的人缘0
laura9 发表于 2018-10-27 03:05:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (43)
 
 
0% (0)  踩
Barbados 发表于 2018-10-27 02:36
O(m+n)是不是从右上往左下走,每次先往左走,遇到每行最左的1就往下走,遇到有1就拐向左走,然后循环?感觉 ...

我是这么想的,但是面试官好像不认同我的做法
回复

使用道具 举报

我的人缘0
Barbados 发表于 2018-10-27 03:11:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (63)
 
 
10% (7)  踩
laura9 发表于 2018-10-26 11:05. check 1point3acres for more.
我是这么想的,但是面试官好像不认同我的做法

要讲清楚吧, 每次要往下拐前就是代表当前所在行是返回结果,往下走如果遇到0,说明此行的1在后面,此行一定不是返回结果,要排除。当遇到1的时候,说明此行的1有可能会更左边,返回结果更新至此行,由此循环直到边界。
回复

使用道具 举报

我的人缘0
laura9 发表于 2018-10-27 03:14:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (43)
 
 
0% (0)  踩
Barbados 发表于 2018-10-27 03:11
要讲清楚吧, 每次要往下拐前就是代表当前所在行是返回结果,往下走如果遇到0,说明此行的1在后面,此行 ...

我是这么说的 当前行找到的leftmost index,下一行从index - 1的地方从右往左找1,不是1就continue
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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

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

手机版|小黑屋|一亩三分地

GMT+8, 2019-5-26 12:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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