题目重点:先保证 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 不算使用。
解题路线
- 用 accounts set 检查合法 ID,locked_until map 查上次锁截止;is_available(a,t) 为存在且 t≥locked_until[a]。如果题目时间戳是闭区间,等号处需调整。
- 显式 acquire(a,d,now) 先检查可用,再设置 locked_until[a]=now+d 和 last_used[a]=递增使用序号;d=0 立刻释放但仍更新 LRU 次序。失败不改变状态。
- 自动 acquire 遍历所有可用账户取最小 (last_used,输入序号),然后复用显式 acquire 更新;不要在不可用账号中选最老者。
- 若查询数多且锁到期动态变化,可用按到期时间的 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 时如何保证同账号不被双分配?
