Core Interview & Competitive Patterns

Competitive programming and technical interviews center on a core suite of canonical archetype patterns that recur across domains. By mastering interval consolidation, heap selection, prefix-sum hash table invariants, and single-cycle ALU bit manipulation, developers can rapidly classify unstructured problem statements and implement optimal solutions under strict time constraints.

This module synthesizes essential problem-solving patterns frequently encountered in systems design and algorithmic interviews, focusing on invariant preservation and asymptotic efficiency.

By the end of this chapter, you will be able to:

1. Consolidate Disjoint & Overlapping Intervals: Sort time boundaries to merge intervals and allocate minimum resource pools via min-heaps in $\mathcal{O}(n\log n)$ time.
2. Track Dynamic Order Statistics: Maintain the $K$-th largest element in $\mathcal{O}(n\log K)$ time and maintain running medians from real-time streams in $\mathcal{O}(\log n)$ insertion time using dual heaps.
3. Exploit Hash Table Invariants: Formulate prefix sum frequency mappings to count continuous subarrays summing to $K$ in $\mathcal{O}(n)$ time across negative numbers.
4. Leverage Single-Cycle Bit Manipulation: Apply hardware-level bitwise primitives (n & (n - 1), n & -n, XOR cancellation) to solve parity, power-of-two, and frequency queries in $\mathcal{O}(1)$ time.

Given an array of intervals $[s_i,e_i]$, combine all overlapping segments into non-overlapping contiguous ranges:

1. Sort by Start Time: Order intervals such that $s_0\le s_1\le \cdots \le s_{n-1}$.
2. Linear Merge Sweep:
   • If the current interval starts after the active merged interval ends ($s_i>\text{last}.\text{end}$), append it as a new disjoint interval.
   • Otherwise, an overlap exists: update $\text{last}.\text{end}\leftarrow \max (\text{last}.\text{end},e_i)$.

export function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  // Sort ascending by start boundary
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const lastMerged = merged[merged.length - 1];

    if (current[0] <= lastMerged[1]) {
      // Overlap detected: expand ending boundary
      lastMerged[1] = Math.max(lastMerged[1], current[1]);
    } else {
      // Disjoint: start new interval block
      merged.push(current);
    }
  }

  return merged;
}

Given meeting schedule intervals, calculate the minimum number of rooms required so that no two meetings overlap in the same room.

• Min-Heap Strategy: Sort meetings by start time. Maintain a min-heap storing the end times of ongoing meetings.
• When evaluating meeting $[s_i,e_i]$:
  • If $s_i\ge \text{heap}.\text{min}()$, the earliest ending meeting has completed $⟹$ reuse the room by popping the root.
  • Push $e_i$ into the min-heap.
• Result: The peak heap size reflects the minimum rooms needed. Overall time complexity: $\mathcal{O}(n\log n)$.

To extract the $K$ largest elements from an unsorted stream of $n$ elements:

• Sorting the full array requires $\mathcal{O}(n\log n)$ time.
• By maintaining a Min-Heap of size $K$, we process each element in $\mathcal{O}(\log K)$ time:
  • Push incoming element $x$ into the min-heap.
  • If the heap size exceeds $K$, remove the minimum element ($\text{extractMin}$).
  • After processing all $n$ items, the heap contains strictly the $K$ largest elements, with the root representing the $K$-th largest element.

To maintain the exact running median of numbers arriving sequentially in $\mathcal{O}(\log n)$ insertion and $\mathcal{O}(1)$ query time:

• Partition the dataset into two balanced halves:
  1. Max-Heap (low): Holds the smaller half of elements (root is the maximum of the lower partition).
  2. Min-Heap (high): Holds the larger half of elements (root is the minimum of the upper partition).

Median Query:

• If total elements is odd: return $\text{low}.\text{peek}()$.
• If total elements is even: return $(\text{low}.\text{peek}()+\text{high}.\text{peek}())/2.0$.

Given an unsorted array containing positive and negative integers, count the total number of continuous subarrays whose sum equals $K$.

Mathematical Invariant

Let $P[i]$ denote the prefix sum up to index $i$. A subarray $A[j\dots i]$ evaluates to sum $K$ if and only if:

By recording the frequencies of prefix sums in a hash table as we iterate, we can query in $\mathcal{O}(1)$ time how many prior prefixes satisfy $P[j-1]=P[i]-K$.

export function subarraySumEqualsK(nums: number[], k: number): number {
  const prefixFrequency = new Map<number, number>();
  // Base case: prefix sum of 0 occurs once initially
  prefixFrequency.set(0, 1);

  let runningSum = 0;
  let totalSubarrays = 0;

  for (let i = 0; i < nums.length; i++) {
    runningSum += nums[i];
    const targetComplement = runningSum - k;

    if (prefixFrequency.has(targetComplement)) {
      totalSubarrays += prefixFrequency.get(targetComplement)!;
    }

    prefixFrequency.set(
      runningSum,
      (prefixFrequency.get(runningSum) || 0) + 1
    );
  }

  return totalSubarrays;
}

Bitwise operations execute directly in CPU Arithmetic Logic Units (ALUs) in a single clock cycle ($\approx 0.3\text{ ns}$).

Primitive 1: Brian Kernighan's Bit-Counting Algorithm

Clears the lowest set bit in an integer in $\mathcal{O}(\text{number of set bits})$:

Proof: Subtracting 1 flips the lowest set bit to 0 and turns all subsequent trailing zeros into ones. Performing a bitwise AND between $n$ and $n-1$ clears exactly that lowest set bit while keeping all higher bits unchanged.

Primitive 2: Power-of-Two Detection

A positive integer is a power of 2 if and only if its binary expansion contains exactly one set bit:

Primitive 3: XOR Cancellation (Single Unique Element)

Exploiting algebraic properties $x\oplus x=0$ and $x\oplus 0=x$: When all elements in an array appear twice except for one unique element, XORing every value collapses duplicate pairs to 0, isolating the unique value in $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space.

Primitive 4: Isolate Lowest Set Bit

Primitive 5: Bitmask Manipulation Primitives

• Test bit $k$: (n >> k) & 1
• Set bit $k$: n | (1 << k)
• Clear bit $k$: n & ~(1 << k)
• Toggle bit $k$: n ^ (1 << k)

1. Halim, S., Halim, F., & Skiena, S. S. (2020). Competitive Programming 4: The Lower Bound of Programming Contests. CP4 Pte Ltd.
2. Laaksonen, A. (2020). Guide to Competitive Programming: Learning and Improving Algorithms Through Contests (2nd ed.). Springer.
3. Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.
4. Warren, H. S. (2012). Hacker's Delight (2nd ed.). Addison-Wesley Professional.