Advanced Algorithms and Problem Solving Questions

Comprehensive assessment of advanced algorithmic reasoning, design, and optimization for hard and composite problems. Covers advanced dynamic programming techniques including state compression and bitmask dynamic programming, combinatorial generation and backtracking, recursion and divide and conquer strategies, greedy algorithms with correctness proofs, and advanced graph algorithms such as breadth first search, depth first search, shortest path algorithms including Dijkstra and Bellman Ford, minimum spanning tree, network flow, strongly connected components, and topological sort. Also includes advanced tree and string algorithms such as suffix arrays and advanced hashing, bit manipulation and low level optimizations, algorithmic reductions and heuristics, and complexity analysis including amortized reasoning. Candidates should recognize applicable patterns, combine multiple data structures in a single solution, transform brute force approaches into optimized solutions, prove correctness and derive time and space complexity bounds, handle edge cases and invariants, and articulate trade offs and incremental optimization strategies. At senior levels expect mentoring on algorithmic choices, designing for tight constraints, and explaining engineering implications of algorithm selection.

MediumTechnical

20 practiced

Given n <= 20 items with positive integer weights and capacity W, count the number of subsets whose total weight is <= W. Implement an efficient solution in C++ or Python using bitmask DP or meet-in-the-middle. Describe the time/space trade-offs and how to optimize the meet-in-the-middle counting using sorting and two-pointer technique.

Sample Answer

Approach: for n ≤ 20 meet-in-the-middle is ideal. Split items into two halves, enumerate all subset sums of each half (2^(n/2) each), sort the second list and for each sum in the first list count how many second sums ≤ W - s using binary search (or use two-pointer on both sorted lists). This yields O(2^(n/2) log 2^(n/2)) time and very small memory.

Python implementation (clear and efficient):

python

from bisect import bisect_right

def count_subsets_leq_W(weights, W):
    n = len(weights)
    a = weights[:n//2]
    b = weights[n//2:]
    
    # enumerate subset sums for a and b
    sums_a = []
    for mask in range(1 << len(a)):
        s = 0
        for i in range(len(a)):
            if mask & (1 << i):
                s += a[i]
        if s <= W:
            sums_a.append(s)
    sums_b = []
    for mask in range(1 << len(b)):
        s = 0
        for i in range(len(b)):
            if mask & (1 << i):
                s += b[i]
        if s <= W:
            sums_b.append(s)
    
    sums_b.sort()
    # for each sum in a, count how many in b are <= W - s using binary search
    count = 0
    for s in sums_a:
        remaining = W - s
        # bisect_right returns index of first > remaining => that's the count
        count += bisect_right(sums_b, remaining)
    return count

Key points:- Two-pointer alternative: sort sums_a and sums_b; use i from 0..len(a)-1 and j from len(b)-1 downwards: for each i advance j down while sums_a[i] + sums_b[j] > W; then add j+1 to count. This is O(M log M) for sort + O(M) for two-pointer, where M ≈ 2^(n/2).- Time: O(2^(n/2) * n/2 + 2^(n/2) log 2^(n/2)) dominated by O(2^(n/2) log 2^(n/2)).- Space: O(2^(n/2)) to store sums.- Trade-offs: Bitmask DP (straight 2^n enumeration) is simpler but O(2^n); meet-in-the-middle reduces to ~2 * 2^(n/2) work. Use binary search when many repeated queries; use two-pointer if both lists sorted to avoid log factor.- Edge cases: handle W < 0 (answer 0), empty list (answer 1: empty subset), large weights (> W) filtered early.

HardTechnical

24 practiced

Implement Dinic's max-flow algorithm in C++ or Java for directed graphs with up to 1e5 edges. Your implementation should build level graphs via BFS and compute blocking flows via DFS. Explain practical optimizations like current-arc optimization and capacity scaling, and analyze when Dinic is preferable to Edmonds-Karp or Push-Relabel.

Sample Answer

To implement Dinic's algorithm: build level graph with BFS, then repeatedly send blocking flows using DFS with current-arc optimization (store iterators to avoid revisiting dead edges). Capacity scaling (process only edges with capacity >= threshold, halving threshold) can help on graphs with huge capacity ranges. Dinic typically outperforms Edmonds–Karp (O(VE^2)) and is often comparable to best Push–Relabel in practice; Dinic is excellent for unit-capacity or layered graphs and when multiple augmenting paths per BFS exist.

C++ implementation (supports up to ~1e5 edges — use long long for capacities if needed):

cpp

#include <bits/stdc++.h>
using namespace std;
struct Edge{int to; int rev; long long cap;};
struct Dinic {
    int N;
    vector<vector<Edge>> G;
    vector<int> level, it;
    Dinic(int n):N(n),G(n),level(n),it(n){}
    void addEdge(int u,int v,long long c){
        G[u].push_back({v,(int)G[v].size(),c});
        G[v].push_back({u,(int)G[u].size()-1,0});
    }
    bool bfs(int s,int t){
        fill(level.begin(), level.end(), -1);
        queue<int>q; level[s]=0; q.push(s);
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(auto &e:G[u]) if(e.cap>0 && level[e.to]==-1){
                level[e.to]=level[u]+1; q.push(e.to);
            }
        }
        return level[t]!=-1;
    }
    long long dfs(int u,int t,long long f){
        if(u==t) return f;
        for(int &i=it[u]; i<(int)G[u].size(); ++i){
            Edge &e = G[u][i];
            if(e.cap>0 && level[e.to]==level[u]+1){
                long long ret = dfs(e.to,t,min(f,e.cap));
                if(ret>0){
                    e.cap -= ret;
                    G[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    long long maxflow(int s,int t){
        long long flow=0;
        while(bfs(s,t)){
            fill(it.begin(), it.end(), 0);
            while(true){
                long long pushed = dfs(s,t,LLONG_MAX);
                if(!pushed) break;
                flow += pushed;
            }
        }
        return flow;
    }
};

Key points:- Current-arc optimization: the it[] pointer avoids re-scanning exhausted edges inside DFS, giving practical speed gains.- Complexity: O(min(V^{2/3}, sqrt(E)) * E) for unit networks or O(E * sqrt(V)) in many bipartite cases; general worst-case O(V^2 E) but much faster in practice.- Capacity scaling: reduce BFS/DFS work by ignoring tiny capacities until threshold halved — helps when max capacity >> typical augmenting flow.- When to use: Prefer Dinic for sparse graphs, unit capacities, or many parallel augmenting paths. Use Edmonds–Karp only for simplicity/small graphs. Use Push–Relabel for dense graphs or when highest practical performance on arbitrary capacities is needed.

Edge cases:- Multiple edges, self-loops (avoid if meaningless)- Large capacities -> use 64-bit- Ensure graph size and recursion depth: convert DFS to iterative if stack limits are a concern.

MediumTechnical

23 practiced

Implement Dijkstra's algorithm in C++ or Python for a weighted directed graph with non-negative weights. Your implementation should return shortest distances from a given source and reconstruct the shortest path to a specified target. Input format: n nodes labeled 0..n-1 and adjacency list of (neighbor, weight) pairs. Aim for O(m log n) time.

Sample Answer

Use Dijkstra with a min-heap (priority queue), track distances and predecessors to reconstruct path.

python

import heapq

def dijkstra(n, adj, src, target=None):
    """
    n: number of nodes (0..n-1)
    adj: adjacency list where adj[u] = list of (v, weight)
    src: source node
    target: optional target node for early stop
    Returns: (dist, prev)
      dist: list of distances (float('inf') when unreachable)
      prev: list of predecessors (None for no predecessor)
    """
    dist = [float('inf')] * n
    prev = [None] * n
    dist[src] = 0
    pq = [(0, src)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue  # stale entry
        if target is not None and u == target:
            break  # early exit when target settled
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, prev

def reconstruct_path(prev, src, target):
    if prev[target] is None and src != target:
        return []  # unreachable
    path = []
    u = target
    while u is not None:
        path.append(u)
        if u == src:
            break
        u = prev[u]
    path.reverse()
    if path[0] != src:
        return []  # unreachable
    return path

# Example usage:
# n = 5
# adj = {0: [(1,2),(2,5)], 1: [(2,1)], 2: [(3,2)], 3: [(4,1)], 4: []}
# dist, prev = dijkstra(n, adj, 0, target=4)
# path = reconstruct_path(prev, 0, 4)

Key points:- Uses min-heap for O(m log n) (m edges, n nodes).- prev[] stores predecessor for path reconstruction.- Checks stale heap entries to avoid extra work.- Early stop if target provided improves average time.Time: O((n + m) log n) ≈ O(m log n) for sparse graphs.Space: O(n + m).Edge cases: disconnected nodes, source == target, zero-weight edges, large weights (use float('inf')). Alternative: use Fibonacci heap for better theoretical bound but higher constant factors.

HardTechnical

16 practiced

As a senior engineer you must choose an algorithm for a production service under strict 100ms tail latency and limited memory. Option A: approximate linear-time algorithm with ~1% error and predictable memory; Option B: exact algorithm with O(n log n) time and higher memory. Describe how you would evaluate, benchmark, decide which to ship, mitigate risk, roll out (canary/A-B), monitor SLOs, and mentor the team on this technical decision.

Sample Answer

Situation/constraints: We must deliver a production service with a strict 100ms tail latency SLO and limited memory. Two options: A (approximate, linear time, ~1% error, predictable low memory) and B (exact, O(n log n), higher memory).

How I'd evaluate and decide- Clarify requirements with stakeholders: is 1% approximation acceptable for correctness/SLA and downstream consumers? What fraction of requests require exactness? What is the memory hard limit, and what is the p99 latency SLO vs p50?- Define success criteria: p99 < 100ms under peak load, memory < limit, correctness constraints (max allowable error), operational complexity, and developer cost.

Benchmark plan- Microbench both algorithms in isolation: single-request latencies (p50/p95/p99), memory allocation, GC behavior, CPU, and worst-case inputs.- End-to-end integration tests: run in a staging cluster with realistic traffic patterns and data distributions (including worst-case large n).- Load and stress tests: ramp concurrency to expected peak and 2x, inject high-cardinality/degenerate cases to measure tail behavior.- Measure variance, not just mean: capture p50/p95/p99, 99.9, and latency histogram; record memory percentiles, CPU utilization, and error distribution for Option A.

Decision criteria and trade-offs- If Option A reliably meets p99 and memory needs and 1% error is within product tolerance, prefer A for predictable performance and lower operational risk.- If Option B is necessary for correctness on a meaningful fraction of requests, consider a hybrid: use A by default and B for heavy/critical requests, or only for requests flagged as needing exactness.

Risk mitigation and rollout- Implement feature flagging and canarying: ship behind a flag; deploy to small canary cohort (e.g., 1–5% traffic) segmented by tenant or region.- Gradual ramp with automated rollback thresholds: monitor p99, error rate, memory, CPU, and business metrics; if any breach threshold, automatically rollback.- Fallbacks: if A returns results outside expected error profile or latency spikes, fallback to B or reject with graceful degradation.- Resource controls: use memory limits, circuit breakers, and queueing to avoid system-wide overload.

Monitoring and SLOs- Instrument both algorithms to emit: - Latency histograms (p50/p95/p99/99.9) - Memory usage and GC pause times - Error metrics: approximation deviation distribution, out-of-bound counts - Business metrics: user-visible error rate, success rate, revenue impacts- Create alerts on SLO breaches and unusual drift in approximation error.- Add dashboards and runbooks describing triage steps.

Mentoring the team- Run a design review session explaining benchmarks, trade-offs, and decision rationale.- Pair-program on the feature-flag integration, canary automation, and monitoring instrumentation.- Provide a checklist (benchmarks to run, thresholds to observe) and a short brown-bag on performance testing best practices (latency tail causes, GC tuning, profiling).- Encourage blameless post-deploy reviews and document lessons learned.

Outcome: choose the option that meets correctness and operational SLOs with the least systemic risk—often the approximate algorithm with rigorous testing, fallbacks, and gradual rollout—but remain pragmatic: if exactness is required, use hybrid routing or optimize exact algorithm with targeted improvements.

MediumTechnical

18 practiced

Describe and implement suffix array construction using the doubling algorithm (O(n log n)) for a string s (n up to 1e5). Produce both the suffix array and the LCP array. Explain correctness and how LCP can be used to answer substring frequency queries efficiently.

Sample Answer

To build a suffix array in O(n log n) we use the doubling algorithm: assign initial ranks by characters, then iteratively sort suffixes by (rank[i], rank[i + k]) for k = 1,2,4,... doubling each step until ranks are unique. After the suffix array, compute LCP with Kasai's algorithm in O(n). Using SA and LCP, substring frequency queries (count occurrences of pattern p) reduce to finding the range of suffixes whose prefixes match p — two binary searches on SA (lower/upper bound). LCP helps accelerate repeated queries by reusing matched-prefix lengths between comparisons, but basic binary search is already O(|p| log n).

Python implementation (n up to 1e5 — this is optimized but for worst-case constant factors C++ may be faster):

python

def build_sa(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0]*n
    k = 1
    while True:
        sa.sort(key=lambda i: (rank[i], rank[i+k] if i+k<n else -1))
        tmp[sa[0]] = 0
        for i in range(1,n):
            prev, cur = sa[i-1], sa[i]
            tmp[cur] = tmp[prev] + ( (rank[cur], rank[cur+k] if cur+k<n else -1) != (rank[prev], rank[prev+k] if prev+k<n else -1) )
        rank, tmp = tmp, rank
        if rank[sa[-1]] == n-1:
            break
        k <<= 1
    return sa

def build_lcp(s, sa):
    n = len(s)
    rank = [0]*n
    for i, pos in enumerate(sa): rank[pos]=i
    lcp = [0]*(n-1)
    h=0
    for i in range(n):
        r = rank[i]
        if r==n-1:
            h=0
            continue
        j = sa[r+1]
        while i+h < n and j+h < n and s[i+h]==s[j+h]: h+=1
        lcp[r]=h
        if h: h-=1
    return lcp

def count_occurrences(s, sa, pattern):
    # find lower bound
    n = len(s)
    def cmp(i):
        sub = s[i:i+len(pattern)]
        return -1 if sub < pattern else (0 if sub==pattern else 1)
    lo, hi = 0, n
    while lo<hi:
        mid=(lo+hi)//2
        if s[sa[mid]:sa[mid]+len(pattern)] < pattern: lo=mid+1
        else: hi=mid
    l=lo
    lo, hi = 0, n
    while lo<hi:
        mid=(lo+hi)//2
        if s[sa[mid]:sa[mid]+len(pattern)] <= pattern: lo=mid+1
        else: hi=mid
    r=lo
    return r-l  # number of suffixes starting with pattern

Key points / correctness:- Doubling sorts by first 2k chars using previous ranks; when ranks become unique, order is full suffix order — proven by induction on k.- Kasai computes LCP using inverse SA and reuses previous LCP-1 to achieve O(n).- To count occurrences of pattern p, suffixes with prefix p form a contiguous interval in SA; binary search finds its bounds in O(|p| log n). Using LCP and enhanced search techniques (e.g., LCP-aware binary search or interval tree) can reduce comparisons for many queries.

Complexity:- SA construction: O(n log n) comparisons and sorts; with radix/Counting sort can be O(n log n) time with lower constants.- LCP: O(n).- Query: O(|p| log n) (can be improved).

Unlock Full Question Bank

Get access to hundreds of Advanced Algorithms and Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.