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

88 practiced

Design an algorithm to compute pairwise Pearson correlation coefficients between many feature vectors efficiently on GPU when the number of features is large and cannot fit full pairwise matrix in memory. Discuss blocking, streaming dot-product computation, numerical stability for mean/variance, and how to exploit BLAS routines. Provide pseudocode for blocked computation.

Sample Answer

High-level approach:- Compute Pearson r(i,j) = cov(xi,xj) / (σ_xi * σ_xj). We stream features in column blocks that fit GPU memory, compute means/variances with numerically-stable one-pass (Welford) per column, then compute blockwise dot-products (covariances) using BLAS GEMM on centered columns. Accumulate partial covariance tiles to avoid storing full NxN matrix.

Pseudocode (blocked, GPU-friendly):

python

# A: M x N matrix (M samples, N features) stored on host.
# Bsize: number of feature columns per block that fit GPU memory

# Step 1: compute mean and variance for every column using streaming Welford on CPU/GPU
means = zeros(N)
vars = zeros(N)
counts = 0
for each column_block in stream_columns(A, Bsize):
    # move block to GPU
    block = upload_gpu(column_block)  # M x b
    # Welford per column implemented on GPU kernel or use cuBLAS reduction
    block_means, block_vars = welford_reduction(block)
    update_global_welford(means, vars, counts, block_means, block_vars, b)
    counts += M

# Step 2: blocked covariance via centered GEMM
# We'll compute upper-triangular tiles only and stream results to disk/host
for i_block in range(0, N, Bsize):
    Xi = upload_gpu(get_columns(A, i_block, Bsize))  # M x bi
    center_columns_inplace(Xi, means[i_block:i_block+bi])  # subtract means
    scale_columns_inplace(Xi, 1.0)  # keep unscaled for covariance
    for j_block in range(i_block, N, Bsize):
        Xj = upload_gpu(get_columns(A, j_block, Bsize))  # M x bj
        center_columns_inplace(Xj, means[j_block:j_block+bj])
        # Use GEMM: C = Xi^T * Xj  => bi x bj matrix of dot-products
        C = gemm(transpose(Xi), Xj)  # uses cuBLAS for high throughput
        # Normalize to covariance: cov = C / (M - 1)
        # Convert to Pearson r using precomputed stddevs
        for p in range(bi):
            for q in range(bj):
                denom = sqrt(vars[i_block+p] * vars[j_block+q])
                r = (C[p,q] / (counts - 1)) / denom if denom > 0 else 0
                write_output_tile(i_block+p, j_block+q, r)
        free_gpu(Xj)
    free_gpu(Xi)

Key details and rationale:- Numerical stability: Welford/online algorithm avoids catastrophic cancellation when computing mean/variance across large M and streaming blocks. Compute variances with double precision if possible.- Blocking & memory: Blocks sized to maximize GPU occupancy while leaving room for temporary buffers and GEMM workspace. Compute only upper triangle and stream results to host or disk.- Exploit BLAS: Use cuBLAS GEMM for dot-products (Xi^T * Xj) which is far faster than element-wise kernels. Use batched GEMM when blocks are further split.- Streaming: Read features from storage in column-major chunks; overlap data transfers with compute using CUDA streams: while GEMM runs on block i, prefetch next block j.- Parallel reduction: When centering, use cuBLAS/Thrust reductions; center in-place to avoid extra copies.- Numerical types: Use FP32 for inputs if performance-critical, but compute means/vars and GEMM in FP32 with accumulation in FP64 if supported (Tensor cores/mixed precision) to reduce error.- Complexity: Each GEMM computes bi*bj entries with cost O(M*bi*bj); overall roughly O(M*N^2 / Bsize) GPU flops but memory I/O bound if M small.

Edge cases:- Features with zero variance -> define r=0 or NaN per policy.- Extremely large M: compute means/vars in multiple passes if necessary, but Welford handles streaming.- Sparse features: convert to sparse-dense strategy to exploit sparsity for speed/memory.

This pattern yields a scalable, numerically-stable GPU implementation that maximizes BLAS throughput while avoiding storing full NxN matrix in memory.

MediumTechnical

103 practiced

Scenario: your team needs a feature-store data structure to serve millions of sparse categorical features with low-latency reads and occasional writes. Choose among hash tables, sorted arrays (B+-tree), compressed sparse row (CSR), and an on-disk key-value store. For each option, explain algorithmic access patterns, memory layout, concurrency model, eviction policy, and why you would pick one for serving high-QPS model inference.

Sample Answer

Requirements clarification: low-latency reads at high QPS, millions of sparse categorical keys, occasional writes (updates/inserts), memory budget likely constrained, strong concurrency, and simple eviction (LRU/TTL) acceptable.

Hash table- Access pattern: O(1) expected point-lookup; good for random sparse keys.- Memory layout: open-addressing or chained buckets; open-addressing has better cache locality but needs load-factor control; chaining uses pointers (more memory).- Concurrency: lock sharding or lock-free (atomic CAS) per bucket for reads; reads can be mostly lock-free if updates are rare.- Eviction: maintain auxiliary LRU or TTL index; integrating LRU into concurrent hash is moderate complexity.- Suitability: Excellent for ultra-low read latency and high QPS when dataset fits RAM.

Sorted array / B+-tree- Access pattern: O(log n) lookups; range scans efficient.- Memory layout: nodes/pages optimized for disk/CPU cache; pointers and node overhead.- Concurrency: mature algorithms (latches, optimistic concurrency), more complex to scale for many readers.- Eviction: natural for on-disk B+-tree with caching layer; need cache for hot keys.- Suitability: Overkill for point-read dominated inference; higher lookup latency than hash.

Compressed Sparse Row (CSR)- Access pattern: best for dense access patterns on vectorized indices (range or batched), not random single-key lookup.- Memory layout: compact arrays of indices and values; excellent memory density.- Concurrency: read-only CSR is trivial and lock-free; updates are expensive (rebuild/append).- Eviction: hard; CSR is static unless rebuilt.- Suitability: If features are stored as sparse vectors and read in large batches, CSR is efficient; not ideal for frequent point updates or random single-key reads.

On-disk key-value store (RocksDB/Redis-on-disk)- Access pattern: higher latency due to I/O unless cached; good persistence.- Memory layout: SSTables/WAL; caching layer (block cache) critical.- Concurrency: built-in multi-threading and durability guarantees.- Eviction: usually configurable (LRU caches); cold keys evicted from memory to disk.- Suitability: Good for datasets larger than RAM or when persistence matters; higher tail latency unless fronted by an in-memory cache.

Recommendation for high-QPS model inference- Primary: in-memory sharded hash table (open-addressing or hopscotch) with lock-free reads and sharded write locks. Keep load factor <= 0.7, use 64-bit keys and compact value encoding. Maintain a small LRU/TTL metadata structure per shard for eviction.- Secondary: back this with an on-disk KV (RocksDB) as source-of-truth for cold keys and for asynchronous writes. Populate hot-key cache proactively (warm-up) and use batching for writes to reduce contention.Rationale: Hash tables give lowest consistent lookup latency and best CPU cache behavior for millions of sparse keys; pairing with an on-disk store covers durability and capacity without affecting hot-path latency.

HardTechnical

103 practiced

Describe algorithms for k-means clustering when data cannot fit in memory: explain streaming/minibatch k-means and provide pseudocode for the minibatch update step. Discuss convergence guarantees, learning rate schedules, and initialization strategies like k-means++ in the streaming context.

Sample Answer

When data doesn’t fit in memory, use streaming/minibatch variants of k-means that update centroids incrementally instead of recomputing distances over the whole dataset each iteration.

Approach summary:- Streaming k-means: read points one-by-one (or small chunks), update nearest centroid using an online update (exponential or averaged).- Mini-batch k-means: sample small random batches repeatedly; for each batch compute assignments and perform small online updates — much cheaper per iteration and often converges faster in wall-clock time.

Minibatch update pseudocode (Python-style):

python

# centroids: k x d array
# counts: k-length array of effective counts (for averaging)
# batch: b x d array of points
# eta_schedule(i, n_i): returns learning rate for i-th centroid, optionally using counts

for x in batch:
    j = argmin_j ||x - centroids[j]||^2            # assign
    counts[j] += 1
    eta = eta_schedule(j, counts[j])              # e.g., 1/counts[j] or alpha/(alpha+counts[j])
    centroids[j] = (1 - eta) * centroids[j] + eta * x

Learning rate schedules and rationale:- eta = 1 / n_j (where n_j is number of points assigned to centroid j) yields empirical-running-average convergence to sample mean for that cluster; behaves like stochastic approximation (Robbins–Monro).- Use eta = alpha / (alpha + n_j) to stabilize early larger steps (alpha ~ 10-100).- Constant small eta can track nonstationary data streams.

Convergence guarantees:- Full-batch k-means has monotonic decrease in objective and converges to a local minimum in finite steps.- Mini-batch/streaming methods are stochastic approximation algorithms; they lack finite-step guarantees but under Robbins–Monro conditions (sum eta_t = inf, sum eta_t^2 < inf) they converge almost surely to a stationary point of the expected objective. In practice, they reach good local minima faster but may oscillate; decreasing learning rates reduce oscillation.

Initialization strategies in streaming:- k-means++ improves final quality by spreading seeds; for streaming: - Use an initial reservoir sample (size m) from the stream, run k-means++ on that sample to initialize centroids. - Online k-means++ (streaming k-means++) variants use weighted sampling: maintain summary (e.g., coresets) and apply D^2 sampling on summary points. - Practical: run a single pass with reservoir sampling (m ~ 10k), apply k-means++ then switch to minibatch updates.

Practical tips:- Use mini-batch size 256–4096 depending on memory/IO.- Maintain per-centroid counts or exponential decay for drifting data.- Periodically recompute exact centroids using accumulated assignments or run a short full-batch refinement on a representative coreset.- Monitor inertia and silhouette on held-out sample to detect poor convergence or need for reinitialization.

MediumTechnical

100 practiced

Implement Disjoint Set Union (Union-Find) with path compression and union by rank in Python. Provide functions find(x) and union(x, y). Explain amortized time complexity and an example use-case in clustering or Kruskal's MST for ML feature graphs.

Sample Answer

To implement Disjoint Set Union (Union-Find) with path compression and union by rank, we store parent pointers and a rank (approximate tree height). find(x) compresses path by making visited nodes point directly to root. union(x, y) attaches the lower-rank root under the higher-rank root (tie: increment rank).

python

class UnionFind:
    def __init__(self, n):
        # parents[i] = parent of i; initially itself
        # rank[i] = upper bound on tree height
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # iterative path compression
        while x != self.parent[x]:
            # path-halving: point x to its grandparent
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already in same set
        # union by rank: attach smaller rank under 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
        return True

Key points:- Path compression + union by rank yields nearly-constant amortized time: inverse-Ackermann α(n), effectively O(1) for all practical n.- Use-case: In Kruskal's MST for feature-graph construction (e.g., building a graph connecting similar data points), sort edges by weight and union endpoints if they are in different sets to avoid cycles; this produces an MST used for manifold learning or hierarchical clustering.- For clustering: use DSU to form components by connecting edges below a threshold; components = clusters. Edge cases: initialize size correctly, handle dynamic labeling (map items to indices).

MediumTechnical

80 practiced

Implement Tarjan's algorithm in Python to find articulation points (cut vertices) and bridges in an undirected graph. Provide code or detailed pseudocode, explain the discovery time and low-link values concept, and state the time complexity.

Sample Answer

To find articulation points and bridges in an undirected graph we use Tarjan's DFS-based algorithm. We assign each node a discovery time (tin) when first visited and maintain a low-link value (low) equal to the earliest discovery time reachable from that node via DFS tree edges + at most one back-edge. A node u is an articulation point if (1) u is root of DFS and has >1 child, or (2) u is not root and some child v has low[v] >= tin[u]. An edge (u,v) is a bridge if low[v] > tin[u] (v is in u's subtree and cannot reach u or ancestors).

Python implementation (adj list; nodes 0..n-1):

python

from collections import defaultdict

def tarjans_articulation_bridges(n, edges):
    g = defaultdict(list)
    for u,v in edges:
        g[u].append(v); g[v].append(u)

    timer = 0
    tin = [-1]*n
    low = [0]*n
    visited = [False]*n
    articulation = set()
    bridges = []

    def dfs(u, parent):
        nonlocal timer
        visited[u] = True
        tin[u] = low[u] = timer; timer += 1
        children = 0
        for v in g[u]:
            if v == parent: continue
            if visited[v]:
                # back edge
                low[u] = min(low[u], tin[v])
            else:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent is not None and low[v] >= tin[u]:
                    articulation.add(u)
                if low[v] > tin[u]:
                    bridges.append((u, v))
        if parent is None and children > 1:
            articulation.add(u)

    for i in range(n):
        if not visited[i]:
            dfs(i, None)

    return list(articulation), bridges

Key points:- tin[u]: discovery time (DFS order index).- low[u]: smallest tin reachable from u via tree/back edges.- Bridges when low[child] > tin[parent]; articulation when low[child] >= tin[parent] (non-root) or root with multiple children.

Time complexity: O(n + m) where n = nodes, m = edges (each edge considered constant times). Space: O(n + m) for adjacency + O(n) for arrays.

Edge cases:- Disconnected graphs: run DFS from every unvisited node (code handles that).- Parallel edges: may require handling to avoid misclassifying bridges (treat multiedges explicitly).

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.