狗家oa

刚刚刚做完的google家oa，就是地里那两道，时钟和种花。时钟用的dfs，种花用union find，不过仿照lc128 find b

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

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

rong>补充内容 (2018-8-14 01:56):
oa过了 已约电面～～

point8808 发表于 2018-8-10 15:08
求问种花的题要怎么用union find呢 是找k个empty slots的第一天？

我遇到是大于等于k个连续的flowers 算一组， 求最晚有m组的日期。遇到一个pos，看pos－1 和pos＋1有木有花，有花的的花相应的pos－1 or pos ＋ 1 就是boundary，boundary会提前记录已这个为boundary 的group of flowers有几朵。这样新的pos来了之后就更新boundary 和size就可以

Dyanngg 发表于 2018-8-11 12:21
还是从第一天开始种花，然后每到group是m 的时候 要遍历一下boundary上 checksize是不是k。

soga 那其实只要记录所有boundary的位置就好啦 不过如果把boundary对存在set里 每次更新都要遍历 最后算法的复杂度就是o(n^2) 了是么 有可以复杂度更优的解法嚒 （激发了好奇心

Dyanngg 发表于 2018-8-11 03:59
我遇到是大于等于k个连续的flowers 算一组， 求最晚有m组的日期。遇到一个pos，看pos－1 和pos＋1有木有 ...

那这样的话 是从最后一天搜索？ 如果要找m组k个的话 就是每次更新都遍历一边boundary数组查看是不是满足条件？

补充内容 (2018-8-11 12:09):
所以是o(n)的复杂度？

求问种花的题要怎么用union find呢 是找k个empty slots的第一天？

楼主什么时候投的啊 这就已经收到oa了

spencerzy 发表于 2018-8-10 15:15
楼主什么时候投的啊 这就已经收到oa了

找人内推的，内推一周后收到oa

point8808 发表于 2018-8-11 12:04
那这样的话 是从最后一天搜索？ 如果要找m组k个的话 就是每次更新都遍历一边boundary数组查看是不是满足 ...

还是从第一天开始种花，然后每到group是m 的时候 要遍历一下boundary上 checksize是不是k。

point8808 发表于 2018-8-11 12:47
soga 那其实只要记录所有boundary的位置就好啦 不过如果把boundary对存在set里 每次更新都要遍历 最后算 ...

谢谢楼主热心解答！

请问2019 winter intern 是什么时候工作？今年底还是明年summer