1/31 Google oniste

面试前一天在地里看面经的时候发现最近好多Onsite的题都有一两道是一样的，所以大家可以重点复习下最近的面经。

第一轮：
在一个一维的坐标上，rain drop 把一个给定长度的sidewalk 全部打湿的题， rain drop的location是随机的，能打湿的范围会给出。
具体思路就是merge interval来做，之前面经也有讨论过

第二轮
这个面试官似乎就是之前有人说的不喜欢笑的面试官，有点严肃
先给了道pl

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

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

ethod判断是否report，输入是station名和timestamp
我的想法是用一个map来存，follow up是怎么优化，然后问复杂度（一问复杂度就很方，答得挺不好的这里。。






补充内容 (2017-2-26 05:09):
Failed

SuperMe 发表于 2017-2-7 13:26
如果设一个visited矩阵的话，是不是就是O(n)?

补充内容 (2017-2-7 13:27):

是这样，所以具体要看代码怎么执行的

SuperMe 发表于 2017-2-7 13:37
没太懂你的意思，如果这个drop 和其他已经打湿的interval有重合呢？

如果有重合就无视掉，反正最后是要求打湿整个路面。

楼主你好，请问第四轮你是存的timestamp 为key, station发送次数为value, 还是3个station name为key, value是HashSet contains timestamp? 优化怎么答得？

求问第一题之前讨论的地方在哪呢？能否发个链接。
第三题每条路径能否能走重复的地方呢？

第一轮好像是很早很早的面经里出现的
好像是这样：
sidewalk是一个大区间，比如[0,100]
raindrop是一个小区间，比如[x, x+1]，x为随机数

每次出现一滴raindrop，更新区间湿润的状态，然后判断是否整个sidewalk全部打湿。时间要求O(1)

方法是把大区间化成100个等长的小区间，和raindrop长度相同
每个区间记录几个状态：左边打湿的长度，右边打湿的长度。
再加一个counter，如果完全打湿，counter++

每次随机产生一个x，判断位置，更新对应区间的状态。counter达到100说明全部打湿了

问下设计题能不能具体说清楚一点点，谢谢了

timestamp是一个时间点还是区间？event发送到接受是不是有时间间隔？

DFS一般就是指数，指数的大小一般就是走的length步数。总体上的时间一般按照指数估量。
但实际上，算法里一般会有很多剪枝优化，中途跳出递归等情况。

notturno 发表于 2017-2-6 13:40
第一轮好像是很早很早的面经里出现的
好像是这样：
sidewalk是一个大区间，比如[0,100]

谢谢，这可以用segment tree做？什么叫左边，右边打湿的长度？输入是类似有个阈值n吗？打湿n次就算完全打湿？还有如果最后除不尽剩的部分怎么处理呢

月下一只喵 发表于 2017-2-6 23:54
谢谢，这可以用segment tree做？什么叫左边，右边打湿的长度？输入是类似有个阈值n吗？打湿n次就算完全打 ...

https://lxia.gitbooks.io/summary ... aindrop_wen_ti.html

notturno 发表于 2017-2-7 06:48
https://lxia.gitbooks.io/summary-of-learning/content/.2_mianjing/sidewalk_raindrop_wen_ti.html

非常感谢～～

第三题复杂度感觉是3^n,因为除了第一圈能走8个位置，后面每个格子只能走3个位置(假设不能倒退，如果能倒退那就是8^n)。

补充内容 (2017-2-7 12:01):
不是不能倒退，而是不能走走过的地方