NYU克朗MIS,18年研二在读体验

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 810|回复: 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硕士+<3个月短暂实习/全职 - 内推|Pittsburgh 码农类General实习@Facebookfresh grad应届毕业生

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

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

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 给你点个赞!

查看全部评分


上一篇:bloomberg on campus面试给了最后一轮但是一直不给确切时间
下一篇:Pinterest VS Airbnb
我的人缘0
太空牛仔 发表于 2018-10-28 02:17:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  54% (109)
 
 
45% (91)  踩
第二题有个很野的做法是二维二分,同时对i 和 j进行二分,需要注意的是在进入左上和右下之前要对当前行当前列进行二分,以免遗漏,时间应该是max(logm, logn) ^2,我自己想出来的,理论上来说应该是最优,可是咋没看到有人用。
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

我的人缘0
TTTynthia 发表于 2018-10-27 02:51:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (64)
 
 
11% (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)   【踩】
全局: 顶  87% (48)
 
 
12% (7)  踩
TTTynthia 发表于 2018-10-26 10:51
为什么这个方法的复杂度是(m+n)啊。。

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

使用道具 举报

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

使用道具 举报

我的人缘0
laura9 发表于 2018-10-27 03:05:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
0% (0)  踩
Barbados 发表于 2018-10-27 02:36
O(m+n)是不是从右上往左下走,每次先往左走,遇到每行最左的1就往下走,遇到有1就拐向左走,然后循环?感觉 ...
. check 1point3acres for more.
我是这么想的,但是面试官好像不认同我的做法
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
laura9 发表于 2018-10-27 03:14:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (29)
 
 
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, 2018-12-12 07:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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