Problem Decomposition

Problem Decomposition

[!NOTE] This module explores the core principles of Problem Decomposition, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Trap: “I’ll just start coding.”

Most candidates fail because they solve the wrong problem. Decomposition is the art of breaking a vague request into concrete, testable constraints.

2. The Signal vs. Noise Framework

A problem statement is a mix of Signal (Constraints) and Noise (Story).

Example: “Design a leaderboard.”

  • Noise: “We have millions of gamers playing every day…”
  • Signal: “High write throughput (Updates).”
  • Signal: “Real-time read throughput (Top K).”

Goal: Extract the signal. Ignore the noise.

3. The 4-Step Decomposition Protocol

  1. Inputs & Outputs:
    • “What exactly goes in? (Int array? Stream?)”
    • “What comes out? (Index? Boolean? Sorted List?)”
  2. Constraints:
    • “Can numbers be negative?”
    • “Is the array sorted?”
    • “Memory limit?”
  3. Edge Cases:
    • “Empty input?”
    • “One element?”
    • “All duplicates?”
  4. Strategy Selection:
    • “Sorted input → Binary Search or Two Pointers.”
    • “Top K elements → Heap.”

4. Hardware Truth: Cognitive Load

Why write things down? Your brain’s “Working Memory” can hold ~4 chunks of information. Writing down constraints offloads them from RAM to Disk (Whiteboard), freeing up your brain for the Algorithm.

5. Deep Dive Strategy Lab: Problem Decomposition

Intuition Through Analogy

Think of this chapter like solving under whiteboard time pressure. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?