近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 872|回复: 15
收起左侧

GG六月onsite

[复制链接] |试试Instant~ |关注本帖

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

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

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

x
帮朋友发帖,六月初onsite。第一轮:leetcode 10 https://leetcode.com/problems/re ... ching/#/description
第二轮:第一问:二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。第二问,二维坐标中有多个不重叠的矩形,要求生成一个任意坐标点,位置在这些矩形中,要求生成的点落在各矩形的概率相同。followup:如果提供这两个function,isOverlap(rectangle a, rectangle b) 判断两个矩形是否重合, split(rectangle a, rectangle b) 若两矩形重合,将两个矩形分成互补重叠的小矩形, 问题是: 如何在上述的矩形中加入一个新的矩形。
第三轮:给定一个0-1 matrix,0表示wall,1表示可以走,问从第一行是否能够找到一条path到达最后一行。followup 1:打印出最短的path。followup 2:如果不是0-1 matrix,0依旧表示wall,而>=1表示经过改点的cost,要求打印出从第一行走到最后一行cost最小的path
第四轮:写一个表示employment的class,其中有三个method: makeManager(p1, p2): 将p1安排为p2的manager, makeColleague(p1, p2): build p1和p2为同事关系, isManager(p1, p2): 判断p1是否为p2的manager
第五轮:给出一组同义词的mapping关系,比如:(fast, quick), (fast, speedy), (learn, study)表示fast==quick, fast==speedy, learn==study, 但是fast!=quick. 要求写一个function判断两个senten是否为同义关系。IsSynonymous(List<List<Strings>> synonymousWords, Strings sentence1, Strings sentence2). followup:如果同义关系可以传递,比如:speedy==quick, 修改上述function。


补充内容 (2017-6-22 13:59):
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 更正:
第五轮:给出一组同义词的mapping关系,比如:(fast, quick), (fast, speedy), (learn, study)表示fast==quick, fast==speedy, learn==study, 但是quick!=speedy. 要求写一个function判断两个senten是否为...

评分

1

查看全部评分

本帖被以下淘专辑推荐:

edyyy 发表于 7 天前 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
多谢楼主分享
题不简单啊
回复 支持 反对

使用道具 举报

cuijinxxx 发表于 6 天前 | 显示全部楼层
关注一亩三分地微博:
Warald
G家最近钟爱几何题啊
回复 支持 反对

使用道具 举报

adamduwidoff 发表于 3 天前 | 显示全部楼层
麻烦问一下是mountain View的branch么?
回复 支持 反对

使用道具 举报

白丁117 发表于 前天 12:30 | 显示全部楼层
请教第2轮 如何随机生成坐标,使其落在各个矩形概率相同?,如果重叠,如何分割矩形? 第5轮为啥fast!=quick 第1个条件不是fast==quick吗?谢谢lz~
回复 支持 反对

使用道具 举报

rgc588 发表于 前天 12:42 | 显示全部楼层
白丁117 发表于 2017-6-22 12:30
请教第2轮 如何随机生成坐标,使其落在各个矩形概率相同?,如果重叠,如何分割矩形? 第5轮为啥fast!=quic ...

估计是打错了应该是quick!=speedy
回复 支持 反对

使用道具 举报

rgc588 发表于 前天 12:44 | 显示全部楼层
二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。矩形是和X Y轴平行么?
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 前天 13:45 | 显示全部楼层
rgc588 发表于 2017-6-22 12:42-google 1point3acres
估计是打错了应该是quick!=speedy

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

使用道具 举报

 楼主| yanshuining 发表于 前天 13:46 | 显示全部楼层
rgc588 发表于 2017-6-22 12:44
二维坐标中给了一个矩形,要求生成一个任意一个坐标点,位置在矩形内。矩形是和X Y轴平行么?

矩形平行于XY轴
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 前天 13:57 | 显示全部楼层
白丁117 发表于 2017-6-22 12:30
请教第2轮 如何随机生成坐标,使其落在各个矩形概率相同?,如果重叠,如何分割矩形? 第5轮为啥fast!=quic ...

第二轮,其实是一道概率题。我的想法是:比如给出的矩形array是: rectangle[] rec_array, 先生成一个长度为矩形总数的area_array,area_array中各个元素的值为第i个矩形的面积加上前面所有矩形的面积。所有矩形的总面积为sum_area. 然后在[0,sum_area]中任取一个数,可以得到该数落在了area_array的第i个区间内(这里可以用binary search做)。最后就在第i个矩形里面取一个任意点就可以了。
回复 支持 反对

使用道具 举报

白丁117 发表于 前天 21:22 | 显示全部楼层
yanshuining 发表于 2017-6-22 13:57
第二轮,其实是一道概率题。我的想法是:比如给出的矩形array是: rectangle[] rec_array, 先生成一个长度 ...

谢谢lz回复~没有很明白,为啥array要存前i个矩形的sum,遇到重叠的矩形做法相同吗?
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 昨天 01:44 | 显示全部楼层
白丁117 发表于 2017-6-22 21:22
谢谢lz回复~没有很明白,为啥array要存前i个矩形的sum,遇到重叠的矩形做法相同吗?

如果有重叠的矩形,需要先将重叠的矩形处理成Non-overlap的,就是followup的问题
回复 支持 反对

使用道具 举报

grasssu2 发表于 昨天 01:52 | 显示全部楼层
在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗?如果这样的话,就在所有矩形区域范围外随便加一个不就好了?
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 昨天 01:58 | 显示全部楼层
白丁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>
复制代码
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 昨天 01:59 | 显示全部楼层
grasssu2 发表于 2017-6-23 01:52
在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗?如果这 ...

要加入的矩阵,坐标是给定的
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 昨天 02:03 | 显示全部楼层
额~ LZ不会黏贴代码。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-24 01:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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