الگوهای الگوریتمی + مسائل کلیدیAlgorithm Patterns + Must-Know Problems

Picture yourself as a seasoned chef, five years in the kitchen. Nobody expects you to invent a brand-new recipe under pressure. They expect you to glance at the ingredients on the counter and instantly know: this becomes a soup, that becomes a stew — reach for the technique you've drilled a thousand times. An algorithm interview is exactly this. The goal of this chapter is to turn you from "someone who solves every problem from scratch" into "someone who recognizes the shape of a problem in seconds."

Part 0 — a few words you must know cold

Before we start, let's build four words so we never drop them on you unexplained later.

• Complexity O(n) (big-O): how an algorithm's work grows as the input grows. Imagine hunting for a name in an n-page phone book. Page by page is O(n); halving the search each time (binary search) is O(log n); scanning the whole array once per element is O(n²).
• Brute force: the simplest solution that comes to mind, even if slow — e.g. trying all pairs. Always state it first; it's both a correctness baseline and a way to buy thinking time.
• Invariant: a statement that stays true through the entire run of a loop, like a house rule that's never broken. In a sorted array, "every pair we skipped was provably not a solution" is an invariant.
• Monotonic: something that moves in only one direction — always growing or always shrinking, never bouncing. Like water heating on a stove, only rising. You'll see "monotonic" a lot, because it's the heart of many of these patterns.

Mental model: interviews are pattern recognition, not invention

At 5 years in, you are not expected to derive Dijkstra from scratch under pressure. You are expected to map a problem onto a known pattern in the first 90 seconds, state the brute force, then reach for the pattern that removes a factor of n (or turns exponential into polynomial).

The golden insight: the recognition signal is almost always hidden in the input shape and the ask. Like a doctor guessing a diagnosis from a handful of symptoms, you guess the pattern from a few keywords. This table is your diagnostic chart:

The rest of this chapter drills each pattern: the recognition cue, one or two solved problems with idiomatic Java, and the complexity you must be able to state cold.

1. Two pointers

Recognize: a sorted array (or one you can sort), and you need a pair/triple, or you're partitioning in place. Two indices walking toward each other (or same-direction, one lagging) turn an O(n²) scan into O(n). The keyword is "sorted" — sortedness is what lets you throw away half the pairs.

Two Sum II (sorted input)

// Sorted ascending. Return 1-based indices of the pair summing to target.
int[] twoSumSorted(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == target) return new int[]{lo + 1, hi + 1};
        if (sum < target) lo++;   // need bigger -> move left pointer up
        else hi--;                // need smaller -> move right pointer down
    }
    return new int[]{-1, -1};
}

Read it line by line. lo is the finger on the short side, hi on the tall side. While they haven't met (lo < hi), compute the sum. Too small → lo++ ("go taller"); too big → hi-- ("go shorter"). O(n) time, O(1) space.

3Sum (the classic dedup trap)

Now the ask is a triple summing to zero. The trick: fix one element as the "anchor" and run a Two-Sum two-pointer over the rest to find its complement.

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip duplicate anchors
        if (nums[i] > 0) break;                          // no way to reach 0 with all positives
        int lo = i + 1, hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) lo++;
            else if (sum > 0) hi--;
            else {
                res.add(List.of(nums[i], nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;  // skip dup lows
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;  // skip dup highs
                lo++; hi--;
            }
        }
    }
    return res;
}

O(n²) time (sort is O(n log n), dominated by the nested walk), O(1) extra beyond output.

2. Sliding window

Recognize: "contiguous" subarray/substring, and you want the longest/shortest/all windows satisfying a constraint. A window [left, right] expands on the right and contracts on the left; each index enters and leaves at most once → O(n). The magic word is "contiguous."

Longest substring without repeating characters

int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];        // last seen index+1 per ASCII char, 0 = unseen
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, last[c]);   // jump left past the previous occurrence
        best = Math.max(best, right - left + 1);
        last[c] = right + 1;              // store index+1 so 0 means "unseen"
    }
    return best;
}

Here right is the window's leading edge, swallowing one fresh char each step. If we've seen that char before, we jump left to sit just past its previous occurrence — shrinking from the left until the window is "repeat-free" again. The index+1 trick is clever: since last starts at zero, storing the real index would confuse the char at position 0 with "unseen"; storing index+1 makes zero unambiguously mean "never seen."

Minimum window substring (variable window with a need-map)

String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int required = t.length();                 // total chars still to satisfy
    int left = 0, bestLen = Integer.MAX_VALUE, bestL = 0;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) required--;   // consumed a needed char
        while (required == 0) {                        // window valid -> try shrinking
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; }
            if (need[s.charAt(left)]++ == 0) required++; // releasing a needed char
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}

O(|s| + |t|). Here need[c] is a "shopping list": how many of each char you still need. Each char you swallow crosses one off; when required hits zero, every item is satisfied and the window is "valid," so you start shrinking from the left to find the smallest valid window.

Fixed-size window (e.g. max sum of k consecutive elements) is the simpler cousin: add the incoming, subtract the outgoing, no inner while loop. Because the length is fixed, you never need a variable shrink.

3. Fast & slow pointers (Floyd)

Recognize: linked lists — cycle detection, find the middle, find the cycle entry — or "detect a repeat in a functional sequence" (LeetCode 287) with O(1) space. Whenever you hear "no extra space" and "linked list," your mind should jump to Floyd.

Cycle detection + entry point

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;            // +1 per step
        fast = fast.next.next;       // +2 per step
        if (slow == fast) {          // they meet -> cycle exists
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }  // Floyd phase 2
            return p;                // cycle entry
        }
    }
    return null;                     // fast hit null -> no cycle
}

O(n) time, O(1) space. Phase one detects the collision. Phase two is a beautiful bit of math magic: after they meet, the distance from head to the entry equals the distance from the meeting point to the entry. So you reset one pointer to head and advance both one step at a time; they converge exactly at the cycle's entry. (Full proof in interview Q4.)

Find the middle

ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    return slow;   // for even length, returns the second middle
}

Same idea, simpler: when the fast runner reaches the end, the slow one is exactly at the middle — having covered half the distance. This "find the middle in one pass" trick underpins linked-list merge sort and much more.

4. Prefix sums (and difference arrays)

Recognize: many "sum of range [i, j]" queries, or "count subarrays with sum k". Precompute cumulative sums so each range answer is O(1).

Subarray sum equals K

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);                 // empty prefix sums to 0, occurs once
    int prefix = 0, result = 0;
    for (int n : nums) {
        prefix += n;
        // number of earlier prefixes P such that prefix - P == k
        result += count.getOrDefault(prefix - k, 0);
        count.merge(prefix, 1, Integer::sum);
    }
    return result;
}

See the logic in odometer terms: if "cumulative sum so far" is prefix, then any subarray summing to k started at a point whose cumulative sum was prefix - k. So we just count how many times we've previously reached cumulative value prefix - k. O(n) time and space.

2D prefix sums answer submatrix-sum queries in O(1) after O(mn) preprocessing: sum(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. (Same "odometer subtraction," now in two dimensions via inclusion-exclusion.)

Difference array is the inverse of prefix sums: to apply many range-increment updates then read once, add +delta at l and -delta at r+1, then take a prefix sum. Each update is O(1). Like marking only "where an increment starts and stops," then summing it all up at the end.

5. Binary search — including on the answer space

Recognize: monotonic search space. Either a sorted array, or a predicate f(x) that is false-false-…-true-true (a boundary). A predicate is just a function that returns yes/no. The second form — "binary search on the answer" — is the senior differentiator.

The lower-bound template (memorize this one)

// First index in [lo, hi) where pred(index) is true; hi if none.
int lowerBound(int lo, int hi, IntPredicate pred) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // avoids int overflow vs (lo+hi)/2
        if (pred.test(mid)) hi = mid;   // answer is mid or left
        else lo = mid + 1;              // answer is strictly right
    }
    return lo;
}

This template finds "the first place the predicate turns true" — the false→true boundary. If pred(mid) is true, maybe mid itself is the answer, so we don't discard it (hi = mid); if false, the answer is strictly to the right (lo = mid + 1).

Koko eating bananas (search on answer)

Now the real magic: the problem has no sorted array at all. Koko has n piles and must finish within h hours; we want the minimum eating speed (bananas per hour). "The smallest speed that finishes in time" means searching on the answer itself.

// Minimum eating speed to finish all piles within h hours.
int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int speed = lo + (hi - lo) / 2;
        long hours = 0;
        for (int p : piles) hours += (p + speed - 1) / speed;  // ceil(p/speed)
        if (hours <= h) hi = speed;    // feasible -> try slower
        else lo = speed + 1;           // too slow -> need faster
    }
    return lo;
}

O(n log maxPile). The pattern: define feasible(x) (monotonic in x — the faster you eat, the sooner you finish), binary-search the smallest/largest feasible x. Same skeleton solves "split array largest sum", "capacity to ship packages in D days", "minimize max distance".

6. Backtracking

Recognize: enumerate all subsets/permutations/combinations, or constraint satisfaction (N-Queens, Sudoku, word search). Build a candidate incrementally, and undo the last choice when a branch is exhausted. Complexity is output-bound: subsets O(2ⁿ), permutations O(n!). That is, the number of answers itself is this big, and you can't beat it.

Subsets

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));          // every node is a valid subset; copy it
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                    // choose
        backtrack(nums, i + 1, path, res);    // explore (i+1 avoids reusing/reordering)
        path.remove(path.size() - 1);         // un-choose (the backtrack step)
    }
}

The three lines inside the loop are exactly the maze triad: choose (path.add), explore (recurse), un-choose (path.remove). The start parameter keeps us moving forward so each subset is built once, not in different orders.

Permutations

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    dfs(nums, used, new ArrayList<>(), res);
    return res;
}
void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; path.add(nums[i]);
        dfs(nums, used, path, res);
        used[i] = false; path.remove(path.size() - 1);   // undo both mutations
    }
}

The difference from subsets is that order matters and each element must appear once per permutation. The used array is a "reserved" sign: it marks which elements are currently present in the path under construction. Note that when undoing you must revert both mutations (used[i] and path).

N-Queens (column + two-diagonal marking)

int totalNQueens(int n) {
    return place(n, 0, new boolean[n], new boolean[2*n], new boolean[2*n]);
}
// col[c], diag[r+c], anti[r-c+n] track occupied lines.
int place(int n, int row, boolean[] col, boolean[] diag, boolean[] anti) {
    if (row == n) return 1;
    int count = 0;
    for (int c = 0; c < n; c++) {
        int d = row + c, a = row - c + n;
        if (col[c] || diag[d] || anti[a]) continue;      // attacked -> prune
        col[c] = diag[d] = anti[a] = true;
        count += place(n, row + 1, col, diag, anti);
        col[c] = diag[d] = anti[a] = false;              // backtrack
    }
    return count;
}

The r+c / r-c+n trick maps each diagonal to a unique index so the attack check is O(1). Why? Every cell on one main diagonal shares the same row+col, and every cell on one anti-diagonal shares the same difference (which we shift by +n to make it a valid array index). So instead of scanning the diagonal, you check a single boolean.

7. Greedy

Recognize: a locally optimal choice provably leads to a global optimum. The hard part is proving the greedy invariant (exchange argument) — if you can't, it's probably DP.

Jump Game (reachability)

boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;             // can't even reach i
        farthest = Math.max(farthest, i + nums[i]);  // greedily extend reach
    }
    return true;
}

Here being greedy means: at each cell we keep only "the farthest I can reach so far." If the counter i overtakes that reach, there's an unbridgeable gap and we can never get there.

Non-overlapping intervals (interval scheduling — greedy by end time)

// Min intervals to remove so the rest don't overlap.
int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1])); // sort by END
    int end = Integer.MIN_VALUE, removed = 0;
    for (int[] iv : intervals) {
        if (iv[0] >= end) end = iv[1];   // keep it: no overlap with last kept
        else removed++;                  // overlaps -> drop the one ending later
    }
    return removed;
}

8. Dynamic programming

Recognize: optimal substructure + overlapping subproblems. That is, the big answer is built from optimal answers to smaller pieces, and those pieces recur. Signals: "count the number of ways", "min/max cost/length", "can you reach/partition". Define three things — the state (what describes a subproblem), the transition (how you get here from smaller subproblems), and the base case — then decide top-down (memoized recursion) vs bottom-up (table).

1D — Climbing stairs / House robber

// House Robber: max sum with no two adjacent picked.
int rob(int[] nums) {
    int take = 0, skip = 0;              // best if we did / didn't rob previous house
    for (int n : nums) {
        int newTake = skip + n;          // rob this -> must have skipped previous
        skip = Math.max(skip, take);     // skip this -> best of previous states
        take = newTake;
    }
    return Math.max(take, skip);
}

O(n) time, O(1) space. Here the whole "DP table" collapses to two rolling variables, because each state depends only on the previous one. take is "best loot if I rob this house," skip is "best loot if I skip it." Since you can't rob two adjacent houses, to rob this one you must have skipped the previous.

0/1 Knapsack (2D → 1D space optimization)

int knapsack(int[] weight, int[] value, int cap) {
    int[] dp = new int[cap + 1];         // dp[w] = best value with capacity w
    for (int i = 0; i < weight.length; i++)
        for (int w = cap; w >= weight[i]; w--)   // iterate capacity DOWNWARD
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[cap];
}

O(n·cap) time, O(cap) space.

Coin change (min coins, unbounded)

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);         // sentinel = "infinity"
    dp[0] = 0;
    for (int coin : coins)
        for (int a = coin; a <= amount; a++)     // UPWARD -> coins reusable
            dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

O(amount·coins). Here amount + 1 plays "infinity": since no valid answer needs more than amount coins, anything larger means "impossible." Note this loop is upward — the exact opposite of 0/1 knapsack — because each coin can be used many times.

Longest Increasing Subsequence (patience sorting, O(n log n))

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];  // tails[i] = smallest tail of an LIS of length i+1
    int size = 0;
    for (int x : nums) {
        int i = Arrays.binarySearch(tails, 0, size, x);
        if (i < 0) i = -(i + 1);         // decode insertion point
        tails[i] = x;                    // replace first tail >= x (or extend)
        if (i == size) size++;
    }
    return size;                         // NOTE: tails is not the actual LIS, only its length
}

The O(n²) DP (dp[i] = 1 + max dp[j] for j<i, nums[j]<nums[i]) is fine to state first, then optimize to O(n log n) with the tails array + binary search. The name "patience sorting" comes from the card game: you place each card on the first pile whose top card exceeds it. Here we do exactly that with binarySearch; and remember that since the value isn't found, binarySearch returns an encoded negative that we decode with -(i+1).

Edit distance (2D DP)

int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;   // delete all of a's prefix
    for (int j = 0; j <= n; j++) dp[0][j] = j;   // insert all of b's prefix
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a.charAt(i-1) == b.charAt(j-1)
                ? dp[i-1][j-1]                                  // chars match -> free
                : 1 + Math.min(dp[i-1][j-1],                   // replace
                      Math.min(dp[i-1][j], dp[i][j-1]));       // delete / insert
    return dp[m][n];
}

O(mn) time and space; reducible to O(min(m,n)) space by keeping two rows.

9. Intervals

Recognize: the input is a list of [start, end] pairs and you must merge, insert, count overlaps, or find free slots. The universal first move is sort by start (sometimes by end for greedy scheduling), then sweep.

Merge intervals

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // by start
    List<int[]> out = new ArrayList<>();
    int[] cur = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= cur[1])                 // overlap
            cur[1] = Math.max(cur[1], intervals[i][1]); // extend current
        else { out.add(cur); cur = intervals[i]; }      // gap -> flush and start new
    }
    out.add(cur);
    return out.toArray(new int[0][]);
}

Because you sorted by start, you only need to hold the current interval: if the next one starts before the current's end, they overlap and you extend the current's end (to whichever is farther); otherwise there's a gap, so flush the current and start fresh.

Meeting rooms II (min rooms = max concurrent overlaps)

int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
    Arrays.sort(starts); Arrays.sort(ends);
    int rooms = 0, maxRooms = 0, e = 0;
    for (int s = 0; s < n; s++) {
        while (e < n && ends[e] <= starts[s]) { rooms--; e++; }  // a meeting freed a room
        rooms++;                                                  // this meeting takes a room
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

The lovely idea: the minimum number of rooms needed equals the maximum number of meetings running at the same time. So we build two sorted event streams — starts and ends — and, like watching a door in and a door out, each "start" takes a room and each "end" frees one; the peak of occupied rooms is the answer. This "sweep two sorted event streams" idea (or a min-heap of end times) generalizes to any "max concurrent" question. O(n log n).

10. Monotonic stack

Recognize: "next greater/smaller element", "how far until a larger value", histogram/rectangle areas, stock spans. Maintain a stack that stays sorted (increasing or decreasing); each element is pushed and popped once → O(n). "Monotonic" just means the stack that preserves its ordering.

Daily temperatures (next greater)

int[] dailyTemperatures(int[] t) {
    int[] answer = new int[t.length];
    Deque<Integer> stack = new ArrayDeque<>();   // indices of a decreasing temp sequence
    for (int i = 0; i < t.length; i++) {
        while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
            int prev = stack.pop();              // today is prev's next warmer day
            answer[prev] = i - prev;
        }
        stack.push(i);
    }
    return answer;   // unresolved indices stay 0
}

The stack holds indices of days still waiting for a "warmer day," with decreasing temperatures. Each warmer day that arrives pops all the cooler waiting days off the stack and records their distances. Those that never get an answer stay zero.

Largest rectangle in histogram

int largestRectangleArea(int[] h) {
    Deque<Integer> stack = new ArrayDeque<>();   // increasing heights (by index)
    int best = 0;
    for (int i = 0; i <= h.length; i++) {
        int cur = (i == h.length) ? 0 : h[i];    // sentinel 0 flushes the stack at the end
        while (!stack.isEmpty() && cur < h[stack.peek()]) {
            int height = h[stack.pop()];
            int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
            int width = i - leftBoundary - 1;    // bars strictly between boundaries
            best = Math.max(best, height * width);
        }
        stack.push(i);
    }
    return best;
}

O(n). The key to understanding it: when we pop a bar, i is its first-smaller-to-the-right and the new stack top is its first-smaller-to-the-left. So the distance between those two boundaries is exactly the maximal width for which that bar is the limiting height — and the area is height × width. That sentinel 0 at the end exists so anything still on the stack gets flushed and counted.

11. Top-K / heaps / quickselect

Recognize: "K largest/smallest/most-frequent", "K closest to origin", "median of a stream". A heap gives O(n log k); quickselect gives average O(n) for a single K-th query. (A heap is that mound-shaped tree where the smallest or largest element is always at the top.)

Top-K frequent elements (min-heap of size K)

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    // Min-heap keyed by frequency; keep only the K most frequent.
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
    for (int key : freq.keySet()) {
        heap.offer(key);
        if (heap.size() > k) heap.poll();   // evict the least frequent so far
    }
    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) res[i] = heap.poll();
    return res;
}

O(n log k).

Median from a data stream (two heaps)

class MedianFinder {
    // lo: max-heap of the smaller half; hi: min-heap of the larger half.
    private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> hi = new PriorityQueue<>();

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());                 // funnel through to keep ordering correct
        if (hi.size() > lo.size()) lo.offer(hi.poll());  // rebalance: lo >= hi in size
    }
    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

Common pitfalls & gotchas

These are the potholes even experienced people fall into. Read them once, carefully:

• Integer overflow: mid = lo + (hi - lo) / 2, and use long for running sums (subarraySum, Koko hours). And know that Math.abs(Integer.MIN_VALUE) is negative (its negation doesn't fit in int).
• Off-by-one in windows: window length is right - left + 1. Decide before coding whether your window is [left, right] inclusive.
• Knapsack loop direction: downward for 0/1, upward for unbounded. Getting this backwards silently produces wrong answers, not crashes.
• Backtracking without deep copy: res.add(path) stores a reference; you must res.add(new ArrayList<>(path)) or every entry mutates to empty.
• Sliding window with negatives: doesn't work for "sum equals K" — the window isn't monotonic. Use prefix sums + hashmap.
• Greedy without proof: many "greedy-looking" problems (coin change with arbitrary denominations) are actually DP. If you can construct a counterexample to the greedy choice, it's DP.
• PriorityQueue comparator overflow: (a, b) -> a - b overflows for large ints; use Integer.compare(a, b).
• Floyd's second phase: reset one pointer to head, not to the meeting point's neighbor.

Best practices for the interview itself

An interview isn't just code; it's the narration of your thinking. Run these five steps like a ritual:

1. Restate the problem and confirm constraints (n size, value range, sorted?, duplicates?, negatives?). The constraints tell you the target complexity: n ≤ 20 screams backtracking/bitmask; n ≤ 10⁵ means O(n log n); n ≤ 10⁹ means binary search on the answer or math.
2. State brute force + its complexity first. It's a correctness baseline and buys thinking time.
3. Name the pattern out loud. "This is a sliding-window problem because we want the longest contiguous window under a constraint."
4. Code the template you've memorized; narrate invariants as you go.
5. Dry-run one small example and one edge case (empty, single element, all-same).

Interview Questions

Now the golden part: fifteen questions asked often in real interviews. Each sits in its own box; try to answer before you read on.

List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(1); res.add(path);
path.add(2); res.add(path);
System.out.println(res);

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
pq.offer(2_000_000_000); pq.offer(-2_000_000_000);
System.out.println(pq.poll());