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

GG六月onsite

🔗
白丁117 2017-6-22 21:22:33 | 只看该作者
全局:
yanshuining 发表于 2017-6-22 13:57
第二轮,其实是一道概率题。我的想法是:比如给出的矩形array是: rectangle[] rec_array, 先生成一个长度 ...

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

使用道具 举报

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

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

使用道具 举报

🔗
grasssu2 2017-6-23 01:52:40 | 只看该作者
全局:
在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗?如果这样的话,就在所有矩形区域范围外随便加一个不就好了?
回复

使用道具 举报

🔗
 楼主| 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>
复制代码
回复

使用道具 举报

🔗
 楼主| yanshuining 2017-6-23 01:59:28 | 只看该作者
全局:
grasssu2 发表于 2017-6-23 01:52
在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗?如果这 ...

要加入的矩阵,坐标是给定的
回复

使用道具 举报

🔗
 楼主| yanshuining 2017-6-23 02:03:06 | 只看该作者
全局:
额~ LZ不会黏贴代码。。。
回复

使用道具 举报

🔗
allenyao0702 2017-7-1 13:20:16 | 只看该作者
全局:
多谢楼主分享
回复

使用道具 举报

🔗
cxl89 2017-7-5 06:08:00 | 只看该作者
全局:
请问第三轮里面要求打印path是用bfs做的吗?每次bfs的时候build一个图然后倒着print?多谢楼主
回复

使用道具 举报

🔗
熟狗脸 2017-7-5 10:18:01 | 只看该作者
全局:
请教一下第三题: >=1表示经过该点的cost

这个用BFS怎么做呢?需要用priority queue 而不是一般的queue 吗?
回复

使用道具 举报

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

使用道具 举报

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

本版积分规则

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