Data Structures & Algorithms Masterclass

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐⭐
• Concept / Summary: Computational thinking is a formal problem-solving process that formulates problems such that their solutions can be represented as computational steps.
• Detailed Explanation:
  Computational thinking is not merely programming; it is an analytical methodology used to deconstruct complexity. It comprises four fundamental pillars:

1. Decomposition: Breaking down a complex, multifaceted problem into smaller, isolated, manageable sub-problems (e.g., dividing an e-commerce checkout into inventory deduction, tax calculation, payment processing, and notification).
2. Pattern Recognition: Observing trends, repeating structures, or shared characteristics across decomposed problems (e.g., recognizing that searching an inventory and searching user records both boil down to binary search on ordered sets).
3. Abstraction: Filtering out irrelevant hardware or domain-specific noise to focus purely on core mathematical and logical properties (e.g., modeling a road transportation network purely as a directed weighted graph of vertices and edges).
4. Algorithm Design: Developing a step-by-step, deterministic sequence of instructions or rules that guarantees a correct result for any valid input in finite time.

• Code Example:

// Demonstrating algorithmic decomposition: Calculating Order Total
public class ComputationalThinkingDemo {
    // 1. Decomposed step: Calculate raw subtotal
    public static double calculateSubtotal(double[] prices) {
        double sum = 0;
        for (double p : prices) sum += p;
        return sum;
    }
    // 2. Decomposed step: Apply discount rule
    public static double applyDiscount(double subtotal, double discountPercent) {
        return subtotal * (1.0 - (discountPercent / 100.0));
    }
    // 3. Decomposed step: Calculate tax
    public static double applyTax(double netAmount, double taxRatePercent) {
        return netAmount * (1.0 + (taxRatePercent / 100.0));
    }
    public static void main(String[] args) {
        double[] cart = {49.99, 19.99, 29.99};
        double subtotal = calculateSubtotal(cart);
        double discounted = applyDiscount(subtotal, 10.0);
        double total = applyTax(discounted, 5.0);
        System.out.printf("Final Total: $%.2f\n", total);
    }
}

• Common Pitfalls & Edge Cases:
  Conflating computational thinking with writing syntax; attempting to code an algorithm before decomposing the problem state and boundary rules leads to spaghetti code and unhandled edge cases.
• Follow-up Questions:
  How does abstraction in computational thinking map to the concept of Abstract Data Types (ADTs) in software engineering?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Problem identification involves establishing unambiguous input specifications, expected output formats, preconditions, constraints, and success criteria.
• Detailed Explanation:
  A computational problem is a mathematical relationship between a set of valid inputs (domain) and corresponding valid outputs (codomain). Rigorous identification requires answering five essential questions:

1. Input Domain: What exact data types, structures, and bounds are expected? (e.g., array of 32-bit signed integers, size N where 1 <= N <= 10^5).
2. Output Specification: What must be returned? (e.g., indices of the pair summing to target, or boolean indicating existence).
3. Preconditions: What can be assumed before execution? (e.g., array is already sorted in non-descending order, or input contains no null elements).
4. Resource Constraints: What are the strict time complexity limits (e.g., must execute within 1.0 second, implying at most ~10^7 operations) and memory limits (e.g., 256 MB)?
5. Degenerate and Edge Cases: What happens if the input is empty (N=0), has a single element (N=1), contains duplicates, or contains extreme values (e.g., Integer.MIN_VALUE)?

• Code Example:

public class ProblemDefinitionCheck {
    // Problem: Find two distinct indices i and j such that arr[i] + arr[j] == target.
    // Preconditions: arr != null, arr.length >= 2, exactly one valid pair exists.
    public static int[] twoSumSorted(int[] arr, int target) {
        if (arr == null || arr.length < 2) {
            throw new IllegalArgumentException("Violates precondition: minimum 2 elements required");
        }
        int left = 0, right = arr.length - 1;
        while (left < right) {
            long currentSum = (long) arr[left] + arr[right]; // Prevent 32-bit integer overflow
            if (currentSum == target) {
                return new int[] {left, right};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        throw new IllegalStateException("No valid pair found satisfying the target constraint");
    }
    public static void main(String[] args) {
        int[] sorted = {2, 7, 11, 15};
        int[] result = twoSumSorted(sorted, 9);
        System.out.println("Indices: " + result[0] + ", " + result[1]);
    }
}

• Common Pitfalls & Edge Cases:
  Failing to account for integer overflow when summing boundary inputs like Integer.MAX_VALUE + Integer.MAX_VALUE.
• Follow-up Questions:
  What is the difference between a decision problem, an optimization problem, and a search problem?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: An algorithm is a theoretical step-by-step mathematical recipe; pseudocode is an informal, language-agnostic textual representation; a program is concrete, machine-executable code bound to language syntax.
• Detailed Explanation:
  The three concepts represent different levels of abstraction in problem solving:

1. Algorithm: A formal, abstract mathematical sequence of well-defined, unambiguous steps that transforms an input into an output and is guaranteed to terminate. It is completely independent of programming languages, compilers, operating systems, and computer hardware.
2. Pseudocode: A high-level description of an algorithm that uses the structural conventions of programming (loops, conditionals) but omits language-specific syntax (such as type declarations, semicolons, memory allocation, and imports). Its goal is human readability and conceptual clarity.
3. Program: A concrete realization of an algorithm written in a formal programming language (like Java, C++, or Python). It must strictly follow compiler grammars, manage hardware constraints, handle exceptions, and can be compiled into bytecode or machine code for CPU execution.

• Code Example:

// Algorithm: Find maximum element in an array
// Pseudocode:
//   function findMax(A, n):
//     maxVal <- A[0]
//     for i <- 1 to n - 1 do:
//       if A[i] > maxVal then maxVal <- A[i]
//     return maxVal

// Concrete Program (Java):
public class AlgorithmComparison {
    public static int findMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("Array cannot be null or empty");
        }
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        return maxVal;
    }
    public static void main(String[] args) {
        System.out.println("Max: " + findMax(new int[]{12, 45, 7, 89, 23}));
    }
}

• Common Pitfalls & Edge Cases:
  Writing pseudocode that relies heavily on language-specific quirks (like Python list slicing or Java Streams) rather than fundamental algorithmic primitives.
• Follow-up Questions:
  What formal criteria did Donald Knuth specify for a valid algorithm (finiteness, definiteness, input, output, effectiveness)?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: The Böhm-Jacopini theorem proves that any computable algorithm can be expressed using only three basic control flow constructs: sequence, selection, and iteration.
• Detailed Explanation:
  In structured programming, all complex logic can be synthesized from three fundamental building blocks:

1. Sequence: Executing computational statements sequentially one after another in order of appearance (A followed by B).
2. Selection (Conditional): Choosing one of several execution paths based on a boolean predicate (e.g., if-else, switch).
3. Iteration (Repetition): Repeating a block of statements while a boolean condition remains true (e.g., while, for, do-while).

Turing Completeness:
The Böhm-Jacopini theorem (1966) mathematically established that any algorithm executable by a Turing machine can be written in a structured programming language containing only these three constructs. Unrestricted jumps (goto) are never mathematically required.

• Code Example:

public class AlgorithmicConstructs {
    public static int collatzConjectureSteps(int n) {
        // Construct 1: Sequence (initialization)
        int steps = 0;
        int current = n;
        
        // Construct 3: Iteration (while loop)
        while (current != 1) {
            // Construct 2: Selection (if-else condition)
            if (current % 2 == 0) {
                current = current / 2;
            } else {
                current = 3 * current + 1;
            }
            steps++;
        }
        return steps;
    }
    public static void main(String[] args) {
        System.out.println("Steps for 6: " + collatzConjectureSteps(6)); // 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (8 steps)
    }
}

• Common Pitfalls & Edge Cases:
  Creating non-terminating iterations by failing to update loop control variables inside all branches of selection constructs.
• Follow-up Questions:
  Can recursion replace iteration completely in language runtimes, and how does Church-Turing thesis relate to lambda calculus?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Problem decomposition splits monolithic problems into decoupled, cohesive subroutines, enabling independent implementation, reasoning, unit testing, and reuse.
• Detailed Explanation:
  Without decomposition, algorithms suffer from high cognitive load, tight coupling, and difficult debugging.
  Key benefits of decomposition in DSA include:

1. Isolation of Invariants: When implementing complex algorithms (like AVL tree balancing or QuickSort), decomposing logic into rotateRight(), balanceFactor(), and partition() allows verifying local correctness independently.
2. Testability: Each decomposed component can be tested against boundary edge cases in isolation without needing full end-to-end setups.
3. Reusability: Subroutines like swap(), binarySearch(), or gcd() can be reused across multiple algorithmic pipelines.
4. Divide-and-Conquer Mapping: Decomposition forms the direct basis for recursive divide-and-conquer paradigms where a problem of size N is solved by solving sub-problems of size N/2.

• Code Example:

public class DecompositionExample {
    // Top-level Problem: Verify if two strings are anagrams of each other.
    // Decomposed Step 1: Normalize input (remove non-alphanumeric, lowercase)
    private static String sanitize(String s) {
        return s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    }
    // Decomposed Step 2: Build frequency map
    private static int[] buildFrequency(String s) {
        int[] freq = new int[256];
        for (char c : s.toCharArray()) freq[c]++;
        return freq;
    }
    // Decomposed Step 3: Compare frequencies
    private static boolean compareFrequencies(int[] f1, int[] f2) {
        for (int i = 0; i < 256; i++) {
            if (f1[i] != f2[i]) return false;
        }
        return true;
    }
    // Composite Orchestrator
    public static boolean isAnagram(String s1, String s2) {
        String clean1 = sanitize(s1);
        String clean2 = sanitize(s2);
        if (clean1.length() != clean2.length()) return false;
        return compareFrequencies(buildFrequency(clean1), buildFrequency(clean2));
    }
    public static void main(String[] args) {
        System.out.println("Anagram: " + isAnagram("Astronomer", "Moon starer")); // true
    }
}

• Common Pitfalls & Edge Cases:
  Over-decomposition into excessive tiny functions that adds call-stack overhead and obscures the macro-level data flow.
• Follow-up Questions:
  How does decomposition in functional programming (pure functions) prevent hidden side-effects compared to procedural decomposition?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Pattern recognition maps new problem requirements to well-known algorithmic archetypes such as Two Pointers, Sliding Window, Prefix Sums, or BFS.
• Detailed Explanation:
  When solving novel computational challenges, experienced engineers do not invent new algorithms from scratch. They recognize underlying structural patterns:

1. Contiguous Subarrays with Criteria: Points directly to the Sliding Window or Prefix Sum pattern.
2. Sorted Array Element Pairing: Points to the Two-Pointer convergence technique.
3. Shortest Path in Unweighted State Space: Points to Breadth-First Search (BFS).
4. Overlapping Subproblems with Optimal Substructure: Points to Dynamic Programming.
5. Next Greater / Smaller Element: Points to Monotonic Stacks.
   Generalization involves abstracting parameter constraints so that the same implementation solves a broader family of problems (e.g., using Comparator<T> rather than hardcoded integer comparisons).

• Code Example:

import java.util.*;
public class PatternRecognitionDemo {
    // Pattern: Two-Pointer convergence applied to find if a string is a palindrome
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
    }
}

• Common Pitfalls & Edge Cases:
  Forcing a problem into an unfitting pattern (e.g., trying to use Two Pointers on an unsorted array without sorting first).
• Follow-up Questions:
  What algorithmic patterns are best suited for hierarchical tree-like dependencies (e.g., Topological Sort)?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Abstraction conceals complex low-level mechanics while exposing clean, intuitive operational interfaces.
• Detailed Explanation:
  In computational thinking, abstraction enables programmers to reason about systems at multiple conceptual levels:

1. Mathematical Level: A set of nodes and relations (Graph G = (V, E)).
2. ADT Level: Interface operations like addVertex(), addEdge(), getNeighbors().
3. Data Structure Level: Adjacency list backed by ArrayList<LinkedList<Integer>> or adjacency matrix int[][].
4. Hardware Level: CPU cache hierarchy, memory page allocation, and pointer dereferencing.

By working through abstraction barriers, changing the internal representation from a 2D matrix to an adjacency list does not break client-facing algorithms like Dijkstra's or BFS.

• Code Example:

import java.util.*;
public class AbstractionDemo {
    // Abstract Interface
    public interface QueueADT<T> {
        void enqueue(T item);
        T dequeue();
        boolean isEmpty();
    }
    // Concrete Implementation using LinkedList
    public static class LinkedListQueue<T> implements QueueADT<T> {
        private LinkedList<T> list = new LinkedList<>();
        public void enqueue(T item) { list.addLast(item); }
        public T dequeue() { return list.removeFirst(); }
        public boolean isEmpty() { return list.isEmpty(); }
    }
    public static void main(String[] args) {
        QueueADT<String> queue = new LinkedListQueue<>();
        queue.enqueue("Task 1");
        queue.enqueue("Task 2");
        System.out.println("Served: " + queue.dequeue());
    }
}

• Common Pitfalls & Edge Cases:
  Leaky abstractions where client code relies on unspecified internal side-effects or orderings of the underlying data structure.
• Follow-up Questions:
  Why is the Abstract Data Type (ADT) pattern the foundation of Object-Oriented design in Java?

• Difficulty: Advanced
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Formal verification uses preconditions (entry criteria), postconditions (exit guarantees), and loop invariants (truths held across iterations) to prove algorithm correctness.
• Detailed Explanation:
  To prove that an algorithm works for all inputs rather than just passing sample test cases, we rely on three formal assertions:

1. Precondition: An assertion about input data that must evaluate to true before the routine executes. If violated, behavior is undefined.
2. Postcondition: An assertion guaranteed to evaluate to true upon algorithm termination provided preconditions were satisfied.
3. Loop Invariant: A formal condition that is:
   • Initialization: True prior to the first iteration of the loop.
   • Maintenance: If true before an iteration, remains true before the next iteration.
   • Termination: When the loop terminates, the invariant provides a useful property proving the algorithm's postcondition.

• Code Example:

public class LoopInvariantDemo {
    // Algorithm: Linear Search
    // Invariant: Target does not exist in arr[0 ... i - 1]
    public static int linearSearch(int[] arr, int target) {
        // Precondition: arr != null
        assert arr != null : "Array must not be null";
        for (int i = 0; i < arr.length; i++) {
            // Invariant holds: target not in arr[0 ... i-1]
            if (arr[i] == target) {
                // Postcondition 1: Returned index matches target
                return i;
            }
        }
        // Postcondition 2: Target not found anywhere in arr[0 ... n-1]
        return -1;
    }
    public static void main(String[] args) {
        System.out.println("Found at: " + linearSearch(new int[]{4, 2, 9, 7}, 9));
    }
}

• Common Pitfalls & Edge Cases:
  Assuming loop invariants remain valid when loops terminate via abrupt breaks or unhandled runtime exceptions.
• Follow-up Questions:
  How is the loop invariant method used to prove the correctness of Insertion Sort and Binary Search?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐⭐
• Concept / Summary: By comparing input size bounds against modern CPU execution budgets (~10^7 to 10^8 basic operations per second), you can predetermine viable algorithmic complexities.
• Detailed Explanation:
  Standard competitive programming platforms and enterprise SLA benchmarks allocate approximately 1.0 second for execution. Modern CPUs process roughly 10^7 to 10^8 elementary instructions per second.
  Use this constraint table during problem identification:
• N <= 10: O(N!) or O(2^N * N) - Permutations, Travelling Salesperson (TSP).
• N <= 20 to 25: O(2^N) - Backtracking, recursive exhaustive search, meet-in-the-middle.
• N <= 500: O(N³) - Floyd-Warshall, matrix multiplication, cubic DP.
• N <= 5,000: O(N²) - Nested loops, bubble/selection/insertion sorts, quadratic DP.
• N <= 100,000 (10^5): O(N log N) or O(N) - Sorting, binary search, tree traversals, two pointers.
• N <= 1,000,000 (10^6): O(N) or O(N log N) - Linear scan, hash maps, simple sorting.
• N >= 10^9: O(log N) or O(1) - Binary search on answer, mathematical formulas, bitwise arithmetic.
• Code Example:

public class ConstraintBudgetDemo {
    public static void main(String[] args) {
        int n = 100_000;
        System.out.println("For N = " + n + ":");
        System.out.println("O(N^2) operations = " + ((long)n * n) + " (Guaranteed TLE ~10^10 ops)");
        System.out.println("O(N log N) operations = " + (long)(n * (Math.log(n) / Math.log(2))) + " (Safe ~1.6 * 10^6 ops)");
    }
}

• Common Pitfalls & Edge Cases:
  Implementing an O(N²) algorithm when N = 10^5, which requires 10^10 operations and takes ~100 seconds, resulting in immediate TLE.
• Follow-up Questions:
  How does memory constraint analysis (e.g., 256 MB limit) dictate maximum array dimensions in Java?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: A deterministic algorithm always produces the exact same execution trajectory and output for a given input; non-deterministic algorithms incorporate randomness or branching possibilities.
• Detailed Explanation:
  In computer science:

1. Deterministic Algorithms: Every computational step is fully determined by the current state and input. Given input X, the program follows an identical sequence of CPU instructions and always yields output Y (e.g., standard Binary Search, Merge Sort, Dijkstra's algorithm).
2. Non-Deterministic / Randomized Algorithms: The algorithm makes random choices or explores multiple hypothetical execution paths concurrently:
   • Las Vegas Algorithms: Always return the correct answer, but their running time is a random variable (e.g., Randomized QuickSort with random pivot selection).
   • Monte Carlo Algorithms: Have deterministic or fixed runtimes, but carry a small, bounded probability of returning an incorrect or approximate result (e.g., Miller-Rabin Primality Test).

• Code Example:

import java.util.Random;
public class DeterminismDemo {
    private static final Random rng = new Random();
    // Deterministic: Always picks index 0 as pivot
    public static int deterministicPivot(int low, int high) {
        return low;
    }
    // Randomized (Las Vegas): Random pivot prevents O(N^2) adversarial degradation
    public static int randomizedPivot(int low, int high) {
        return low + rng.nextInt(high - low + 1);
    }
    public static void main(String[] args) {
        System.out.println("Random pivot [0, 9]: " + randomizedPivot(0, 9));
    }
}

• Common Pitfalls & Edge Cases:
  Assuming randomized algorithms are non-reproducible in testing; failing to seed random number generators prevents deterministic unit testing.
• Follow-up Questions:
  What is the class NP (Non-Deterministic Polynomial time) and how does it relate to polynomial verifiability?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Top-down breaks a high-level problem down into sub-problems recursively; bottom-up solves primitive sub-problems first and combines them iteratively into the full solution.
• Detailed Explanation:
  These two overarching philosophies apply across system design, algorithmic planning, and dynamic programming:

1. Top-Down (Stepwise Refinement / Memoization):
   • Starts with the abstract macro-problem: f(N).
   • Formulates recurrence: f(N) = f(N-1) + f(N-2).
   • Breaks it down on demand using recursion.
   • Relies on call stack and cache tables (memoization) to avoid redundant subproblem evaluation.
2. Bottom-Up (Synthesis / Tabulation):
   • Starts with the smallest possible base cases: dp[0] = 0, dp[1] = 1.
   • Iteratively builds solutions for successively larger subproblems: dp[i] = dp[i-1] + dp[i-2].
   • Avoids call-stack overhead, eliminates risk of StackOverflowError, and often enables space-optimization (e.g., maintaining only the last 2 variables).

• Code Example:

public class TopDownVsBottomUp {
    // Top-down with Memoization
    public static int fibTopDown(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibTopDown(n - 1, memo) + fibTopDown(n - 2, memo);
    }
    // Bottom-up with Tabulation
    public static int fibBottomUp(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
    public static void main(String[] args) {
        System.out.println("Top-down Fib(10): " + fibTopDown(10, new int[11]));
        System.out.println("Bottom-up Fib(10): " + fibBottomUp(10));
    }
}

• Common Pitfalls & Edge Cases:
  Deep top-down recursion in languages without tail-call optimization like Java can trigger StackOverflowError when N > 10^4.
• Follow-up Questions:
  When is top-down memoization strictly faster than bottom-up tabulation (hint: sparse state spaces)?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐⭐
• Concept / Summary: Systematic boundary value analysis identifies extreme data states: null/empty containers, singletons, identical values, sorted/reverse orders, and numerical limits.
• Detailed Explanation:
  A robust algorithm must handle degenerate cases without crashing or producing incorrect results. When analyzing a problem, always test these boundary profiles:

1. Volume Extremes: Empty input (length = 0), single-element (length = 1), massive inputs (length = 10^6).
2. Ordering Extremes: Already perfectly sorted, strictly reverse-sorted, or completely randomized.
3. Value Extremes: All elements identical ([7, 7, 7, 7]), all zeroes, alternating signs, Integer.MIN_VALUE and Integer.MAX_VALUE.
4. Structural Extremes (Trees/Graphs): Skewed tree (linked list degradation), disconnected graph, graph with self-loops or multi-edges, cycle-rich graph.
5. Pointer Boundaries: Head deletions, tail insertions, out-of-bounds queries.

• Code Example:

public class BoundaryAnalysisDemo {
    public static double findAverage(int[] nums) {
        // Edge Case 1: Null check
        if (nums == null) throw new IllegalArgumentException("Array cannot be null");
        // Edge Case 2: Zero elements (division by zero prevention)
        if (nums.length == 0) return 0.0;
        // Edge Case 3: Sum overflow prevention
        long totalSum = 0;
        for (int x : nums) {
            totalSum += x;
        }
        return (double) totalSum / nums.length;
    }
    public static void main(String[] args) {
        System.out.println("Avg of empty: " + findAverage(new int[]{}));
        System.out.println("Avg of max integers: " + findAverage(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE}));
    }
}

• Common Pitfalls & Edge Cases:
  Dividing by array length without verifying length > 0, producing NaN or ArithmeticException.
• Follow-up Questions:
  How does property-based testing (e.g., jqwik in Java) automatically generate degenerate edge cases?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: A state space models all reachable configurations of a system as vertices and valid transition actions as directed edges.
• Detailed Explanation:
  Many computational problems (puzzles, robotic routing, game engines, workflow automation) can be formalized as state spaces:

1. State: A discrete snapshot of all relevant variables at a specific moment (e.g., position of pieces in Chess or 8-puzzle).
2. Initial State: The starting configuration.
3. Action / Transition Model: Legal moves that transition state S into a successor state S'.
4. Goal State / Goal Test: A boolean predicate verifying if state S fulfills the victory or solution condition.
5. Path Cost: Sum of step costs along transitions.

Once a problem is modeled as a state space, standard graph traversal algorithms (BFS for shortest moves, DFS for reachability, A* for heuristic routing) solve it automatically.

• Code Example:

import java.util.*;
public class StateSpaceWaterJug {
    // State: (amount in 4L jug, amount in 3L jug). Goal: exactly 2L in 4L jug.
    record State(int j4, int j3) {}
    public static int minStepsToMeasure2L() {
        Queue<State> q = new LinkedList<>();
        Set<State> visited = new HashSet<>();
        State start = new State(0, 0);
        q.add(start);
        visited.add(start);
        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                State curr = q.poll();
                if (curr.j4 == 2) return steps; // Goal state reached
                // Transitions: Fill 4L, Fill 3L, Empty 4L, Empty 3L, Pour 4L->3L, Pour 3L->4L
                List<State> nextStates = List.of(
                    new State(4, curr.j3), new State(curr.j4, 3),
                    new State(0, curr.j3), new State(curr.j4, 0),
                    new State(Math.max(0, curr.j4 - (3 - curr.j3)), Math.min(3, curr.j3 + curr.j4)),
                    new State(Math.min(4, curr.j4 + curr.j3), Math.max(0, curr.j3 - (4 - curr.j4)))
                );
                for (State ns : nextStates) {
                    if (visited.add(ns)) q.add(ns);
                }
            }
            steps++;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println("Min transitions to 2L: " + minStepsToMeasure2L()); // 6
    }
}

• Common Pitfalls & Edge Cases:
  State space explosion: Failing to track visited states causes infinite loops or exponential memory exhaustion.
• Follow-up Questions:
  What heuristic function makes an A* search optimal when traversing an expansive state space?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Heuristics are rule-of-thumb computational strategies that find satisfactory near-optimal solutions in reasonable time for NP-hard problems where exact algorithms require exponential time.
• Detailed Explanation:
  In computational complexity:

1. Intractability: Problems in class NP-Hard (like 0/1 Knapsack with massive capacity, Travelling Salesperson Problem, Graph Coloring) lack known polynomial-time O(N^k) exact algorithms. Brute force requires O(2^N) or O(N!), which for N = 100 exceeds the atoms in the observable universe.
2. Heuristic: An educated rule that guides search toward good solutions (e.g., Nearest Neighbor for TSP, Greedy ratio choice for Knapsack).
3. Approximation Algorithms: Heuristics with provable mathematical bounds guaranteeing the solution is within a factor (1 + ε) of the true theoretical optimum.

• Code Example:

import java.util.*;
public class HeuristicTSP {
    // Greedy Heuristic: Nearest Neighbor algorithm for TSP
    public static List<Integer> nearestNeighborTour(int[][] dist) {
        int n = dist.length;
        boolean[] visited = new boolean[n];
        List<Integer> tour = new ArrayList<>();
        int current = 0;
        tour.add(current);
        visited[current] = true;
        for (int step = 1; step < n; step++) {
            int nearest = -1, minD = Integer.MAX_VALUE;
            for (int next = 0; next < n; next++) {
                if (!visited[next] && dist[current][next] < minD) {
                    minD = dist[current][next];
                    nearest = next;
                }
            }
            visited[nearest] = true;
            tour.add(nearest);
            current = nearest;
        }
        return tour;
    }
    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };
        System.out.println("Heuristic Tour: " + nearestNeighborTour(dist));
    }
}

• Common Pitfalls & Edge Cases:
  Mistaking a heuristic for an exact algorithm; heuristics can get trapped in local optima and fail to deliver the global maximum.
• Follow-up Questions:
  What is the difference between an admissible heuristic and a consistent heuristic in A* search?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Termination is proven using a strictly decreasing variant function bounded from below; correctness is proven using loop invariants.
• Detailed Explanation:
  To mathematically demonstrate that an iterative loop is sound:

1. Termination Proof via Loop Variant:
   Define an integer-valued quantity V (the variant) based on loop variables such that:
   • In each iteration, V decreases by at least 1: V_{k+1} < V_k.
   • The loop continues only while V >= 0.
     Since an integer cannot decrease indefinitely while bounded below by zero (Well-Ordering Principle of natural numbers), the loop must terminate in a finite number of steps.
2. Correctness Proof via Invariant:
   Prove that the invariant condition holds at initialization, is maintained through each iteration, and upon termination, directly yields the intended postcondition.

• Code Example:

public class TerminationProofDemo {
    // Algorithm: Integer Division (x / y) using repeated subtraction
    // Variant function V = remainder
    public static int divide(int x, int y) {
        if (y <= 0) throw new IllegalArgumentException("Divisor must be > 0");
        int quotient = 0;
        int remainder = x;
        // V = remainder. Each loop subtracts y >= 1, so V strictly decreases.
        // Loop terminates when V < y.
        while (remainder >= y) {
            remainder -= y;
            quotient++;
        }
        return quotient;
    }
    public static void main(String[] args) {
        System.out.println("23 / 5 = " + divide(23, 5)); // 4
    }
}

• Common Pitfalls & Edge Cases:
  Failing to account for zero or negative step sizes, causing the variant to oscillate or increase, producing an infinite loop.
• Follow-up Questions:
  How does Alan Turing's Halting Problem prove that a general algorithm to verify termination for all arbitrary programs is impossible?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: The time-space trade-off describes scenarios where computational speed can be increased at the cost of consuming more memory, or memory can be minimized at the cost of slower execution.
• Detailed Explanation:
  Engineering decisions constantly balance time and memory constraints:

1. Trading Space for Time (Faster, more RAM):
   • Hash Tables: Pre-allocate large bucket arrays to achieve O(1) lookups instead of O(N) array scans.
   • Lookup Tables / Memoization: Precomputing results (e.g., sine tables, factorial factorizations) so calculations take O(1) time at runtime.
   • Prefix Sums: Allocate an extra O(N) array so range queries run in O(1) rather than O(N).
2. Trading Time for Space (Slower, minimal RAM):
   • In-place Algorithms: Reversing an array or sorting via Heapsort uses O(1) auxiliary space but may run slower than Merge Sort with O(N) auxiliary buffers.
   • Recomputing on demand: Calculating values dynamically rather than caching them when running in memory-constrained IoT or micro-controller environments.

• Code Example:

public class TimeSpaceTradeoff {
    // Space-efficient: O(1) extra space, but O(N) time per range sum query
    public static int rangeSumSlow(int[] arr, int l, int r) {
        int sum = 0;
        for (int i = l; i <= r; i++) sum += arr[i];
        return sum;
    }
    // Time-efficient: O(N) auxiliary space, but O(1) time per query
    public static class FastRangeSum {
        private int[] prefix;
        public FastRangeSum(int[] arr) {
            prefix = new int[arr.length + 1];
            for (int i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] + arr[i];
        }
        public int query(int l, int r) {
            return prefix[r + 1] - prefix[l];
        }
    }
    public static void main(String[] args) {
        int[] data = {3, 1, 4, 1, 5, 9};
        FastRangeSum fast = new FastRangeSum(data);
        System.out.println("Sum [1..4]: " + fast.query(1, 4)); // 1 + 4 + 1 + 5 = 11
    }
}

• Common Pitfalls & Edge Cases:
  Caching excessively in memory without eviction limits, leading to JVM OutOfMemoryError.
• Follow-up Questions:
  How do bloom filters optimize this trade-off by accepting a small false-positive rate for huge memory savings?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: A dry run is a manual step-by-step paper execution of an algorithm using sample inputs while recording variable states in a trace table.
• Detailed Explanation:
  Dry running is an essential debugging and verification skill. A trace table tracks every variable's value across each discrete clock/step:

1. Identify all state variables (i, j, sum, flag).
2. Write down column headers for Step Number, Line of Code, Conditions Evaluated, Variable Values, and Output.
3. Walk line-by-line simulating the CPU without guessing.
4. Record exact state mutations at each loop iteration.
   This practice immediately exposes off-by-one errors, improper boolean inversion, and unexpected loop termination.

• Code Example:

public class DryRunTarget {
    // Target algorithm to trace
    public static int mystery(int a, int b) {
        int res = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                res += a;
            }
            a <<= 1;
            b >>= 1;
        }
        return res;
    }
    // Tracing mystery(3, 5):
    // Init: a=3, b=5, res=0
    // Iter 1: b=5 (odd, 5&1==1) -> res = 0+3=3, a=6, b=2
    // Iter 2: b=2 (even, 2&1==0) -> res = 3, a=12, b=1
    // Iter 3: b=1 (odd, 1&1==1) -> res = 3+12=15, a=24, b=0
    // Exit: returns 15 (Binary Russian Peasant Multiplication: 3 * 5 = 15)
    public static void main(String[] args) {
        System.out.println("Result: " + mystery(3, 5)); // 15
    }
}

• Common Pitfalls & Edge Cases:
  Relying on mental shortcuts rather than recording actual variable values in the trace table during tricky bitwise or pointer updates.
• Follow-up Questions:
  How does dry running assist in discovering the loop invariant of an algorithm?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Real-world domains are mapped to mathematical entities: entities become vertices, associations become edges, hierarchies become trees, and constraints become inequalities.
• Detailed Explanation:
  Software engineering problems translate directly to discrete mathematical structures:

1. Networks & Social Graphs: People/Routers -> Vertices; Friendships/Cables -> Edges (undirected or directed, weighted by latency/capacity).
2. File Systems & Organization Charts: Parent-child containment -> Directed Trees (acyclic, single root).
3. Task Scheduling with Prerequisites: Tasks -> Vertices; Precedence constraints (Task A must finish before Task B) -> Directed Acyclic Graph (DAG) solved by Topological Sort.
4. Access Control & Permissions: Users, Roles, Resources -> Bipartite graphs or Disjoint Sets (Union-Find).
5. Memory Management: Free memory blocks -> Linked Lists or Red-Black Trees of interval ranges.

• Code Example:

import java.util.*;
public class ProblemModelingDemo {
    // Problem: Course prerequisites (e.g. Must take 101 before 201)
    // Modeled as: Cycle detection in a Directed Graph
    public static boolean canFinishAllCourses(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]); // p[1] -> p[0]
            inDegree[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) q.add(i);
        }
        int enrolled = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            enrolled++;
            for (int neighbor : adj.get(c)) {
                if (--inDegree[neighbor] == 0) q.add(neighbor);
            }
        }
        return enrolled == numCourses; // True if no dependency cycle exists
    }
    public static void main(String[] args) {
        int[][] pre = {{1, 0}, {2, 1}}; // 0 -> 1 -> 2
        System.out.println("Can complete: " + canFinishAllCourses(3, pre)); // true
    }
}

• Common Pitfalls & Edge Cases:
  Failing to model anti-symmetry or transitivity in relations, leading to missed cycle detection.
• Follow-up Questions:
  Why is bipartite matching the mathematical foundation behind ride-sharing driver-rider assignment algorithms?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Test-driven thinking forces early articulation of expected behaviors, boundary limits, and invariant assertions before code implementation.
• Detailed Explanation:
  Writing automated test suites ensures algorithms satisfy both happy paths and edge cases:

1. Equivalence Partitioning: Partition the input domain into valid and invalid classes. Testing one representative from each partition provides broad coverage.
2. Boundary Value Testing: Focus tests on the edges of input partitions (e.g., if valid range is 1 <= N <= 100, test 0, 1, 2, 99, 100, 101).
3. Regression Safety: Optimizing an algorithm from O(N²) to O(N log N) can introduce subtle edge-case bugs; comprehensive unit tests detect regressions instantly.
4. Fuzzing / Stress Testing: Comparing the output of an optimized algorithm against a simple, slow, guaranteed-correct brute-force algorithm on thousands of random inputs.

• Code Example:

import java.util.Arrays;
public class StressTestingDemo {
    // Fast algorithm to test
    public static int fastMax(int[] arr) {
        int m = arr[0];
        for (int x : arr) if (x > m) m = x;
        return m;
    }
    // Simple brute-force reference
    public static int bruteForceMax(int[] arr) {
        int[] copy = arr.clone();
        Arrays.sort(copy);
        return copy[copy.length - 1];
    }
    public static void main(String[] args) {
        int[] test = {5, 2, 9, 1, 7};
        assert fastMax(test) == bruteForceMax(test) : "Mismatch detected!";
        System.out.println("Test passed successfully!");
    }
}

• Common Pitfalls & Edge Cases:
  Only testing with 'happy path' inputs provided in problem examples, leaving null, empty, and duplicate scenarios unverified.
• Follow-up Questions:
  How does property-based testing differ from traditional example-based unit testing?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Assertions (assert condition : message;) document and verify internal assumptions that should never be violated if the algorithm is logically sound.
• Detailed Explanation:
  In Java, the assert keyword validates internal consistency during development and testing without impacting production performance:

1. Precondition Validation: Used in private helper methods to check assumptions (assert index >= 0 && index < size;).
2. Postcondition Validation: Ensures the method delivered its contract before returning.
3. Internal Invariants: Confirms intermediate state variables remain within valid mathematical boundaries.
4. Execution Control: Enabled using -ea (enable assertions) JVM flag during test runs; disabled in production builds to eliminate runtime CPU overhead.

• Code Example:

public class AssertionDemo {
    public static int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // Internal Invariant: mid must always be within current search window
            assert mid >= low && mid <= high : "Mid pointer out of bounds!";
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50};
        System.out.println("Index: " + binarySearch(sorted, 30));
    }
}

• Common Pitfalls & Edge Cases:
  Using assert for public API argument validation instead of explicit exceptions like IllegalArgumentException; because assertions can be disabled via -da, public API checks would be bypassed.
• Follow-up Questions:
  Why should assertions never contain expressions with side effects (like assert list.remove(item);)?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Non-functional requirements dictate data structure selection beyond pure asymptotic Big-O, incorporating lock contention, memory alignment, and GC overhead.
• Detailed Explanation:
  An algorithm with O(1) complexity may still be unsuitable if its non-functional attributes violate system architecture constraints:

1. Thread Safety: Is the data structure read/write concurrently? Standard ArrayList or HashMap will corrupt memory; alternatives like ConcurrentHashMap or Copy-on-Write arrays must be chosen.
2. Memory Footprint & GC Pressure: High-frequency allocation of thousands of small wrapper objects (Integer, Node) triggers GC pauses. Using primitive arrays (int[]) or off-heap buffers dramatically improves throughput.
3. Scalability & Latency Jitter: Amortized O(1) resizing in ArrayList causes periodic latency spikes when arrays double. Fixed-capacity ring buffers provide predictable zero-latency guarantees required in high-frequency trading.

• Code Example:

import java.util.concurrent.ConcurrentHashMap;
public class NonFunctionalReqDemo {
    // Thread-safe, non-blocking concurrent counter cache
    private final ConcurrentHashMap<String, Long> metrics = new ConcurrentHashMap<>();
    public void recordHit(String endpoint) {
        metrics.merge(endpoint, 1L, Long::sum); // Atomic, lock-free update
    }
    public long getHits(String endpoint) {
        return metrics.getOrDefault(endpoint, 0L);
    }
    public static void main(String[] args) {
        NonFunctionalReqDemo demo = new NonFunctionalReqDemo();
        demo.recordHit("/api/v1/users");
        demo.recordHit("/api/v1/users");
        System.out.println("Hits: " + demo.getHits("/api/v1/users")); // 2
    }
}

• Common Pitfalls & Edge Cases:
  Assuming synchronized wrappers (e.g. Collections.synchronizedMap) scale well under high concurrent read loads; lock contention creates massive bottlenecks.
• Follow-up Questions:
  How does mechanical sympathy (aligning code with hardware CPU cache lines) affect data structure performance?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: Pre-implementation complexity estimation calculates expected operation counts from constraints to select the right algorithm before writing a single line of code.
• Detailed Explanation:
  Before writing code, analyze problem inputs to determine the target complexity:

1. Input: N = 200,000.
2. Time limit: 1.0s (~10^8 operations).
3. Evaluate possibilities:
   • O(N²) = (2 * 10^5)² = 4 * 10^10 operations -> TLE.
   • O(N log N) = 2 * 10^5 * log2(200,000) ~ 2 * 10^5 * 18 ~ 3.6 * 10^6 operations -> Well within budget!
4. Decision: Must use sorting, divide-and-conquer, or balanced BSTs. Quadratic approaches are discarded immediately.
   This saves hours of dead-end coding and architectural refactoring.

• Code Example:

public class ComplexityEstimator {
    public static void estimate(long n) {
        System.out.println("Evaluating feasibility for N = " + n);
        long n2 = n * n;
        long nLogn = (long)(n * (Math.log(n) / Math.log(2)));
        System.out.println("  O(N log N): " + nLogn + " ops -> " + (nLogn < 1e8 ? "FEASIBLE" : "UNFEASIBLE"));
        System.out.println("  O(N^2):     " + n2 + " ops -> " + (n2 < 1e8 ? "FEASIBLE" : "UNFEASIBLE"));
    }
    public static void main(String[] args) {
        estimate(100_000);
    }
}

• Common Pitfalls & Edge Cases:
  Ignoring the constant factors hidden by Big-O notation; an O(N) algorithm with a constant factor of 500 can run slower than an O(N log N) algorithm with a constant factor of 2.
• Follow-up Questions:
  How does Big-O notation differ from Big-Omega and Big-Theta in performance bounds estimation?

• Difficulty: Intermediate
• Frequency: ⭐⭐⭐⭐
• Concept / Summary: A Finite State Machine (FSM) models an algorithm as a set of discrete states, inputs that trigger transitions between states, and actions associated with transitions.
• Detailed Explanation:
  Many parsing, validation, and tokenization algorithms are cleanly solved by formulating them as FSMs:

1. States: Finite set of conditions (e.g., START, INTEGER_PART, DECIMAL_POINT, FRACTION_PART, EXPONENT, ERROR).
2. Inputs: Stream of symbols (digits, signs, '.', 'e').
3. Transitions: Lookup function mapping (Current State, Input Symbol) -> Next State.
4. Accepting States: States indicating valid termination.
   This avoids nested convoluted if-else flags and guarantees deterministic validation of string patterns.

• Code Example:

public class StateMachineValidator {
    enum State { START, SIGN, DIGIT, DOT, FRACTION }
    // Validates if string is a valid floating point number
    public static boolean isValidNumber(String s) {
        State state = State.START;
        for (char c : s.trim().toCharArray()) {
            switch (state) {
                case START:
                    if (c == '+' || c == '-') state = State.SIGN;
                    else if (Character.isDigit(c)) state = State.DIGIT;
                    else if (c == '.') state = State.DOT;
                    else return false;
                    break;
                case SIGN:
                    if (Character.isDigit(c)) state = State.DIGIT;
                    else if (c == '.') state = State.DOT;
                    else return false;
                    break;
                case DIGIT:
                    if (Character.isDigit(c)) state = State.DIGIT;
                    else if (c == '.') state = State.FRACTION;
                    else return false;
                    break;
                case DOT:
                case FRACTION:
                    if (Character.isDigit(c)) state = State.FRACTION;
                    else return false;
                    break;
            }
        }
        return state == State.DIGIT || state == State.FRACTION;
    }
    public static void main(String[] args) {
        System.out.println("Valid '3.14': " + isValidNumber("3.14")); // true
        System.out.println("Valid '-.5': " + isValidNumber("-.5"));   // true
        System.out.println("Valid '3.': " + isValidNumber("3."));     // false
    }
}

• Common Pitfalls & Edge Cases:
  Omitting transition handling for unexpected input symbols, which can cause unhandled exceptions or silent state leakage.
• Follow-up Questions:
  How do regular expressions map directly to Deterministic Finite Automata (DFA)?

• Difficulty: Beginner
• Frequency: ⭐⭐⭐⭐⭐
• Concept / Summary: Off-by-one errors (OBOEs) occur when an iterative algorithm iterates one time too many or one time too few, typically around zero-based indexing or inclusive/exclusive boundaries.
• Detailed Explanation:
  The classic 'fencepost error' asks: To build a 100-meter straight fence with posts spaced 10 meters apart, how many posts are needed? The answer is 11, not 10.
  In programming, OBOEs occur when:

1. Confusing <= with < on array bounds (i <= arr.length causes ArrayIndexOutOfBoundsException).
2. Slicing ranges: In Java substring(start, end), start is inclusive and end is exclusive; length is end - start.
3. Binary Search boundary updates: Using high = mid instead of high = mid - 1 when mid has already been tested.
   Prevention Rules:

• Always adopt asymmetric half-open intervals [start, end): length is simply end - start.
• Explicitly trace boundary cases (N=0, N=1, N=2) on paper.
• Code Example:

public class OffByOnePrevention {
    // Binary Search with asymmetric interval [low, high]
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1; // Inclusive boundary
        while (low <= high) {      // Loop invariant: target is within [low, high]
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) low = mid + 1; // Exclude mid
            else high = mid - 1;                       // Exclude mid
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {10, 20, 30};
        System.out.println("Find 30: " + binarySearch(arr, 30)); // 2
    }
}

• Common Pitfalls & Edge Cases:
  Using low < high instead of low <= high in standard binary search, causing the search to miss targets located at single-element boundaries.
• Follow-up Questions:
  What is Dijkstra's rationale for why numbering should start at zero and intervals should be open at the right end?

• Difficulty: Advanced
• Frequency: ⭐⭐⭐⭐⭐
• Concept / Summary: Designing an API rate limiter involves problem decomposition, constraint analysis, choosing between fixed window, sliding window log, and token bucket data structures.
• Detailed Explanation:
  Case Study: Design a rate limiter allowing at most M requests per user within a rolling W-second window.

1. Decomposition:
   • Identify user key.
   • Retrieve request history for user.
   • Prune timestamps older than now - W.
   • Check if current count < M. If yes, record current timestamp and accept; else, reject.
2. Data Structure Choice:
   • Fixed array / Counter: Fails at window boundaries (allows 2x burst across boundary).
   • Sliding Window Log using a Double-Ended Queue (Deque): Store timestamps. O(1) amortized insertion, O(1) eviction of expired timestamps from front.
3. Space Complexity: At most M timestamps stored per active user.
4. Time Complexity: Amortized O(1) per request.

• Code Example:

import java.util.*;
public class SlidingWindowRateLimiter {
    private final int maxRequests;
    private final long windowSizeMillis;
    private final Map<String, Deque<Long>> userLogs = new HashMap<>();

    public SlidingWindowRateLimiter(int maxRequests, long windowSizeSeconds) {
        this.maxRequests = maxRequests;
        this.windowSizeMillis = windowSizeSeconds * 1000L;
    }

    public synchronized boolean allowRequest(String userId) {
        long now = System.currentTimeMillis();
        Deque<Long> timestamps = userLogs.computeIfAbsent(userId, k -> new ArrayDeque<>());

        // Evict timestamps older than rolling window
        long cutoff = now - windowSizeMillis;
        while (!timestamps.isEmpty() && timestamps.peekFirst() <= cutoff) {
            timestamps.pollFirst();
        }

        if (timestamps.size() < maxRequests) {
            timestamps.addLast(now);
            return true; // Request allowed
        }
        return false; // Rate limit exceeded
    }

    public static void main(String[] args) {
        SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(3, 1); // 3 reqs per 1 sec
        String user = "user_123";
        System.out.println(limiter.allowRequest(user)); // true
        System.out.println(limiter.allowRequest(user)); // true
        System.out.println(limiter.allowRequest(user)); // true
        System.out.println(limiter.allowRequest(user)); // false (throttled!)
    }
}

• Common Pitfalls & Edge Cases:
  Memory leak caused by never evicting inactive user keys from the outer HashMap; a production implementation must combine weak references or TTL-based cache eviction.
• Follow-up Questions:
  How does the Token Bucket algorithm differ from the Sliding Window Log in terms of memory efficiency for high-throughput APIs?