Algorithmic Problem Solving Questions

Evaluates ability to decompose computational problems, design correct and efficient algorithms, reason about complexity, and consider edge cases and correctness. Expectation includes translating problem statements into data structures and algorithmic steps, justifying choices of approach, analyzing time and space complexity, optimizing for constraints, and producing test cases and proofs of correctness or invariants. This topic covers common algorithmic techniques such as sorting, searching, recursion, dynamic programming, greedy algorithms, graph traversal, and trade offs between readability, performance, and maintainability.

HardSystem Design

76 practiced

Design a high-throughput, low-latency system to deduplicate JSON log events arriving as a distributed stream at tens of millions per minute across multiple regions. Provide algorithmic choices for deduplication within time windows (exact hash sets vs probabilistic structures), state-management strategies (local vs centralized), and discuss fault tolerance, bounded-memory behavior, and realistic consistency guarantees.

Sample Answer

Requirements & constraints:- Ingest tens of millions/min across regions, low-latency (<100s ms) dedupe within sliding/ tumbling time windows (e.g., 5–60 min), bounded memory, survive node failures, and provide practical consistency (no lost business-critical events).

High-level architecture:- Ingestion: regional Kafka clusters (or Kinesis) with partitioning by dedupe key (event ID or canonicalized hash) to route duplicates to same shard.- Stream processing: stateful stream processors (Flink or Kafka Streams) running per-region with keyed state (RocksDB backend) and checkpointing to durable storage (S3/GCS).- Optional central store for cross-region coordination: geo-replicated Redis/Scylla with strong regional reads and async cross-region replication for rare cross-region dedupe.

Deduplication algorithm choices:1. Exact set (hash set in state): store canonicalized event-id -> first-seen timestamp. Pros: zero false positives; cons: memory heavy. Use when correctness critical.2. Probabilistic structures: - Bloom filter / counting Bloom: tiny memory, configurable false-positive rate (no false negatives). Use for best-effort dedupe (analytics). - Cuckoo filter: supports deletions (for sliding windows) with better space/throughput. - HyperLogLog is wrong class (cardinality only).Recommendation: use Cuckoo/Counting Bloom per-key window when memory constrained and occasional false positives are acceptable; otherwise exact hashed set with eviction.

State management & bounded-memory:- Keyed local state per processing task (RocksDB) with TTL eviction: keep only entries within window + grace period. Compact/merge small events, persist checkpoints frequently.- Use windowing: tumbling or sliding windows to bound state. Evict by time (event-time watermark).- For probabilistic filters: periodically rotate filters per-window (double-buffering) and discard old ones to bound memory.

Fault tolerance & consistency:- Use exactly-once semantics where possible: Flink’s two-phase commit + Kafka transactional sinks to avoid duplicates on retry. Checkpointing frequency trades off latency.- For local-state approach: rely on durable checkpoints & leader-rebalance; on failure, restored state maintains dedupe history up to last checkpoint (some duplicates may be reprocessed if failure between checkpoint and crash — choose at-least-once vs exactly-once accordingly).- Centralized store option gives stronger cross-instance dedupe (consistent view), but increases latency and must be sharded, replicated, and backed by circuit-breakers/cache.

Practical trade-offs:- If business requires strict no-duplicates for small subset, route those events to exact-path (stronger resources). Bulk analytics can use probabilistic path.- Tune Bloom false-positive rate p via m = -n ln p / (ln2)^2; choose p small (0.01–0.001) for acceptable loss.- Use canonicalization + cryptographic hash (SHA-256 truncated) as dedupe key to avoid collisions.

Operational notes:- Monitor filter false-positive rate, state size, checkpoint lag.- Run chaos tests for failover; size RocksDB and checkpoint intervals for recovery-time SLA.- Provide metrics & backfill path: persist raw stream for reprocessing if dedupe logic later found too aggressive.

This design balances throughput, latency, and bounded memory by combining partitioned local state, windowed eviction, and probabilistic/exact choices depending on business correctness needs.

MediumTechnical

79 practiced

Given a large list of items and integer k, implement top_k_frequent(items, k) in Python that returns the k most frequent elements. Discuss trade-offs between hashmap+heap, quickselect over counts, and streaming/distributed approaches (Misra-Gries, Count-Min, map-reduce). Provide sample code for the in-memory approach.

Sample Answer

To solve top_k_frequent(items, k) in-memory, the simplest robust approach is: (1) count frequencies with a hashmap, (2) use a min-heap of size k to keep top k by frequency. That is O(n log k) time and O(m) space for counts (m = distinct items). Below is sample Python code and then trade-offs vs quickselect and streaming/distributed methods.

python

import heapq
from collections import Counter
from typing import List, Any, Tuple

def top_k_frequent(items: List[Any], k: int) -> List[Any]:
    """
    Return k most frequent elements. Uses hashmap + min-heap.
    Time: O(n + m log k) ~ O(n log k) worst-case
    Space: O(m + k)
    """
    if k <= 0:
        return []
    counts = Counter(items)  # O(n)
    # min-heap of (freq, item); keep size <= k
    heap: List[Tuple[int, Any]] = []
    for item, freq in counts.items():  # m iterations
        if len(heap) < k:
            heapq.heappush(heap, (freq, item))
        else:
            if freq > heap[0][0]:
                heapq.heapreplace(heap, (freq, item))
    # extract items sorted by descending freq
    return [item for freq, item in sorted(heap, key=lambda x: -x[0])]

Key points and trade-offs:- Hashmap + heap: simple, stable memory for counts, best for moderate distinct cardinality. Good when k << m.- Quickselect on counts: compute list of (item, freq) then quickselect by freq to find kth threshold and filter — average O(m) time and O(m) space. Faster when m is much smaller than n and you can afford full distinct list; worst-case O(m^2) without random pivot.- Streaming / distributed (for massive data or real-time): - Misra-Gries (a.k.a. Frequent algorithm): deterministic, uses O(k) counters to return approximate top-k candidates with bounded error; great for single-pass streaming when memory limited. - Count-Min Sketch: probabilistic, sublinear space, point-estimates of counts with tunable error and confidence. Use for heavy-hitter detection but needs post-filtering to remove false positives. - MapReduce: map -> emit (item,1), shuffle aggregate sums, reduce to counts, then either sort or use partial top-k in each mapper to reduce network. Scales to huge datasets but has higher latency and operational cost.Edge cases:- k > number of distinct items: return all distinct- empty items list or k <= 0: return []- ties: heap approach returns arbitrary tie order; sort tie-breaker can be added if deterministic order required.

Choose method based on data size, distinct cardinality, memory, latency, and error tolerance.

HardTechnical

78 practiced

Design and describe a randomized SVD algorithm (randomized range finder) to compute the top-k singular vectors of a very large sparse matrix (e.g., 10M x 1M). Explain random projection dimension, oversampling, power iterations, orthonormalization, and how to exploit sparsity and streaming I/O constraints.

Sample Answer

Approach summary:Use the randomized range finder to approximate the top-k SVD of A (size m×n, very large & sparse). Draw a small random test matrix Ω, form Y = A Ω, orthonormalize Y to get Q, compute B = Qᵀ A (small), then SVD(B) and map back: U ≈ Q U_B. Choose parameters l = k + p (oversampling), and optionally apply q power iterations to improve spectral decay.

Algorithm (high level):1. Choose k (target), p (oversampling 10–20), set l = k + p. Choose q (0–2 typical; larger if spectrum decays slowly).2. Draw Ω ∈ R^{n×l} (Gaussian or structured random like SRHT / sparse sign).3. For i = 0..q: - Compute Y = A (Aᵀ ( ... (A Ω) ... )) performing q extra multiplies (power iterations). Use orthonormalization between multiplications (see next).4. Orthonormalize columns of Y → Q (tall-skinny QR).5. Compute small B = Qᵀ A (size l×n) — stream over A’s rows/blocks to compute B without holding A in memory.6. Compute SVD(B) = U_B Σ Vᵀ; set U = Q U_B; return top-k components.

Key choices and why:- Oversampling p: p≈10–20 reduces failure probability and stabilizes subspace when spectra have close singular values. l=k+p ensures with high probability the top-k subspace is captured.- Power iterations q: amplifies separation between top singular directions and the tail, reducing approximation error from O(σ_{k+1}) to O((σ_{k+1}/σ_k)^{2q+1}). Use q=1–2 if necessary; each q costs two extra sparse matvecs (A and Aᵀ).- Orthonormalization: Use stable QR (Householder or TSQR) after initial Y and after each multiply in power iterations to avoid numerical instability and loss of orthogonality.- Random projection choice: For extremely large n, use structured random matrices (SRHT) or sparse Random Sign / CountSketch to reduce cost of forming Ω and improve cache performance. Gaussian is simplest and robust.

Exploiting sparsity and streaming I/O:- Compute Y = A Ω using sparse matrix–dense matrix multiply (SpMM). With A stored in CSR/CSC or distributed, process row/column blocks so only chunks are read into memory.- For B = Qᵀ A, stream A in row-blocks: for each block A_block, accumulate B += Q_blockᵀ A_block. This is I/O-efficient: single pass over A for formation of Y, and one more pass for B (or combined with power iterations).- Use block/mini-batch matvecs to utilize BLAS GEMM on dense blocks while reading sparse slices.- For very large m (10M), keep Q in memory as tall-skinny (m×l) — l small (e.g., few hundreds). If Q itself is too big, store Q in distributed FS and perform TSQR or use out-of-core QR (merge R factors).- Use streaming TSQR: compute local QR per partition, collect R’s, compute global QR on small R's.

Complexity and trade-offs:- Dominant cost: (2q+1) sparse SpMMs of cost O(nnz(A) l). Memory: O((m+n) l) for Q and intermediate B, small when l ≪ n,m.- Trade-offs: larger p reduces error but increases cost; larger q improves accuracy for clustered spectra but doubles matvec cost per iteration and requires Aᵀ access.

Practical tips:- Pre-scale/center columns if needed (streaming mean subtraction).- Use double precision for stability during power iterates.- Validate by computing residuals ||A - U_k Σ_k V_kᵀ|| on a small sample or via Hutchinson trace estimates.- If single-pass required (streaming), use single-pass randomized algorithms (no power iterations) with larger p and structured random projections, accepting lower accuracy.

This approach yields an accurate, scalable top-k SVD suitable for very large sparse matrices while respecting I/O and memory limits.

MediumTechnical

89 practiced

Implement a UnionFind (Disjoint Set Union) class with union and find operations, optimized by union-by-rank and path compression. Provide complexity analysis (alpha(n) inverse-Ackermann) and show an example use-case such as connectivity queries over dynamic edges.

Sample Answer

To implement Disjoint Set Union (UnionFind) with union-by-rank and path compression, keep parent and rank arrays. find uses path compression (attach nodes directly to root). union attaches smaller-rank tree under larger-rank tree; if ranks equal, increment rank of new root. This yields nearly-constant amortized time: O(alpha(n)) per op (inverse-Ackermann).

python

class UnionFind:
    def __init__(self, n):
        # parent[i] = parent of i; rank approximates tree height
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of disjoint sets

    def find(self, x):
        # Path compression: make x point directly to root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected
        # Union by rank: attach smaller tree to larger
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

Key points:- Path compression + union-by-rank gives amortized O(alpha(n)) per operation.- Space O(n).

Edge cases:- Invalid indices (should validate input).- Repeated unions (idempotent).

Example use-case: dynamic connectivity over streaming edges (e.g., social network friendships). For n users, process edge stream and answer connectivity queries:

python

uf = UnionFind(n)
for u,v in edge_stream:
    uf.union(u, v)
# query
uf.connected(a, b)

This scales to millions of users; for offline MST (Kruskal) or clustering tasks, DSU is standard.

MediumTechnical

74 practiced

Implement an LRUCache class in Python supporting get(key) and put(key, value) in O(1) time. Cache has fixed capacity and evicts the least recently used item on overflow. Provide implementation (doubly linked list + hashmap or use OrderedDict) and discuss thread-safety and how you'd apply this in a model-serving scenario where predictions are cached.

Sample Answer

Use a doubly-linked list for recency order and a hashmap for O(1) lookup. The list head is most-recent, tail least-recent. On get/put we move nodes to head; on overflow we remove tail.

python

class Node:
    def __init__(self, k, v):
        self.k = k
        self.v = v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        assert capacity > 0
        self.cap = capacity
        self.map = {}              # key -> Node
        # dummy head/tail to simplify ops
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if not node:
            return -1
        # mark recently used
        self._remove(node)
        self._add_to_head(node)
        return node.v

    def put(self, key, value):
        node = self.map.get(key)
        if node:
            node.v = value
            self._remove(node)
            self._add_to_head(node)
            return
        if len(self.map) >= self.cap:
            # evict LRU (tail.prev)
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]
        new = Node(key, value)
        self.map[key] = new
        self._add_to_head(new)

Key points:- Time: O(1) average for get/put; Space: O(capacity).- Edge cases: capacity=1, updating existing key, get missing key.

Thread-safety:- This implementation is not thread-safe. For multi-threaded access wrap public methods with a lock (threading.Lock) or use finer-grained read-write locking. For multi-process serving, use an external cache (Redis, Memcached) instead of in-process structure.

Applying to model serving:- Cache model predictions by a stable input hash (e.g., serialized features + normalization) to avoid recomputation for repeated requests.- Use TTLs to avoid staleness when model or data drift occurs; include model-version in cache keys for invalidation after redeploy.- For high QPS or multi-node services, use a centralized cache (Redis) to share cached predictions and support persistence and eviction policies.- Monitor hit-rate, size, and latency; guard against caching large objects (store pointers or compressed outputs).

Unlock Full Question Bank

Get access to hundreds of Algorithmic Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.