分享被裁一年半后重回美国的经历

一亩三分地论坛

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

最近看过此主题的会员

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

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
zyy6799 发表于 2018-3-14 02:29:26 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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这么高么
下一篇:Autodesk 面经
我的人缘0
anywho 发表于 2018-3-14 03:48:48 | 显示全部楼层
  此人我要顶:
 
25% (1) 【我投】
  此人我要踩:
 
75% (3) 【我投】
1 算所有的矩形的面积和  S 然后给每一个矩形分配一个对应的区间 比如 3个矩形的面积分别是1,4,9 那可以分别分配[0,1],[1,6],[6,15]
2 随机产生[0,S] 里的数 通过这个数落在哪个区间里来决定哪个矩形被选中
3 在这个矩形里 根据分别在x 和y 的方向上产生随机坐标 得到的点就是符合要求的点
回复 支持 6 反对 1

使用道具 举报

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

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

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

回复 支持 2 反对 0

使用道具 举报

我的人缘0
dqlsll123 发表于 2018-3-14 03:46:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
蓄水池算法
回复 支持 反对

使用道具 举报

我的人缘0
zhengyiyu 发表于 2018-3-14 05:46:57 | 显示全部楼层
  此人我要顶:
 
100% (7) 【我投】
  此人我要踩:
 
0% (0) 【我投】
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% (暂未有人投票) 【我投】
我想问的是关于这道题的follow up,求大神解答。
当有多个rectangles,并且考虑overlap时,overlap的部分怎么处理。本来想着跟天际线类似,但是多出一个维度,貌似又要麻烦不少,这部分的code该怎么写呢?先谢过。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

非常感谢呀!!如果有多个矩形重叠的的话,是不是分割?但是分割的话,有些矩形就不是正常的形状了吧。这个怎么思考呢?.留学论坛-一亩-三分地
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| zyy6799 发表于 2018-3-14 07:35:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dqlsll123 发表于 2018-3-14 03:46. From 1point 3acres bbs
蓄水池算法
. visit 1point3acres for more.
您好,这个为什么要有蓄水池算法? 不直接rand()% (total_area)产生的数字来选定是哪个矩形?
回复 支持 反对

使用道具 举报

我的人缘0
shiningsnow 发表于 2018-3-14 23:25:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同想问多个overlap分成多个小矩形怎么code?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
水浅王八多 发表于 2018-3-16 06:21:14 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
同求问当有overlap时候怎么处理重叠部分。
回复 支持 反对

使用道具 举报

我的人缘0
yzkst06100 发表于 2018-3-17 10:08:53 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
有overlap 就把overlap的部分看成独立的 rec,然后再用二楼的算法
回复 支持 反对

使用道具 举报

我的人缘0
Ferocious丶 发表于 2018-3-17 14:42:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主有啥好的想法么? 好像用binary index tree可以做?
用bit的range update, point query.
每次从m*n里random出一个点,然后query一下这个点是不是大于0,
如果大于0就返回这个点,等于0就接着random
不过时间复杂度有点高,每次query是logm*logn,运气最差要random (mn-totalarea)次
但每次update也是logm*logn,这部分复杂度会低些
求交流-。-

补充内容 (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

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

custom counter

GMT+8, 2018-6-26 00:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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