小众学校Baylor University CS系介绍

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 1517|回复: 13
收起左侧

[找工就业] 狗家一道高频题求问

[复制链接] |试试Instant~
我的人缘0
zyy6799 发表于 2018-3-14 02:29:26 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩

2018(4-6月)-[]CS硕士+<3个月短暂实习/全职 - Other|美国其他地区 码农类General全职@Googlefresh grad应届毕业生

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

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

x
最近碰到狗家一道高频提,求问地理大神这道题是咋个意思。
given a list of rectangles which are not intersect with others ,each rectangle has four points, write a method to choose a point uniformly for the list of rectangles



上一篇:居然被阿里简历拒,阿里bar这么高么
下一篇:A9暑假实习求组织!!!!!!
我的人缘0
anywho 发表于 2018-3-14 03:48:48 | 显示全部楼层
本楼: 【顶】   85% (6)
 
 
14% (1)   【踩】
全局: 顶  90% (47)
 
 
9% (5)  踩
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以分别分配[0,1],[1,6],[6,15]
2 随机产生[0,S] 里的数 通过这个数落在哪个区间里来决定哪个矩形被选中
3 在这个矩形里 根据分别在x 和y 的方向上产生随机坐标 得到的点就是符合要求的点
回复

使用道具 举报

我的人缘0
groundzyy1 发表于 2018-3-29 23:28:39 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  98% (338)
 
 
1% (6)  踩
水浅王八多 发表于 2018-3-16 06:21
同求问当有overlap时候怎么处理重叠部分。

刚面过个类似的,是如何用小方框覆盖满一个大方框的

讨论完了,面试官告诉我,可以用一个叫做quadtree的东西

回复

使用道具 举报

我的人缘0
dqlsll123 发表于 2018-3-14 03:46:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (23)
 
 
8% (2)  踩
蓄水池算法
回复

使用道具 举报

我的人缘0
groundzyy1 发表于 2018-3-14 05:46:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (338)
 
 
1% (6)  踩
anywho 发表于 2018-3-14 03:48
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以 ...

不知道为啥会有1个反对,但是感觉这个算法是正解

因为只需要走一次所有矩形,计算面积,然后random一个number出来就搞定了。

类似的题面试碰到过,是一个stream读进来的文件(但是知道总行数),每行要random放到一个小文件里面,并且要确保每个小文件里面的行数相同或者最多差一个。最后讨论出来的解法就是你的这个算法的简化版,因为不需要再去矩形里面算具体的点了。
回复

使用道具 举报

我的人缘0
Adali 发表于 2018-3-14 06:47:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
我想问的是关于这道题的follow up,求大神解答。
当有多个rectangles,并且考虑overlap时,overlap的部分怎么处理。本来想着跟天际线类似,但是多出一个维度,貌似又要麻烦不少,这部分的code该怎么写呢?先谢过。
回复

使用道具 举报

我的人缘0
jtqv84 发表于 2018-3-14 06:51:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  60% (6)
 
 
40% (4)  踩
anywho 发表于 2018-3-14 03:48
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以 ...

(不是我点的反对啊)
能不能只生成一次随机数?总感觉按你这个方法生成三次随机数的话,随机性无法保证。也可能是我想错了。
回复

使用道具 举报

我的人缘0
 楼主| zyy6799 发表于 2018-3-14 07:33:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
anywho 发表于 2018-3-14 03:48
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以 ...

非常感谢呀!!如果有多个矩形重叠的的话,是不是分割?但是分割的话,有些矩形就不是正常的形状了吧。这个怎么思考呢?
回复

使用道具 举报

我的人缘0
 楼主| zyy6799 发表于 2018-3-14 07:35:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩

您好,这个为什么要有蓄水池算法? 不直接rand()% (total_area)产生的数字来选定是哪个矩形?

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


回复

使用道具 举报

我的人缘0
shiningsnow 发表于 2018-3-14 23:25:55 | 显示全部楼层
同想问多个overlap分成多个小矩形怎么code?
回复

使用道具 举报

我的人缘0
dqlsll123 发表于 2018-3-15 00:57:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (23)
 
 
8% (2)  踩
zyy6799 发表于 2018-3-14 07:35
您好,这个为什么要有蓄水池算法? 不直接rand()% (total_area)产生的数字来选定是哪个矩形?

高端大气上档次。而且复杂度一样
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-11 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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