《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4104|回复: 40
收起左侧

GG六月onsite

[复制链接] |试试Instant~ |关注本帖
yanshuining 发表于 2017-6-17 06:23:29 | 显示全部楼层 |阅读模式

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

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

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

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是否为...

评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| yanshuining 发表于 2017-6-22 13:57: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个矩形里面取一个任意点就可以了。
回复 支持 1 反对 0

使用道具 举报

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轴
回复 支持 反对

使用道具 举报

白丁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>. 1point3acres.com/bbs
  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. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
这个用BFS怎么做呢?需要用priority queue 而不是一般的queue 吗?
回复 支持 反对

使用道具 举报

 楼主| yanshuining 发表于 2017-7-6 02:04:12 | 显示全部楼层
熟狗脸 发表于 2017-7-5 10:18
请教一下第三题: >=1表示经过该点的cost. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

这个用BFS怎么做呢?需要用priority queue 而不是一般的queue  ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这道followup没有要求写code,面试官只需要我说出思路即可。我的解法没有用到priotiry queue,还是用queue做bfs。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 07:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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