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.

EasyTechnical

20 practiced

Write a function (in your language of choice) that removes duplicates from a sorted array in-place and returns the new length. Your solution should run in O(n) time and use O(1) additional space. Explain boundary cases (empty array, all duplicates) and describe how the approach must change if the array is not sorted but you must perform deduplication on a memory-limited client.

Sample Answer

**Approach (brief)** Use two pointers: a slow pointer `i` tracks the position to write the next unique value; a fast pointer `j` scans the array. When nums[j] != nums[i], increment `i` and set nums[i] = nums[j]. Works in-place, O(n) time, O(1) extra space.

**Code (JavaScript)**

javascript

// removes duplicates from sorted array in-place, returns new length
function removeDuplicates(nums) {
  if (!nums || nums.length === 0) return 0;
  let i = 0; // last unique index
  for (let j = 1; j < nums.length; j++) {
    if (nums[j] !== nums[i]) {
      i++;
      nums[i] = nums[j];
    }
  }
  return i + 1; // length is index + 1
}

**Key concepts & complexity** - Two-pointer in-place deduplication for sorted data. - Time: O(n). Space: O(1) extra. - Stable with respect to order (keeps first occurrences).

**Boundary cases** - Empty array -> returns 0. - Single-element -> returns 1. - All duplicates (e.g., [2,2,2]) -> i stays 0, returns 1; array becomes [2,...]. - No duplicates -> returns original length, array unchanged.

**If array is not sorted (memory-limited client)** - If you can afford to sort in-place (e.g., QuickSort/Timsort): sort in-place O(n log n) then apply two-pointer. - If client memory is very constrained and dataset too large: use external sort (chunk, sort chunks on disk, merge) or stream to server to deduplicate. - If approximate dedup with tiny memory acceptable: use a Bloom filter to filter probable uniques (false positives possible).

For a full-stack role, prefer server-side or background job (external sort/DB unique index) when client memory is limited.

HardTechnical

30 practiced

Propose a memory layout and search algorithm for a compressed prefix trie (radix tree) used in an in-memory key-value store where cache misses dominate latency. Consider node packing, inline labels, pointer elimination (indexing into contiguous arrays), SIMD-friendly comparisons, and path compression. Analyze trade-offs between lookup speed, update complexity, and memory overhead.

Sample Answer

**Approach summary**Design a cache-friendly, compacted radix tree stored in contiguous arrays to minimize pointer chasing, use inline labels for short edges, and SIMD-assisted key fragment comparisons. Lookups become index arithmetic + small linear/SIMD compares; updates handle splits with local reallocations.

**Memory layout**- One contiguous node array (Node[]). Each Node: - 32-bit header: type/label length/child-count/flags - 32-bit payload index (or value slot) or 0 - 16/8-bit inline label bytes up to L (e.g., L=8) - child metadata: for small fanout, store (char byte, uint32 child_index) pairs in-line; for large fanout, store an index to a compact child-list slab.- Separate slabs: Labels slab (for long compressed edges), values slab.- Free-list per slab for updates to limit global moves.

**Lookup algorithm**1. Start at root index = 0, position p = 0 in key.2. At node: compare inline label (length l) with key[p:p+l]: - If l ≤ SIMD width, use SIMD memcmp; else fall back to scalar or compare label slice pointer with longer label in labels slab (also SIMD-ready).3. If mismatch => fail; else p += l.4. If payload present and p == key.length => return value.5. Search child-list: for small child-count, linear scan with SIMD-friendly packing of child bytes; for larger, use binary search on sorted child bytes or small bitmap -> direct select.6. Follow child_index (integer) — no pointers.

Pseudocode (lookup core)

uint32 lookup(key):
  i=0; node_idx=0
  while true:
    node = Node[node_idx]
    if simd_cmp(node.label, key[i:]) != full_match: return NOT_FOUND
    i += node.label_len
    if i==key.len and node.has_value: return value_at(node.value_idx)
    child = find_child(node, key[i])
    if child == NONE: return NOT_FOUND
    node_idx = child.index

**Optimizations**- Pointer elimination: child_index is 32-bit offset into Node[]. Contiguous memory ensures index fits and improves prefetching.- SIMD: compare up to 16/32 bytes at once (SSE/AVX2/NEON), return mismatch position quickly.- Path compression: store maximal compressed labels; reduces node hops and cache lines.- Inline small labels and child entries to keep hot path within one cache line (~64B).

**Trade-offs**- Lookup speed: very high due to reduced pointer chasing, SIMD compares, and path compression. Best when keys share long prefixes.- Update complexity: moderate — inserts/splits require shifting node array or allocating in slab and updating parent child_index. Use local reallocation or indirection via small relocation table to avoid global moves.- Memory overhead: lower than pointer-based tries because no 64-bit pointers and header compression, but labels slab + child lists add complexity. Inline limits (L) trade extra copies vs fewer indirections.- Concurrency: need atomic swaps for child_index and epoch-based reclamation for safe updates.

**When to choose**- Read-heavy, latency-sensitive systems: prefer this layout.- Write-heavy workloads: consider relaxed compaction or hybrid (log-structured updates + periodic compaction).

HardTechnical

16 practiced

Explain Johnson's algorithm for all-pairs shortest paths: compute node potentials with Bellman-Ford, reweight edges to non-negative values, then run Dijkstra from each source. Provide a correctness sketch showing reweighting preserves shortest-path order, discuss numerical stability and overflow issues, and analyze runtime on large sparse graphs.

Sample Answer

**Approach (one-paragraph)** Johnson’s algorithm computes all-pairs shortest paths for graphs with negative weights (but no negative cycles) by: (1) add a new node q linked to every vertex with edge weight 0 and run Bellman–Ford from q to get potentials h(v); (2) reweight each original edge (u,v) to w'(u,v)=w(u,v)+h(u)-h(v) so all w' >= 0; (3) run Dijkstra from every vertex on the reweighted graph and recover original distances.

**Key formulas / invariants**

text

w'(u,v) = w(u,v) + h(u) - h(v)

Plain English: this shifts edge costs by vertex potentials.

text

d'(s,t) = d(s,t) + h(s) - h(t)

Intuition: any path’s total weight gains the telescoping sum of h terms, so shortest-path order is preserved and you can recover d(s,t)=d'(s,t)-h(s)+h(t).

**Correctness sketch**- Bellman–Ford from q yields h(v)=dist(q,v) or detects a negative cycle (fail early).- For any edge (u,v), triangle inequality from q implies h(v) <= h(u)+w(u,v) so w'(u,v) >= 0.- For any s→t path P, weight'(P) = weight(P) + h(s) - h(t). Minimizers are identical because adding the same constant (h(s)-h(t)) to every s→t path preserves ordering. Hence running Dijkstra on non-negative w' gives correct shortest-path trees; convert back using the second formula.

**Numerical stability & overflow**- Treat “infinity” separately; never add INF to numbers. Check Bellman–Ford relaxations with INF guards.- Use 64-bit signed integers if weights and path lengths fit; otherwise use arbitrary-precision or saturating arithmetic. Beware sums of many large negative/positive weights causing overflow.- Detect negative cycles with Bellman–Ford early; don’t proceed if found.- Use careful comparisons (<= vs <) to avoid precision issues when using floating point weights—prefer integers.

**Runtime on large sparse graphs**- Bellman–Ford: O(VE). Dijkstra with binary heap: O(E log V) per source, so V runs cost O(V E log V). Total O(VE log V + VE) → dominated by O(V E log V).- For sparse graphs E = O(V): runtime ≈ O(V^2 log V), much better than Floyd–Warshall’s O(V^3) for large V.- With a Fibonacci heap, Dijkstra per source is O(E + V log V) so total becomes O(VE + V^2 log V) — sometimes preferable for dense cases.- Practical note for full-stack use: for web services handling large sparse graphs, prefer Johnson for negative edges; if all weights non-negative and many sources, run Dijkstra only for the needed sources; consider caching computed shortest-paths or using multi-source variants / heuristics to reduce repeated work.

MediumSystem Design

22 practiced

Design a server-side index to support fast arbitrary substring queries over 10GB of logs. Compare building a suffix array, suffix automaton, and an inverted index approach. For each, discuss construction time, memory footprint, query time, update/append strategies for continuous log ingestion, and pragmatic operational trade-offs.

Sample Answer

**Approach summary (goal: fast arbitrary substring queries over 10GB logs)**

**Suffix Array**- Construction: O(n)–O(n log n) with SA algorithms (e.g., SA-IS); for 10GB this is expensive but one-time offline task.- Memory: stores full text + SA (4–8 bytes per position) → ~40–80GB extra; plus LCP for faster searches.- Query time: binary search on SA O(m log n) where m = pattern length; with FM-index (compressed SA) can be much faster and smaller.- Updates: poor — appends require rebuilding or complex merge; not suited for continuous ingestion.- Trade-offs: best for pure read-heavy, exact substring matching; heavy offline resource cost.

**Suffix Automaton (SAM)**- Construction: online O(n) time, single pass; memory proportional to distinct substrings ~2n states worst-case.- Memory: could be ~tens of GB for 10GB logs, but often smaller in practice.- Query time: O(m) to check existence and can be extended to count/locate occurrences with extra indexing.- Updates: naturally supports streaming appends incrementally.- Trade-offs: good for existence and counts, but retrieving positions needs extra tracking (adds memory). More complex to implement/maintain.

**Inverted Index (n-grams / tokens) — Pragmatic choice**- Construction: tokenize into k-grams (e.g., 3-grams) or word tokens; build postings lists.- Memory: controllable via k, compression (delta, variable byte); likely tens of GB but much smaller than raw SA.- Query time: fast — decompose query into n-grams, intersect postings; false positives require verification over original logs.- Updates: excellent — append new logs, update postings incrementally; fits streaming pipelines (Kafka → indexer).- Trade-offs: approximate for arbitrary substrings (choose k to balance recall/size). Simple to shard, replicate, and integrate with search stacks (Elasticsearch/Lucene).

Recommendation for Full-Stack context: use an n-gram inverted index with compression and background verification. It balances query latency, incremental updates, operational simplicity, and integrates well with existing infra. Consider hybrid: inverted index for fast filtering + occasional background suffix-structure rebuilds for heavy analytical queries.

MediumTechnical

22 practiced

You're building a server-side diff tool for code reviews. Design an algorithm to compute the Longest Common Subsequence (LCS) between two files up to 5000 lines. Discuss time/space trade-offs, improvements such as Hunt-Szymanski or bitset-based DP, and memory-efficient strategies (Hirschberg) to reconstruct diff hunks for UI rendering.

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.