【父母B签】写一个同样适合爸妈看的签证攻略

一亩三分地论坛

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

最近看过此主题的会员

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yangdaxian 发表于 2018-6-13 03:14:17 | 显示全部楼层 |阅读模式
本楼: 【顶】   50% (1)
 
 
50% (1)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩

2018(4-6月) 码农类General 硕士 全职@Google - Other - 技术电面  | Other | fresh grad应届毕业生

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

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

x
题目我之前没见到过,希望大家一起讨论一下最优解法。
游客,本帖隐藏的内容需要积分高于 160 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

-google 1point3acres
请大家来讨论一下。
-google 1point3acres

补充内容 (2018-6-13 09:24):
好几个同学说看不到,那我把分数降一降吧
游客,本帖隐藏的内容需要积分高于 120 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


补充内容 (2018-6-13 09:25):
[/hide=120]我当时做的是n^2的,结果是加面了,所以我想和大家讨论一下,看是否有nlogn的做法[/hide]

补充内容 (2018-6-17 07:11):
根据目前大家的讨论,应该是没法nlogn内完成的,不过如果有觉得可行的具体解法欢迎写出来讨论

补充内容 (2018-6-17 07:13):
再补充一下,上面说的没法nlogn完成是指的没有办法用常见的算法在面试时间内完成, magicsets 同学给出了一篇论文,使用了比较复杂的算法能够在nlogn时间内完成,感兴趣的同学可以下载来看看。

评分

参与人数 4大米 +8 收起 理由
Anakin09 + 1 给你点个赞!
happyrabbit + 3 给你点个赞!
dnullptr + 3 给你点个赞!
xiaozhi1017 + 1 很有用的信息!

查看全部评分


上一篇:小众Oculus电面
下一篇:BB昂赛跪经
我的人缘0
aiyawocao 发表于 2018-6-14 12:24:39 | 显示全部楼层
本楼: 【顶】   100% (4)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
1. 哇,好题~
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap:. Waral 博客有更多文章,
只是每次 merge时用 isOverlap()来把下一个“吃进去”。
每次“吃”时要Math.max() 打擂台 刷新最高右上角y值。
4. Merged 的 “intervals”只关心每次 “merged的大块” block了的y的最低值和最高值。
5.扫一遍merged 的“intervals” 判断有没有 某个interval 堵住了[0,1].
6.google的题果然不一样。。哪来那么多人整天自己编题啊。。
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-6-14 14:10:11 | 显示全部楼层
本楼: 【顶】   66% (2)
 
 
33% (1)   【踩】
全局: 顶  97% (233)
 
 
2% (6)  踩
这题是可以O(nlogn)时间,不过应该并不简单。

首先注意到一个关键性质:. more info on 1point3acres
一堆方块可以堵住路,当且仅当存在一条连续的曲线(“栅栏”),其起点和终点分别在道路不同的两边,且对于曲线上每个点P,都存在某个方块S,使得S在P里面。

所以本质上我们是要寻找是否存在一组“连在一起”的方块,这组方块同时与x轴以及y=1相交。

“连在一起”本质上就是要求所有长方形的联通分量(connected components),所以问题的难点是怎么在O(nlogn)时间里找到所有的连通分量。找到后我们对于每个连通分量内的所有正方形看看最小最大的y值就可以了。

然后算法这篇文章(的第一部分)中有:
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
(我上传到这里了:https://github.com/jqdocshare/docs/blob/master/plane-rect-cc.pdf)

文章是1983年的,里面还特意提了一下:
Of course, there is a naive algorithm for the problem of finding the connected components to check every pair of rectangles for their intersections, but it takes 0(n^2) time.
. 牛人云集,一亩三分地

算法挺麻烦的,楼主可以自己看一下... 不知道这文章的168个引用中有没有提出改进的方法。.本文原创自1point3acres论坛


补充内容 (2018-6-14 14:12):. 一亩-三分-地,独家发布
有些口误.. “方块”和“正方形”都是指长方形
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-16 12:19:17 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩
xiaozhi1017 发表于 2018-6-16 11:22. 牛人云集,一亩三分地
今天又想了一遍 merge的地方还是觉得是O(n^2) 楼主有什么进展吗?

根据现有的讨论来看,如果不用之前一个同学给出论文的复杂nlogn做法的话,我感觉应该是做不到nlogn的。。。30楼同学的做法我觉得有点问题,如果想修改成符合题意的做法,还是要n^2
回复

使用道具 举报

我的人缘0
Anakin09 发表于 2018-6-19 01:08:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  79% (181)
 
 
20% (46)  踩
yangdaxian 发表于 2018-6-19 00:08
这个目前看是不可行的,因为无论怎么排序都无法保证能够找到所有重叠的长方形。讲真,我已经有点累了,之 ...

哈哈哈哈哈哈lz不用一个个回复啦,认真看了前面的讨论都会有自己的判断的。. more info on 1point3acres

补充内容 (2018-6-19 01:09):
给lz加个米以表谢意

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
FML 发表于 2018-6-17 09:29:10 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  91% (61)
 
 
8% (6)  踩
StevenXie 发表于 2018-6-17 09:13
先sort矩形,然后merge矩形,最后求最大,最小Y

哥们儿我跟你想的应该一样
回复

使用道具 举报

我的人缘0
芝芝vivi 发表于 2018-6-17 00:50:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  0% (0)
 
 
100% (1)  踩
哈哈哈哈 看不了
回复

使用道具 举报

我的人缘0
szyyn95 发表于 2018-6-16 11:50:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  85% (92)
 
 
14% (15)  踩
merge的时候肯定不能只看X轴啊,因为如果和这个interval里面的方块没有重合,那X轴交叉也没意义啊,而且和任何一个interval比的时候,肯定要和里面所有的方块比,所以正常做应该是n方。30楼的思路我看了一下,理论上来讲可以,但是实在是太麻烦了,我觉得楼主被加面,可能和最优解没关系

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘1
肥宅快乐水 发表于 2018-6-15 02:37:42 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  75% (266)
 
 
24% (88)  踩
yangdaxian 发表于 2018-6-15 02:14
2的重点在于如何找到所有相连的长方形吧,倒不是merge这块。

相连的长方形会变成一个新的大长方形, 用priority queue吧. 其实就是merge rectangle
回复

使用道具 举报

我的人缘0
Dylan_Hong 发表于 2018-6-13 03:45:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
分不够 看不到
回复

使用道具 举报

我的人缘0
xiaozhi1017 发表于 2018-6-13 06:42:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (18)
 
 
18% (4)  踩
利口把伞溜是矩阵重叠

堵路我只能想出O(n^2)的还不好实现,碰到这种映射的就不会......

求大神指教

感谢分享!. From 1point 3acres bbs

补充内容 (2018-6-13 08:08):. 牛人云集,一亩三分地
将矩阵按y排序 沿着y轴从下往上扫 前一个矩阵如果和后一个矩阵overlap就save后一个矩阵 再往上找 想了很久 我只能想到O(n^2)的 哎

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

回复

使用道具 举报

我的人缘0
老冯123 发表于 2018-6-13 07:15:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
我也在准备投狗狗的,回复下转个积分,希望能跟楼主讨论一下
回复

使用道具 举报

我的人缘0
qinyi93 发表于 2018-6-13 07:30:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (2)
 
 
66% (4)  踩
积分不够看不到
回复

使用道具 举报

我的人缘0
fcheng1013 发表于 2018-6-13 07:35:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
积分不够看不到 楼主可以好心发个私信不? 拜托啦!! fcheng1013@gmail.com
回复

使用道具 举报

我的人缘0
hyforever 发表于 2018-6-13 08:37:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (55)
 
 
19% (13)  踩
是不是相当于合并多个y值区间,然后判断0-1这个区间在不在合并的区间内?  时间nlogn行么?
回复

使用道具 举报

我的人缘0
devilnut 发表于 2018-6-13 08:49:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (27)
 
 
12% (4)  踩
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形过一遍就可以了
回复

使用道具 举报

我的人缘0
Liuyi_Jin 发表于 2018-6-13 09:01:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  45% (10)
 
 
54% (12)  踩
楼主能不能好心给发一下邮箱m13641542734@163.com
回复

使用道具 举报

我的人缘0
devilnut 发表于 2018-6-13 09:02:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (27)
 
 
12% (4)  踩
devilnut 发表于 2018-6-13 08:49
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形 ...
. 围观我们@1point 3 acres
不好意思 请无视……
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:20:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩
devilnut 发表于 2018-6-13 09:02
不好意思 请无视……
. 1point3acres
啊,其实我基本就是这么做的啊,你觉得这个时间复杂度能做到多少
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:21:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩
xiaozhi1017 发表于 2018-6-13 06:42
.留学论坛-一亩-三分地利口把伞溜是矩阵重叠. Waral 博客有更多文章,

堵路我只能想出O(n^2)的还不好实现,碰到这种映射的就不会......
. Waral 博客有更多文章,
我当时也做的是n^2的,后来加面了,所以我在想是不是nlogn的解法
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:58:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩
hyforever 发表于 2018-6-13 08:37
是不是相当于合并多个y值区间,然后判断0-1这个区间在不在合并的区间内?  时间nlogn行么?

请问nlogn具体怎么实现?
回复

使用道具 举报

我的人缘0
StevenXie 发表于 2018-6-13 09:59:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
积分不够,求楼主分享,万分感谢!187132225xts@gmail.com
回复

使用道具 举报

我的人缘0
hyforever 发表于 2018-6-13 10:04:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (55)
 
 
19% (13)  踩
yangdaxian 发表于 2018-6-13 09:58.1point3acres网
请问nlogn具体怎么实现?

好像是之前做的利口,但忘了第几题了抱歉
两种方法吧,对一个数组,数组元素为pair【start, end】
1\对数组按start进行排序,然后一次看后一个的start在不在前一个的start-end之间,在则更新前一个end。这样一次插入,
2、将start和end分为两个数组分别排序,如果start[i + 1] > end那么数轴区间就在这个地方分隔开来了,然后将这个区间存入即可
之后判断就之间遍历一遍结果区间集就行了
nlogn主要就是排序的时间复杂度
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 11:02:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (19)
 
 
9% (2)  踩
hyforever 发表于 2018-6-13 10:04
好像是之前做的利口,但忘了第几题了抱歉
两种方法吧,对一个数组,数组元素为pair【start, end】
1\对 ...

不好意思啊,没有特别看懂这个做法,这个具体到这些长方形上怎么做呢?因为两个长方形的y范围重合不代表两个长方形一定重合
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-8-16 20:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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