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

19 practiced

Implement the Misra-Gries (Frequent) algorithm in Python to find all elements that occur more than n/k times in a stream. Include code, explain the memory guarantees, and show how to merge counters from multiple workers to get a correct global heavy-hitter set with provable guarantees.

Sample Answer

We can use the Misra–Gries (a.k.a. Frequent) algorithm to maintain at most k-1 candidate counters for a stream and guarantee that every element with true frequency > n/k is in the candidate set. Memory is O(k). The algorithm is mergeable: you can merge per-worker MG summaries by summing counts for matching keys then repeatedly removing the smallest count (or decrementing all) until ≤ k-1 candidates remain; this preserves the same provable error bounds.

Approach:1. Maintain a dict of up to k-1 counters.2. On each element: if in counters, increment; elif len<candidates, add with count=1; else decrement all counts by 1 and drop zeros.3. To get true heavy hitters, after processing you must (optionally) do a second pass over data (or aggregated exact counts) limited to candidates to confirm which exceed n/k.

Python implementation (stream as iterator; supports merge):

python

from collections import Counter
from typing import Dict, Iterable, Tuple

class MisraGries:
    def __init__(self, k: int):
        assert k >= 2
        self.k = k
        self.counters: Dict[object, int] = {}

    def process(self, stream: Iterable):
        for x in stream:
            if x in self.counters:
                self.counters[x] += 1
            elif len(self.counters) < self.k - 1:
                self.counters[x] = 1
            else:
                # decrement all by 1 and remove zeros
                to_delete = []
                for key in list(self.counters):
                    self.counters[key] -= 1
                    if self.counters[key] == 0:
                        del self.counters[key]

    def merge(self, other: "MisraGries") -> "MisraGries":
        assert self.k == other.k
        merged = MisraGries(self.k)
        merged.counters = dict(self.counters)  # shallow copy
        for key, cnt in other.counters.items():
            merged.counters[key] = merged.counters.get(key, 0) + cnt
        # If too many candidates, prune by repeated global decrement:
        while len(merged.counters) > self.k - 1:
            # find minimum count
            m = min(merged.counters.values())
            # subtract m from all (faster) and remove zeros
            for key in list(merged.counters):
                merged.counters[key] -= m
                if merged.counters[key] == 0:
                    del merged.counters[key]
        return merged

    def candidates(self) -> Dict[object, int]:
        return dict(self.counters)

Key points and guarantees:- Memory: O(k) counters (k-1 keys).- Error bound: For final summary over stream length n, for any element x not in candidates, true_count(x) ≤ n/k. For any candidate y, the stored count is a lower bound: stored_count(y) ≤ true_count(y) and true_count(y) ≤ stored_count(y) + n/k.- Merge correctness: Summing per-key counts from partitions produces counts that are each a lower bound on true global counts; pruning by repeatedly subtracting the same amount from all keys simulates global decrements and preserves the guarantee that any element with true global frequency > n/k remains as a candidate.- To produce exact heavy hitters (> n/k), after building/merging summaries, do a second pass (or use exact aggregated counts) restricted to candidate keys and filter by threshold n/k.

Complexity:- Per element: amortized O(1) updates (worst-case O(k) when decrementing).- Merge: O(u + k log k) where u is unique keys in both summaries (pruning steps linear in k).

EasyTechnical

16 practiced

Explain when to choose a hash-based join vs. a sort-merge join in a distributed data pipeline. Compare algorithmic complexity, memory and network IO, skew robustness, support for range predicates, and operational considerations (e.g., ease of checkpointing, fault tolerance). Give examples from Spark or MapReduce environments.

Sample Answer

Use-case summary: choose hash-based join (broadcast or shuffled hash) when one side is small or equi-join keys are evenly distributed and you need low-latency joins. Choose sort-merge join when both sides are large, you already have data partitioned/sorted on join keys, or you need range/inequality joins and stronger robustness to skewed sizes.

Comparison:

- Algorithmic complexity: - Hash join: O(n + m) expected (build hash on smaller side, probe larger). Excellent average-case. - Sort-merge join: O(n log n + m log m) if sorting required; O(n + m) if inputs already sorted/partitioned.

- Memory and network I/O: - Hash join: memory heavy for build side (must fit hash table or be chunked); broadcast hash minimizes shuffle if small side fits driver/executor memory. Shuffled hash needs partitioned hash tables per reducer. Network I/O low for broadcast; higher if spilling and repeated shuffle. - Sort-merge: requires shuffling to partition by key but then sorts; stable memory use using external sort (streams to disk), so less peak memory but more disk I/O. Network I/O similar to shuffle phase for both—sort-merge often has predictable shuffle cost.

- Skew robustness: - Hash join: suffers if build side or key distribution is skewed — a single partition can blow up memory. Mitigate via salting, sampling, or skew-aware strategies. - Sort-merge: more robust because external sort can spill large partitions; but a very skewed key can still overload a single reducer unless mitigated (range partitioning, custom partitioner).

- Support for range/inequality predicates: - Hash join: only supports equality joins. - Sort-merge: supports equality and range/inequality joins efficiently because sorted order enables merge-style sweeping and range scans.

- Operational considerations (checkpointing, fault tolerance): - Hash join: in systems like Spark, broadcast hash is simple and recomputable — small data broadcasted on task retry; shuffled hash may require disk spill state but is recomputable from lineage. Checkpointing is less common; intermediate state is ephemeral. - Sort-merge: aligns with Spark’s shuffle write/read model; shuffle files are written to local disk and can be recomputed on failure. External sort spill files mean jobs tolerate larger-than-memory. Checkpointing at shuffle boundaries is natural in MapReduce (map outputs persisted for reduce stage).

Examples:- Spark: Spark SQL uses BroadcastHashJoin when one side size < spark.sql.autoBroadcastJoinThreshold. For large tables, it uses SortMergeJoin (requires same partitioning and sorting; used by default for large equi-joins). Spark also offers ShuffleHashJoin for cases where both are partitioned but smallish per-partition.- Hadoop MapReduce: Classic map-side joins (replicated small table into distributed cache → broadcast hash) vs. reduce-side sort-merge joins where mappers tag and reducers receive all records for a key and perform merge logic.

Recommendation:- If one table << other and fits memory: use broadcast/hash join for performance and lower latency.- If both large, or need range joins, or stable behavior under larger-than-memory: use sort-merge.- Always sample data to detect skew and choose salt/partitioning strategies or hybrid approaches (skew-aware join) when necessary.

EasyTechnical

16 practiced

Explain Count-Min Sketch and when you would prefer it over a Bloom filter or exact HashMap for frequency estimation in streaming telemetry. Describe how to choose width (w) and depth (d) to achieve error bounds epsilon and delta, show how to estimate frequency for an item, and explain merging sketches across parallel workers.

Sample Answer

Count‑Min Sketch (CMS) is a compact, mergeable sketch for approximate frequency counts in data streams. It maintains a d×w matrix of nonnegative counters and d pairwise‑independent hash functions. For each incoming item x you increment counters at positions (i, h_i(x)) for i=1..d.

When to prefer CMS:- Use CMS when you need fast, memory‑bounded approximate frequencies (heavy hitters, approximate cardinalities per key) on high‑throughput streams.- Prefer CMS over a Bloom filter because Bloom filters only answer membership queries (with false positives) and do not provide frequency estimates.- Prefer CMS over an exact HashMap when memory or CPU at scale is constrained (e.g., massive cardinality or per‑worker memory limits); CMS trades controlled additive error for much smaller space and O(d) update/query time.

Error bounds and choosing w, d:- CMS guarantees that for true frequency f(x) and L1 total count F = Σ_y f(y), the estimate f̂(x) satisfies f̂(x) ≥ f(x) and with probability ≥ 1−δ: f̂(x) ≤ f(x) + εF.- To achieve additive error εF with failure probability δ choose: w = ceil(e / ε) (e ≈ 2.71828) d = ceil(ln(1/δ)) (Common derivation: use pairwise hashing and median-of-means via d rows; other constants appear in alternate analyses, but these are standard.)

Estimating frequency for an item:- Query: compute counts c_i = C[i, h_i(x)] for i=1..d. Return f̂(x) = min_i c_i.- Rationale: each c_i is f(x) plus noise from collisions; taking the minimum reduces overestimation bias.

Merging across parallel workers:- CMS is linear: to merge sketches built over disjoint or overlapping partitions, perform element‑wise addition of the d×w counter matrices (assuming identical w,d and identical hash functions). The merged sketch has counts equal to the sum of partitions and preserves the same error guarantees.- Practical note: ensure consistent hash functions and identical parameters across workers; when using different seeds, remap or rebuild with same seeds.

Complexity and practical tips:- Space: O(w·d) = O((1/ε)·log(1/δ)). Update/query time: O(d).- Use conservative update (optional) to reduce overestimation when tracking counts that only increase moderately.- Monitor total F (sum of increments) to interpret εF additive error.- If you need no overestimation (exact top‑k), combine CMS with a heavy-hitters algorithm (Count‑Sketch or SpaceSaving) or maintain exact counts for top candidates.

HardTechnical

30 practiced

Provide a high-level proof sketch that union-by-rank combined with path compression yields amortized near-constant time per union/find operation bounded by the inverse-Ackermann function α(n). Explain the intuition behind the bound, key lemmas used, and the practical implications for processing billions of union/find operations in data lineage or clustering workloads.

Sample Answer

Proof sketch (high level):

Goal: Show sequence of m union/find operations on n items using union-by-rank + path compression takes O(m α(n)) time, where α is the inverse-Ackermann function (very slowly growing).

Intuition:- Union-by-rank keeps trees shallow by always attaching a lower-rank root under a higher-rank root; a node’s rank only increases when two equal-rank roots are unioned, so ranks along parent pointers strictly increase.- Path compression flattens trees during finds, making future finds cheaper.- Combine these: few rank increases per node, and path compression ensures most traversals are across edges that get shortened; only very few expensive hops remain. The accounting yields the α(n) factor.

Key lemmas / steps:1. Rank monotonicity: A node’s rank is nondecreasing and a child’s rank < parent’s rank. Ranks are integers bounded by ⌊log n⌋ in a simple bound, but tighter analysis uses Ackermann-related hierarchy.2. Size lower bound: A node of rank r has subtree size ≥ 2^r (so rank ≤ log n). This limits how many nodes can have large rank.3. Level decomposition (Tarjan): Define a rapidly-growing sequence A0,A1,... related to Ackermann; assign each node a level based on its rank relative to that sequence. There are only α(n) meaningful levels because Ackermann grows extremely fast.4. Charging argument: For a single find, charge each traversed node to either (a) a successful compression that reduces its level (can happen only few times because levels increase rarely), or (b) an amortized constant. Summing charges over all operations yields O(m α(n)) total work.

Consequence: amortized cost per operation is O(α(n)), which for all realistic n is ≤ 4–5. For example, even if n is astronomically large (far beyond counts in real systems), α(n) ≤ 5.

Practical implications for data engineering:- For data lineage or clustering at billion-scale (n,m ~ 10^9–10^12), the DSU cost is effectively constant per operation. Using union-by-rank + path compression in distributed/in-memory pipelines yields negligible overhead relative to I/O and shuffling costs.- Implementation notes: prefer iterative finds with path compression, use 32/64-bit arrays for parent/rank, and batch unions/finds to exploit locality. In distributed settings, coordinate merges (e.g., via hierarchical aggregation or union of partition-level DSUs) to avoid communication blowups; the local complexity guarantee still ensures CPU time for union/find is not the bottleneck.

EasyTechnical

20 practiced

Implement a Python function merge_sorted_files(file1_path, file2_path, output_path, buffer_lines) that merges two very large sorted text files (one record per line) into a single sorted output. Files do not fit in memory; you may only buffer up to buffer_lines lines in memory at any time. Provide code or clear pseudocode, explain IO patterns, how you handle duplicate keys, and discuss edge cases such as different line encodings and partially corrupt lines.

Sample Answer

Approach: stream both files in parallel, reading at most buffer_lines lines total into memory. Use small internal buffers (generators that refill by reading blocks of lines). Compare current head lines and write the smaller one to output. Preserve duplicates (write both); optionally dedupe with a flag.

python

import io

def _line_iter(path, buffer_lines, encoding='utf-8', errors='strict'):
    with open(path, 'r', encoding=encoding, errors=errors) as f:
        while True:
            block = []
            for _ in range(buffer_lines):
                line = f.readline()
                if not line:
                    break
                # strip only trailing newline; preserve key formatting
                block.append(line.rstrip('\n'))
            if not block:
                break
            for line in block:
                yield line

def merge_sorted_files(file1_path, file2_path, output_path, buffer_lines, encoding='utf-8', errors='strict', dedupe=False):
    it1 = _line_iter(file1_path, max(1, buffer_lines//2), encoding, errors)
    it2 = _line_iter(file2_path, max(1, buffer_lines//2), encoding, errors)
    try:
        a = next(it1)
    except StopIteration:
        a = None
    try:
        b = next(it2)
    except StopIteration:
        b = None

    with open(output_path, 'w', encoding=encoding, errors=errors) as out:
        last_written = None
        while a is not None or b is not None:
            # choose which to write
            if b is None or (a is not None and a <= b):
                candidate = a
                try:
                    a = next(it1)
                except StopIteration:
                    a = None
            else:
                candidate = b
                try:
                    b = next(it2)
                except StopIteration:
                    b = None

            if dedupe and candidate == last_written:
                continue
            out.write(candidate + '\n')
            last_written = candidate

Key points / IO pattern:- Read blocks (buffered lines) from each file to reduce syscalls; iterators yield one line at a time to merge logic.- buffer_lines parameter is divided between the two inputs so total buffered lines ≤ buffer_lines.- Streaming merge is O(n) time, O(buffer_lines) memory.

Duplicate handling:- Default: preserve duplicates and their relative order from inputs.- Option dedupe=True will suppress consecutive duplicates in output (useful if both files may contain same keys).

Edge cases:- Different encodings: expose encoding and errors args; choose 'utf-8' or detect with chardet prior to run.- Partially corrupt lines: open with errors='replace' or wrap reads in try/except; log and skip malformed lines.- Very small buffer_lines: ensure at least 1 line per source.- Empty files or trailing newlines: handled by StopIteration.- Non-text binary content: detect and fail fast with clear error.

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.