详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1258|回复: 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% (45)
 
 
10% (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% (294)
 
 
1% (5)  踩
水浅王八多 发表于 2018-3-16 06:21
同求问当有overlap时候怎么处理重叠部分。
. 1point3acres
刚面过个类似的,是如何用小方框覆盖满一个大方框的

讨论完了,面试官告诉我,可以用一个叫做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% (294)
 
 
1% (5)  踩
anywho 发表于 2018-3-14 03:48
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以 ...

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

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

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

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
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. Waral 博客有更多文章,
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以 ...

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

使用道具 举报

我的人缘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 那可以 ...

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

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

回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
shiningsnow 发表于 2018-3-14 23:25:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
同想问多个overlap分成多个小矩形怎么code?
回复

使用道具 举报

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

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

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

回复

使用道具 举报

我的人缘0
水浅王八多 发表于 2018-3-16 06:21:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (40)
 
 
4% (2)  踩
同求问当有overlap时候怎么处理重叠部分。
回复

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-17 10:08:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (55)
 
 
1% (1)  踩
有overlap 就把overlap的部分看成独立的 rec,然后再用二楼的算法
回复

使用道具 举报

我的人缘0
Ferocious丶 发表于 2018-3-17 14:42:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
楼主有啥好的想法么? 好像用binary index tree可以做?
用bit的range update, point query.. Waral 博客有更多文章,
每次从m*n里random出一个点,然后query一下这个点是不是大于0,
如果大于0就返回这个点,等于0就接着random
不过时间复杂度有点高,每次query是logm*logn,运气最差要random (mn-totalarea)次
但每次update也是logm*logn,这部分复杂度会低些. 围观我们@1point 3 acres
求交流-。- 来源一亩.三分地论坛.

补充内容 (2018-3-18 04:21):
可以用range update, range query优化query,需要两个bit来做.每次query m*n一半的面积,如果这部分sum>0,说明这部分有长方形的点,再取这部分的一半,反之取另一半.每次cut一半,直至只剩一个点.time log(mn)*logm*logn
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-23 12:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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