谷歌onsite面经

入职了一段时间，补发一下几个月前的面经。朋友内推后跳过电面直接onsite。一共五轮面试，全部是美国人，最后一轮bq的就省略了。
第一轮，问n个球放进k个bucket使得所有bucket都非空，有几种方法。我给了一个计算公式，面试官问我的公式做了什么假设。想了想发现是球和bucket都不是distinguishable。
他又问我如果球是distinguishable，或者bucket是distinguishable，或者两者都是，分别要怎么计算。然后再让我选一种实现打印所有放法。follow up是怎么样进行性能优化。

第二轮好像是一道时不时出现的面经题，但我面那时还不是特别高频。data stream里面最后k个数去掉top 5%和bot

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

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

。follow up面试官还问能不能进一步优化。还讨论了一下前面的代码哪一部分在多线程环境下可能会出问题，怎么解决。

大概timeline是周一onsite完周五通知准备送hc，下下周一早上通知hc过，同一周team match完，隔周二compete了一下就签了offer。从onsite到签offer大概三周半，算比较快。

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

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

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

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

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

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

求问第二题的思路

多谢楼主！第二题如果用两个priority queue加上一个list来存k个数，需要继续优化吗？

iwishgandi 发表于 2020-2-7 01:09
多谢楼主！第二题如果用两个priority queue加上一个list来存k个数，需要继续优化吗？

感觉这样不够，因为当一个数从list pop出来之后，如果他同时在pq里面，需要找到下一个5%的数补回去。这就需要另外一个sorted的数据结果了

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

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

第三题是不是就用dfs或bfs把所有节点数字加起来？有那么简单吗？还是需要再优化的办法？

第四题的话是不是应该是ts是递增的, 但是每次操作类型不定, 比如:
[[0,'q'], ['5', 'v'], [10, 'v'], ['15', 'v'], [17,'q'], ['25', 'v'], ...]

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

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

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

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

woyaoshuati 发表于 2020-2-7 02:48
谢谢楼主分享！请问第二题可以用priority queue 维持 k * 5% + 1个数就行了？每次加进来数就更新一下顶端数 ...

抱歉，可以用伪代码描述一下或者是把步骤写详细一些么？后面的描述我不太确定你的意思。。不好意思