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.
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 39Coding ProblemHard
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.
OrderedDictmove_to_end(key)popitem(last=False) to evict LRUO(1) all operations
Solution
from collections import OrderedDict
classLRUCache:
def__init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict() # maintains insertion/access orderdefget(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as most recently usedreturn self.cache[key]
defput(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
iflen(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 40Coding ProblemMedium
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.
stack of (value, current_min) tuplesmin() at push timeO(1) getMin
Solution
classMinStack:
def__init__(self):
# Each item is (value, min_so_far) — track the running min
self.stack = []
defpush(self, val: int) -> None:
current_min = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, current_min))
defpop(self) -> None:
self.stack.pop()
deftop(self) -> int:
return self.stack[-1][0]
defgetMin(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 41Coding ProblemMedium
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
classFrequencyTracker:
def__init__(self):
self.counts = Counter()
defadd(self, item: Any) -> None:
self.counts[item] += 1defremove(self, item: Any) -> None:
if self.counts[item] > 0:
self.counts[item] -= 1if self.counts[item] == 0:
del self.counts[item] # keep Counter cleandeftop_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 42Coding ProblemHard
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.
deque per usertime.time()popleft() expired timestampsdefaultdict(deque)
Solution
import time
from collections import defaultdict, deque
classRateLimiter:
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)
defis_allowed(self, user_id: str) -> bool:
now = time.time()
dq = self.calls[user_id]
# Remove calls that are outside the current windowwhile dq and dq[0] < now - self.window:
dq.popleft()
iflen(dq) < self.max_calls:
dq.append(now) # record this callreturnTruereturnFalse# 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 43Coding ProblemMedium
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.
TrieNode class with children dictdict.setdefaultis_end flagiterative traversal
Solution
classTrieNode:
def__init__(self):
self.children: dict = {}
self.is_end: bool = FalseclassTrie:
def__init__(self):
self.root = TrieNode()
definsert(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 = Truedef_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:
returnNone
node = node.children[ch]
return node
defsearch(self, word: str) -> bool:
node = self._find_node(word)
return node is not None and node.is_end
defstarts_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 44Coding ProblemHard
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).
Kahn's BFS algorithmin-degree trackingdeque for BFScycle detection via remaining nodes
Solution
from collections import defaultdict, deque
from typing import List, Dict, Optional
deftask_order(tasks: List[str], deps: Dict[str, List[str]]) -> Optional[List[str]]:
# Build: in_degree = number of prerequisites per task
in_degree = {t: 0for 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] -= 1if in_degree[dependent] == 0:
queue.append(dependent)
# If not all tasks are in the result, there's a cyclereturn order iflen(order) == len(tasks) elseNone
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 45Coding ProblemMedium
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.
DFS with visited setgraph.get(node, [])outer loop over all nodessorted() for determinism
Solution
from typing import Dict, List
defconnected_components(graph: Dict[str, List[str]]) -> List[List[str]]:
visited: set = set()
components = []
defdfs(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))
returnsorted(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.