一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3004|回复: 38
收起左侧

G-o-o-g-l-e 电面

[复制链接] |试试Instant~ |关注本帖
leixiang5 发表于 2016-9-23 09:17:20 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
应该是挂了...所以拿出来跟大家分享分享吧...求大神给解法...最好能给code...小弟我无能为力~
hmmm...昨天面的..晚上6点面的..面试官迟了五分钟才join我的google hangout....结果没声音..然后就电话说话...google hangout视频..就是这么的霸气`...直接用2个设备..
面试官是个印度人- -..口音实在是太蛋疼了....他说啥..我都要猜...我都要重复下..问他是不是这个意思...- -到最后你懂得...他脸色很臭...
印度哥哥一上来...一句废话都不说 (真的是连他名字叫什么..都不说..也不问我任何问题..我连名字都没告诉他..)...他google doc也不打开..直接跟我说...let's say you are given a list of rectangles..determine whether they can form a union rectangle..题目一听..就操蛋了- -...电面问我这么visual的题目...意思就是..看看这些rectangles能不能组成一个完整的rectangle...我刚开始以为..完全没坐标..要自己拼凑rectangles来看看是不是..结果印度哥哥说你不能挪动的啊..都是fix了- -..好吧..看来长方形有坐标的...心里直接说..尼玛..你出的题真好...结果上leetcode看了下..跟leetcode perfect rectangle类似..但是允许rectangles overlap......然后就跟她瞎扯- -...过程就是他不懂我..我不懂她...扯了30分钟..他受不了了..就说要不你写code的吧- -...毫无头绪..都不知道咋动笔啊....随便写了几行到了6:45..宿舍火警响了....他就说...我给你email..你写完发给我把..说声拜拜然后就滚出去了...回到家...敲敲敲代完了代码..发给他...今天跟同学讨论了下...发现解法错的...哈哈..坐等据信了~
谢谢大家看戏...求大米!!!!!!!!!!!

. 1point3acres.com/bbs
补充内容 (2016-10-2 00:35):
再面一轮...这轮作废...因为火警..code没写多少..
wcyz666 发表于 2016-10-3 05:58:39 | 显示全部楼层
模糊的感觉是先找到上下左右四条边,然后从左向右扫,同时保证从上到下的线上是全部被覆盖的。。。

题外话,有个思路:以后跟小伙伴合作,万一面试面不好了,就赶紧把火警叫起来。。。。
回复 支持 1 反对 0

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 10:02:02 | 显示全部楼层
Henry要工作 发表于 2016-9-23 10:01
楼主加油。还有别的机会的

...你哪位啊- -赤裸裸盗用我的头像~
回复 支持 0 反对 1

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 10:02:51 | 显示全部楼层
gaocan1992 发表于 2016-9-23 09:48
Java哥加油,和HR争取下吧,毕竟火警是特殊情况

哈..跟hr说了.."I'm so sorry to hear about the fire alarm and the effect it has on the interview time. I'm still waiting for the engineer to submit your feedback and they typically do that within a week after the interview, but I'll give you a call then. "
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-23 09:43:20 | 显示全部楼层
其实就是perfect rectangle变种,如果允许overlap的话,判断条件改改就行
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 09:45:42 | 显示全部楼层
wtcupup 发表于 2016-9-23 09:43
其实就是perfect rectangle变种,如果允许overlap的话,判断条件改改就行

...求详细解答...因为perfect rectangle其中一个条件就是所有的面积加起来必须是等于boundary rec面积
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-23 09:48:52 | 显示全部楼层
Java哥加油,和HR争取下吧,毕竟火警是特殊情况
回复 支持 反对

使用道具 举报

1peter 发表于 2016-9-23 09:51:24 | 显示全部楼层
wtcupup 发表于 2016-9-23 09:43
其实就是perfect rectangle变种,如果允许overlap的话,判断条件改改就行

没那么简单吧
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-9-23 10:01:18 | 显示全部楼层
楼主加油。还有别的机会的
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 10:03:05 | 显示全部楼层

我也是这么觉得的~...
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-9-23 10:04:01 | 显示全部楼层
允许有overlap感觉很难弄。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最愚蠢的暴力办法就是把先验证四个顶点,然后四个顶点之间构成矩形的所有点都遍历一次,看是否包含在给定rectangles的范围内
. From 1point 3acres bbs
mark一下求后人奇思妙解
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 10:05:35 | 显示全部楼层
Romeobaby 发表于 2016-9-23 10:04-google 1point3acres
允许有overlap感觉很难弄。。。
最愚蠢的暴力办法就是把先验证四个顶点,然后四个顶点之间构成矩形的所有 ...

这样速度太慢了~...给2个1 million长的..1milllion宽的rectangles..这是要million * million的节奏啊~
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-9-23 11:03:08 | 显示全部楼层
leixiang5 发表于 2016-9-23 10:05
这样速度太慢了~...给2个1 million长的..1milllion宽的rectangles..这是要million * million的节奏啊~

求好一点的解。。。这不是允许overlap嘛。。。. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

queiie 发表于 2016-9-23 21:03:36 | 显示全部楼层
跟wtcupup说的一样,具体方法看perfect ralectangle o(nlogn)的解法,改下条件变量
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-23 21:38:13 | 显示全部楼层
楼主,我有个不成熟的想法,就是把上下左右的点找出来,然后就知道应有的面积,把所有矩形面积和减去重叠面积后的结果跟应有面积对比
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 22:06:18 | 显示全部楼层
WhatsFLAG 发表于 2016-9-23 21:38
楼主,我有个不成熟的想法,就是把上下左右的点找出来,然后就知道应有的面积,把所有矩形面积和减去重叠面 ...

哈..我email给他最后的答案也是这个...但是其实也很慢...要用到union rule..
比如A union B union C = A + B + C - A union B - A union C - B union C + A union B union C.... from: 1point3acres.com/bbs
三个就要算7个operators...4个的话貌似是11个?...5个的话15...所以n的话..貌似要做3 + 7 + 11 + 15 + ... + 3 + 4 * n

补充内容 (2016-9-23 22:08):
哦对。。我email给她的答案错的。。只
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-23 22:21:44 | 显示全部楼层
leixiang5 发表于 2016-9-23 22:06
哈..我email给他最后的答案也是这个...但是其实也很慢...要用到union rule..
比如A union B union C = A ...

我的理解就是sweep line从左往右,遇到右上角就出队列,新进队列的跟老元素取交集,所有交集难道不能直接累加吗?为什么要一次考虑两个以上的图形啊
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-23 22:41:08 | 显示全部楼层
WhatsFLAG 发表于 2016-9-23 22:21
我的理解就是sweep line从左往右,遇到右上角就出队列,新进队列的跟老元素取交集,所有交集难道不能直接 ...

也许可以~...这太需要visual了...
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-23 23:09:35 | 显示全部楼层
我感觉40分钟写出来好困难啊,存不存在三哥给三哥留位置的潜规则这种说法啊
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-9-24 01:11:36 | 显示全部楼层
WhatsFLAG 发表于 2016-9-23 23:09. From 1point 3acres bbs
我感觉40分钟写出来好困难啊,存不存在三哥给三哥留位置的潜规则这种说法啊
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谁知道呢......过几天有没有onsite就知道了~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 20:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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