Cheat sheets: going deeper

Name the state in one sentence BEFORE any code.
Plain recursion first -> memo (int[][] filled with -1) -> table if time.
Recursion depth near n risks StackOverflowError: go bottom-up.
Order of fill: every dp cell I read must already be final.
Answer where? ____    Do they want the number or the items? ____

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class Idioms {
  // ok(cond, msg): throws AssertionError when cond is false
  public static void main(String[] args) {
    // min-heap of {dist, node} by dist; compare, never subtract
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[] {9, 1});
    pq.add(new long[] {3, 2});
    ok(pq.poll()[0] == 3, "min-heap");

    // max-heap of ints; k-largest keeps a MIN-heap of size k
    PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(Collections.reverseOrder());
    maxHeap.add(4);
    maxHeap.add(7);
    ok(maxHeap.peek() == 7, "max-heap");

    // sort intervals by start without overflow
    int[][] iv = {{5, 8}, {1, 3}};
    Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));
    ok(iv[0][0] == 1, "sort by start");

    // deque as stack (push/pop) and as 0-1 BFS queue (addFirst/addLast)
    Deque<Integer> st = new ArrayDeque<>();
    st.push(1);
    st.push(2);
    ok(st.pop() == 2, "stack");

    // count with merge; default with getOrDefault
    Map<String, Integer> cnt = new HashMap<>();
    cnt.merge("a", 1, Integer::sum);
    cnt.merge("a", 1, Integer::sum);
    ok(cnt.get("a") == 2 && cnt.getOrDefault("z", 0) == 0, "merge");

    // sorted map: floor/ceiling are O(log n) "nearest" queries
    TreeMap<Integer, String> tm = new TreeMap<>();
    tm.put(10, "x");
    tm.put(20, "y");
    ok(tm.floorKey(15) == 10 && tm.ceilingKey(15) == 20, "floor");

    // midpoint that cannot overflow; long for sums and products
    int lo = 2_000_000_000, hi = 2_100_000_000;
    ok(lo + (hi - lo) / 2 == 2_050_000_000, "mid");
    ok(1_000_000 * 1_000_000L == 1_000_000_000_000L, "long");
  }
}

Clock: 0-10 clarify + scope | 10-20 skeleton | 20-55 must-haves
       55-70 error paths | 70-82 bonus + extension | 82-90 clean + notes
Patterns: strategy, state, observer, factory, builder, command,
repository, decorator. Reach for one only if a requirement needs it.
State machine (order, vending, elevator): a table (state, event) -> state;
look up and refuse BEFORE the history entry and the change. Test every
pair: 6 legal and 24 illegal in the lesson's order, each illegal one
leaves state and history unchanged. Threads: sheet C7.
Out of scope (say it aloud): ______________________________
Extension I expect: ________________  Run command: ________________

Say it first: "single-threaded; the ceiling is ___ ; next I would ___".
Three race shapes (the author's grouping, not a standard):
 1 check-then-act   two gates both see one free spot and both take it
 2 read-modify-write  count++ is read, add, write; two threads lose one
 3 two fields move together   a transfer debits one, credits the other
Fix: make check and act ONE step, or hold ONE lock around both.
Locks vs atomics: one variable -> atomic (AtomicInteger, LongAdder);
  a check plus a change on more than one variable -> lock;
  per key in a map -> ConcurrentHashMap.compute(key, ...)
Two locks -> take them in one fixed order (deadlock).
Visibility: a flag read by another thread needs volatile or a lock.

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.LongAdder;

class Races {
  // Shape 1, check-then-act: the check and the change must be one step.
  static class Spots {
    private final AtomicInteger free;
    Spots(int n) { free = new AtomicInteger(n); }

    boolean take() {                      // one variable: compare-and-set
      int f;
      do {
        f = free.get();
        if (f == 0) return false;         // check
      } while (!free.compareAndSet(f, f - 1)); // act, only if unchanged
      return true;
    }
  }

  // Shape 2, read-modify-write: count++ is a read, an add and a write.
  static final LongAdder entered = new LongAdder();

  // Shape 3, two fields change together: one lock must cover both.
  static class Account {
    final int id;
    long cents;
    Account(int id, long cents) { this.id = id; this.cents = cents; }
  }

  static boolean transfer(Account a, Account b, long amt) {
    Account first = a.id < b.id ? a : b, second = first == a ? b : a;
    synchronized (first) {                // fixed order: no deadlock
      synchronized (second) {
        if (a.cents < amt) return false;  // check + change, both locks
        a.cents -= amt;
        b.cents += amt;
        return true;
      }
    }
  }
}

Page fields: Relevance | Scope | Decisions | Motivation | Concerns
Questions: seat, level, gap, level risk, bar, decision path;
          scope, on-call, promotion, manager style, overlap
Heard from them (use two by name): ____________ / ____________
Two decisions with costs: ______________ / ______________
The doubt I will close on: ______________________

Offer: fixed ___ variable ___ bonus ___ stock ___ level ___
Year-1 cash: ___    Year-2 cash: ___ (no one-time items)
My ask: +___ gross nets ___ (template T3)   Net a month: ___
Example only, invented base of 23,06,500 taxable, new regime (lesson 12):
  +1 lakh nets 73,662; +2 lakh nets 1,42,462; +4 lakh nets 2,80,062
  (first 93,500 at 25%, rest at 30%, 4% cess). Yours will differ.
My number: ___    My reason: ____________    Deadline: ____
Written offer first. Never say a number I would not accept.

Allowed? ___ (ask in writing; if not stated, assume not)
One third-party account of one format (AI lesson, Figure A.3, reported by
candidates, not a company rule): 60 min = fix a bug, build, optimise
Each prompt: constraint + the code. After each accepted change: run tests.
Reject or rewrite one suggestion, say why. Add one edge-case test.
I can explain every line I keep.