Sorting and Searching Algorithms Questions

Approach (brief)
Binary-search on the smaller array to partition both arrays so left partitions contain k = (m+n+1)//2 elements. Maintain invariant: max(leftA) <= min(rightB) and max(leftB) <= min(rightA). When invariant holds, median is either max(lefts) (odd) or average of max(lefts) and min(rights) (even).

Code

from typing import List
import math

def find_median_sorted_arrays(a: List[int], b: List[int]) -> float:
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    total = m + n
    half = (total + 1) // 2

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2           # elements from a in left partition
        j = half - i                 # elements from b in left partition

        Aleft = a[i-1] if i > 0 else -math.inf
        Aright = a[i] if i < m else math.inf
        Bleft = b[j-1] if j > 0 else -math.inf
        Bright = b[j] if j < n else math.inf

        if Aleft <= Bright and Bleft <= Aright:
            if total % 2:            # odd
                return float(max(Aleft, Bleft))
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
        elif Aleft > Bright:
            hi = i - 1
        else:
            lo = i + 1
    raise ValueError("Input arrays not sorted or invalid")

Correctness reasoning
Partitioning ensures left side contains k smallest elements. Binary search on i adjusts relative sizes until cross-boundary order holds (Aleft <= Bright and Bleft <= Aright). When true, extremes of partitions determine median. Using infinities handles empty partitions. Loop runs O(log min(m,n)); only O(1) extra space.

Edge cases

• One array empty (works via infinities).
• All elements on one side equal.
• Even/odd total length handled by half and parity check.

Clarify constraints & goal

• Input: 1 TB log file on disk, sort by timestamp.
• Memory: 1 GB RAM available to worker; assume OS needs some (reserve ~200 MB), leaving ~800 MB for sorting/buffers.
• Goal: produce a single sorted file for downstream analytics.

High-level approach

• Use external merge-sort (sort-then-merge) with multi-pass k-way merging, optimization for sequential I/O and parallel chunking.

Step-by-step plan

1. Chunking (map phase)

• Choose chunk size = 600–700 MB to leave RAM for buffers/heap/OS. With 1 TB this yields ~1500 chunks.
• Read chunk sequentially from disk into memory buffer, parse records, and in-memory sort by timestamp (use efficient radix/unicode-aware comparator as appropriate).
• Write each sorted chunk as a run file to disk (e.g., runs/run0001.sorted). Write sequentially to avoid seeks; use fsync or atomic rename as needed.

2. Parallelism

• Read+sort stage: run multiple parallel workers limited by CPU cores and memory. For example with 4 cores, run 3 workers each using ~700 MB total shared memory pool and letting one core handle I/O coordination.
• Use thread/process pool; throttle concurrency so aggregated memory < available.

3. Disk I/O considerations

• Use large sequential reads/writes (e.g., 1–4 MB I/O buffers).
• Prefer SSD for better random-read merge performance; if HDD, emphasize sequential passes and fewer merge passes.
• Optionally compress runs (e.g., snappy) to reduce I/O if CPU allows.

4. Final merge (reduce phase)

• Direct k-way merging of ~1500 runs would require too many file descriptors and small buffers. Use multi-pass merging:
  • Pick fan-in K based on file descriptor limit and buffer needs, e.g., K = 64.
  • Merge groups of K runs into intermediate runs. Each merge uses a K-way min-heap of current head records and per-run read buffer (e.g., 1–2 MB each). Memory per merge ≈ K * buffer_size + heap ≈ 64*1MB ~ 64MB.
  • Repeat merging passes: 1500 -> ceil(1500/64)=24 intermediate runs -> final merge of 24 runs in one pass.
• Final pass: open all remaining runs, allocate read buffers per run and a write buffer; maintain min-heap keyed on timestamp to output the next record. Flush writes in large blocks.

5. Implementation details & robustness

• Use stream parsing to avoid storing whole records; store pointers or small in-memory structs.
• Use stable sort if needed.
• Checkpoint progress (which runs produced) to resume on failure.
• Validate final sort by sampling and checking monotonic timestamps.

Complexity & trade-offs

• I/O cost: O(N log_K N) in passes but dominated by sequential reads/writes ~ 2–(passes) × data size. Typical two- or three-pass merge is efficient.
• CPU: in-memory sorts per chunk cost O(M log M) per chunk; merging uses heap operations O(log K) per record.
• Trade-offs: Larger K reduces passes but increases memory and descriptors; compression reduces I/O at cost of CPU.

This plan produces a single sorted output while respecting 1GB memory by tuning chunk size, using parallel chunk-sorts, and performing controlled multi-pass k-way merges with buffered sequential I/O.

Approach (two‑pointer merge)
Use two pointers i, j iterating over arrays a and b, append the smaller element to result until one array is exhausted, then extend with the remainder. Stable, O(n) time.

Code

from typing import List

def merge_sorted(a: List[int], b: List[int]) -> List[int]:
    # Two-pointer merge into a new list
    i = j = 0
    n, m = len(a), len(b)
    res: List[int] = []
    while i < n and j < m:
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    if i < n:
        res.extend(a[i:])
    if j < m:
        res.extend(b[j:])
    return res

Complexity

• Time: O(n + m)
• Space: O(n + m) for result (in-place alternative below avoids extra array)

Edge cases

• One or both arrays empty
• Duplicates and negative numbers handled by <= comparator

In-place alternative (a has extra capacity at end)
If array a has capacity to hold b (e.g., a contains valid n elements followed by space for m more), merge from the end:

• Set write = n + m - 1, i = n - 1, j = m - 1
• While j >= 0: place larger of a[i] and b[j] at a[write], decrement pointers
• This is O(n + m) time and O(1) extra space — useful in backend systems to reduce allocations when merging large sorted datasets.

Approach (brief)
Use median-of-medians: partition array into groups of 5, find each group's median, recursively find median of those medians as pivot, partition around pivot and recurse into correct side. That guarantees a good pivot and worst-case linear time.

Code

import java.util.*;
public class Selection {
  // returns k-th smallest (0-based)
  public static int medianOfMediansSelect(int[] arr, int k) {
    if (k < 0 || k >= arr.length) throw new IllegalArgumentException();
    return select(arr, 0, arr.length - 1, k);
  }

  private static int select(int[] a, int lo, int hi, int k) {
    while (true) {
      if (lo == hi) return a[lo];
      int pivot = pivotByMedianOfMedians(a, lo, hi);
      int[] range = partition(a, lo, hi, pivot);
      int leftSize = range[0] - lo;
      if (k < leftSize) hi = range[0] - 1;
      else if (k <= range[1] - lo) return pivot;
      else {
        k -= (range[1] - lo + 1);
        lo = range[1] + 1;
      }
    }
  }

  private static int pivotByMedianOfMedians(int[] a, int lo, int hi) {
    int n = hi - lo + 1;
    if (n <= 5) {
      Arrays.sort(a, lo, hi + 1);
      return a[lo + n/2];
    }
    int numMeds = 0;
    for (int i = lo; i <= hi; i += 5) {
      int end = Math.min(i + 4, hi);
      Arrays.sort(a, i, end + 1);
      int med = a[i + (end - i)/2];
      swap(a, lo + numMeds, indexOf(a, med, i, end)); // move median forward
      numMeds++;
    }
    return select(a, lo, lo + numMeds - 1, numMeds/2);
  }

  private static int indexOf(int[] a, int val, int lo, int hi) {
    for (int i = lo; i <= hi; i++) if (a[i] == val) return i;
    return lo;
  }

  private static int[] partition(int[] a, int lo, int hi, int pivot) {
    int i = lo, lt = lo, gt = hi;
    while (i <= gt) {
      if (a[i] < pivot) swap(a, lt++, i++);
      else if (a[i] > pivot) swap(a, i, gt--);
      else i++;
    }
    return new int[]{lt, gt};
  }

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

Why O(n) worst-case (sketch)
Grouping into 5 ensures each median is >= two elements in its group and <= two elements. The median-of-medians pivot is greater than at least 3n/10 elements and less than at least 3n/10 elements. Recurrence: T(n) <= T(n/5) + T(7n/10) + O(n). This solves to T(n) = O(n). Intuitively: pivot eliminates a constant fraction each step so total work sums linearly.

Edge cases / notes

• k is 0-based; validate bounds.
• Using group size 5 is standard; 3 worsens constants, larger sizes increase median-finding cost.

Approach (two pointers)

• Use left/right pointers on the sorted array. Move pointers inward; when sum equals target, record the value pair and skip duplicates to ensure unique pairs. This is O(n) time and O(1) extra space (output excluded).

Code

from typing import List, Tuple

def unique_pairs(nums: List[int], target: int) -> List[Tuple[int,int]]:
    res = []
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            res.append((nums[i], nums[j]))
            # skip duplicates for left
            left_val = nums[i]
            while i < j and nums[i] == left_val:
                i += 1
            # skip duplicates for right
            right_val = nums[j]
            while i < j and nums[j] == right_val:
                j -= 1
        elif s < target:
            i += 1
        else:
            j -= 1
    return res

Explanation & Complexity

• Why: Sorted order lets us adjust pointers deterministically.
• Time: O(n) — each element visited at most once.
• Space: O(1) extra (output excluded).
• Edge cases: empty array, single element, all duplicates, negative numbers. This implementation handles them by pointer checks.