手写限流 allow(userId, timestamp)
哪些公司问过
答案要点
- 数据结构:HashMap<userId, 时间戳队列>,队列按时间递增
- 每次调用先从队头弹出窗口外(≤ t-10s)的时间戳
- 窗口内已满 3 次返回 false,否则记录时间戳并返回 true
- 每个用户队列至多 3 个元素,时间 O(1),空间 O(用户数)
- 边界与并发:确认窗口开闭、拒绝请求是否计数,加锁并清理不活跃用户
易错点
- 被拒绝的请求也加入队列,持续请求的用户会一直被拒
- 窗口边界用小于还是小于等于没有确认
- 多线程下检查和插入不是原子操作
面试官常见追问
- 为什么不用固定窗口计数器?
- 分布式场景怎么实现?
- 如果限制改成每分钟 10 万次,这个方案还合适吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。