Google电面

周三电面的，题不难，类似
给定一个二维点列表，如果任何两个点的距离（直线）<= k，则将它们组合在一起。例如

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

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

几个人的fb，就很迷，google现在还有HC吗，当时面试，HR也没说面的什么级别。

想到一个新思路但是不完整，不确定是否可行，抛个砖引个玉： 把二维平面分成边长为k / sqrt(2)的正方形的方格，方格内的点都是在一个组里。
相邻方格子的也可能属于一个组，还没想好怎么判断。

如果k比较小的话，还可以遍历k，O(N * K ^ 2)

union find, O(nlogn)?

匿名用户 发表于 2022-10-28 11:01
union find, O(nlogn)?

union find不是nlogn呀～

匿名用户 发表于 2022-10-28 12:11
union find不是nlogn呀～

O(nlg*n)

匿名用户 发表于 2022-10-28 12:25
O(nlg*n)

这题问的是有多少个联通呀，感觉不能比N^2低了～

楼主是最近面的？

1. 先把每两个点之间的边扫出来 , O(n^2), n 是点的个数
2. union find with 卢静亚索，O(m * log(n)), m 是边的个数
time complexity  一共 O(n^2 + m * log(n))