Fundamental Algorithms and Techniques Questions

Covers core algorithmic concepts and problem solving patterns commonly assessed in technical interviews. Topics include searching algorithms such as binary search; sorting algorithms such as merge sort and quick sort; graph traversal methods such as breadth first search and depth first search; recursion and divide and conquer techniques; greedy heuristics; and dynamic programming including memoization and tabulation. Also includes implementation patterns such as two pointers, sliding window, prefix sums, and divide and conquer composition, as well as practical considerations like in place versus out of place implementations, stability for sorting, recursion stack and memory usage, and amortized analysis. Candidates should be able to implement these algorithms correctly, explain correctness and trade offs, analyze time and space complexity using Big O notation for best case average case and worst case, select appropriate approaches given input constraints, combine patterns to solve composite problems, and optimize or refactor solutions while handling edge cases.

HardTechnical

75 practiced

Given a weighted directed graph, compare Dijkstra vs Bellman-Ford vs Floyd-Warshall for computing shortest paths. For a large sparse graph representing distances between entities in an ML feature graph, which algorithm would you choose and why? Provide complexity analysis and discuss negative edge weights implications.

Sample Answer

High-level comparison- Dijkstra: single-source shortest paths for non‑negative weights. Using a binary heap: O((V + E) log V) ≈ O(E log V) for sparse graphs. With Fibonacci heap: O(E + V log V). Fast in practice, low memory, no handling of negative edges.- Bellman‑Ford: single‑source and supports negative edge weights; detects negative cycles. Time O(V·E), space O(V). Slower, useful when negatives are present or you must detect negative cycles.- Floyd‑Warshall: all‑pairs shortest paths, dynamic programming, handles negative weights (but not negative cycles). Time O(V^3), space O(V^2). Good for dense or small graphs when you need every-pair distances.

Complexities summary- Dijkstra (binary heap): O(E log V) time, O(V) space.- Bellman‑Ford: O(VE) time, O(V) space.- Floyd‑Warshall: O(V^3) time, O(V^2) space.- Johnson (useful hybrid): one Bellman‑Ford O(VE) + V Dijkstras O(V·(E log V)) → good for sparse graphs when all-pairs needed and no negative cycles.

Recommendation for a large sparse ML feature graph- If edge weights are non‑negative and you need distances from one or a few sources: use Dijkstra with a binary heap (or optimized priority queue). It’s fast (O(E log V)), memory-light, and practical at scale.- If you need all‑pairs on a large sparse graph: use Johnson’s algorithm (Bellman‑Ford once to reweight, then V Dijkstras). It asymptotically and practically outperforms Floyd‑Warshall on sparse graphs.- If negative weights exist: - If single-source: Bellman‑Ford (detects negative cycles). - If all‑pairs and negatives but no negative cycles: Johnson’s algorithm is preferable to Floyd‑Warshall for large sparse graphs.- If negative cycles exist and meaningful for the application, you must handle or eliminate them (Bellman‑Ford detects cycles; distances are undefined otherwise).

Practical notes for ML systems- Prefer Dijkstra for runtime efficiency and memory. Use sparse graph representations (adj lists), vectorized batch queries, and approximate nearest‑neighbor or pruning if exact all‑pairs distances are unnecessary.- Benchmark on real data; choose Johnson only if many sources required and graph is sparse but contains negative edges (or use domain fixes to avoid negatives).

MediumTechnical

62 practiced

Design an algorithm to maintain the median of a sliding window over an integer stream of fixed size w. Provide a data structure approach (e.g., two heaps) and discuss how to handle deletions efficiently, time/space complexity, and practical considerations for anomaly detection in real-time ML pipelines.

MediumTechnical

119 practiced

Given a directed graph, write a Python function to detect if it contains a cycle using DFS and node coloring (white/gray/black). Explain why this detects back-edges and where cycle detection fits in ML pipelines (e.g., validating feature dependency graphs).

Sample Answer

To detect a cycle in a directed graph we can run DFS with node coloring: white = unvisited, gray = visiting (on recursion stack), black = finished. A back-edge is found when DFS sees a neighbor colored gray — that means there's an edge from a node to one of its ancestors, which is exactly a directed cycle.

python

def has_cycle(graph):
    """
    graph: dict[node] -> list of neighbor nodes (directed)
    Returns True if graph contains a directed cycle.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}

    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, []):
            if color.get(v, WHITE) == GRAY:
                return True  # back-edge -> cycle
            if color.get(v, WHITE) == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE and dfs(node):
            return True
    return False

Key points:- Back-edge detection: encountering a gray neighbor indicates an ancestor in current call stack → cycle.- Time: O(V + E); Space: O(V) for color map and recursion stack.- Edge cases: nodes with no outgoing edges, disconnected components, missing nodes in dictionary (handled with get()).

Where this fits in ML pipelines:- Validate directed acyclic graphs (DAGs) for feature/transform dependencies, dataflow jobs, and DAG-based schedulers (Airflow). Catching cycles early prevents infinite loops, incorrect feature computation order, and deployment failures.

MediumTechnical

90 practiced

Explain the 0/1 Knapsack problem and contrast full DP solution vs a greedy approximation. Provide a scenario in ML engineering where a greedy approach might be acceptable (e.g., pruning features under strict latency) and where exact DP is necessary (e.g., constrained resource allocation). Outline implementations and complexity trade-offs.

Sample Answer

The 0/1 Knapsack problem: given n items each with value v_i and weight w_i, and a capacity W, choose a subset (each item at most once) to maximize total value without exceeding W. It’s NP-hard in general but solvable exactly with pseudo-polynomial dynamic programming.

Full DP solution (exact):- Approach: DP[i][c] = max value using first i items with capacity c. Recurrence: DP[i][c] = max(DP[i-1][c], DP[i-1][c-w_i] + v_i) if c>=w_i.- Implementation sketch: 1D array of length W+1 rolling over items (iterate items outer, capacities descending).- Complexity: Time O(nW), Space O(W). Guarantees optimality but cost grows with capacity (pseudo-polynomial).

Greedy approximation:- Approach: sort items by value/weight ratio (v_i/w_i) and pick highest ratios until capacity filled. Works optimally for fractional knapsack, not 0/1.- Complexity: O(n log n) for sort, O(n) selection, low memory.- Trade-off: Fast and simple but can be arbitrarily suboptimal for 0/1 cases (counterexamples exist).

ML engineering scenarios:- Greedy acceptable: Real-time feature pruning in a low-latency inference pipeline where each feature has an importance score and cost (latency). Under strict per-request budget, selecting top importance-per-cost features quickly (greedy) minimizes latency with minimal engineering overhead; occasional suboptimality is tolerable if empirical A/B tests show negligible accuracy loss.- Exact DP necessary: Constrained resource allocation for on-device model compilation where energy or memory budgets are tight and misallocation causes failures (e.g., selecting quantized submodules to fit in flash). Here optimal selection avoids costly re-deployments; DP ensures maximum utility within hard constraints.

Practical notes:- If W and n are moderate, use DP for guarantees. If W huge or decisions must be instantaneous, use greedy or heuristic (greedy + local search, knapsack FPTAS gives (1-ε)-approx with time O(n^3 / ε)).- Combine: run greedy to get upper/lower bounds and apply DP on reduced candidate set (prune low-ratio items) to balance speed and optimality.

HardTechnical

65 practiced

Explain median-of-medians selection algorithm that achieves worst-case O(n) time. Provide a high-level description and sketch of proof for linear time, and discuss practicality vs randomized Quickselect in ML systems that require strict upper bounds on latency.

Unlock Full Question Bank

Get access to hundreds of Fundamental Algorithms and Techniques interview questions and detailed answers.

Join thousands of developers preparing for their dream job.