Algorithmic Problem Solving Questions

Evaluates ability to decompose computational problems, design correct and efficient algorithms, reason about complexity, and consider edge cases and correctness. Expectation includes translating problem statements into data structures and algorithmic steps, justifying choices of approach, analyzing time and space complexity, optimizing for constraints, and producing test cases and proofs of correctness or invariants. This topic covers common algorithmic techniques such as sorting, searching, recursion, dynamic programming, greedy algorithms, graph traversal, and trade offs between readability, performance, and maintainability.

HardSystem Design

81 practiced

You need to sort a 500GB file on a machine with 8GB RAM. Design an external merge sort: describe how to create initial runs, multi-way merge strategy, number of passes, I/O complexity, and optimizations such as replacement selection, compression, and parallel merging.

Sample Answer

Requirements & constraints:- Input size N = 500 GB, RAM M = 8 GB.- Goal: sort entire file with minimal I/O and passes.

High-level plan:1) Create initial runs (pass 0)2) Multi-way merge runs until single sorted file

1. Creating initial runs- Read as much as memory allows, sort in-memory, write as a run.- Practical memory for data buffers + program overhead: reserve ~7 GiB for data.- Run size R ≈ 7 GiB → number of runs = ceil(500 / 7) ≈ 72 runs.- Use an efficient in-memory sort (introsort/timsort) and write runs sequentially.

Replacement selection (optimization)- Use replacement selection with a min-heap to produce average runs ≈ 2×M (≈14 GB). That can halve number of runs → ~36 runs on average, reducing merge passes.

2. Multi-way merge strategy- Use a k-way merge where k is number of runs merged simultaneously, limited by: - Memory for one input buffer per run + one output buffer. - Example: if we allocate 1 MiB input buffer per run and 64 MiB output buffer, k ≈ (M - overhead - output)/1MiB ≈ ~7000 MiB/1MiB ≈ ~7000 (theoretical). In practice OS limits, open-file limits, and I/O efficiency suggest k in tens to low hundreds.- Choose k = 64 (practical): with ~72 runs, log_64(72) ≈ 2 → two merge passes (one k-way merge merging many into bigger runs then final merge).- Implementation: priority queue (min-heap) of size k holding current head of each buffer; refill buffers asynchronously using background I/O threads.

3. Number of passes & I/O complexity- Initial run creation: read N once, write N → 2N I/O.- Each merge pass reads N and writes N → 2N per pass.- Total I/O = 2N * (1 + num_merge_passes).- With 72 runs and k=64 → num_merge_passes = 2 → total I/O ≈ 2N*(1+2)=6N (i.e., ~3 TB transferred).- With replacement selection reducing runs to ~36, passes = 1 with k=64 (since 36 ≤ 64) → total I/O ≈ 2N*(1+1)=4N.

4. Practical optimizations- Buffers & async I/O: use large sequential read/write buffers, overlap I/O with CPU using threads/async prefetch to hide latency.- Compression: compress runs on disk (e.g., LZ4) to reduce disk I/O when CPU is spare; tradeoff CPU decompression vs lower IO.- Parallel merging: if multiple disks/SSDs available, distribute runs across disks and do independent merges in parallel to increase throughput. On multi-core machines, parallelize comparisons and buffer management.- Multi-stage cascading merges: if k is limited, do balanced merges to keep pass count low and avoid too many temporary files.- External libraries: consider using existing tools (e.g., GNU sort with -T and -S settings) or frameworks (Hadoop external sort) for robustness.- Stability and fault tolerance: write runs atomically, resume capability by checkpointing run metadata.

Trade-offs- Larger k reduces passes but increases open files and memory for buffers.- Replacement selection increases average run length but requires a heap and streaming logic.- Compression reduces I/O but uses CPU; beneficial on CPU-heavy, IO-constrained setups.

Example final config (practical):- Use replacement selection to create ~36 runs (~14 GB each).- Choose k = 32–64 with 2–4 MiB per run buffer, async I/O threads, and LZ4 compression.- Expected passes: 1–2 merges; total I/O 4–6×N depending on runs — acceptable for 500 GB on commodity hardware.

MediumTechnical

84 practiced

Given an integer array, return the k most frequent elements. Implement in Java or Python using a min-heap or quickselect and discuss time/space trade-offs and when to prefer heap vs quickselect. Example: nums=[1,1,1,2,2,3], k=2 => [1,2].

Sample Answer

To solve this, count frequencies with a hash map then either:- use a min-heap of size k (streaming top-k), or- use Quickselect on the list of unique elements to partition by frequency (average linear).

Here's a clear Python implementation using a min-heap:

python

import heapq
from collections import Counter

def topKFrequent(nums, k):
    # Count frequencies
    freq = Counter(nums)
    # Min-heap of (frequency, num)
    heap = []
    for num, f in freq.items():
        if len(heap) < k:
            heapq.heappush(heap, (f, num))
        else:
            # If current freq bigger than smallest in heap, replace
            if f > heap[0][0]:
                heapq.heapreplace(heap, (f, num))
    # Extract numbers from heap
    return [num for (_, num) in heap]

Key points:- Heap approach: simple, streaming-friendly, good when k << n_unique or when input is streaming.- Quickselect: average O(n) time, O(1) extra (in-place on unique list), but worst-case O(n^2) unless randomized; better when k is large (close to n_unique) and you can afford in-place operations.

Complexity:- Building frequency map: O(n) time, O(n) space.- Heap: O(n_unique log k) time, O(k) extra space.- Quickselect: O(n_unique) avg time, O(1) extra (plus map), O(n_unique) worst-case time if not randomized.

Edge cases:- k == 0 or nums empty => return []- k >= number of unique elements => return all unique elements- Duplicates handled by Counter

When to prefer:- Prefer heap for streaming data or small k.- Prefer quickselect for large k with in-memory data and performance-sensitive use (use random pivot to avoid worst-case).

HardTechnical

84 practiced

Provide a rigorous correctness proof for Dijkstra's algorithm (non-negative weights). Explain the invariant maintained when extracting the minimum-distance vertex from the priority queue, use contradiction to show shortest path property, and then discuss why negative edge weights break this property and how Bellman-Ford handles them.

Sample Answer

Claim: In Dijkstra's algorithm (non-negative edge weights) when a vertex u is extracted from the min-priority queue, dist[u] equals the true shortest-path distance d(s,u).

Invariant: At any point, for every extracted (finalized) vertex v, dist[v] = d(s,v). For every non-extracted vertex x, dist[x] is an upper bound: dist[x] ≥ d(s,x), and the priority queue orders vertices by these current upper bounds.

Proof by induction on number of extractions:Base: First extracted is s with dist[s]=0=d(s,s).Inductive step: Assume invariant holds for all extracted vertices. Let u be the next extracted vertex (chosen minimal dist[] among unextracted). Suppose for contradiction dist[u] > d(s,u). Consider a shortest path P from s to u; let y be the first vertex on P that is unextracted (possibly u) and x its predecessor (so x is extracted). By induction dist[x]=d(s,x). Edge (x,y) has weight w ≥ 0, so d(s,y)=d(s,x)+w ≥ dist[x]+w. During relaxation when x was extracted, we would have set dist[y] ≤ dist[x]+w = d(s,y). Since all later updates only decrease dist[y], at extraction time dist[y] ≤ d(s,y). Because edge weights non-negative, distances along P are nondecreasing, so dist[u] ≤ dist[y] + (remaining nonnegative sums) = d(s,u). But we assumed dist[u] > d(s,u) and u had minimal dist among unextracted, contradiction. Hence dist[u]=d(s,u).

Why negative weights break this: The argument uses nonnegativity to ensure once a vertex is finalized, no future path via an unextracted vertex can produce a shorter route to it. If an edge with negative weight leads from an unextracted vertex to a finalized vertex, that finalized vertex's distance could be lowered later, violating the invariant. Example: s→a weight 2, s→b weight 5, b→a weight -4. Dijkstra finalizes a with dist=2 but true shortest dist to a is 1 via b; the algorithm misses that.

How Bellman–Ford handles negatives: Bellman–Ford repeatedly relaxes all edges up to |V|-1 times. Correctness: any shortest simple path has at most |V|-1 edges, so after k iterations all shortest paths with ≤k edges are found; after |V|-1 iterations all simple shortest paths are discovered. Bellman–Ford detects negative cycles by checking for any edge relaxable after |V|-1 iterations; existence implies a negative cycle reachable from s. Trade-off: Bellman–Ford is O(VE) vs Dijkstra’s O(E + V log V) with a heap, but supports negative weights (no negative cycles).

EasyTechnical

74 practiced

Implement a function in Python/Java/C++ that, given an unsorted integer array nums and an integer target, returns indices of two numbers that add to target. Assume exactly one solution and you cannot use the same element twice. Aim for O(n) time and O(n) space. Example: nums = [2,7,11,15], target = 9 => [0,1]. Provide a short explanation of correctness and complexity.

Sample Answer

To solve this, use a hash map to record numbers seen and their indices while scanning the array once. For each number x, check if target - x is already in the map; if so return its index and current index. This is O(n) time and O(n) space.

python

def two_sum(nums, target):
    """
    Return indices of two numbers that add to target.
    Assumes exactly one solution and no reuse of same element.
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    raise ValueError("No two sum solution")

java

import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Correctness: when current number's complement was seen earlier, their indices form a valid solution; since exactly one solution exists, first match is correct. Time complexity: O(n) single pass. Space complexity: O(n) for the hash map. Edge cases: negative numbers, duplicates, and minimal-length arrays are handled.

MediumTechnical

138 practiced

Implement an algorithm to compute the length of the Longest Increasing Subsequence (LIS) in O(n log n) time using the patience-sorting (tails) approach in C++/Java. Explain how binary search is used to maintain tails and why tails length equals LIS length. Provide an example.

Sample Answer

Approach: Use the patience-sorting "tails" method. Maintain an array tails[] where tails[len] = the smallest possible tail value of an increasing subsequence of length len+1. For each number, binary-search tails to find the first element >= num and replace it (or append if none). The number of tails kept equals LIS length.

cpp

// C++ implementation
#include <vector>
#include <algorithm>

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails; // tails[i] = smallest tail of all increasing subseq of length i+1
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x); // first >= x
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

Why binary search: tails is strictly increasing, so lower_bound finds the correct position in O(log n) to either extend a subsequence (append) or improve an existing subsequence by decreasing its tail, maximizing future extension opportunities.

Why tails length == LIS length: Each tails index represents the minimal tail for subsequences of that length. You can’t have an increasing subsequence longer than the number of distinct lengths tracked; conversely, building greedily ensures existence of subsequences reaching that length.

Example: nums = [3,1,2,1,8,5,6]Process: tails evolve -> [3] -> [1] -> [1,2] -> [1,2] -> [1,2,8] -> [1,2,5] -> [1,2,5,6]. Result = 4.

Time: O(n log n). Space: O(n) (tails). Edge cases: empty input -> 0; duplicates handled by lower_bound.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.