Snap 电面 求大米

给一个二维 matrix，０代表水，有个 API 可以叫，每叫一次就会随机盖一个砖块，用１代表，问多少时间后才可以从左边过河到右边。

我的解法是用

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

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

有桥可以过去。
O(N*logN)

祝大家好运，也祝我好运+求大米!!

我的想法是用union find:
建立两个额外的点 最开始分别和第一列所有的格子和最后一列所有的格子union
然后每一次API Call 的时候union以后 看看这两个点是不是在一个union里 这样的话每次Call 是LogN

补充内容 (2023-04-14 02:12 +08:00):
我把每一次union / find的时间复杂度假设是log(N)

如果是假设amortized O(1) 的话 每次API Call 时间复杂度是O(1)

snap现在面会有裁员的风险吗

leetcode 有这道题吗

匿名用户 发表于 2023-4-13 07:16
snap现在面会有裁员的风险吗

我也很好奇 😆

snap might face layoff issue, no?

匿名用户 发表于 2023-4-13 12:05
snap might face layoff issue, no?

裁员这个事情普通员工也无从知晓
不过我们组还有6-7个hc

nicezg 发表于 2023-4-13 01:41
leetcode 有这道题吗

305 variant

利口 要救起灵