Fundamental Algorithms and Techniques Questions

Covers core algorithmic concepts and problem solving patterns commonly assessed in technical interviews. Topics include searching algorithms such as binary search; sorting algorithms such as merge sort and quick sort; graph traversal methods such as breadth first search and depth first search; recursion and divide and conquer techniques; greedy heuristics; and dynamic programming including memoization and tabulation. Also includes implementation patterns such as two pointers, sliding window, prefix sums, and divide and conquer composition, as well as practical considerations like in place versus out of place implementations, stability for sorting, recursion stack and memory usage, and amortized analysis. Candidates should be able to implement these algorithms correctly, explain correctness and trade offs, analyze time and space complexity using Big O notation for best case average case and worst case, select appropriate approaches given input constraints, combine patterns to solve composite problems, and optimize or refactor solutions while handling edge cases.

EasyTechnical

87 practiced

Explain time and space complexity for common Python list operations including indexing, append, pop, insert at beginning, remove by value, slicing, iteration, and concatenation. Include best, average and worst case where applicable and discuss amortized analysis for append and cases when operations trigger copies.

HardTechnical

120 practiced

Convert recursive in-order traversal of a binary tree into an iterative Python generator using an explicit stack that yields node values lazily. Provide code for the traversal, discuss time and space complexity, mention tail-recursion elimination considerations and when you would prefer iterative traversal over recursion in production code with deep trees.

Sample Answer

Approach: simulate the recursive in-order (left, node, right) using an explicit stack and a while loop so the function is a lazy generator that yields node values on demand.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_iter(root):
    """
    Iterative in-order traversal as a lazy generator.
    Yields node.val in-order using an explicit stack.
    """
    stack = []
    curr = root

    # Descend left as far as possible, pushing nodes.
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        # Visit node
        node = stack.pop()
        yield node.val
        # Traverse right subtree next
        curr = node.right

Key points:- The inner loop pushes left children (simulating recursion), the pop yields a value, then we move to the right.- Because this is a generator, values are produced lazily; caller consumes as needed.

Complexity:- Time: O(n) overall (each node is pushed/popped at most once); per-yield amortized O(1).- Space: O(h) worst-case stack, where h is tree height (O(n) in skewed tree, O(log n) for balanced).

Tail-recursion elimination:- Python does not perform tail-call optimization; recursive in-order will hit RecursionError on deep trees. Converting to iterative eliminates recursion and stack overflow risk.- Note: you can also rewrite recursion to be tail-recursive in languages that optimize tail calls, but Python won't help.

When to prefer iterative over recursion:- Production systems with potentially deep trees (unbounded input) to avoid recursion depth limits.- When you need lazy streaming of results, cancellation, or backpressure control.- When minimizing call-stack overhead or when deterministic memory bounds are required.

Alternatives/trade-offs:- Morris traversal: O(1) extra space but temporarily mutates tree pointers (not safe if tree must remain immutable or concurrent).- Recursive version: simpler and more readable for small trees or controlled depths.

MediumTechnical

72 practiced

Implement topological sort using Kahn's algorithm in Python. Given number of nodes and adjacency list return one valid ordering or an empty list if a cycle exists. Explain how indegree is used, analyze time and space complexity, and describe how you would produce a lexicographically smallest topological order if node labels are comparable.

Sample Answer

To solve this, use Kahn's algorithm: compute each node's indegree, enqueue nodes with indegree 0, repeatedly pop and append to the ordering, and decrement neighbors' indegrees (enqueue when they become 0). If the output length != number of nodes a cycle exists.

python

from collections import deque, defaultdict
import heapq
from typing import List, Dict, Iterable

def kahn_toposort(n: int, adj: Dict[int, Iterable[int]]) -> List[int]:
    """
    n: number of nodes (assumes nodes are 0..n-1 or a known set size)
    adj: adjacency list mapping node -> iterable of neighbors
    Returns a valid topological ordering or [] if a cycle exists.
    """
    indeg = [0] * n
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1

    q = deque([u for u in range(n) if indeg[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == n else []

# For lexicographically smallest order (when node labels are comparable), replace deque with a min-heap:
def kahn_toposort_lexicographic(n: int, adj: Dict[int, Iterable[int]]) -> List[int]:
    indeg = [0] * n
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1

    heap = [u for u in range(n) if indeg[u] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)

    return order if len(order) == n else []

Key points:- Indegree tracks how many prerequisites a node has; nodes with 0 indegree can be placed next.- Cycle detection: remaining nodes with nonzero indegree prevent completion.Time complexity: O(n + m) where m = edges (each node and edge processed once). Space complexity: O(n + m) for indegree array and adjacency storage.Edge cases: disconnected graph, isolated nodes, invalid node labels (adjust mapping), empty graph.

HardTechnical

80 practiced

Implement Karatsuba multiplication in Python to multiply two large integers represented as strings using a divide-and-conquer approach. Explain the recurrence T(n) = 3T(n/2) + O(n) and analyze time complexity compared to O(n^2) grade-school multiplication. Discuss base-case thresholds, handling carries and signs, and when FFT-based multiplication should be considered instead.

Sample Answer

To implement Karatsuba, split each integer string into high/low halves, recursively compute z0 = low1*low2, z2 = high1*high2, z1 = (low1+high1)*(low2+high2) - z2 - z0, then combine as z2 * 10^(2*m) + z1 * 10^m + z0. This reduces multiplications from 4 to 3 per level.

python

def karatsuba(a: str, b: str) -> str:
    # Helper: strip sign and leading zeros
    sign = '-' if (a[0]=='-') ^ (b[0]=='-') else ''
    a, b = a.lstrip('+-').lstrip('0') or '0', b.lstrip('+-').lstrip('0') or '0'
    if a == '0' or b == '0':
        return '0'
    # Use int for small sizes (base case threshold)
    if len(a) <= 9 or len(b) <= 9:
        return sign + str(int(a) * int(b))
    # make lengths equal and even
    n = max(len(a), len(b))
    m = (n + 1)//2
    a = a.zfill(2*m); b = b.zfill(2*m)
    high1, low1 = a[:-m], a[-m:]
    high2, low2 = b[:-m], b[-m:]
    z0 = int(karatsuba(low1, low2))
    z2 = int(karatsuba(high1, high2))
    sum1 = str(int(low1) + int(high1)); sum2 = str(int(low2) + int(high2))
    z1 = int(karatsuba(sum1, sum2)) - z2 - z0
    res = z2 * 10**(2*m) + z1 * 10**m + z0
    return sign + str(res)

Recurrence & complexity:- T(n) = 3T(n/2) + O(n) (O(n) for additions/zero-padding). By Master theorem, T(n)=Theta(n^{log_2 3}) ≈ Theta(n^{1.585}), faster than grade-school O(n^2).

Practical notes:- Base-case threshold: use grade-school or builtin int multiplication for small n (e.g., <= 8–9 digits) to avoid recursion overhead.- Carries: combining with integer arithmetic handles carries implicitly; if implementing digit arrays, perform normalization and carry propagation after combining.- Signs: strip and restore sign; handle zero separately.- When to use FFT: for very large sizes (tens of thousands+ digits) FFT/Schönhage–Strassen (O(n log n)) becomes faster despite higher constants. Karatsuba is good for medium-large numbers.

MediumTechnical

85 practiced

Implement randomized quicksort in Java for an array of integers using in-place partitioning. Choose pivot randomly to avoid worst-case behavior on already sorted inputs. Analyze average and worst-case time and space complexity, and explain how tail recursion elimination or recursion on smaller partition first can reduce stack depth.

Sample Answer

To implement randomized quicksort in-place, pick a random pivot, partition the array around it, then recursively sort partitions. To bound stack depth, always recurse on the smaller partition and loop to sort the larger one (tail recursion elimination).

java

import java.util.Random;

public class RandomizedQuickSort {
    private static final Random rnd = new Random();

    public static void quicksort(int[] a) {
        if (a == null || a.length < 2) return;
        quicksort(a, 0, a.length - 1);
    }

    // Sorts a[l..r] in-place
    private static void quicksort(int[] a, int l, int r) {
        while (l < r) {
            // Random pivot selection
            int pivotIndex = l + rnd.nextInt(r - l + 1);
            int pivot = a[pivotIndex];
            // Move pivot to end for partitioning
            swap(a, pivotIndex, r);

            // Lomuto partition
            int store = l;
            for (int i = l; i < r; i++) {
                if (a[i] < pivot) {
                    swap(a, store++, i);
                }
            }
            swap(a, store, r); // pivot to its final place

            // Recurse on smaller partition first to limit stack depth
            int leftSize = store - l;
            int rightSize = r - store;
            if (leftSize < rightSize) {
                quicksort(a, l, store - 1);
                l = store + 1; // tail-call elimination: loop to sort right
            } else {
                quicksort(a, store + 1, r);
                r = store - 1; // tail-call elimination: loop to sort left
            }
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Key points:- Random pivot reduces probability of worst-case on adversarial/sorted inputs.- Using recursion on the smaller partition + loop for the larger eliminates tail recursion and ensures stack depth is O(log n) on average.Complexity:- Average time: O(n log n)- Worst-case time: O(n^2) (extremely unlikely with random pivots, requires bad luck)- Space: O(log n) average stack (due to recursion), O(n) worst-case without the smaller-first ruleEdge cases:- Null or empty arrays, arrays with many equal elements (Lomuto handles equals by placing them on right; for many duplicates, 3-way partitioning is better).

Unlock Full Question Bank

Get access to hundreds of Fundamental Algorithms and Techniques interview questions and detailed answers.

Join thousands of developers preparing for their dream job.