来八一下卖力IT部门

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1399|回复: 26
收起左侧

骨骼店面面经顺便问一下约昂赛

[复制链接] |试试Instant~ |关注本帖
我的人缘0
siy 发表于 2017-12-6 03:16:06 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (49)
 
 
2% (1)  踩

2017(10-12月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Pass | fresh grad应届毕业生

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

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

x
第一次发帖,贡献个面经。

点面一道题,给一个矩阵里面有0和1, 问判断是否以1为四个角能组成rectangle。返回是否即可。

给了n^2m^2暴力解和nm^2的set解法。. 围观我们@1point 3 acres

写了第二个的code,我是自定义了一个class, 这样在用set的时候要自己写equal和hashCode。sb了纠结了一会才给弄出来。店面完了才意识到可以用HashMap<Integer, HashSet<Integer>>这样存就可以。好在给过了。

顺便问一下从hr通知过了到约onsite一般是多久。。。hr把我转给了一个recruiter,我等了一个星期多了这个recruiter也不理我,发邮件骚扰也不理。。。
. 围观我们@1point 3 acres
谢谢大家了


补充内容 (2017-12-8 05:03):
不好意思忘记说了,当时还特意问了一下面试官,面试官意思是只需要考虑以行或列为边的矩形

评分

参与人数 2大米 +6 收起 理由
TingDallas + 3 很有用的信息!
codingsapien + 3 很有用的信息!

查看全部评分


上一篇:巨硬面经和时间线
下一篇:Qualtrics最后一轮
我的人缘0
HOMIE 发表于 2017-12-6 14:53:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (2)   【踩】
全局: 顶  50% (2)
 
 
50% (2)  踩
如果输入矩阵里只有0和1,那么通过对任意两行相加,如果得到的数组含有两个2,是否能证明矩形存在呢?时间复杂度是n^2 或 m^2。

补充内容 (2017-12-6 14:56):
1 0 1 1
1 1 1 0
0 0 1 1
通过对第一行和第二行进行相加,得到2 1 2 1.那么说明[0,0] [0,2] [1,0] [1,2]这四个点可以组成矩形。
只想到几个test case,不知道这个方法有没有bug。。大家可以讨论下。
回复

使用道具 举报

我的人缘0
marcusg 发表于 2017-12-6 04:19:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (9)
 
 
10% (1)  踩
Lz什么时候面的呀
回复

使用道具 举报

我的人缘0
 楼主| siy 发表于 2017-12-6 04:45:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (49)
 
 
2% (1)  踩
marcusg 发表于 2017-12-6 04:19
Lz什么时候面的呀

感恩节之前两天。。。。
回复

使用道具 举报

我的人缘0
codingsapien 发表于 2017-12-6 04:58:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (55)
 
 
6% (4)  踩
所以更好的解法应该是 nm(n + m)?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| siy 发表于 2017-12-6 05:18:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (49)
 
 
2% (1)  踩
codingsapien 发表于 2017-12-6 04:58. 围观我们@1point 3 acres
所以更好的解法应该是 nm(n + m)?

对每一行,得到每一对1的列坐标pair,存到set里,遍历行如果有重复就true, complexity是n * m * m。应该会有更好的解法吧。
回复

使用道具 举报

我的人缘0
get_bits 发表于 2017-12-6 16:37:08 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  40% (2)
 
 
60% (3)  踩
马克一下 谢谢楼主
回复

使用道具 举报

我的人缘0
LUOLUOLNSH 发表于 2017-12-6 22:58:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
多谢lz分享 ~~ 想问问如果用HashMap<Integer, HashSet<Integer>>存的话 key 和value 都分别是什么泥?key 是行吗?
回复

使用道具 举报

我的人缘0
啊lch 发表于 2017-12-7 01:23:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (106)
 
 
0% (1)  踩
HOMIE 发表于 2017-12-6 14:53
如果输入矩阵里只有0和1,那么通过对任意两行相加,如果得到的数组含有两个2,是否能证明矩形存在呢?时间 ...

我觉得不行吧,你这样没有考虑对角线的情况,比如说:
0 1 0 1
1 0 1 0
0 1 0 0
这样的话 [0,1][1,0][1,2][2,1]也能构成一个矩形  
回复

使用道具 举报

我的人缘0
penggeqiang 发表于 2017-12-7 01:28:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (78)
 
 
10% (9)  踩
慢慢等。。最近假期多,估计得约到1月份了
回复

使用道具 举报

我的人缘0
penggeqiang 发表于 2017-12-7 01:29:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (78)
 
 
10% (9)  踩
啊lch 发表于 2017-12-7 01:23
我觉得不行吧,你这样没有考虑对角线的情况,比如说:
0 1 0 1
1 0 1 0

对角线的情况叫“菱形”吧。。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
啊lch 发表于 2017-12-7 01:45:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (106)
 
 
0% (1)  踩
penggeqiang 发表于 2017-12-7 01:29
对角线的情况叫“菱形”吧。。

不是啊,有时候是菱形有时候是矩形,像我举的例子就是个正方形
回复

使用道具 举报

我的人缘0
penggeqiang 发表于 2017-12-7 01:49:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (78)
 
 
10% (9)  踩
啊lch 发表于 2017-12-7 01:45
不是啊,有时候是菱形有时候是矩形,像我举的例子就是个正方形

对,我想错了。
回复

使用道具 举报

我的人缘0
HOMIE 发表于 2017-12-7 08:21:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  50% (2)
 
 
50% (2)  踩
啊lch 发表于 2017-12-7 01:23 来源一亩.三分地论坛.
我觉得不行吧,你这样没有考虑对角线的情况,比如说:
0 1 0 1
1 0 1 0

同意,没想到这个case。如果考虑对角线的话,是不是需要单独考虑了,通过比较列坐标的方法就不适用于菱形。
回复

使用道具 举报

我的人缘0
Nanthan_ford 发表于 2017-12-7 09:01:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
啊lch 发表于 2017-12-7 01:23
我觉得不行吧,你这样没有考虑对角线的情况,比如说:
0 1 0 1
1 0 1 0

. 1point3acres感觉这道题general是不是不需要考虑这种情况吧
回复

使用道具 举报

我的人缘0
get_bits 发表于 2017-12-7 17:28:19 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  40% (2)
 
 
60% (3)  踩
马克一下 谢谢楼主!
回复

使用道具 举报

我的人缘0
zeehw 发表于 2017-12-7 17:40:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
siy 发表于 2017-12-6 05:18
对每一行,得到每一对1的列坐标pair,存到set里,遍历行如果有重复就true, complexity是n * m * m。应该 ...
. 1point3acres
谢谢楼主分享.本文原创自1point3acres论坛
这么解的话就是说这道题不用考虑组成斜的矩形的情形了吧?
回复

使用道具 举报

我的人缘0
qingsong 发表于 2017-12-7 18:22:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (35)
 
 
0% (0)  踩
大家看这个思路行不行。
把每行看成二进制数字,所以首先把矩阵转成n个数字的数组,然后每两个数做“与”操作,结果里面有2个1,就说明可以组成矩形。
如果行数多于列数,我们可以改成把每列转成数字,所以总时间复杂度应该是O(m * n)
回复

使用道具 举报

我的人缘0
hychin 发表于 2017-12-8 02:48:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (242)
 
 
18% (54)  踩
得看长宽多少 要是超过32位 位数组内部也只能每32个每32个与一下
回复

使用道具 举报

我的人缘0
 楼主| siy 发表于 2017-12-8 05:02:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (49)
 
 
2% (1)  踩
LUOLUOLNSH 发表于 2017-12-6 22:58. 一亩-三分-地,独家发布
多谢lz分享 ~~ 想问问如果用HashMap存的话 key 和value 都分别是什么泥?key 是行吗?

key是一个纵坐标,set里面放另一个纵坐标。因为是按行遍历,不需要考虑横坐标的。如果你是按列遍历就反过来就行
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-8-17 21:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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