📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 41
跳转到指定楼层
上一主题 下一主题
收起左侧

GG六月onsite

全局:

2017(4-6月) 码农类General 硕士 全职@google - Other - Onsite  | | Other | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
帮朋友发帖,六月初onsite。第一轮:leetcode 10
第二轮:第一问:二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。第二问,二维坐标中有多个不重叠的矩形,要求生成一个任意坐标点,位置在这些矩形中,要求生成的点落在各矩形的概率相同。followup:如果提供这两个function,isOverlap(rectangle a, rectangle b) 判断两个矩形是否重合, split(rectangle a, rectangle b) 若两矩形重合,将两个矩形分成互补重叠的小矩形, 问题是: 如何在上述的矩形中加入一个新的矩形。
第三
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
ng>
更正:
第五轮:给出一组同义词的mapping关系,比如:(fast, quick), (fast, speedy), (learn, study)表示fast==quick, fast==speedy, learn==study, 但是quick!=speedy. 要求写一个function判断两个senten是否为...

评分

参与人数 7大米 +62 收起 理由
atlantic7200 + 5 给你点个赞!
chenx376 + 3 很有用的信息!
chasedream1 + 3 感谢分享!
zzwcsong + 40
david.fang + 3 感谢分享!

查看全部评分


上一篇:求问Google的coding sample是什么鬼
下一篇:口袋宝石电面二,某越同学看到此贴请留言

本帖被以下淘专辑推荐:

推荐
 楼主| yanshuining 2017-6-22 13:57:57 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +2 收起 理由
Self_Learner + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
 楼主| yanshuining 2017-6-23 01:58:20 | 只看该作者
全局:
白丁117 发表于 2017-6-22 21:22
谢谢lz回复~没有很明白,为啥array要存前i个矩形的sum,遇到重叠的矩形做法相同吗?

大致的code如下, 用左下和右上的两个点,四个值表示一个矩阵, (x1, y1, x2, y2)
  1. <div>
  2. </div><div><div>def randomPoint(recs):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>n = len(recs)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>area_array = [0 for i in xrange(n+1)]</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>for i in xrange(1, n+1):</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>area_array[i] = area_array[i-1] + (recs[i][2]-recs[i][0])*(recs[i][3]-recs[i][1])</div><div>
  3. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>sum_area = array_array[n]</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>random_area = random.randint(0, sum_area)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>rec_index = binarySearch(random_area, area_array) - 1 </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>random_point = getRandomPoint(recs[rec_index])</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return random_point</div><div>
  4. </div><div>def binarySearch(target, array):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>start=0; end=len(array)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>while start+1<end:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>mid = start+(end-start)/2</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>if array[mid]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>start=mid</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>else:</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>end=mid</div><div>
  5. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>if array[end]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return end</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>if array[start]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return start</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return 1</div><div>
  6. </div><div>def getRandomPoint(rec):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>(x1, y1, x2, y2) = rec</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>x = random.randint(x1,x2)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>y = random.randint(y1, y2)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return (x, y)</div></div>
复制代码
回复

使用道具 举报

🔗
edyyy 2017-6-17 21:16:43 | 只看该作者
全局:
多谢楼主分享
题不简单啊
回复

使用道具 举报

🔗
cuijinxxx 2017-6-18 06:06:28 | 只看该作者
全局:
G家最近钟爱几何题啊
回复

使用道具 举报

🔗
adamduwidoff 2017-6-21 04:13:35 | 只看该作者
全局:
麻烦问一下是mountain View的branch么?
回复

使用道具 举报

🔗
白丁117 2017-6-22 12:30:13 | 只看该作者
全局:
请教第2轮 如何随机生成坐标,使其落在各个矩形概率相同?,如果重叠,如何分割矩形? 第5轮为啥fast!=quick 第1个条件不是fast==quick吗?谢谢lz~
回复

使用道具 举报

🔗
rgc588 2017-6-22 12:42:43 | 只看该作者
全局:
白丁117 发表于 2017-6-22 12:30
请教第2轮 如何随机生成坐标,使其落在各个矩形概率相同?,如果重叠,如何分割矩形? 第5轮为啥fast!=quic ...

估计是打错了应该是quick!=speedy
回复

使用道具 举报

🔗
rgc588 2017-6-22 12:44:08 | 只看该作者
全局:
二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。矩形是和X Y轴平行么?
回复

使用道具 举报

🔗
 楼主| yanshuining 2017-6-22 13:45:41 | 只看该作者
全局:
rgc588 发表于 2017-6-22 12:42
估计是打错了应该是quick!=speedy

对,我一时手快打错了。是quick!=speedy。谢谢更正
回复

使用道具 举报

🔗
 楼主| yanshuining 2017-6-22 13:46:15 | 只看该作者
全局:
rgc588 发表于 2017-6-22 12:44
二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。矩形是和X Y轴平行么?

矩形平行于XY轴
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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