Category F · 7 Problems

Data Structure Design

Design classes that work correctly and efficiently. These are the classic "implement a data structure" interview questions that test OOP, Python stdlib knowledge, and algorithmic thinking together.

Problems: 7
Difficulty: Medium – Hard
Key tools: OrderedDict · deque · heapq · Counter · BFS/DFS
Interview tip: For design problems, always clarify the API first. State the time complexity of each method. Mention what you'd handle differently for production (thread safety, persistence, etc.). In Python, know your collections module — it often gives you the right building block in one import.
P 39 Coding Problem Hard
LRU Cache
Implement an LRU (Least Recently Used) cache with a fixed capacity. Implement get(key) → value or -1 and put(key, value). When capacity is exceeded, evict the least recently used entry. Both operations must run in O(1) time.
Example
cache = LRUCache(2) cache.put(1, 1) # cache: {1:1} cache.put(2, 2) # cache: {1:1, 2:2} cache.get(1) # → 1 (1 is now most recently used) cache.put(3, 3) # evicts key 2 (LRU), cache: {1:1, 3:3} cache.get(2) # → -1 (not found)
OrderedDictmove_to_end(key) popitem(last=False) to evict LRUO(1) all operations
Solution
from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() # maintains insertion/access order def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: # Remove the LRU item (the front of the ordered dict) self.cache.popitem(last=False)
Key insight: OrderedDict maintains insertion order AND supports move_to_end(key) in O(1). The front of the OrderedDict is always the LRU item. Every access (get or put) moves the key to the end (MRU position). When capacity is exceeded, popitem(last=False) removes the front (LRU) item. Interviewers love this solution — it's Pythonic and correct in <15 lines.
P 40 Coding Problem Medium
Min Stack
Design a stack that supports push(val), pop(), top(), and getMin(). All operations must run in O(1) time. getMin() returns the minimum value currently in the stack.
Example
s = MinStack() s.push(-2); s.push(0); s.push(-3) s.getMin() → -3 s.pop() s.top() → 0 s.getMin() → -2
stack of (value, current_min) tuples min() at push timeO(1) getMin
Solution
class MinStack: def __init__(self): # Each item is (value, min_so_far) — track the running min self.stack = [] def push(self, val: int) -> None: current_min = min(val, self.stack[-1][1]) if self.stack else val self.stack.append((val, current_min)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]
Key insight: Store a pair at each stack position: (value, min_at_this_level). When pushing, compute the new minimum as min(new_val, current_top_min). When popping, the minimum for the remaining stack is just self.stack[-1][1] — no re-computation needed. This is O(1) for all operations at the cost of 2× memory.
P 41 Coding Problem Medium
Frequency Tracker
Design a class that supports add(item), remove(item), and top_k(k) which returns the k most frequent items at that moment. Ties in frequency can be broken arbitrarily.
Example
ft = FrequencyTracker() ft.add("apple"); ft.add("apple"); ft.add("banana"); ft.add("cherry") ft.top_k(2) → ["apple", "banana"] # or ["apple", "cherry"] — tie for 2nd ft.remove("apple") ft.top_k(1) → ["banana"] # or ["cherry"]
CounterCounter.most_common(k) counter decrement and cleanup
Solution
from collections import Counter from typing import List, Any class FrequencyTracker: def __init__(self): self.counts = Counter() def add(self, item: Any) -> None: self.counts[item] += 1 def remove(self, item: Any) -> None: if self.counts[item] > 0: self.counts[item] -= 1 if self.counts[item] == 0: del self.counts[item] # keep Counter clean def top_k(self, k: int) -> List[Any]: return [item for item, _ in self.counts.most_common(k)]
Key ideas: Counter.most_common(k) uses a heap internally to return the k most common items in O(n log k) time. On remove: decrement the count, then delete the key if it reaches 0. Leaving zero-count keys in the Counter would make most_common include them incorrectly. For a production version needing O(1) top_k, you'd use a sorted container or a bucket-sort based approach.
P 42 Coding Problem Hard
Sliding Window Rate Limiter
Design a RateLimiter(max_calls, window_seconds) class with method is_allowed(user_id) → bool. It returns True if the user has made fewer than max_calls in the last window_seconds seconds, and records this call. Returns False (and does not record) if the limit is exceeded.
Example
# max 3 calls per 60 seconds limiter = RateLimiter(max_calls=3, window_seconds=60) limiter.is_allowed("alice") → True (1st call) limiter.is_allowed("alice") → True (2nd call) limiter.is_allowed("alice") → True (3rd call) limiter.is_allowed("alice") → False (4th call — blocked)
deque per usertime.time() popleft() expired timestampsdefaultdict(deque)
Solution
import time from collections import defaultdict, deque class RateLimiter: def __init__(self, max_calls: int, window_seconds: float): self.max_calls = max_calls self.window = window_seconds # user_id -> deque of timestamps of their recent calls self.calls: dict = defaultdict(deque) def is_allowed(self, user_id: str) -> bool: now = time.time() dq = self.calls[user_id] # Remove calls that are outside the current window while dq and dq[0] < now - self.window: dq.popleft() if len(dq) < self.max_calls: dq.append(now) # record this call return True return False # limit exceeded, do not record
Key idea — sliding window with a deque: Each user has a deque of call timestamps. On each request: (1) remove timestamps older than window_seconds from the front. (2) If the remaining count is under the limit, allow and record; otherwise deny. The deque gives O(1) append and O(1) popleft, making each check amortised O(calls_in_window). This is the sliding window log algorithm — more precise than the simpler "fixed window counter" approach.
P 43 Coding Problem Medium
Trie (Prefix Tree)
Implement a Trie with three methods: insert(word), search(word) → bool, and starts_with(prefix) → bool. search checks if the exact word was inserted. starts_with checks if any inserted word begins with the given prefix.
Example
trie = Trie() trie.insert("apple") trie.search("apple") → True trie.search("app") → False (not inserted, only prefix exists) trie.starts_with("app") → True trie.insert("app") trie.search("app") → True
TrieNode class with children dictdict.setdefault is_end flagiterative traversal
Solution
class TrieNode: def __init__(self): self.children: dict = {} self.is_end: bool = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for ch in word: # setdefault: get existing child or create a new TrieNode node = node.children.setdefault(ch, TrieNode()) node.is_end = True def _find_node(self, prefix: str): # Walk to the node at the end of prefix, or return None node = self.root for ch in prefix: if ch not in node.children: return None node = node.children[ch] return node def search(self, word: str) -> bool: node = self._find_node(word) return node is not None and node.is_end def starts_with(self, prefix: str) -> bool: return self._find_node(prefix) is not None
Key ideas: Each node stores a dict of children (character → TrieNode) and a boolean is_end. setdefault(ch, TrieNode()) in insert creates new nodes lazily — clean one-liner. A shared _find_node helper avoids duplicating the walk logic. search = find node AND check is_end. starts_with = just find the node. Space: O(total characters inserted). Search/insert: O(word length).
P 44 Coding Problem Hard
Task Scheduler — Topological Sort
Given a list of tasks and a dependency dict {task: [list of tasks it depends on]}, return a valid execution order (no task runs before its dependencies). If a circular dependency exists, return None. This is Kahn's algorithm (BFS topological sort).
Example
tasks = ["A", "B", "C", "D"] deps = {"A": [], "B": ["A"], "C": ["A"], "D": ["B", "C"]} task_order(tasks, deps) → ["A", "B", "C", "D"] # or ["A", "C", "B", "D"] # Circular dependency: task_order(["X","Y"], {"X":["Y"], "Y":["X"]}) → None
Kahn's BFS algorithmin-degree tracking deque for BFScycle detection via remaining nodes
Solution
from collections import defaultdict, deque from typing import List, Dict, Optional def task_order(tasks: List[str], deps: Dict[str, List[str]]) -> Optional[List[str]]: # Build: in_degree = number of prerequisites per task in_degree = {t: 0 for t in tasks} graph: dict = defaultdict(list) for task, prerequisites in deps.items(): for pre in prerequisites: graph[pre].append(task) # pre → task edge in_degree[task] += 1 # Start with tasks that have no dependencies queue = deque(t for t in tasks if in_degree[t] == 0) order = [] while queue: t = queue.popleft() order.append(t) for dependent in graph[t]: in_degree[dependent] -= 1 if in_degree[dependent] == 0: queue.append(dependent) # If not all tasks are in the result, there's a cycle return order if len(order) == len(tasks) else None
Kahn's algorithm: (1) Compute in-degree (number of dependencies) for each task. (2) Start a BFS queue with all tasks that have in-degree 0 (no dependencies). (3) Process each task: add to result, decrement in-degree of its dependents. When a dependent's in-degree hits 0, all its prerequisites are done → add it to the queue. (4) If the result doesn't include all tasks, a cycle exists. Time: O(V + E) where V = tasks, E = dependency edges.
P 45 Coding Problem Medium
Graph Connected Components
Given an undirected graph as an adjacency dict {node: [neighbours]}, find all connected components. Return a list of lists, each sorted alphabetically. The outer list should also be sorted.
Example
graph = { "A": ["B"], "B": ["A", "C"], "C": ["B"], "D": ["E"], "E": ["D"], "F": [] } connected_components(graph) → [["A", "B", "C"], ["D", "E"], ["F"]]
DFS with visited setgraph.get(node, []) outer loop over all nodessorted() for determinism
Solution
from typing import Dict, List def connected_components(graph: Dict[str, List[str]]) -> List[List[str]]: visited: set = set() components = [] def dfs(node: str, component: list): visited.add(node) component.append(node) for neighbour in graph.get(node, []): if neighbour not in visited: dfs(neighbour, component) for node in graph: if node not in visited: component: list = [] dfs(node, component) components.append(sorted(component)) return sorted(components)
Key ideas: The outer loop over all nodes ensures we discover every component, even isolated ones. The inner DFS marks all nodes in the current component as visited, so we never process them again. Using a nested function dfs with closure access to visited is cleaner than passing it as a parameter. Sort both the inner components and the outer list for deterministic output.
← Category E: Nested JSON Category G: Algorithms →