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.

EasyTechnical

77 practiced

Explain, with concrete examples, the practical differences between common complexity classes: O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n). For each class give one algorithm/operation that fits it, and discuss how doubling the input size affects runtime to help an engineer choose algorithms in practice.

HardTechnical

87 practiced

Implement Levenshtein edit distance (insert/delete/replace cost 1) between strings s and t and additionally produce the edit script (sequence of operations) to transform s into t. Provide a Python implementation using O(m*n) time and O(m*n) space, and explain how you would reduce space when only the distance is needed.

Sample Answer

Approach: Use classic DP to compute an (m+1)x(n+1) table where dp[i][j] = min edits to transform s[:i] → t[:j]. Fill base rows/cols for insert/delete, then compute replace/min of three ops. To produce an edit script, backtrack from dp[m][n] to dp[0][0] choosing the operation that led to the cell.

python

def levenshtein_with_script(s: str, t: str):
    m, n = len(s), len(t)
    # dp[i][j] = distance s[:i] -> t[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        dp[i][0] = i
    for j in range(1, n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s[i - 1] == t[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # delete s[i-1]
                dp[i][j - 1] + 1,      # insert t[j-1]
                dp[i - 1][j - 1] + cost  # replace or match
            )

    # Backtrack to produce script
    i, j = m, n
    script = []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] and s[i - 1] == t[j - 1]:
            script.append(f"KEEP '{s[i-1]}'")
            i -= 1; j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            script.append(f"REPLACE '{s[i-1]}' -> '{t[j-1]}'")
            i -= 1; j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            script.append(f"DELETE '{s[i-1]}'")
            i -= 1
        else:
            script.append(f"INSERT '{t[j-1]}'")
            j -= 1

    script.reverse()
    return dp[m][n], script

# Example:
# dist, ops = levenshtein_with_script("kitten", "sitting")
# print(dist)  # 3
# print("\n".join(ops))

Key points:- Time: O(m*n) (DP fill). Space: O(m*n) for full table to allow backtracking.- If only distance needed, reduce space to O(min(m,n)) by keeping only two rows (current and previous). That yields same time but linear space.- If you need the edit script with linear space, use Hirschberg's algorithm: divide-and-conquer that computes split points using forward and backward linear-space DP — still O(m*n) time but O(min(m,n)) space.Edge cases: empty strings, identical strings (script will be all KEEP), Unicode characters (works as long as strings iterate by character).

MediumTechnical

76 practiced

Given a string s, find the length of the longest substring without repeating characters. Implement in Python using sliding-window with a hashmap to track last seen indices. Example: 'abcabcbb' -> 3. Explain why the algorithm runs in O(n) time and analyze space usage with respect to the character set.

Sample Answer

We can use a sliding-window with two pointers (left, right) and a hashmap that stores the last seen index of each character. When we encounter a character already seen inside the current window, advance left to one past that previous index. This ensures each character is processed at most twice.

python

def length_of_longest_substring(s: str) -> int:
    """
    Sliding-window + hashmap of last seen indices.
    Returns length of longest substring without repeating characters.
    """
    last = {}            # char -> last index seen
    left = 0             # window start (inclusive)
    max_len = 0

    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            # move left just past previous occurrence to maintain uniqueness
            left = last[ch] + 1
        last[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# Example:
# print(length_of_longest_substring("abcabcbb"))  # -> 3

Why O(n) time:- The right pointer visits each character once (n iterations).- The left pointer only moves forward and never exceeds n. Each character causes at most one left movement when its previous occurrence is skipped.- Hashmap operations (lookup/update) are O(1) average, so overall time is O(n).

Space complexity:- O(min(n, m)) where m is the size of the character set. In worst-case for arbitrary Unicode strings m could be large but bounded by distinct characters in s; for ASCII it's O(min(n,128)) => O(n) worst-case but typically O(1) if m is fixed small.

Edge cases:- Empty string -> 0- All characters identical -> 1- Long unicode strings -> hashmap holds distinct codepoints accordingly.

MediumTechnical

94 practiced

Given an array of strings, group anagrams together. Implement in JavaScript: function groupAnagrams(strs) { ... }. Use a hash map where the key is either the sorted string or a character-count signature. Discuss time/space trade-offs and handling of large alphabets or Unicode.

Sample Answer

Approach: Use a hashmap where the key is either the sorted string (simple) or a character-count signature (linear per string). I'll show the character-count signature (O(L) per string where L = length), which avoids O(L log L) cost of sorting.

javascript

function groupAnagrams(strs) {
  // Use Map from signature -> array of words
  const map = new Map();

  for (const s of strs) {
    // build character-count signature for ASCII lowercase a-z
    const counts = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
      const code = s.charCodeAt(i) - 97; // assume 'a'..'z'
      if (code >= 0 && code < 26) counts[code]++;
      else {
        // fallback: use sorted key for unexpected chars
        const key = s.split('').sort().join('');
        const arr = map.get(key) || [];
        arr.push(s);
        map.set(key, arr);
        // continue outer loop
        continue;
      }
    }
    const key = counts.join('#'); // e.g. "1#0#2#..."
    const arr = map.get(key) || [];
    arr.push(s);
    map.set(key, arr);
  }

  return Array.from(map.values());
}

Key points:- Time: using counts -> O(N * L) where N = number strings, L = avg length. Sorted-key approach is O(N * L log L).- Space: O(N * L) to store keys and output.- Trade-offs: sorted-key is simpler and robust for arbitrary alphabets/Unicode; count-signature is faster for bounded alphabets (e.g., lowercase English) but requires fixed-size count array. For large alphabets or Unicode, use a hashmap of codepoint->count to build a deterministic signature (or fall back to sorted string). Ensure signature separator to avoid collisions.- Edge cases: empty strings, single char, very long strings, mix of Unicode — handle with appropriate key strategy and memory considerations.

MediumTechnical

73 practiced

Given an unweighted undirected graph represented as an adjacency list and a start node, compute shortest distances (in number of edges) to all reachable nodes using BFS. Implement in Java: Map<Integer,Integer> bfsDistances(Map<Integer,List<Integer>> graph, int start). Explain correctness and O(V+E) time complexity.

Sample Answer

Approach:Use a standard breadth-first search (BFS). Maintain a queue of nodes to visit and a distances map that also serves as the visited set. Initialize start distance = 0, enqueue start, then for each dequeued node set neighbor distance = current+1 if unseen and enqueue it. BFS visits nodes in increasing order of edge count, so distances are shortest.

java

import java.util.*;

public class GraphBFS {
    public static Map<Integer,Integer> bfsDistances(Map<Integer,List<Integer>> graph, int start) {
        Map<Integer,Integer> dist = new HashMap<>();
        if (graph == null || !graph.containsKey(start)) return dist; // no reachable nodes from missing start

        Queue<Integer> q = new ArrayDeque<>();
        dist.put(start, 0);
        q.add(start);

        while (!q.isEmpty()) {
            int u = q.poll();
            int d = dist.get(u);
            List<Integer> neighbors = graph.getOrDefault(u, Collections.emptyList());
            for (int v : neighbors) {
                if (!dist.containsKey(v)) {        // unseen => shortest path found
                    dist.put(v, d + 1);
                    q.add(v);
                }
            }
        }
        return dist;
    }
}

Correctness:BFS explores nodes by nondecreasing distance from start. When a node is first discovered, the path used is the fewest edges possible; marking it visited (dist map) prevents revisiting longer paths. Thus dist[v] holds the minimum number of edges.

Time & Space Complexity:- Time: O(V + E). Each node is enqueued/processed at most once (O(V)), and each edge is considered from its endpoint adjacency lists once (total O(E)).- Space: O(V) for dist and O(V) for the queue in worst case.

Edge cases:- Empty graph or start missing → returns empty map.- Isolated start node → returns {start:0}.- Graph with self-loops or duplicate edges → handled because we only process unseen neighbors.

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.