GG六月onsite

帮朋友发帖，六月初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
Curated Interview Questions from Top Companies

ng>
更正：
第五轮：给出一组同义词的mapping关系，比如：(fast, quick), (fast, speedy), (learn, study)表示fast==quick, fast==speedy, learn==study, 但是quick!=speedy. 要求写一个function判断两个senten是否为...

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

白丁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>

复制代码

多谢楼主分享
题不简单啊

G家最近钟爱几何题啊

麻烦问一下是mountain View的branch么？

请教第2轮 如何随机生成坐标，使其落在各个矩形概率相同？，如果重叠，如何分割矩形？ 第5轮为啥fast!=quick 第1个条件不是fast==quick吗？谢谢lz～

白丁117 发表于 2017-6-22 12:30
请教第2轮 如何随机生成坐标，使其落在各个矩形概率相同？，如果重叠，如何分割矩形？ 第5轮为啥fast!=quic ...

估计是打错了应该是quick！=speedy

二维坐标中给了一个矩形，要求生成一个任意一个坐标点，位置在矩形内。矩形是和X Y轴平行么？

rgc588 发表于 2017-6-22 12:42
估计是打错了应该是quick！=speedy

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

rgc588 发表于 2017-6-22 12:44
二维坐标中给了一个矩形，要求生成一个任意一个坐标点，位置在矩形内。矩形是和X Y轴平行么？

矩形平行于XY轴