Roblox Coding题目解析 Rate Limiting

这是Roblox的coding面试题，题目是实现一个带有时间窗口的rate limiting函数。这个题目有两部分，可以在面试环境里运行代码，而且面试环境里有提前准备好的测试样例，如果能全部跑过基本上就能过这一轮面试。

我是在电面被问到这个题目的，面试官是国人。

第一部分

第一部分的函数签名如下

def solution(requests: List[int], window_length: int, max_in_window: int) -> List[bool]:

其中，

• requests 是一系列请求到达的时间戳，
• window_length 是时间窗口的长度，
• max_in_window 是时间窗口里最多能同时存在的请求的数量。
• 返回值是一个布尔类型的数组，对应于每个请求是否能通过

到目前为止这题并不难，用一个简单的队列结构即可实现。稍后我会在本贴一楼附上参考的实现。

第二部分

第二部分的描述比较冗长，下面我总结了一下。

在第一部分的基础上加入了另外两个参数，user_id 和 experience. 这里解释一下 experience, 其实可以理解成不同的产品。也就是说，rate limiting不仅仅是基于时间窗口，还要分用户和产品或者不同的游戏。不同的用户、到不同的产品的请求要分开rate limit. 函数签名如下

def solution(requests: List[int], user_ids: List[int], experiences: List[str], 
             window_length: int, max_in_window: int) -> List[bool]:

前三个参数的数组长度都是相同的，即每个请求的时间戳，及其对应的用户ID和产品名称。

下面是一些参考的输入

windowLength = 5, maxInWindow = 1

正确的输出是[true, false, false, true]

这部分的原理和第一部分是类似的，就是写起来比较啰嗦。稍后我会在本贴一楼附上参考的实现。