南湾单身码农平均一年能存多少钱?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 3841|回复: 76
收起左侧

Google 电面

[复制链接] |试试Instant~
我的人缘0
yangdaxian 发表于 2018-6-13 03:14:17 | 显示全部楼层 |阅读模式

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.
. 牛人云集,一亩三分地

补充内容 (2018-6-13 09:25):
[/hide=120]我当时做的是n^2的,结果是加面了,所以我想和大家讨论一下,看是否有nlogn的做法[/hide]
. Waral 博客有更多文章,
补充内容 (2018-6-17 07:11):
根据目前大家的讨论,应该是没法nlogn内完成的,不过如果有觉得可行的具体解法欢迎写出来讨论

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

评分

参与人数 4大米 +8 收起 理由
Anakin09 + 1 给你点个赞!
happyrabbit + 3 给你点个赞!
dnullptr + 3 给你点个赞!
chillin1017 + 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:
只是每次 merge时用 isOverlap()来把下一个“吃进去”。
每次“吃”时要Math.max() 打擂台 刷新最高右上角y值。. 1point3acres
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% (290)
 
 
2% (6)  踩
这题是可以O(nlogn)时间,不过应该并不简单。
. more info on 1point3acres
首先注意到一个关键性质:
一堆方块可以堵住路,当且仅当存在一条连续的曲线(“栅栏”),其起点和终点分别在道路不同的两边,且对于曲线上每个点P,都存在某个方块S,使得S在P里面。

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

“连在一起”本质上就是要求所有长方形的联通分量(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):. visit 1point3acres for more.
有些口误.. “方块”和“正方形”都是指长方形
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-16 12:19:17 | 显示全部楼层
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)   【踩】
全局: 顶  78% (210)
 
 
21% (56)  踩
yangdaxian 发表于 2018-6-19 00:08
这个目前看是不可行的,因为无论怎么排序都无法保证能够找到所有重叠的长方形。讲真,我已经有点累了,之 ...

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

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

使用道具 举报

我的人缘0
FML 发表于 2018-6-17 09:29:10 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  93% (107)
 
 
6% (8)  踩
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)   【踩】
全局: 顶  87% (241)
 
 
12% (33)  踩
merge的时候肯定不能只看X轴啊,因为如果和这个interval里面的方块没有重合,那X轴交叉也没意义啊,而且和任何一个interval比的时候,肯定要和里面所有的方块比,所以正常做应该是n方。30楼的思路我看了一下,理论上来讲可以,但是实在是太麻烦了,我觉得楼主被加面,可能和最优解没关系
回复

使用道具 举报

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

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

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


回复

使用道具 举报

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

使用道具 举报

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

堵路我只能想出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)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
我也在准备投狗狗的,回复下转个积分,希望能跟楼主讨论一下
回复

使用道具 举报

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

使用道具 举报

我的人缘0
hyforever 发表于 2018-6-13 08:37:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (94)
 
 
12% (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
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 这样每个矩形 ...

不好意思 请无视……
回复

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:20:17 | 显示全部楼层
devilnut 发表于 2018-6-13 09:02
不好意思 请无视……

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

使用道具 举报

我的人缘0
 楼主| yangdaxian 发表于 2018-6-13 09:21:30 | 显示全部楼层
xiaozhi1017 发表于 2018-6-13 06:42
利口把伞溜是矩阵重叠

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

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-21 14:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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