Data structure design and trie interview questions
14 coding interview questions on designing data structures and tries, each with the correct answer and a full explanation.
Design a data structure
LRU Cache with O(1) get and put. Which structure?
Show answer
Answer
Hash map from key to node in a doubly linked list ordered by recency
The map finds the node and the doubly linked list unlinks and moves it in O(1). A heap makes updates O(log n) with stale entries. A singly linked list cannot remove a node without its predecessor in O(1). A sorted array is O(n) per access.
An LRU cache passes put tests but evicts the wrong key after get(k). What is the likely bug?
Show answer
Answer
get returns the value without moving the node to the most recent end
A read is a use, so get must refresh recency. A missing capacity check would fail put tests too. Storing values breaks moves for every operation, not only after get. Wrong end eviction fails without get.
In a Python interview you implement an LRU cache with O(1) get and put and want the least code. Which standard library type supports move_to_end and popitem(last=False)?
Show answer
Answer
collections.OrderedDict
OrderedDict supports O(1) move_to_end and popping from either end. A plain dict keeps insertion order but has no move_to_end. A deque cannot remove an arbitrary key in O(1). heapq has no key lookup.
Time Based Key-Value Store: set(key, value, t) with strictly increasing t per key, get(key, t) returns the value with the largest timestamp <= t. Best get?
Show answer
Answer
Binary search the per key list of (t, value) with bisect_right on t
Appends keep each list sorted, so bisect_right on the timestamps (a parallel list or key=) finds the floor in O(log n). Scanning is O(n). A per timestamp dict cannot find the floor of a missing t. Sorting on each get is O(n log n).
Sliding window rate limiter: at most N requests per user in the last W seconds, exact. Which per user structure?
Show answer
Answer
A deque of timestamps, pop from the left while older than now - W
The deque holds exactly the requests in the window and each timestamp is popped once. A fixed window counter allows up to 2N across a boundary. One timestamp cannot count requests. A global heap mixes users and costs log n.
Insert Delete GetRandom (a set with insert, remove and uniform random pick) in O(1) average. How does remove work?
Show answer
Answer
Swap the item with the last element in the array, update its index in the map, then pop
Swapping with the last keeps the array dense so pop is O(1) and random indexing stays uniform. list.remove is O(n). Tombstones make getRandom non uniform or unbounded. Converting a set to a list is O(n).
LFU Cache with O(1) operations, ties broken by least recently used. What extra state beyond key to node?
Show answer
Answer
Frequency to ordered list of keys, plus the current minimum frequency
Buckets per frequency with recency order, plus min frequency, give O(1) eviction. A heap is O(log n). Counters alone cannot find the victim quickly. A sorted list is O(n) to update.
Flatten Nested List Iterator (iterate the integers of a nested list in order). Lazy approach that keeps hasNext correct with empty nested lists like [[], [[]]]?
Show answer
Answer
A stack of iterators; hasNext advances until it finds an integer
hasNext must skip empty lists, so it does the advancing. Eager flattening works but is not lazy, which the question asks for. Returning a list's first item fails on nested lists. A non empty stack can hold only empty lists, so True is wrong.
Design an in memory key value store with begin, set, get, rollback and commit, where transactions can nest and commit applies only the innermost transaction. What structure?
Show answer
Answer
A base dict plus a stack of change layers. set writes to the top layer. get checks layers from top to bottom, then the base, and needs a tombstone for deletes. rollback pops the top layer. commit merges the top layer into the one below (or the base). Each operation is O(depth) for get, O(1) for set.
Design a spreadsheet where cells hold numbers or formulas referencing other cells. How do you update dependents and detect cycles?
Show answer
Answer
Keep a dependency graph from a cell to the cells that use it. On set, parse the new references, then check for a cycle with DFS from the cell through its dependents: if it reaches any of the new references, reject the formula. Otherwise update the edges and recompute dependents in topological order. Cache values and invalidate only reachable dependents.
Many prefix queries (startsWith) over a large word list. Why a trie instead of a hash set of words?
Show answer
Answer
A prefix check costs O(L) regardless of how many words share it
A trie walks L nodes for a prefix of length L. A set would need every prefix stored or a scan. Tries usually use more memory because of per node maps. Sets store strings fine. Ordered traversal is a side effect, not the reason.
Trie insert("apple"), then search("app") returns True. What is the bug?
Show answer
Answer
search checks only that the path exists, not an end of word flag
A path for app exists inside apple, so search must check is_end at the final node. Skipping a character would fail other cases. The root holds no character by design. A list or dict for children is an implementation detail.
Word Search II: find which of many words can be traced through adjacent cells of an m x n board. Why build a trie of words instead of running Word Search per word?
Show answer
Answer
One DFS per cell explores all words sharing a prefix and prunes when no word continues
The trie shares prefix work across words and stops paths no word can follow. DFS is not O(1). Visited marking is still needed. Moves are not diagonal.
Design Add and Search Words where '.' matches any letter. What does search do on '.'?
Show answer
Answer
Recurse into every child at that level
A wildcard can be any letter, so try each child. Skipping shifts the remaining pattern. Picking one child misses matches. Failing ignores the wildcard.
