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.

HardSystem Design

138 practiced

Propose algorithms for computing connected components in a massive graph that doesn't fit on a single machine. Compare distributed BFS/DFS, label propagation, and distributed union-find approaches. Discuss communication cost, convergence, and how you'd partition the graph to minimize cross-partition messages.

Sample Answer

Requirements & constraints:- Find connected components (CC) on a graph too large for one machine; must minimize network I/O, converge quickly, tolerate failures, and produce component IDs for downstream analytics.

High-level options (comparison):1) Distributed BFS/DFS (partitioned, frontier-based)- Approach: run parallel BFS from unvisited seeds; propagate frontier across partitions until all reachable vertices are visited.- Communication: high when frontiers cross partitions; each level requires exchange of boundary messages (synchronous or async).- Convergence: exact in O(diameter) supersteps per component; expensive for high-diameter components.- When to use: small-diameter graphs, or when you need actual traversal order / shortest-path distances too.- Drawbacks: redundant work if many seeds overlap; hard to parallelize across many components efficiently.

2) Label Propagation (LP) / connected-components by iterative id-min propagation (Pregel-style)- Approach: initialize vertex label = vertex id; each superstep each vertex sends its label to neighbors, sets its label to min(received, current). Repeat until labels converge.- Communication: one message per edge per active superstep (can be reduced by sending only on label change). Total messages ≈ O(E * iterations).- Convergence: typically fast in practice (logarithmic in diameter for many graphs), but worst-case O(diameter). Deterministic variant uses min; asynchronous variants converge faster.- Pros: simple, massively parallel, easy to implement on Pregel/Giraph/GraphX. Good for very large graphs.- Cons: communication-heavy for dense graphs; needs many iterations on high-diameter graphs.

3) Distributed Union-Find (disjoint-set) with batching / graph contraction- Approach: perform local union-find within partitions to compress components, then coordinate merges across partitions using boundary edges (exchange representative ids), iteratively compress.- Communication: lower than naive LP because local compression eliminates many edges; cross-partition merges require exchanging representative mappings. If using spanning forests / edge sampling, you can reduce rounds dramatically.- Convergence: often faster in rounds than LP if you aggressively contract; final global compression required (path compression across partitions).- Pros: fewer messages if partitioning yields large local components; exact.- Cons: more complex to implement distributedly (require careful concurrent union/merge protocols), potential coordination bottleneck for merging many components into one.

Partitioning strategies to minimize cross-partition messages:- Edge-cut partitioning: aim to minimize number of boundary edges (METIS, KaHIP) — best when graph is static and pre-partition cost acceptable.- Streaming/heuristic partitioning: for one-pass ingestion (hashing by vertex with heuristics, greedy vertex migration like HDRF) — practical at scale.- Vertex-cut (as in PowerGraph): split high-degree vertices across partitions to balance load; reduces hot-spot messaging for power-law graphs by distributing heavy-degree work, but introduces coordination for replicated vertices.- Community-aware partitioning: if natural communities exist, keep communities together to minimize cross-partition communication.

Communication & convergence trade-offs (summary):- LP: simple, highly parallel, but message-heavy per iteration; asynchronous variants and delta propagation (send only on label change) reduce cost.- BFS-based: fewer total messages for small-diameter components, but many synchronous rounds if diameter large; better when you can start from few seeds.- Union-Find: can dramatically lower messages by contracting locally, but requires careful global merging and coordination.

Practical recommendations for a Data Scientist:- If using an existing cluster framework, prefer label-propagation CC implemented on Spark GraphX or Pregel/Giraph with delta-optimization and asynchronous execution for most large graphs.- For graphs with strong local locality or where preprocessing cost is acceptable, run a METIS-like partitioner then apply distributed union-find to exploit large local components.- For power-law graphs, use vertex-cut frameworks (PowerGraph) to balance load and avoid hotspots.- Add optimizations: compress local components before network exchange, send only changed labels, batch boundary updates, and use approximate early-stopping if exact CC not required for downstream models.- Test on representative graph samples to measure iterations, bytes transferred, and wall-clock time; tune partitioner and algorithm accordingly.

Fault tolerance & operational notes:- Use frameworks with checkpointing (Spark, Flink) or design idempotent merge operations.- Monitor skew (high-degree vertices), network throughput, and iteration counts; instrument with bytes/message metrics to guide partitioning changes.

HardTechnical

74 practiced

You need to engineer features for a categorical variable with millions of distinct values (e.g., user IDs). Discuss encoding strategies (one-hot, target encoding, hashing trick, learned embeddings), data structures for storing encodings for serving (dense tables, hash maps, embeddings), and trade-offs in memory, serving latency, and target leakage during model training.

Sample Answer

Requirements & constraints: clarify model type (tree vs. linear vs. NN), training vs. serving throughput, update frequency of IDs, and privacy/PII rules. These drive choices.

Encoding strategies- One-hot: exact, interpretable for low-cardinality only. Memory explodes (millions dims), sparse storage helps training but inference and most models can’t handle millions of columns.- Target encoding (mean/likelihood): compresses each ID to a scalar (or a few stats). Pros: very compact, fast serving. Cons: severe target leakage if not properly cross-validated (use out-of-fold, time-based folding, or smoothing + prior). Handles unseen IDs via global prior.- Hashing trick: maps IDs into a fixed-size integer space (e.g., 2^20). Pros: controlled memory, no dictionary required, constant-time lookup, simple for linear models and trees. Cons: collisions introduce noise; interpretability lost; needs careful choice of hash size.- Learned embeddings (NN): map IDs to dense vectors learned jointly with model. Pros: powerful for capturing similarity, compact (e.g., 128-dim per ID). Cons: for millions of IDs, embedding table memory is huge; cold/unseen IDs need fallback; training requires special handling for distributed lookup and updates.

Serving data structures- Dense embedding table (matrix): fast O(1) lookup, GPU/CPU memory contiguous. For millions of IDs × 64 dims → memory large (millions*64*4 bytes ~ 256MB per million).- Hash maps (key→small struct or scalar): flexible, good for sparse updates, but higher per-entry overhead and slower than array index.- On-disk stores or remote parameter servers: reduce memory on single host but add network latency; use for very large tables with caching layer.- Hybrid caches: keep hot IDs in RAM (dense table), cold ones use hashed default or on-disk store.

Trade-offs and mitigations- Memory vs. accuracy: larger hash sizes / larger embedding dims reduce collision/info loss but increase memory. Use dimensionality reduction, compressed quantized embeddings (8-bit/16-bit), or product/hashed embeddings.- Serving latency: array-indexed dense tables fastest. Hash maps and remote lookups add latency—mitigate with local LRU cache and batching lookups.- Target leakage: major risk for target encoding and embeddings trained on full dataset. Use K-fold out-of-fold target encoding, time-based splits for temporal data, or holdout counters. For embeddings, avoid training on labels directly if using precomputed embeddings—use separate epochs or implicit feedback-only signals.- Cold/unseen IDs: use global priors, hashed buckets, or "unknown" learned vector. For target encoding use prior-smoothed estimate.- Operational complexity: learned embeddings + distributed parameter servers are powerful but require infra (sharding, consistency, checkpointing). Hashing + target encoding simpler to deploy.

Recommendation pattern- If real-time low-latency and memory-constrained: use hashing trick for feature + small scalar target-encoding statistics (with proper OOF computation).- If model is NN and infra supports it: learned embeddings for frequent IDs, plus a hashed/prior fallback for long tail; use mixed precision / quantization and caching.- Always instrument: monitor hit rates, collision effects, and A/B test encoding strategies. Use privacy-safe aggregation and validate leakage protections.

EasyTechnical

75 practiced

Explain the differences between Big O, Big Theta, and Big Omega notations. Give concrete function examples where the notations differ (e.g., f(n)=n log n vs g(n)=n) and describe when each notation is useful when analyzing algorithms in data-science pipelines such as feature extraction and model training.

MediumTechnical

84 practiced

Write a Python function to detect a cycle in a directed graph using depth-first search and tracking the recursion stack. Explain how back edges indicate cycles and compare this approach with Kahn's algorithm using indegree removal.

Sample Answer

To detect a cycle in a directed graph with DFS + recursion-stack tracking, we mark nodes as: 0=unvisited, 1=visiting (in recursion stack), 2=visited. A back edge is an edge from a node to an ancestor currently in the recursion stack (state 1); its presence means a cycle.

python

from collections import defaultdict

def has_cycle_dfs(edges, n=None):
    """
    edges: iterable of (u, v) directed edges
    n: optional number of nodes (0..n-1). If None, inferred from edges.
    Returns True if graph has a directed cycle.
    """
    g = defaultdict(list)
    nodes = set()
    for u, v in edges:
        g[u].append(v)
        nodes.add(u); nodes.add(v)
    if n is None:
        nodes = list(nodes)
    else:
        nodes = list(range(n))

    state = {}  # node -> 0/1/2

    def dfs(u):
        state[u] = 1  # visiting
        for v in g.get(u, ()):
            s = state.get(v, 0)
            if s == 1:
                return True  # back edge -> cycle
            if s == 0 and dfs(v):
                return True
        state[u] = 2
        return False

    for u in nodes:
        if state.get(u, 0) == 0:
            if dfs(u):
                return True
    return False

Key points:- Back edge: edge to a node currently marked visiting (1) -> cycle because it reaches an ancestor.- Time: O(V+E); Space: O(V) for recursion and state.- Edge cases: disconnected graph, self-loop (detected as back edge), large depth may cause recursion limit.

Comparison with Kahn's algorithm:- Kahn (indegree removal) is iterative: repeatedly remove nodes with indegree 0; if nodes remain, cycle exists. Time/space also O(V+E).- DFS is straightforward, good for recursion-friendly code and detecting cycles on-the-fly; Kahn is better when you also want a topological order and avoids recursion depth issues. Kahn requires computing indegrees up-front and maintains a queue; DFS can be faster memory-wise when graph is streamed.

HardTechnical

89 practiced

Discuss how memory layout (C vs Fortran order), array contiguity, strides, and broadcasting impact performance in NumPy-heavy pipelines. Provide concrete refactoring suggestions (use of views vs copies, in-place ops, blocking) to reduce copies and improve cache efficiency for large matrix operations.

Sample Answer

Situation: In NumPy-heavy pipelines, large matrix ops dominate runtime — memory layout, contiguity, strides and broadcasting determine whether operations use fast vectorized kernels and caches or create expensive temporaries.

Key concepts (brief):- C-order (row-major) stores rows contiguously; Fortran-order (column-major) stores columns contiguously. Strides tell how many bytes to step to get the next element along each axis.- A contiguous array (C or F) enables SIMD/BLAS kernels to stream memory efficiently. Non-contiguous views (e.g., many transposes, slicing with step) have surprising strides and often force copies when passed to low-level libraries.- Broadcasting avoids explicit expansion but can still create temporaries if the broadcast pattern cannot be expressed as a view for a downstream op.

Refactoring suggestions to reduce copies & improve cache efficiency:1. Prefer contiguous layout that matches heavy kernels: - If you call BLAS-heavy ops on A (row-major loops) use C-order; for column-oriented routines or Fortran-ordered libraries use order='F'. - Use np.ascontiguousarray(A) or np.asfortranarray(A) to make a single copy early rather than repeated implicit copies.2. Favor views over copies: - Use slicing and reshape when it preserves contiguity. Check .flags['C_CONTIGUOUS'] / ['F_CONTIGUOUS'] and .strides. - Avoid .T on large arrays if it will trigger a copy later; explicitly choose storage order when creating arrays.3. Use in-place operations whenever safe: - a *= 2, np.add(a, b, out=a) avoids temporaries and reduces memory pressure. - For chained ops, use out= parameters (np.multiply, np.add) rather than a = a*b.4. Avoid broadcasting copies by aligning shapes: - Pre-reshape with views: b = b.reshape(1, -1) rather than b[None,:] if that yields contiguous strides. - If a scalar broadcast will be reused, materialize once with appropriate order: b = np.broadcast_to(b, shape).copy() only if needed repeatedly.5. Blocking / tiling for cache locality: - For very large matrix multiplies when you can’t rely on optimized BLAS, implement block-wise multiplication to fit L1/L2 cache:

python

def blocked_matmul(A, B, block=256):
    n = A.shape[0]
    C = np.zeros((n,n), order='C')
    for i in range(0,n,block):
        for j in range(0,n,block):
            for k in range(0,n,block):
                C[i:i+block,j:j+block] += A[i:i+block,k:k+block] @ B[k:k+block,j:j+block]
    return C

- Use block sizes tuned to CPU caches; ensure sub-blocks are contiguous to exploit streaming loads.6. Use specialized functions to avoid temporaries: - np.einsum can express complex contractions without intermediate allocations when optimized (use optimize=True). - np.dot/np.matmul call BLAS; ensure inputs are contiguous to avoid copies.

Practical checklist:- Inspect .shape, .strides, .flags before heavy ops.- When transposing frequently for computation, create arrays in the needed order up front.- Replace chained expressions with in-place or out= variants.- Profile (line_profiler, memory_profiler) to find hidden copies.

Trade-offs:- Forcing contiguity early costs a single allocation but prevents many repeated implicit copies — often a net win.- In-place ops save memory but mutate data; copy first if you need originals.

This approach minimizes allocation churn, improves cache hits and lets BLAS/SIMD kernels run at native speed.

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.