IntermediateSystem Design & Data Structures

Design

Implement core data structures and rate-limited services with clear APIs and invariants

Time: O(1) ops typical
Space: O(n)
Pattern Overview

Core Idea

Compose standard structures (hash maps, lists, heaps) to meet API constraints (time/space).

When to Use

Use for cache designs, randomized O(1) sets, and token buckets/leaky buckets for rate limiting.

General Recognition Cues
General indicators that this pattern might be applicable
  • LRU/LFU cache
  • O(1) ops
  • Randomized set
  • Rate limiting
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

LRU/LFU Cache

Evict by recency/frequency

When to Use This Variant
  • get/put O(1)
Use Case
Caching
Advantages
  • Deterministic
  • Proven patterns
Implementation
class LRUCache:
    def __init__(self, capacity):
        self.cap=capacity; self.map={}; self.head=[0,0]; self.tail=[0,0]; self.head[1]=self.tail; self.tail[0]=self.head
    def _remove(self, node): node[0][1]=node[1]; node[1][0]=node[0]
    def _add_front(self, node): node[1]=self.head[1]; node[0]=self.head; self.head[1][0]=node; self.head[1]=node
    def get(self, k):
        if k not in self.map: return -1
        n=self.map[k]; self._remove(n); self._add_front(n); return n[2]
    def put(self, k, v):
        if k in self.map: n=self.map[k]; n[2]=v; self._remove(n); self._add_front(n); return
        n=[None,None,v]; self.map[k]=n; self._add_front(n)
        if len(self.map)>self.cap: lru=self.tail[0]; self._remove(lru); del self.map[next(k for k,val in self.map.items() if val is lru)]
2

Rate Limiter

Token bucket/leaky bucket

When to Use This Variant
  • Windowed limits
Use Case
API throttling
Advantages
  • Predictable
  • Burst control
Implementation
# Token bucket
class TokenBucket:
    def __init__(self, rate, burst): self.rate=rate; self.burst=burst; self.tokens=burst; self.last=0
    def allow(self, now):
        self.tokens=min(self.burst, self.tokens + (now-self.last)*self.rate); self.last=now
        if self.tokens>=1: self.tokens-=1; return True
        return False
3

Randomized Set

Array + map for O(1)

When to Use This Variant
  • Random pick
Use Case
Random access
Advantages
  • O(1) ops
Implementation
import random
class RandomizedSet:
    def __init__(self): self.a=[]; self.pos={}
    def insert(self, val):
        if val in self.pos: return False
        self.pos[val]=len(self.a); self.a.append(val); return True
    def remove(self, val):
        if val not in self.pos: return False
        i=self.pos.pop(val); last=self.a.pop()
        if i<len(self.a): self.pos[last]=i; self.a[i]=last
        return True
    def getRandom(self): return random.choice(self.a)
Common Pitfalls
Watch out for these common mistakes
  • Sync between structures
  • Edge cases on eviction
  • Time-based cleanup
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(1) ops typical

Hash map + list/heap give constant-time ops.

Space Complexity
O(n)

Store n items + metadata.

Ready to test your knowledge?

Test your pattern recognition with interactive questions