SWE / New Grad · VO Coding

Stripe AccountScheduler:时间锁与可用账号 LRU 选择

先保证 locked_until 的半开时间语义,再让 acquire 自动挑可用账号中最久未使用者。

题目重点:先保证 locked_until 的半开时间语义,再让 acquire 自动挑可用账号中最久未使用者。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练版所有操作显式带 now,且 now 非递减;锁区间 [acquire_time,locked_until),因此 now==locked_until 时可用。
  • 未知 account 返回 false/错误按接口定义,训练版 is_available 返回 false;duration 为非负整数,acquire 只对当前可用账号成功。
  • last_used 初始为负无穷,同分时按账户输入顺序;显式和自动 acquire 均更新 last_used。只是查询 is_available 不算使用。

解题路线

  1. 用 accounts set 检查合法 ID,locked_until map 查上次锁截止;is_available(a,t) 为存在且 t≥locked_until[a]。如果题目时间戳是闭区间,等号处需调整。
  2. 显式 acquire(a,d,now) 先检查可用,再设置 locked_until[a]=now+d 和 last_used[a]=递增使用序号;d=0 立刻释放但仍更新 LRU 次序。失败不改变状态。
  3. 自动 acquire 遍历所有可用账户取最小 (last_used,输入序号),然后复用显式 acquire 更新;不要在不可用账号中选最老者。
  4. 若查询数多且锁到期动态变化,可用按到期时间的 min-heap 恢复可用集,再用 LRU 有序结构;堆元素附版本避免重复锁的旧到期事件误释放。若只几十账户,线性扫描更易验证。

手动走一遍

训练例账号 [A,B],A 锁到 10、B 锁到 5。t=8 时 A 不可用、B 可用;自动 acquire(3,8) 只能选 B,并锁至 11。t=10 时 A 刚解锁而 B 仍锁住,自动选择 A;t=11 两者都可用时,若此前 A 在 t=10 使用过、B 在 t=8 使用过,LRU 是 B。

规模与取舍

n 个账号时 is_available 和显式 acquire 期望 O(1),自动选择 O(n),空间 O(n);堆+有序结构可把自动选择/到期处理降到 O(log n) 均摊,但需要版本与一致性维护。

易错点与追问

容易失分的边界

  • 把 now==locked_until 判为仍被锁。
  • 只根据锁到期时间挑选,误把最早解锁当 LRU。
  • is_available 查询更新 last_used,改变后续自动选择。
  • duration=0、重复账号 ID、时间倒退和不存在 ID 未定义。
  • 将无并发训练版自动推广为并发安全实现;真实系统选取与锁定须原子化。

继续深挖

  • 操作时间若会倒退,locked_until 和 last_used 应如何定义?
  • 百万账号且锁截止不断变化时怎样同时维护可用集和 LRU?
  • 多进程同时 acquire 时如何保证同账号不被双分配?
✓已复制微信号!