Design (LC "Design a X")

Scope — LC “design a X” problems — reading the required operations off the problem and picking the structure combination that makes every one of them O(1) or O(log n); the worked designs themselves live in the examples sheet. See also: design_examples.md — the designs, one problem card each; design_patterns.md — consistent hashing, rate limiters and load balancing, asked in the same rounds but not LC problems; ood_design.md — class modelling, SOLID and design patterns for the LLD round; iterator.md — the iterator contract in isolation; hash_map.md and heap.md — the structures most designs combine.

LeetCode Problem Lists

• Design
• Data Stream

0) Concept

0-1) Types

• Data Structure Design: Design custom data structures (Stack, Queue, HashMap, etc.)
• Cache Design: LRU, LFU, Time-based cache systems
• System Component Design: File systems, search systems, rate limiters
• Social Network Design: Twitter, Instagram feed, following/follower systems
• Scheduling/Booking Design: Calendar, meeting rooms, parking systems
• Stream/Iterator Design: Data stream processing, custom iterators
• Game Design: Tic-Tac-Toe, Snake, game boards

0-2) Pattern

Pattern 1: HashMap + LinkedList

• Use Case: Order-sensitive operations (LRU, LFU, insertion order)
• Examples: LRU Cache, LFU Cache, All O(1) Data Structure
• Key Point: HashMap provides O(1) lookup, LinkedList provides O(1) ordering operations

Pattern 2: HashMap + Heap

• Use Case: Priority-based operations, top-k problems
• Examples: Design Twitter, Find Median from Data Stream, Kth Largest Element in a Stream
• Key Point: HashMap tracks data, Heap maintains priority order

Pattern 3: Trie (Prefix Tree)

• Use Case: Autocomplete, prefix search, word validation
• Examples: Search Autocomplete System, Design Add and Search Words Data Structure, Design Search System
• Key Point: Efficient prefix-based operations O(L) where L is word length

Pattern 4: OOD (Object-Oriented Design)

• Use Case: Complex system with multiple components and interactions
• Examples: Parking Lot, Elevator System, Library Management
• Key Point: Focus on classes, interfaces, relationships, and SOLID principles

Pattern 5: Stream/Queue Based

• Use Case: Real-time data processing, moving window operations
• Examples: Moving Average, Hit Counter, Snake Game, Rate Limiter
• Key Point: Deque or Queue for time-window based operations

Pattern 6: HashMap + Array (Swap-to-End Delete)

• Use Case: O(1) insert and delete plus a uniformly random element
• Examples: Insert Delete GetRandom O(1), the same with duplicates (LC 381)
• Key Point: the array gives random access by index; the map gives the index of a value; delete swaps the victim with the last element so the array stays contiguous

Pattern 7: Stack + Auxiliary State

• Use Case: a stack that must also answer an aggregate (min, pending increment, max frequency) in O(1)
• Examples: Min Stack, Design a Stack With Increment Operation, Maximum Frequency Stack
• Key Point: store the aggregate per layer, so it is pushed and popped with the element it describes (stack.md § Template 4)

Pattern 8: Sorted Map / Time Index

• Use Case: queries that need order: the neighbour before or after x, overlaps, ranges, “the value as of time t”
• Examples: My Calendar I / II / III, Range Module, Time Based Key-Value Store, Stock Price Fluctuation
• Key Point: a sorted map (TreeMap, SortedList, or a sorted list + bisect) answers floor / ceiling in O(log n); a hash map has no order, so the same query degrades to O(n)

Pattern 9: Path Hierarchy

• Use Case: a hierarchy addressed by a path or a fixed-width key (files, directories, timestamps)
• Examples: Design File System, Design In-Memory File System, Design Log Storage System
• Key Point: a map keyed by the full path when only exact paths are queried; a trie of path components when a prefix must be listed (ls)

Pattern 10: Aggregate Counters Updated on Write

• Use Case: the read is a summary (who won, an average) that a scan would make slow
• Examples: Design Tic-Tac-Toe, Design Underground System
• Key Point: keep the summary’s ingredients (line sums, a total and a count) and update them on every write, so every read is O(1)

1) General form

1-1) Basic OP

Step 1: Clarify Requirements

• What operations need to be supported?
• What are the time/space complexity requirements?
• What are the edge cases? (empty input, duplicates, concurrency)
• What is the expected scale? (single machine vs distributed)

Step 2: Choose Data Structures

• Map key requirements to appropriate data structures
• Consider trade-offs (time vs space, simplicity vs performance)
• Multiple data structures often needed (HashMap + List, HashMap + Heap, etc.)

Step 3: Define Class Structure

class DesignName:
    def __init__(self, params):
        # Initialize data structures
        self.data_structure1 = {}
        self.data_structure2 = []

    def operation1(self, params):
        # Implement operation
        pass

    def operation2(self, params):
        # Implement operation
        pass

Step 4: Implement Core Operations

• Focus on the required methods
• Maintain invariants (data consistency between structures)
• Handle edge cases

Step 5: Optimize

• Identify bottlenecks
• Use appropriate data structures for O(1) operations when needed
• Consider lazy evaluation or caching

1-2) Interview Tips

Tip 1: Ask Clarifying Questions

• “Should this support concurrent access?” (Usually no for LC problems)
• “What should happen if we try to get a non-existent key?”
• “Are there any constraints on input size or range?”
• “Do we need to support deletion/updates?”

Tip 2: Start with Simple Solution

• Start with brute force using basic data structures
• Explain time/space complexity
• Then optimize based on requirements

Tip 3: Data Structure Selection

• Need fast lookup? → HashMap/HashSet
• Need ordering? → LinkedList, TreeMap, Heap
• Need both? → Combine them (HashMap + LinkedList for LRU)
• Prefix operations? → Trie
• Range queries? → Segment Tree, Binary Indexed Tree
• Time-based operations? → Queue/Deque with timestamps

Tip 4: Common Mistakes to Avoid

• Not maintaining consistency between multiple data structures
• Forgetting to handle edge cases (empty, single element, duplicates)
• Not considering time complexity of helper operations
• Over-engineering (keep it simple if requirements allow)

Tip 5: OOD Specific Tips

• Define clear interfaces and responsibilities
• Use meaningful class and method names
• Consider SOLID principles (especially Single Responsibility)
• Think about extensibility and maintainability

1-3) Things to Notice

Notice 1: OrderedDict in Python

• Combines HashMap and LinkedList functionality
• move_to_end(key): O(1) operation to reorder
• popitem(last=False): Remove first item (FIFO), last=True for LIFO
• Perfect for LRU/LFU cache implementations

Notice 2: Double Data Structure Pattern

• When using multiple data structures, ensure they stay synchronized
• Example: LRU uses cache_dict (lookup) + cache_list (order)
• Always update BOTH when adding/removing/modifying

Notice 3: Dummy Nodes for LinkedList

• Use dummy head/tail nodes to simplify edge cases
• Avoids null checks for head/tail operations
• Common in LRU Cache implementations

Notice 4: Time-based Expiration

• Use timestamp + cleanup strategy
• Lazy cleanup: Remove expired items when accessed
• Eager cleanup: Use heap/queue to track expiration times
• Trade-off: Space (keeping old data) vs Time (cleanup overhead)

Notice 5: defaultdict and Counter

from collections import defaultdict, Counter
# Avoid key existence checks
followers = defaultdict(set)  # Auto-creates empty set
tweet_count = defaultdict(int)  # Auto-creates 0

1-4) Classic LC Problems by Category

Category 1: Cache Design ★★★☆☆Priority 3 of 5 — Worth knowing — usually a variant of a must-know pattern

• LC 146. LRU Cache (Medium) - HashMap + DoublyLinkedList
• LC 460. LFU Cache (Hard) - HashMap + OrderedDict for frequency buckets
• LC 432. All O(1) Data Structure (Hard) - HashMap + DoublyLinkedList of buckets
• LC 1756. Design Most Recently Used Queue (Medium)

Category 2: Data Structure Design

• LC 380. Insert Delete GetRandom O(1) (Medium) - HashMap + ArrayList
• LC 381. Insert Delete GetRandom O(1) - Duplicates (Hard)
• LC 211. Design Add and Search Words Data Structure (Medium) - Trie
• LC 208. Implement Trie (Prefix Tree) (Medium)
• LC 641. Design Circular Deque (Medium)
• LC 622. Design Circular Queue (Medium)
• LC 225. Implement Stack using Queues (Easy)
• LC 232. Implement Queue using Stacks (Easy)

Category 3: Stream/Time-based Design

• LC 346. Moving Average from Data Stream (Easy) - Queue
• LC 362. Design Hit Counter (Medium) - Queue with timestamps
• LC 353. Design Snake Game (Medium) - Queue + Set
• LC 1396. Design Underground System (Medium) - HashMap
• LC 981. Time Based Key-Value Store (Medium) - HashMap + Binary Search

Category 4: File System Design

• LC 1166. Design File System (Medium) - HashMap for path storage
• LC 588. Design In-Memory File System (Hard) - Trie-like nested dict structure
• LC 1244. Design A Leaderboard (Medium) - HashMap + TreeMap

Category 5: Social Network Design

• LC 355. Design Twitter (Medium) - HashMap + Heap for feed merging
• LC 1603. Design Parking System (Easy) - Simple counter

Category 6: Search/Autocomplete Design

• LC 642. Design Search Autocomplete System (Hard) - Trie + Heap
• LC 1268. Search Suggestions System (Medium) - Trie or Sorting
• LC 1146. Snapshot Array (Medium) - HashMap for snapshots

Category 7: Iterator Design

• LC 284. Peeking Iterator (Medium) - Iterator wrapper with lookahead
• LC 251. Flatten 2D Vector (Medium) - Two pointers
• LC 341. Flatten Nested List Iterator (Medium) - Stack for DFS
• LC 281. Zigzag Iterator (Medium) - Queue of iterators

Category 8: Rate Limiter Design

• LC 362. Design Hit Counter (Medium) - Sliding window
• Design Token Bucket Rate Limiter (Common interview question)
• Design Leaky Bucket Rate Limiter (Common interview question)

Category 9: Game Design

• LC 348. Design Tic-Tac-Toe (Medium) - Row/Col/Diagonal counters
• LC 353. Design Snake Game (Medium) - Queue + Set
• LC 1286. Iterator for Combination (Medium)

2) Pattern Selection

A “design a X” question is never solved by one structure. It is solved by naming the operation that would be slow with the obvious structure, then adding a second structure whose only job is to make that one operation fast. Read the required operations off the problem statement first, then pick the pair.

The four questions to ask before writing a line

1. Which operations, and what complexity does each need? Write the class skeleton with the required complexity as a comment on every method before choosing structures. Most wrong answers come from optimising an operation the problem never asked to be fast.
2. What is the eviction or expiry rule? Recency, frequency, and a time window need three different second structures, and the rule is what tells you which.
3. Do queries need order? If any query is “nearest”, “before”, “overlapping” or “range”, a hash map cannot be the only index.
4. What is the invariant, and where is it restored? For two heaps it is the size balance; for LRU it is “head is newest”; for lazy increment it is “the pending delta applies to everything below”. Name it, then make every method end by restoring it.

3) Worked Examples

The designs are problem cards in design_examples.md, one section per pattern above; its Index lists every problem with the card it reduces to.

4) System Design Coding Patterns

Consistent hashing, the two rate limiters and the load-balancing algorithms moved to design_patterns.md. They are asked as coding questions in the same rounds as the problems above, but none of them is a LeetCode problem, and keeping them here made this sheet’s scope two subjects wide.