Sliding Window Rate Limiter

Early October, 2026

Amazon

Mid-level

Phone screen

Early October, 2026

Late September, 2026

💬 **Question**: Design an in-memory rate limiter for multiple clients in Go. --- **🔑 Key Steps**: - Define a `RateLimiter` struct holding a map of client IDs to slices of timestamps, plus a mutex for safe concurrent access. - In `NewRateLimiter`, initialize and return the struct with the given limit and time window. - In `IsAllowed`, lock the mutex, remove timestamps older than the current time minus the window duration, check if the remaining count is below the limit, and if so, append the current timestamp and return true; otherwise, return false. **💻 Code**: ```go package main import ( "sync" "time" ) // RateLimiter tracks request timestamps per client type RateLimiter struct { mu sync.Mutex maxRequests int window time.Duration clientLogs map[string][]time.Time } // NewRateLimiter creates a new rate limiter with a limit and a time window func NewRateLimiter(maxRequests int, requestWindow time.Duration) *RateLimiter { return &RateLimiter{ maxRequests: maxRequests, window: requestWindow, clientLogs: make(map[string][]time.Time), } } // IsAllowed checks if a client can make a request right now func (rl *RateLimiter) IsAllowed(clientID string) bool { rl.mu.Lock() defer rl.mu.Unlock() now := time.Now() cutoff := now.Add(-rl.window) // Clean up old timestamps outside the current time window logs := rl.clientLogs[clientID] validLogs := make([]time.Time, 0, len(logs)) for _, t := range logs { if t.After(cutoff) { validLogs = append(validLogs, t) } } // Check if the client has reached the maximum allowed requests if len(validLogs) >= rl.maxRequests { rl.clientLogs[clientID] = validLogs return false } // Record the new request timestamp validLogs = append(validLogs, now) rl.clientLogs[clientID] = validLogs return true } ``` **💡 Explanation**: - **Time Complexity**: $O(N)$ per check where $N$ is the number of active requests within the time window for that specific client, as we filter old timestamps. - **Space Complexity**: $O(C \times M)$ where $C$ is the number of unique clients and $M$ is the maximum number of requests stored per client within the window. - **Thread Safety**: A mutual exclusion lock (`sync.Mutex`) protects the shared map and slice data structures from data races since multiple goroutines may check rate limits concurrently.