买新车如何让dealer直接竞价?

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1907|回复: 69
收起左侧

Google 电面

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

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

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

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

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


请大家来讨论一下。. 牛人云集,一亩三分地


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

-google 1point3acres
补充内容 (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
magicsets 发表于 2018-6-14 14:10:11 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这题是可以O(nlogn)时间,不过应该并不简单。. Waral 博客有更多文章,

首先注意到一个关键性质:
一堆方块可以堵住路,当且仅当存在一条连续的曲线(“栅栏”),其起点和终点分别在道路不同的两边,且对于曲线上每个点P,都存在某个方块S,使得S在P里面。
. visit 1point3acres for more.
所以本质上我们是要寻找是否存在一组“连在一起”的方块,这组方块同时与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个引用中有没有提出改进的方法。


补充内容 (2018-6-14 14:12):
有些口误.. “方块”和“正方形”都是指长方形
回复 支持 2 反对 1

使用道具 举报

我的人缘0
aiyawocao 发表于 2018-6-14 12:24:39 | 显示全部楼层
  此人我要顶:
 
100% (4) 【我投】
  此人我要踩:
 
0% (0) 【我投】
1. 哇,好题~. 围观我们@1point 3 acres
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap: 来源一亩.三分地论坛.
只是每次 merge时用 isOverlap()来把下一个“吃进去”。
每次“吃”时要Math.max() 打擂台 刷新最高右上角y值。
4. Merged 的 “intervals”只关心每次 “merged的大块” block了的y的最低值和最高值。. 牛人云集,一亩三分地
5.扫一遍merged 的“intervals” 判断有没有 某个interval 堵住了[0,1].
6.google的题果然不一样。。哪来那么多人整天自己编题啊。。
回复 支持 3 反对 0

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 6 天前 | 显示全部楼层
  此人我要顶:
 
50% (1) 【我投】
  此人我要踩:
 
50% (1) 【我投】
xiaozhi1017 发表于 2018-6-16 11:22
今天又想了一遍 merge的地方还是觉得是O(n^2) 楼主有什么进展吗?

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

使用道具 举报

我的人缘0
Anakin09 发表于 3 天前 | 显示全部楼层
  此人我要顶:
 
75% (15) 【我投】
  此人我要踩:
 
25% (5) 【我投】
yangdaxian 发表于 2018-6-19 00:08
这个目前看是不可行的,因为无论怎么排序都无法保证能够找到所有重叠的长方形。讲真,我已经有点累了,之 ...

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

补充内容 (2018-6-19 01:09):
给lz加个米以表谢意
回复 支持 1 反对 0

使用道具 举报

我的人缘0
FML 发表于 5 天前 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
StevenXie 发表于 2018-6-17 09:13
先sort矩形,然后merge矩形,最后求最大,最小Y

哥们儿我跟你想的应该一样
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

我的人缘0
肥宅快乐水 发表于 7 天前 | 显示全部楼层
  此人我要顶:
 
52% (9) 【我投】
  此人我要踩:
 
48% (8) 【我投】
yangdaxian 发表于 2018-6-15 02:14
2的重点在于如何找到所有相连的长方形吧,倒不是merge这块。

相连的长方形会变成一个新的大长方形, 用priority queue吧. 其实就是merge rectangle
Mobile Apps Category (English)728x90
回复 支持 1 反对 0

使用道具 举报

我的人缘0
Dylan_Hong 发表于 2018-6-13 03:45:15 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
分不够 看不到
回复 支持 反对

使用道具 举报

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

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

求大神指教

感谢分享!
.本文原创自1point3acres论坛
补充内容 (2018-6-13 08:08): 来源一亩.三分地论坛.
将矩阵按y排序 沿着y轴从下往上扫 前一个矩阵如果和后一个矩阵overlap就save后一个矩阵 再往上找 想了很久 我只能想到O(n^2)的 哎
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
qinyi93 发表于 2018-6-13 07:30:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
积分不够看不到
回复 支持 反对

使用道具 举报

我的人缘0
fcheng1013 发表于 2018-6-13 07:35:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
积分不够看不到 楼主可以好心发个私信不? 拜托啦!! fcheng1013@gmail.com
回复 支持 反对

使用道具 举报

我的人缘0
hyforever 发表于 2018-6-13 08:37:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
是不是相当于合并多个y值区间,然后判断0-1这个区间在不在合并的区间内?  时间nlogn行么?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
Liuyi_Jin 发表于 2018-6-13 09:01:41 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (7) 【我投】
楼主能不能好心给发一下邮箱m13641542734@163.com
回复 支持 反对

使用道具 举报

我的人缘0
devilnut 发表于 2018-6-13 09:02:53 | 显示全部楼层
  此人我要顶:
 
66% (2) 【我投】
  此人我要踩:
 
34% (1) 【我投】
devilnut 发表于 2018-6-13 08:49
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形 ...

不好意思 请无视……
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:20:17 | 显示全部楼层
  此人我要顶:
 
50% (1) 【我投】
  此人我要踩:
 
50% (1) 【我投】
devilnut 发表于 2018-6-13 09:02
不好意思 请无视……

啊,其实我基本就是这么做的啊,你觉得这个时间复杂度能做到多少
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:21:30 | 显示全部楼层
  此人我要顶:
 
50% (1) 【我投】
  此人我要踩:
 
50% (1) 【我投】
xiaozhi1017 发表于 2018-6-13 06:42
利口把伞溜是矩阵重叠

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

我当时也做的是n^2的,后来加面了,所以我在想是不是nlogn的解法
回复 支持 反对

使用道具 举报

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

请问nlogn具体怎么实现?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
hyforever 发表于 2018-6-13 10:04:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yangdaxian 发表于 2018-6-13 09:58
请问nlogn具体怎么实现?

好像是之前做的利口,但忘了第几题了抱歉. 围观我们@1point 3 acres
两种方法吧,对一个数组,数组元素为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 | 显示全部楼层
  此人我要顶:
 
50% (1) 【我投】
  此人我要踩:
 
50% (1) 【我投】
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

关闭

一亩三分地推荐上一条 /3 下一条

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

custom counter

GMT+8, 2018-6-22 06:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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