Hard Difficulty Algorithmic Problems Questions

Advanced algorithmic problem solving topics commonly encountered in coding interviews, focusing on data structures (arrays, strings, linked lists, trees, graphs, heaps, hashes), algorithmic techniques (dynamic programming, greedy, backtracking, divide and conquer, graph algorithms), and time/space complexity optimization to produce efficient solutions.

HardTechnical

97 practiced

Given inorder and postorder traversal arrays of a binary tree with unique values, reconstruct the binary tree. Implement an iterative O(n) time and O(n) space solution in Python without recursion using a stack, and explain why it works. Discuss robustness for deeply skewed trees and how to avoid recursion depth issues in production.

Sample Answer

Approach (brief): Use postorder's last element as the root and iterate postorder backward. Maintain a stack of nodes representing the current path from root to the most recently added node. Use an index into inorder (starting at the end) to decide whether the next node becomes a right child (if stack top != inorder[in_idx]) or we should pop from stack (matching inorder) and then attach the next node as a left child. This yields an iterative O(n) reconstruction.

python

# python
from typing import List, Optional
class TreeNode:
    def __init__(self, val:int, left:Optional['TreeNode']=None, right:Optional['TreeNode']=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    if not inorder or not postorder or len(inorder) != len(postorder):
        return None

    # Start from last postorder element = root
    post_idx = len(postorder) - 1
    root = TreeNode(postorder[post_idx])
    stack = [root]
    in_idx = len(inorder) - 1
    post_idx -= 1

    while post_idx >= 0:
        node = stack[-1]
        current_val = postorder[post_idx]

        # If stack top != inorder[in_idx], the next node is the right child
        if node.val != inorder[in_idx]:
            node.right = TreeNode(current_val)
            stack.append(node.right)
            post_idx -= 1
        else:
            # Pop nodes that match inorder until mismatch; then attach left child
            while stack and stack[-1].val == inorder[in_idx]:
                node = stack.pop()
                in_idx -= 1
            node.left = TreeNode(current_val)
            stack.append(node.left)
            post_idx -= 1

    return root

Why it works:- Postorder (left, right, root) processed backwards gives root, then right-subtree nodes, then left-subtree nodes. The stack keeps the path of nodes whose left children are not yet attached.- The inorder pointer tells when we've finished a right subtree (when stack top equals inorder[in_idx]) and should pop back to attach left children. This mirrors the recursive boundary logic but uses explicit stack and indices.

Complexity:- Time: O(n) — each node pushed/popped once.- Space: O(n) — stack and tree nodes.

Robustness for deeply skewed trees and avoiding recursion depth issues:- This iterative approach avoids Python recursion entirely, so it is robust for deeply skewed trees (depth ~n) and doesn't hit recursion limits.- In production, prefer iterative algorithms or explicit stacks for tree operations that can be highly unbalanced. If recursion is unavoidable (e.g., other APIs), consider converting to iterative, using sys.setrecursionlimit with caution, or redesigning data processing to stream/flatten trees to limit depth.

MediumTechnical

80 practiced

Implement Longest Common Subsequence (LCS) for two token sequences in Python that returns both length and one LCS using O(n*m) time and O(min(n,m)) space. Provide method for reconstructing the LCS (Hirschberg's algorithm if needed) and discuss when LCS is preferred over edit distance in sequence comparison.

Sample Answer

To compute LCS length and one LCS in O(n*m) time and O(min(n,m)) space, use dynamic programming for lengths with rolling arrays and Hirschberg’s divide-and-conquer to reconstruct the sequence in linear space.

python

def lcs_length_row(a, b):
    # returns last DP row (lengths) for LCS of a and b using O(min(len(a),len(b))) space
    if len(b) < len(a):
        a, b = b, a
    prev = [0] * (len(a) + 1)
    for bj in b:
        cur = [0]
        for i, ai in enumerate(a, 1):
            if ai == bj:
                cur.append(prev[i-1] + 1)
            else:
                cur.append(max(cur[-1], prev[i]))
        prev = cur
    return prev  # length row for a against full b

def hirschberg(a, b):
    # returns one LCS (as list of tokens)
    if not a:
        return []
    if len(a) == 1:
        return [a[0]] if a[0] in b else []
    i = len(a) // 2
    left = lcs_length_row(a[:i], b)
    right = lcs_length_row(a[i:][::-1], b[::-1])[::-1]
    # find split k maximizing left[k] + right[k]
    k = max(range(len(left)), key=lambda x: left[x] + right[x])
    return hirschberg(a[:i], b[:k]) + hirschberg(a[i:], b[k:])

def lcs(a, b):
    # a, b are sequences (lists/strings). Returns (length, one_lcs_sequence)
    seq = hirschberg(list(a), list(b))
    return len(seq), seq

# Example:
# length, seq = lcs("AGGTAB", "GXTXAYB") -> length=4, seq=['G','T','A','B']

Key points:- lcs_length_row computes DP rows in O(len(a)*len(b)) time and O(min(n,m)) space.- Hirschberg splits a into halves, computes forward/backward length rows, finds optimal split, and recurses to reconstruct LCS using O(min(n,m)) extra space and O(n*m) time overall.Complexity: Time O(n*m), Space O(min(n,m)).Edge cases: empty inputs, repeated tokens, non-hashable tokens (works since comparisons use equality).When to prefer LCS vs edit distance:- Use LCS when you need the longest common subsequence (matching relative order, not contiguity) and want an explicit common subsequence (e.g., diff tools, alignment without substitutions).- Use edit distance (Levenshtein) when you care about minimal edits (insert/delete/replace) to transform one sequence into another or need weighted operations; edit distance gives cost-focused similarity while LCS focuses on shared ordered content.

HardTechnical

78 practiced

Implement convolution of two large real-valued arrays using FFT in Python (NumPy allowed). Explain zero-padding to power-of-two, real FFT (rfft) optimization, numerical precision considerations (single vs double), and implement block convolution (overlap-save or overlap-add) to handle signals up to 1e7 elements with limited memory.

Sample Answer

To convolve large real arrays efficiently, use FFT-based convolution with these optimizations: zero-pad to next power-of-two for fast FFT, use real FFT routines (rfft/irfft) to halve complex work, pick dtype (float32 vs float64) balancing memory vs precision, and for very large signals use block convolution (overlap-add) to limit memory.

Approach:1. If both arrays small, do single FFT: pad length = next_pow2(len(a)+len(b)-1), use rfft/irfft.2. For huge signals (len ~1e7), use overlap-add: split input into blocks, FFT of block + kernel once, multiply in freq domain, inverse FFT, accumulate overlaps.

Code (NumPy):

python

import numpy as np

def next_pow2(n):
    return 1 << (n - 1).bit_length()

def convolve_fft(a, b, block_size=None, dtype=np.float64):
    a = np.asarray(a, dtype=dtype)
    b = np.asarray(b, dtype=dtype)
    n_out = a.size + b.size - 1
    # small case: single FFT
    if block_size is None:
        L = next_pow2(n_out)
        A = np.fft.rfft(a, n=L)
        B = np.fft.rfft(b, n=L)
        out = np.fft.irfft(A * B, n=L)[:n_out]
        return out
    # overlap-add: choose block_size (input block length)
    M = b.size
    if block_size <= 0:
        raise ValueError("block_size must be > 0")
    # FFT length: pad block + kernel -1 to next pow2
    L = next_pow2(block_size + M - 1)
    Bf = np.fft.rfft(b, n=L)
    out = np.zeros(n_out, dtype=dtype)
    step = block_size
    for i in range(0, a.size, step):
        block = a[i:i+step]
        Af = np.fft.rfft(block, n=L)
        conv_blk = np.fft.irfft(Af * Bf, n=L)[:block.size + M - 1]
        out[i:i+conv_blk.size] += conv_blk
    return out

Key concepts:- Zero-padding to power-of-two speeds FFT libraries.- rfft/irfft operate on real inputs, reducing storage and compute ~2x.- Single-FFT approach uses O(n log n) time, but requires memory for full padded arrays.- Overlap-add uses O(N log L) time where L is FFT length per block and O(L) memory.

Numerical precision:- float32 halves memory and often suffices in ML pipelines; float64 reduces round-off for very long convolutions or when dynamic range is high. Accumulate in higher precision if possible (e.g., cast blocks to float64 during accumulation).

Edge cases:- Empty inputs, one-element kernels, very small kernel (use direct conv), extremely large block_size causing OOM — tune block_size so L*8*2 (for complex) fits memory.- Consider windowing or scaling if inputs are very large to avoid overflow.

Alternatives/trade-offs:- Overlap-save is similar; overlap-add implemented here for clarity.- Use FFT libraries with multithreading (FFTW, MKL-backed NumPy) or GPU FFTs for better throughput.

HardTechnical

85 practiced

Implement Bellman-Ford in Python to compute shortest paths from a source in a directed graph that may contain negative edges but no negative cycles. Support detection of negative cycles and return appropriate signal. Discuss when Bellman-Ford is preferred over Dijkstra and the practical performance limits for large graphs.

Sample Answer

To solve this, run the Bellman-Ford relaxation |V|-1 times over all directed edges to get shortest distances; then do one more pass to detect negative cycles reachable from the source. Return distances and predecessors, or signal a negative cycle (raise or return None/flag).

python

from typing import List, Tuple, Dict, Optional

def bellman_ford(
    n: int,
    edges: List[Tuple[int,int,float]],
    src: int
) -> Tuple[Optional[List[float]], Optional[List[Optional[int]]]]:
    """
    n: number of vertices (0..n-1)
    edges: list of (u, v, w)
    src: source vertex
    Returns (dist, parent) or (None, None) if a negative cycle reachable from src exists.
    """
    INF = float('inf')
    dist = [INF]*n
    parent: List[Optional[int]] = [None]*n
    dist[src] = 0.0

    # Relax edges |V|-1 times
    for _ in range(n-1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                updated = True
        if not updated:
            break  # early stop

    # Check for negative cycles reachable from src
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None, None  # negative cycle detected

    return dist, parent

Key points:- Uses early exit when no updates occur.- parent[] allows path reconstruction by following predecessors.- Time complexity: O(V*E). Space: O(V+E) for storing graph; algorithm uses O(V) extra.- Edge cases: unreachable nodes (dist stays INF), multiple edges, self-loops, floating-point weights.

When to prefer Bellman-Ford over Dijkstra:- Bellman-Ford supports negative edge weights and detects negative cycles; use it when negative weights exist or when cycle detection is required. If all weights nonnegative, Dijkstra (with binary heap) is faster: O((V+E) log V).

Practical performance limits:- Bellman-Ford is cubic-like when dense: O(V^3) worst if E≈V^2; in practice O(V*E). For large graphs (millions of edges/nodes) it's often too slow. Typical practical limits on commodity hardware: up to low millions of edges if implemented in optimized C++; in Python expect tens to hundreds of thousands of edges before it becomes prohibitively slow. For large-scale problems use:- Johnson's algorithm (reweight + Dijkstra) for all-pairs with negative edges but no negative cycles,- Graph libraries in C/C++ (NetworkX is Python but slow; use igraph or custom C++),- Parallel/distributed approaches or GPU acceleration for specialized workloads.

HardTechnical

73 practiced

Given array nums and integer k, compute the maximum subarray sum where you are allowed to delete at most k elements from the subarray. Implement Python algorithm with O(n*k) time and O(k) space or better, describing DP states and transitions. Discuss use for denoising or removing outlier tokens in sequences.

Sample Answer

Approach (DP intuition)Define dp[j] = maximum subarray sum ending at the current index i using at most j deletions inside that subarray. At each new element x we either:- take x into the subarray (no deletion used): dp[j] + x- delete x (consuming one deletion): dp[j-1] (we don't add x)- start a new subarray at x: x

This yields transitions:new_dp[0] = max(dp[0] + x, x)for j >= 1: new_dp[j] = max(dp[j] + x, dp[j-1], x)

We maintain dp as length k+1 and update in O(k) per element (use a temp array or update right-to-left).

Python implementation (O(n*k) time, O(k) space)

python

def max_subarray_with_k_deletions(nums, k):
    NEG = -10**18
    dp = [NEG] * (k + 1)  # dp[j] = best ending here with <= j deletions
    best = NEG

    for x in nums:
        new = [NEG] * (k + 1)
        # j = 0 (no deletions)
        new[0] = max(dp[0] + x, x)
        best = max(best, new[0])

        # j >= 1
        for j in range(1, k + 1):
            # take x: dp[j] + x
            # delete x: dp[j-1] (use one deletion to skip x)
            # start new subarray with x
            new[j] = max(dp[j] + x, dp[j - 1], x)
            best = max(best, new[j])

        dp = new

    return best

Key concepts and reasoning- dp[j-1] in the formula represents deleting the current element (consuming one deletion) while keeping the previous run.- Starting new subarray (x) must be considered at every step — it handles negative prefixes and allows fresh starts.- Using only an array of length k+1 yields O(k) space; iterating n elements gives O(n*k) time.

Complexity- Time: O(n * k)- Space: O(k)

Edge cases- k >= n: can delete many elements but subarray must contain at least one non-deleted element; algorithm still returns correct max single element if deletions remove others.- All negatives: returns the largest (least negative) single element.- k = 0: reduces to standard Kadane (dp[0] transition).- Empty nums: return NEG or handle separately (e.g., return 0 or None per spec).

Use for denoising / removing outlier tokensThis DP is directly applicable to sequence denoising: treat each token's “score” (e.g., log-probability, attention-weighted importance, or a learned token score) as nums. The algorithm finds contiguous spans whose summed score is maximal while allowing up to k tokens to be dropped (outliers/noise). This is useful for:- Removing spurious tokens in text spans while preserving contiguous context.- Post-processing model outputs (e.g., detect and delete hallucinated tokens).- Denoising time-series by removing up to k high-noise points inside a window while maximizing signal.

Practical notes: choose scoring carefully (e.g., token relevance minus penalty for length), and consider sliding-window variants or regularization if deletions should be sparse or have positional costs.

Unlock Full Question Bank

Get access to hundreds of Hard Difficulty Algorithmic Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.