Roblox OA 面试真题解析：Sliding-Window Rate Limiter 滑动窗口限流

题目描述

给定按时间先后排序的请求流，每条请求带时间戳、用户 ID 和经验值。实现一个滑动窗口限流器：同一用户在过去一个固定时间窗口内的请求数量不超过阈值时才允许通过。请求按时间单调递增到达。

解题思路

为每个用户维护一个队列，保存窗口内已通过的请求时间戳。处理一条请求时，先把队首所有已经滑出窗口的时间戳弹出，再看队列长度：不足阈值则允许并压入当前时间戳，否则拒绝。请求有序到达是前提，队列才能只从队首过期。

from collections import defaultdict, deque

class RateLimiter:
    def __init__(self, window, limit):
        self.window = window
        self.limit = limit
        self.records = defaultdict(deque)

    def is_allowed(self, timestamp, user_id):
        q = self.records[user_id]
        while q and q[0] <= timestamp - self.window:
            q.popleft()
        if len(q) >= self.limit:
            return False
        q.append(timestamp)
        return True

复杂度与易错点

每个用户的时间戳只入队、出队一次，均摊 O(1)；空间 O(活跃用户 × 窗口内请求数)。最容易漏的是「窗口是否包含等于左边界的时间戳」——边界定义要在开始前确认，并保持 is_allowed 与过期判断一致。

FAQ

窗口边界等于 timestamp - window 的时间戳算不算在窗口内？

通常左闭右开，即 [timestamp - window, timestamp) 内计数，等于左边界的时间戳应弹出。具体口径以题面为准，但判断逻辑要前后统一。

参考来源

• LeetCode 359 — Logger Rate Limiter
• LeetCode 362 — Design Hit Counter

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。