Fixed-Window Rate Limiter
Updated
Problem statement
Implement a per-client fixed-window rate limiter. Every string in requests contains a client identifier and a timestamp in milliseconds, separated by one space.
Windows are aligned to multiples of windowSize, beginning at timestamp zero. A request is allowed when fewer than limit earlier allowed requests for that client occupy the same window. Return one boolean decision per request.
Function
fixedWindowDecisions(requests: String[], limit: int, windowSize: long) → boolean[]Examples
Example 1
requests = ["a 0","a 9","a 10","b 10","a 11"]limit = 2windowSize = 10return = [true,true,true,true,true]The first two requests fill client a's first window. Timestamp 10 starts a new window, and client b has an independent counter.
Example 2
requests = ["x 3","x 4","x 5"]limit = 2windowSize = 10return = [true,true,false]All three requests share one window, so the third exceeds the limit.
Constraints
- The request list contains between 1 and 100000 rows.
limitis between 1 and 1000000.windowSizeis between 1 and 10^9 milliseconds.- Each row is
clientId timestamp; client IDs contain only letters, digits, hyphens, or underscores, timestamps are between 0 and 10^12, and rows are ordered by nondecreasing timestamp.
Source note: Author-written prompt excerpt retained for source fidelity.
More Proofpoint interview questions
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- File Storage ServiceCresta · PHONE SCREENCresta interview questions
- Camel CardsRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
- Corporation Reporting LinesMicrosoft · PHONE SCREENMicrosoft interview questions
- Key-Value Store on a Block DeviceLambda · PHONE SCREEN
- LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions