API Rate Limiter

Design a request rate limiting system that restricts how many requests a user can make within a fixed time window. Implement canMakeRequest(userId, timestamp) which returns true if the user is within their limit and records the request, and false if they have exceeded it. Implement getRemainingRequests(userId, timestamp) which returns how many more requests the user is allowed to make in their current window.

The core challenge is tracking request counts per user in a way that naturally resets when the time window expires without requiring any cleanup or iteration. Think about how to encode both the user identity and the time window into a single key so that a new window produces a new key automatically.

Service Message Routing System

Design a service mesh where individual services can send and receive messages. Each service has its own validation logic that determines which messages it will accept. Implement addService(service) which registers a service, addConnection(fromName, toName) which establishes a directional route between two services, route(fromName, message) which delivers a message to all direct neighbors of the sending service provided they pass validation, and broadcast(fromName, message) which propagates a message through the entire reachable graph using BFS, dropping the message at any service whose validation rejects it.

The core challenge is separating two concerns: the graph structure that determines where messages can travel, and the per-service validation logic that determines whether a message is accepted at each node. Think about how a base service interface with an abstract validate method lets you extend to specific service types while keeping the routing logic completely generic. Also consider how the BFS traversal must handle cycles to avoid infinite propagation.

LRU Cache

Design a cache with a fixed capacity that evicts the least recently used entry when full. Implement get(key) which returns the value or -1 if not present, and put(key, value) which inserts or updates a key. Both operations should count as a "use."

The core challenge is doing both operations in O(1). Think about what data structure gives you O(1) lookup and also lets you track access order efficiently.

Task Scheduler

Design a task scheduling system where tasks have a cooldown period — the same task cannot run again until N time units have passed. Implement addTask(taskId, timestamp) which registers a task to be run, and runNext(timestamp) which executes the next eligible task and returns its id, or returns null if none are ready.

Think carefully about how you order tasks when multiple are eligible, and how you track cooldowns per task.

File System

Design an in-memory file system. Implement mkdir(path) which creates a directory at the given path including any missing intermediate directories, createFile(path, content) which creates a file, readFile(path) which returns the file's content, and ls(path) which lists the contents of a directory in alphabetical order.

The structure of the path string is your biggest hint about what the underlying data structure should look like.