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

88 practiced

Implement a function in Python that, given an integer array nums and window size k, returns an array of maximum values for each sliding window in O(n) time and O(k) space. Example: nums=[1,3,-1,-3,5,3,6,7], k=3 -> [3,3,5,5,6,7]. Explain why using a deque yields linear time and discuss handling when input is a stream.

Sample Answer

Approach: use a double-ended queue (deque) that stores indices of elements in decreasing order of their values. For each index i, pop from back while nums[i] >= nums[deque[-1]] (maintain decreasing); push i; pop from front if deque[0] is outside the window (i - deque[0] >= k). The front always holds the index of the current window maximum. This is O(n) because each index is pushed and popped at most once.

python

from collections import deque
from typing import List

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    if k == 0 or not nums:
        return []
    if k == 1:
        return nums[:]  # trivial

    dq = deque()  # will store indices, values in decreasing order
    res = []

    for i, val in enumerate(nums):
        # remove indices whose values are <= current value from back
        while dq and nums[dq[-1]] <= val:
            dq.pop()

        dq.append(i)

        # remove indices outside the window from front
        if dq[0] <= i - k:
            dq.popleft()

        # start recording maxima once the first window is complete
        if i >= k - 1:
            res.append(nums[dq[0]])

    return res

Why deque yields linear time:- Each index enters deque once and can be removed at most once (either from back or front). Therefore total operations on deque are O(n), giving overall O(n) time.

Space: O(k) for deque (at most k indices) and O(n-k+1) for output.

Handling streaming input:- For a stream, keep the same deque of (index, value) but replace absolute indices with a running position counter; remove elements when their position < current_pos - (k-1).- If you cannot store the full output, emit maxima as windows complete. This maintains O(k) memory and O(1) amortized per element.- If the stream is unbounded and late arrivals are possible, you’d need buffering or approximate summaries; otherwise the deque approach works for online sliding-max.

HardTechnical

90 practiced

Given N ≤ 40 integers (possibly negative), design and implement a meet-in-the-middle algorithm in Python to find a subset whose sum is closest to a target T faster than O(2^N). Explain splitting the array, enumerating half-sums, sorting, binary searching complements, and analyze time and memory complexity.

Sample Answer

Split the N<=40 array into two halves A and B (sizes ~N/2). Enumerate all subset sums of each half (2^(N/2) each) via recursion or bitmask; sort one list (say sumsB). For every sum a in sumsA, binary-search in sumsB for value closest to (T - a) to get best combined sum close to T. Track best absolute difference and subset if you need the actual elements.

python

from bisect import bisect_left

def subset_sums(arr):
    sums = [(0, [])]  # (sum, indices)
    for i, v in enumerate(arr):
        new = [(s+v, idx+[i]) for s, idx in sums]
        sums += new
    return sums

def closest_subset(arr, T):
    n = len(arr)
    A, B = arr[:n//2], arr[n//2:]
    sumsA = subset_sums(A)          # O(2^(N/2))
    sumsB = subset_sums(B)
    sumsB.sort(key=lambda x: x[0])
    valsB = [s for s, _ in sumsB]

    best = None  # (absdiff, total_sum, indices)
    for sa, idxA in sumsA:
        want = T - sa
        i = bisect_left(valsB, want)
        for j in (i-1, i):
            if 0 <= j < len(valsB):
                sb, idxB = sumsB[j]
                total = sa + sb
                diff = abs(T - total)
                if best is None or diff < best[0]:
                    # convert B indices to global indices
                    b_offset = n//2
                    best = (diff, total, idxA + [b_offset + ii for ii in idxB])
                    if diff == 0:
                        return best[1], best[2]
    return best[1], best[2]

# Example
# total, indices = closest_subset([3, -2, 7, 1, 4], 6)

Key points:- Splitting reduces exponent from 2^N to ~2*2^(N/2).- Sorting sumsB enables O(log 2^(N/2)) = O(N/2) lookup per sumsA entry.Time complexity: O(2^(N/2) * (N/2)) for enumeration + O(2^(N/2) log 2^(N/2)) for sorting + O(2^(N/2) log 2^(N/2)) for searches → overall O(2^(N/2) * N). Space: O(2^(N/2)) to store half-sums.

Edge cases:- N small (fall back to brute force if desired)- Many duplicates — still works- Need actual elements: track indices as above

Alternatives:- Use meet-in-the-middle with pruning (keep only Pareto-optimal sums) or use hash-based near neighbor for faster approximate lookups.

EasyTechnical

92 practiced

Explain formal definitions and differences between Big O, Big Theta, and Big Omega notation. Give concrete examples and derive tight asymptotic bounds for f(n)=3n^2+10n log n+100. Describe worst-case, average-case, and amortized complexity and explain when each is important in production data pipelines and model training jobs.

MediumTechnical

78 practiced

Implement Union-Find (disjoint set union) with path compression and union by rank in Python. Then use it to implement Kruskal's algorithm to compute the Minimum Spanning Tree (MST) of an undirected weighted graph. Discuss time complexity of union-find operations and overall Kruskal runtime including sorting edges.

Sample Answer

We can implement Union-Find (Disjoint Set Union) with path compression and union by rank to get near-constant amortized operations, then use it in Kruskal’s algorithm: sort edges by weight, iterate edges, and union endpoints if they belong to different sets, adding the edge to the MST.

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

    def find(self, x):
        # path compression
        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
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

Kruskal implementation (graph as list of edges (u,v,w), nodes numbered 0..n-1):

python

def kruskal(n, edges):
    """
    n: number of nodes
    edges: list of (u, v, w)
    Returns: (mst_weight, mst_edges) or (None, None) if MST not possible
    """
    uf = UnionFind(n)
    edges_sorted = sorted(edges, key=lambda e: e[2])
    mst_weight = 0
    mst_edges = []
    for u, v, w in edges_sorted:
        if uf.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break
    if len(mst_edges) != n - 1:
        return None, None  # graph not connected
    return mst_weight, mst_edges

Key points:- Union-Find optimizations: path compression + union by rank give almost-constant amortized time: inverse-Ackermann α(n), effectively O(1) per operation.- Kruskal complexity: sorting edges O(E log E) dominates; E union/find operations at O(α(n)) each. Total: O(E log E + E α(n)) ≈ O(E log E). If E ~ V^2, sorting is O(E log V).- Edge cases: disconnected graphs (no MST), parallel edges (handled by sorting), negative weights (works fine), nodes indexing consistency.- Alternatives: Prim’s algorithm (better when using adjacency lists + binary/ Fibonacci heap for dense/sparse graphs), or Kruskal with randomized pivot selection is irrelevant since sorting is required.

MediumTechnical

73 practiced

Design a single-pass algorithm to compute rolling mean and variance over the last W items of a real-time numeric stream (W can be up to 1M) and flag anomalies when values exceed mean +/- 3*stddev. Constraints: limited memory, single pass, numerical stability. Explain Welford's algorithm for streaming variance and how to remove expired items from a fixed window.

Sample Answer

Approach (brief): keep a fixed-size deque of the last W values and maintain running count n, mean μ and M2 (sum of squared deviations) using Welford’s numerically stable online update for adds. When the window is full, remove the oldest item using the algebraic “remove” counterpart so the algorithm remains single-pass and numerically stable. Anomaly = value outside μ ± 3·std where std = sqrt(M2/(n-1)).

Python implementation (single-pass, O(1) per element, O(W) memory):

python

from collections import deque
import math

class RollingStats:
    def __init__(self, W):
        self.W = W
        self.buf = deque()
        self.n = 0
        self.mean = 0.0
        self.M2 = 0.0  # sum of squared deviations

    def add(self, x):
        # Add new point using Welford's update
        self.buf.append(x)
        self.n += 1
        delta = x - self.mean
        self.mean += delta / self.n
        delta2 = x - self.mean
        self.M2 += delta * delta2

        # If window exceeded, remove oldest
        if self.n > self.W:
            old = self.buf.popleft()
            self.remove(old)

    def remove(self, x):
        # Remove x from running stats (n must be >1 before removal)
        if self.n <= 1:
            # reset
            self.n = 0
            self.mean = 0.0
            self.M2 = 0.0
            return
        # algebraic removal: adjust mean and M2
        n_new = self.n - 1
        mean_new = (self.n * self.mean - x) / n_new
        # numerically stable M2 update
        self.M2 -= (x - self.mean) * (x - mean_new)
        self.mean = mean_new
        self.n = n_new

    def variance(self):
        return self.M2 / (self.n - 1) if self.n > 1 else 0.0

    def std(self):
        return math.sqrt(self.variance())

    def is_anomaly(self, x, k=3):
        if self.n < 2:
            return False
        return abs(x - self.mean) > k * self.std()

Key concepts / reasoning:- Welford’s algorithm updates mean and M2 per point with excellent numerical stability (avoids catastrophic cancellation).- Removing an expired item uses algebraic inversion: compute new mean = (n*mean - x)/(n-1) and adjust M2 by subtracting (x-mean_old)*(x-mean_new). This is exact in real arithmetic and stable in practice.- Complexity: O(1) work per element, O(W) memory for buffer. Handles W up to 1M if memory allows; store floats only.Edge cases / best practices:- If n<2, variance undefined — treat carefully.- For very large W or long runs consider periodic re-centering or higher precision (float64) and occasional recompute from buffer to remove drift.- For heavy tails or non-Gaussian data consider robust thresholds (MAD) instead of ±3σ.

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.