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

77 practiced

Implement an algorithm in C++ to compute the length of the Longest Increasing Subsequence (LIS) in O(n log n) time and O(n) space using the patience-sorting method. Explain the tails array idea and provide example input [10,9,2,5,3,7,101,18] -> result 4. Also discuss how to reconstruct the actual subsequence.

Sample Answer

To solve LIS in O(n log n) we use the patience-sorting / "tails" approach: tails[len] stores the smallest possible tail value of an increasing subsequence of length len+1 seen so far. For each number x, binary-search the leftmost tails[i] >= x and replace it; if x is larger than all tails, append it. The length of tails is the LIS length.

Code (with reconstruction using parent and indices):

cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> reconstructLIS(const vector<int>& nums) {
    int n = nums.size();
    vector<int> tails;               // stores values for binary search
    vector<int> tails_idx;           // stores indices in nums corresponding to tails
    vector<int> parent(n, -1);       // parent pointers to reconstruct

    for (int i = 0; i < n; ++i) {
        int x = nums[i];
        auto it = lower_bound(tails.begin(), tails.end(), x);
        int pos = it - tails.begin();

        if (it == tails.end()) {
            tails.push_back(x);
            tails_idx.push_back(i);
        } else {
            *it = x;
            tails_idx[pos] = i;
        }

        if (pos > 0) parent[i] = tails_idx[pos-1];
    }

    // Reconstruct: start from index tails_idx.back()
    vector<int> lis;
    if (!tails_idx.empty()) {
        int cur = tails_idx.back();
        while (cur != -1) {
            lis.push_back(nums[cur]);
            cur = parent[cur];
        }
        reverse(lis.begin(), lis.end());
    }
    return lis;
}

int lengthOfLIS(const vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int main() {
    vector<int> nums = {10,9,2,5,3,7,101,18};
    cout << "LIS length: " << lengthOfLIS(nums) << "\n";
    auto lis = reconstructLIS(nums);
    cout << "LIS: ";
    for (int v : lis) cout << v << " ";
    cout << "\n";
}

Key points:- tails[i] = smallest tail of an increasing subsequence with length i+1; this greedy choice keeps future extension options maximal.- Use lower_bound to maintain strictly increasing subsequence (replace >= ensures strictly increasing).- Time: O(n log n) due to binary searches; Space: O(n).- Reconstruction requires storing indices and parent pointers; when you update tails_idx[pos] with current index i, set parent[i] = tails_idx[pos-1] (if pos>0). Edge cases: empty input, duplicates handled by lower_bound behavior. Example input yields length 4 and one LIS [2,3,7,18].

EasyTechnical

97 practiced

Compare DFS and BFS: discuss traversal order, memory usage, path-finding properties, and use-case suitability. Provide examples where BFS is the correct choice (shortest path in unweighted graph) and where DFS is better (space-limited deep search). Explain iterative deepening DFS and when to use it.

HardTechnical

151 practiced

Explain and implement suffix array construction in O(n log n) time using the doubling algorithm (sort by 2^k prefixes) and then construct the LCP array with Kasai's algorithm in O(n). Provide either Python or C++ code structure, discuss memory/time trade-offs, and applications in NLP and bioinformatics.

Sample Answer

Approach: Use the doubling algorithm to build suffix array in O(n log n) by iteratively sorting suffixes by their first 2^k characters using pair ranks (rank[i], rank[i+2^k]). After SA, use Kasai’s algorithm to compute LCP in O(n) by scanning suffixes in text order and leveraging previous LCP. This is memory-efficient and practical for large NLP/bioinf datasets.

python

# Python implementation (readable, uses tuples and sorting)
def build_suffix_array(s):
    s += '\0'                      # sentinel smaller than any char
    n = len(s)
    k = 0
    # initial ranks by character
    rank = [ord(c) for c in s]
    sa = list(range(n))
    tmp = [0]*n

    while (1 << k) < n:
        sa.sort(key=lambda i: (rank[i], rank[i + (1<<k)] if i + (1<<k) < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev, cur = sa[i-1], sa[i]
            left = (rank[prev], rank[prev + (1<<k)] if prev + (1<<k) < n else -1)
            right= (rank[cur],  rank[cur  + (1<<k)] if cur  + (1<<k) < n else -1)
            tmp[cur] = tmp[prev] + (1 if right != left else 0)
        rank, tmp = tmp, rank
        k += 1
        if rank[sa[-1]] == n-1:
            break
    return sa[1:]  # drop sentinel position

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

Key points:- Time: SA O(n log n) (log n iterations, each sort O(n log n) if naive; with radix/counting sort you can achieve O(n log n) overall — with custom integer sort each step O(n)).- Kasai LCP: O(n).- Space: arrays rank, sa, tmp, lcp — O(n). Python overhead per element higher; C++ vector<int> is much more memory-efficient and faster (recommended for very large inputs).

Trade-offs:- Python: concise, good for prototyping; higher memory and constant factors.- C++: lower memory, faster; implement counting/radix sort on pairs for true O(n log n) with small constants.- You can reduce memory by using 32-bit integers and in-place transforms.

Applications:- NLP: substring search, phrase mining, building compressed indexes (FM-index), fast pattern matching for token sequences, computing repeated substrings and common prefixes for phrase extraction.- Bioinformatics: genome assembly, finding longest common substrings between sequences, detecting repeats, read alignment acceleration using suffix arrays / FM-index (Burrows-Wheeler transform).

Notes:- For production-scale genomic data, use optimized C++ implementation with suffix automaton/FM-index and external memory approaches for huge genomes.

HardTechnical

74 practiced

Explain the Optimal Binary Search Tree (OBST) dynamic programming solution: given sorted keys and access frequencies, construct a BST minimizing expected search cost. Provide the DP recurrence, an O(n^3) implementation outline, and explain Knuth optimization that reduces it to O(n^2) under quadrangle inequality. Discuss practicality and heuristics for very large n.

Sample Answer

Approach and recurrence- We have sorted keys k1..kn with access frequencies f1..fn (and optionally dummy keys for unsuccessful searches). Let sum(i,j)=sum_{t=i..j} f_t.- Let dp[i][j] = minimal expected search cost for keys i..j (cost counted as sum of frequencies times depth offset 1).Recurrence:dp[i][j] = min_{r in [i..j]} (dp[i][r-1] + dp[r+1][j] + sum(i,j))Base: dp[i][i-1] = 0 (empty), dp[i][i] = f_i.

O(n^3) implementation outline (Python)

python

def optimal_bst(freq):
    n = len(freq)
    # 1-based for clarity
    freq = [0]+freq
    dp = [[0]*(n+2) for _ in range(n+2)]
    opt = [[0]*(n+2) for _ in range(n+2)]
    prefix = [0]*(n+1)
    for i in range(1,n+1): prefix[i]=prefix[i-1]+freq[i]
    def s(i,j): return prefix[j]-prefix[i-1]
    for i in range(1,n+1):
        dp[i][i] = freq[i]
        opt[i][i] = i
    for length in range(2,n+1):
        for i in range(1,n-length+2):
            j = i+length-1
            dp[i][j] = float('inf')
            for r in range(i,j+1):  # try root r
                cost = dp[i][r-1] + dp[r+1][j] + s(i,j)
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    opt[i][j] = r
    return dp, opt

Complexity: O(n^3) time (three nested loops), O(n^2) space.

Knuth optimization -> O(n^2)- If opt[i][j-1] <= opt[i][j] <= opt[i+1][j] (monotone roots), then search range for r reduces to [opt[i][j-1], opt[i+1][j]].- This monotonicity holds when cost function satisfies quadrangle inequality / convexity (true for standard OBST with nonnegative frequencies).- Modify inner loop to try r only in that narrowed interval; overall time becomes O(n^2).

Practicality and heuristics for very large n- Exact DP O(n^2) may still be heavy for millions of keys. Practical options: - Greedy/heuristic: choose weighted median (minimizes weighted depth approximately). - Piecewise/block DP: partition keys into blocks (cluster by cumulative frequency) and solve per-block then combine. - Approximate using entropy: build a Shannon-Fano/Huffman-like tree for static lookups yields good expected cost. - Sampling + local optimization: sample keys to get coarse tree, refine hot regions. - Use balanced BSTs (e.g., weight-balanced, AVL, B-tree) if dynamic updates dominate.- For AI systems: focus optimization on high-frequency “hot” subset; use logs/telemetry to identify and optimize those paths.

MediumTechnical

75 practiced

Implement a simplified regular expression matcher in Python that supports '.' (matches any single character) and '*' (matches zero or more of the preceding element) without using built-in regex libraries. Signature: `def is_match(s: str, p: str) -> bool`. Provide the O(mn) dynamic programming solution and explain the DP state transitions.

Sample Answer

To solve this, use dynamic programming: dp[i][j] = whether s[:i] matches p[:j]. Let m=len(s), n=len(p). Initialize dp[0][0]=True. Handle patterns like a* that can match empty: if p[j-1]=='*' then dp[0][j] = dp[0][j-2].

Transition:- If p[j-1] != '*': dp[i][j] = dp[i-1][j-1] and (p[j-1]==s[i-1] or p[j-1]=='.')- If p[j-1] == '*': two cases 1. Treat "x*" as zero occurrences: dp[i][j] |= dp[i][j-2] 2. If preceding token matches current char (p[j-2]==s[i-1] or p[j-2]=='.'), treat as at least one: dp[i][j] |= dp[i-1][j]

This is O(mn) time and O(mn) space.

python

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # patterns like a*, a*b*, etc. can match empty string
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # zero occurrences of preceding element
                dp[i][j] = dp[i][j - 2]
                # one or more if preceding element matches s[i-1]
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            else:
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

Key points:- dp dimensions (m+1)x(n+1) to include empty prefixes.- '*' refers to preceding element p[j-2]; must guard indices by starting j from 2 for empty init.- Time: O(mn). Space: O(mn) (can be reduced to O(n) by rolling arrays). Edge cases: patterns starting with '*' invalid per problem assumptions (handled by j-2 accesses), multiple '*' in sequence handled by dp logic.

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.