Algorithm Design and Analysis Questions

Covers algorithmic problem solving and analysis fundamentals required in technical interviews. Topics include common data structures, sorting and searching, recursion and divide and conquer, dynamic programming, greedy strategies, backtracking, graph algorithms such as breadth first search and depth first search, shortest path and topological sort, string algorithms, and techniques for deriving correct and efficient solutions. Candidates should demonstrate ability to reason about correctness, derive time and space complexity bounds using Big O notation, and discuss scalability and optimization trade offs for large inputs.

MediumTechnical

79 practiced

Given coin denominations and a target amount, implement a Python function that computes the minimum number of coins required to make that amount (or -1 if impossible). Use bottom-up dynamic programming and explain time/space complexity. Also discuss the limited-count variant and greedy correctness conditions.

Sample Answer

**Approach (brief)** Use bottom-up DP: dp[a] = minimum coins to make amount a. Initialize dp[0]=0 and dp[1..target]=inf. For each coin and for amount from coin..target update dp[a] = min(dp[a], dp[a-coin]+1). Return -1 if dp[target] is inf.

**Code (Python)**

python

from math import inf

def coin_change(coins, target):
    dp = [inf] * (target + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, target + 1):
            if dp[a - c] != inf:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[target] if dp[target] != inf else -1

# Example
# coins = [1,3,4], target = 6 -> returns 2 (3+3 or 4+1+1)

**Complexity** - Time: O(n * T) where n = number of coin types, T = target. - Space: O(T) for dp array.

**Limited-count variant** If each coin has limited quantity, iterate coins and use binary-splitting of counts (convert count k into sums of powers of two) to transform into multiple 0/1 items, then run 0/1 knapsack style updates (iterate amounts descending). This gives O(T * log k_total) extra factor.

**Greedy correctness conditions** Greedy (take largest coin possible) is correct when coin system is canonical (e.g., US denominations). Sufficient but not necessary conditions: each larger coin is multiple of smaller (canonical when canonical coin systems or when coin set is canonical). Counterexamples exist (like coins [1,3,4], target 6 — greedy picks 4+1+1 =3 but optimal is 3+3=2), so prefer DP unless you can prove canonical property.

MediumTechnical

72 practiced

Implement the prefix function (pi) used in the Knuth-Morris-Pratt (KMP) algorithm in Python, then use it to search for a pattern in a text and return all starting indices. Explain why KMP runs in O(n + m) time and how the pi array helps skip redundant comparisons.

Sample Answer

**Approach (brief)** Compute the prefix (pi) array for pattern P: pi[i] = length of longest proper prefix of P[0..i] that's also a suffix. Then run KMP over text T using pi to avoid rechecking characters; report all starting indices.

**Code**

python

def compute_pi(p):
    n = len(p)
    pi = [0]*n
    j = 0
    for i in range(1, n):
        while j > 0 and p[i] != p[j]:
            j = pi[j-1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
    return pi

def kmp_search(t, p):
    if not p: 
        return list(range(len(t)+1))
    pi = compute_pi(p)
    res = []
    j = 0
    for i, ch in enumerate(t):
        while j > 0 and ch != p[j]:
            j = pi[j-1]
        if ch == p[j]:
            j += 1
            if j == len(p):
                res.append(i - j + 1)  # match start
                j = pi[j-1]
    return res

**Why O(n + m)** Each character of pattern and text is processed with at most a constant number of pointer moves: on mismatch we jump j using pi (never increasing i), so i advances through T once and internal j moves total at most O(n + m). The pi array encodes how far to backtrack in the pattern, letting KMP skip rechecking previously matched prefix characters — avoiding quadratic retries typical of naive search.

**Full-stack note:** This runs fast for client- or server-side substring checks (e.g., input validation, log scanning) and is easy to port to JavaScript for frontend use.

EasyTechnical

73 practiced

Compare quicksort and mergesort: explain average-case and worst-case time complexity, space usage, stability, and in-place characteristics. For a full-stack developer choosing a sort implementation (frontend sort vs backend DB sort), what practical factors (memory, stability, dataset characteristics) influence the choice?

MediumTechnical

87 practiced

Implement Kahn's algorithm in Python to produce a topological ordering of a directed graph given as an adjacency list. If the graph contains a cycle, detect it and return an error. Explain time/space complexity and practical applications (e.g., build systems, task scheduling).

Sample Answer

**Approach (brief)** Use Kahn’s algorithm: compute in-degrees, enqueue nodes with in-degree 0, repeatedly remove and reduce neighbors’ in-degrees. If output size != node count, a cycle exists.

python

from collections import deque, defaultdict

def kahn_topological_sort(adj):
    """
    adj: dict/node -> list of neighbors (adjacency list)
    returns: list of nodes in topological order or raises ValueError on cycle
    """
    # compute in-degrees
    indeg = defaultdict(int)
    for u in adj:
        indeg[u] += 0
        for v in adj[u]:
            indeg[v] += 1

    q = deque([n for n, d in indeg.items() if d == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != len(indeg):
        raise ValueError("Graph has at least one cycle; topological ordering not possible")
    return order

**Complexity** - Time: O(V + E) — visit each node and edge once. - Space: O(V + E) — adjacency plus in-degree storage and queue.

**Edge cases** - Disconnected graph (works), nodes with no outgoing edges (ensure present in adj or added with empty list), empty graph.

**Practical applications (Full-Stack view)** - Build systems (compile dependency ordering), task scheduling (background jobs with dependencies), DB migrations (ordering migration scripts), frontend asset bundling (module load order). Kahn’s algorithm is deterministic, simple to implement, and fits well in backend services that compute dependency graphs.

EasyTechnical

96 practiced

Describe how to preprocess an integer array to answer range-sum queries [l, r] in O(1) time. Implement preprocess(arr) and rangeSum(l, r) in Python and explain how to handle updates to array elements (discuss Fenwick tree / Binary Indexed Tree or Segment Tree trade-offs).

Sample Answer

**Approach (brief)** Build a prefix-sum array so any range sum [l, r] is prefix[r+1] - prefix[l] in O(1). For mutable arrays use a Fenwick (BIT) or Segment Tree to get O(log n) updates and queries.

**Code (Python)**

python

# Preprocess: build prefix sums
def preprocess(arr):
    # prefix[i] = sum of arr[0:i]
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i+1] = prefix[i] + v
    return prefix

# Query: O(1)
def rangeSum(prefix, l, r):
    if l < 0 or r >= len(prefix)-1 or l > r:
        raise IndexError("invalid range")
    return prefix[r+1] - prefix[l]

**Complexity**- Preprocess: O(n) time, O(n) extra space- rangeSum: O(1) time

**Handling updates**- If array is immutable or updates are rare: rebuild prefix in O(n) after updates.- If frequent updates: use Fenwick Tree (Binary Indexed Tree) or Segment Tree. - Fenwick: O(log n) update, O(log n) prefix sum, simpler and lower constant factors; efficient for point updates + prefix/range queries. - Segment Tree: O(log n) update/query, supports more complex queries (min/max, range updates with lazy propagation) at the cost of more code and memory.- Trade-off: choose Fenwick for simplicity/performance on sums; choose Segment Tree if you need range updates or other associative operations.

Unlock Full Question Bank

Get access to hundreds of Algorithm Design and Analysis interview questions and detailed answers.

Join thousands of developers preparing for their dream job.