Algorithms and Data Structures Questions

Comprehensive understanding of core data structures such as arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs, and fundamental algorithms including sorting, searching, traversal, string manipulation, and graph algorithms. Ability to analyze and compare time and space complexity using asymptotic notation such as Big O, Big Theta, and Big Omega, and to reason about trade offs between different approaches. Skills include selecting the most appropriate data structure for a problem, designing efficient algorithms, applying algorithmic paradigms such as divide and conquer, dynamic programming, greedy methods, and graph search, and implementing correct and robust code for common interview problems. At more senior levels, this also covers optimizing for large scale through considerations of memory layout, caching, amortized analysis, parallelism and concurrency where applicable, and profiling and tuning for performance in realistic systems.

HardTechnical

80 practiced

Implement Edmonds-Karp (BFS-based Ford-Fulkerson) in Python to compute max flow from source to sink in a directed graph with capacities. Provide complexity analysis and explain how Dinic's algorithm improves performance. Discuss practical optimizations for sparse vs dense graphs.

Sample Answer

Approach (brief): Edmonds–Karp is Ford–Fulkerson with BFS to find shortest augmenting paths (in terms of edges). Repeatedly run BFS on the residual graph to get a path, augment by the bottleneck, update residual capacities until no path exists.

Python implementation:

python

from collections import deque, defaultdict

class EdmondsKarp:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.cap = defaultdict(int)  # (u,v) -> capacity

    def add_edge(self, u, v, w):
        # allow parallel edges; store reverse edges implicitly in cap
        self.adj[u].append(v)
        self.adj[v].append(u)
        self.cap[(u, v)] += w
        self.cap[(v, u)] += 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            parent = [-1] * self.n
            parent[s] = s
            q = deque([s])
            while q and parent[t] == -1:
                u = q.popleft()
                for v in self.adj[u]:
                    if parent[v] == -1 and self.cap[(u, v)] > 0:
                        parent[v] = u
                        q.append(v)
                        if v == t:
                            break
            if parent[t] == -1:
                break  # no augmenting path
            # find bottleneck
            v = t
            bottleneck = float('inf')
            while v != s:
                u = parent[v]
                bottleneck = min(bottleneck, self.cap[(u, v)])
                v = u
            # apply augmentation
            v = t
            while v != s:
                u = parent[v]
                self.cap[(u, v)] -= bottleneck
                self.cap[(v, u)] += bottleneck
                v = u
            flow += bottleneck
        return flow

Key concepts:- BFS ensures shortest-path (edge-wise) augmentations; each augmentation increases the shortest path length of at least one edge in residual graph, bounding iterations.- Use adjacency lists and a capacity map for sparse graphs and to support parallel edges.

Complexity:- Edmonds–Karp runs in O(V * E^2) worst-case (equivalently O(min(V^{2/3}, E^{1/2})? variations exist for special cases) — commonly cited as O(V E^2) since each augmenting path found by BFS costs O(E) and there are O(V E) augmentations in worst-case.

How Dinic improves performance:- Dinic builds a level graph with BFS and then finds a blocking flow using repeated DFS that only goes forward in the level graph. This reduces redundant searches; worst-case O(V^2 E) but in practice much faster. For many graph families (unit capacities, bipartite matching), Dinic achieves O(E sqrt(V)) or similar improved bounds. Key optimization is the "current arc" pointer to avoid re-scanning exhausted edges during DFS.

Practical optimizations:- Sparse graphs: adjacency lists, defaultdict for capacities, early exit on zero-cap edges, use current-edge pointers (for Dinic) and recursion/iterative DFS to avoid overhead.- Dense graphs: use adjacency matrix for O(1) capacity access or Push-Relabel with gap relabeling and highest-label selection for better performance.- Capacity scaling: augment along paths with large capacities first to reduce number of augmentations.- Use integers and efficient deques, avoid per-iteration allocations, and choose algorithm by graph shape: Edmonds–Karp is simple and robust for small graphs; Dinic or Push-Relabel for larger / performance-critical workloads.

HardTechnical

131 practiced

Analyze the amortized cost of hash table resizing and rehashing. Given a hash table that doubles its bucket count when load factor exceeds threshold, derive total cost over n insertions and justify O(1) amortized insert. Discuss practical strategies to avoid large latency spikes during rehash in production systems.

Sample Answer

Approach / derivation:- Suppose we start with capacity C0 (say 1) and double capacity whenever size reaches current capacity (load factor threshold = 1 for simplicity; argument extends to any θ < 1). Let insertions be n.- Each time we resize from capacity 2^k to 2^(k+1) we must rehash (move) all current elements — cost proportional to the old capacity (≈2^k).- Resizes occur at sizes 1,2,4,8,... up to the largest power ≤ n. Total rehash (movement) cost: Sum_{i=0..⌊log n⌋} 2^i ≈ 2^{⌊log n⌋+1} − 1 ≤ 2n − 1 = O(n).- Besides rehash work, each insertion does O(1) work (compute hash, probe/append). So total work for n inserts = O(n) (normal work) + O(n) (all rehash moves) = O(n). Therefore amortized cost per insert = O(n)/n = O(1).- A tighter accounting argument: charge each inserted element an extra constant credit that pays for future moves; when resizing occurs each element is moved a constant number of times (at most once per level), so constant amortized cost holds.

Key points / intuition:- Doubling ensures that number of expensive moves grows geometrically, so their total is a geometric series bounded by O(n).- Worst-case single-insert time can be Θ(n) (the moment a resize happens), but averaged over many inserts it's constant.

Practical strategies to avoid latency spikes in production:- Incremental/gradual rehashing: migrate a small number of buckets per normal operation (e.g., rehash k buckets per insert). This spreads the O(n) work across many requests, turning a pause into many small increments.- Background worker(s): perform rehashing asynchronously on separate thread(s) to keep request latency low; ensure safe synchronization (readers see either old or new bucket; use atomic pointer swap when done).- Copy-on-write / versioned tables: build new table in background, then atomically switch; readers continue on old table until switch—requires reclaiming old memory safely (epoch-based GC, reference counting).- Lock-free or fine-grained locking migrations: avoid global locks during rehash by using per-bucket locks or lock-free transfer to reduce contention.- Hysteresis and overprovisioning: resize at a higher threshold or allocate extra headroom upfront to reduce frequency of resizes and avoid frequent small expansions.- Tune growth factor: doubling minimizes amortized cost; smaller factors reduce memory overhead but increase rehash frequency (trade-off).- Memory and allocator strategies: preallocate contiguous space or use pools to avoid fragmentation and allocation stalls during rehash.- Consistent hashing / chained designs: for distributed or sharded systems, use consistent hashing to avoid large global reassignments.

Trade-offs:- Background rehash reduces tail latency but adds complexity (concurrency, memory overhead).- Incremental rehash increases per-operation overhead but bounds worst-case latency.- Choosing growth factor and threshold trades memory usage vs. frequency and size of rehash work.

This analysis justifies O(1) amortized insert for doubling hash tables and outlines practical techniques to avoid the single-operation latency spikes in production.

MediumTechnical

100 practiced

Compare cache eviction policies LRU, LFU, and FIFO. For each, explain typical implementation approach, complexity, and workloads where it performs well or poorly. Sketch how you would implement LFU with O(1) operations if required. Discuss hybrid strategies used in real systems.

Sample Answer

LRU, LFU, and FIFO are common cache eviction policies with different assumptions and trade-offs.

LRU (Least Recently Used)- Idea: evict the item not used for the longest time.- Typical implementation: doubly-linked list + hash map mapping key→node. On access, move node to head. On eviction remove tail.- Complexity: O(1) average for get/put; O(1) memory overhead per entry.- Works well: workloads with strong temporal locality (recent items likely reused).- Fails: scans or one-off bursts where many items are accessed once (pollution).

LFU (Least Frequently Used)- Idea: evict item with lowest access frequency.- Typical implementation: maintain counts per key and a min-heap (log n) or count buckets.- Complexity: naive heap: O(log n). Better: O(1) using a frequency-list structure (see below).- Works well: workloads with stable hot items over long time (skews).- Fails: when frequency changes slowly or when old hot items dominate despite recency — may need aging.

FIFO (First-In First-Out)- Idea: evict the oldest inserted item regardless of access.- Typical implementation: queue + hash map (to lookup).- Complexity: O(1) for insert/evict; O(1) lookup if map included.- Works well: simple workloads where insertion age correlates with usefulness; very cheap.- Fails: ignores access pattern — can evict frequently used items.

O(1) LFU sketch (classic approach: “frequency list” / O(1) LFU)- Maintain: - hash map key→(value, freq, pointer to node) - doubly-linked lists per frequency f that contain keys with that freq - a pointer to current minimum frequency minFreq- On get(key): increment frequency -> remove node from list f, append to list f+1, update key's freq; if list f becomes empty and f==minFreq, increment minFreq.- On put: if capacity full, evict tail (oldest) of list minFreq; insert new key into list freq=1 and set minFreq=1.- All operations are O(1) because list removal/append and hash updates are constant-time.

Hybrid strategies in real systems- LRU-K: consider the K-th most recent reference to capture both recency and frequency.- ARC (Adaptive Replacement Cache): maintains recent and frequent lists and adapts sizes dynamically between recency and frequency.- CLOCK-Pro / Segmented LRU: approximations to LRU with lower overhead.- TTL + LFU/LRU: combine time-to-live and eviction policy to avoid stale hot-but-expired entries.- Practical systems (Redis, Memcached variants, OS page cache) use approximations (CLOCK, LRU with sampling) to balance accuracy and performance.

Choosing a policy depends on workload: prefer LRU for temporal locality, LFU for persistent hotspots, FIFO only for simplicity or predictable insert-age semantics; consider hybrid/adaptive policies for mixed or unknown workloads.

MediumTechnical

105 practiced

Design a trie-based autocomplete that returns top K suggestions for a given prefix. Implement insert(word, score) and suggest(prefix, k) in Python where score is higher for more relevant words. Describe how you maintain top-K at each node efficiently and discuss memory/time trade-offs.

Sample Answer

Approach:Use a Trie where each node stores:- children map- is_word flag- optionally word and score- a fixed-size min-heap (or sorted list) of top-K entries for that subtree (store (score, word) with score positive; min-heap keeps smallest at root so we evict lowest when >K). On insert, walk the trie and update each node's top-K structure.

This lets suggest(prefix, k) reach the node for prefix in O(|prefix|) and return its top-K in O(k log k) (or O(k) if maintained sorted).

Code (supports variable k per query by storing up to global_K at nodes — choose a reasonable max_K like 50):

python

import heapq
from typing import Dict, List, Tuple

class TrieNode:
    def __init__(self, max_k):
        self.children: Dict[str, TrieNode] = {}
        self.is_word = False
        self.word = None
        self.score = 0
        self.max_k = max_k
        # min-heap of (score, word). We keep size <= max_k
        self.topk: List[Tuple[int, str]] = []

    def push_topk(self, score, word):
        entry = (score, word)
        if len(self.topk) < self.max_k:
            heapq.heappush(self.topk, entry)
        else:
            # replace smallest if new score better or tie but lexicographically smaller not required
            if entry > self.topk[0]:
                heapq.heapreplace(self.topk, entry)

class AutocompleteTrie:
    def __init__(self, max_k=50):
        self.root = TrieNode(max_k)
        self.max_k = max_k

    def insert(self, word: str, score: int):
        node = self.root
        node.push_topk(score, word)
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode(self.max_k)
            node = node.children[ch]
            node.push_topk(score, word)
        node.is_word = True
        node.word = word
        node.score = score

    def suggest(self, prefix: str, k: int) -> List[Tuple[int, str]]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        # node.topk is a min-heap; to return descending scores, sort descending
        items = sorted(node.topk, key=lambda x: (-x[0], x[1]))
        return items[:k]

Key points:- Maintaining top-K at each node makes suggest O(|prefix| + k log k) to sort/format.- Insert cost: O(|word| * log K) because at each node we push/replace in heap.- Space: additional O(N * K) for storing top-K across nodes in worst case (N = total nodes). That can be large.

Trade-offs:- Pros: Very fast suggestions, simple to implement, good for read-heavy systems.- Cons: High memory overhead; updates (insert/score changes) are more expensive since you must update all ancestor nodes' heaps. Deleting or decreasing score is tricky — may require re-computing top-K for affected nodes or using more complex data structures (balanced BSTs, skip lists, or storing references to entries).- Alternatives: Don't store top-K per node; instead, on suggest, traverse subtree and use a heap to collect top-K — saves memory but costs time (O(nodes_in_subtree + log k)). Or store inverted index of prefixes to candidates (more memory but faster retrieval). For dynamic score updates, consider maintaining a global mapping and storing pointers in node buckets with lazy re-heapifying.

Edge cases:- Choose max_k >= maximum requested k. If query k > stored max_k, either increase stored K (rebuild) or perform a subtree search at query time.- Ties in score — break deterministically (lexicographic).- Large vocabulary: consider compressing trie (radix trie) or sharding by prefix.

MediumTechnical

83 practiced

Implement the Knuth-Morris-Pratt (KMP) substring search algorithm in Python: given pattern P and text T, return starting indices of occurrences of P in T. Provide the prefix-function (lps) computation and the matching loop, and explain why KMP runs in O(n+m) time. Give example T='ababcababa', P='aba' -> [0,2,5,7] (overlapping allowed).

Sample Answer

To solve this, compute the prefix-function (lps) for pattern P where lps[i] is the length of the longest proper prefix of P[:i+1] that is also a suffix. Use lps to avoid re-checking characters when a mismatch occurs during the scan of text T.

python

def compute_lps(P):
    n = len(P)
    lps = [0]*n
    length = 0  # length of previous longest prefix suffix
    i = 1
    while i < n:
        if P[i] == P[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]  # fallback
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(T, P):
    if not P:
        return list(range(len(T)+1))  # empty pattern occurs at every position
    lps = compute_lps(P)
    res = []
    i = j = 0  # i -> index in T, j -> index in P
    while i < len(T):
        if T[i] == P[j]:
            i += 1; j += 1
            if j == len(P):
                res.append(i - j)
                j = lps[j-1]  # allow overlapping matches
        else:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    return res

# Example
# T='ababcababa', P='aba' -> [0,2,5,7]

Key points:- compute_lps preprocesses P in O(m) time.- The search scans T once, using lps to shift pattern without backtracking characters => O(n).- Overall time O(n + m), space O(m) for lps.Edge cases: empty pattern, pattern longer than text, repeated characters in pattern (handled by lps).

Unlock Full Question Bank

Get access to hundreds of Algorithms and Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.