# Amazon SDE I / AUTA APJ — Live Code Cheat Sheet (Java)

Companion to [`Answer-BIBLE.md`](Answer-BIBLE.md) (full cards) and [`Question-Research-BIBLE.md`](Question-Research-BIBLE.md) (what people were asked).

This file is the **scan sheet**: clue → pattern → Java DS → complexity → 8-line template. Not a prediction of Job **10454435**. Unnamed stays unnamed. Java is canonical.

**60-min:** LP 10–15 → DSA 40–45. Out loud: clarify → brute DS → optimal DS + why → code → dry run → TC/SC.

---

## 0. Complexity order (say this if they ask “what is faster”)

```
O(1)  <  O(α(n))  <  O(log n)  <  O(n)  <  O(n log n)  <  O(n²)  <  O(n³)  <  O(2ⁿ)  <  O(n!)
         DSU almost-constant     bin-search / heap peek-ish     sort / heap n log     DFS grid n² often
```

| n (typical Live Code) | Budget |
| --- | --- |
| n ≤ 20 | `2ⁿ`, backtracking, permutations |
| n ≤ 100 | `n³` OK |
| n ≤ 1e3 | `n²` OK |
| n ≤ 1e5 | `n log n` or `n` |
| n ≤ 1e6 | `n` or `n log n` tight |
| n ≤ 1e9 / “value range huge, n small” | binary search on **answer**, not on index |

**Space:** extra `O(n)` HashMap/visited is almost always fine. `O(n²)` matrix only if they gave a graph as matrix or n is small.

**Java costs you actually pay:**
- `HashMap` get/put average `O(1)`, worst `O(n)` (don’t mention unless they ask HashMap internals — see §7)
- `TreeMap` every op `O(log n)`
- `PriorityQueue` offer/poll `O(log n)`, peek `O(1)`
- `ArrayList` get `O(1)`, add-at-end amortized `O(1)`, add-at-index `O(n)`
- `LinkedList` as List: get `O(n)` — **do not use as a random-access list**. Use as Deque.
- `String` concat in a loop is `O(n²)` — use `StringBuilder`

---

## 1. Question clue → think of

Your table, plus Rank A/B clues from the Answer Bible (those are **reported**, not “10454435 will ask”).

### 1.A Core clues

| Question clue | Think of |
| --- | --- |
| "contiguous subarray/substring" | Sliding Window / Prefix Sum |
| "longest/shortest subarray satisfying condition" | Sliding Window |
| "exact sum" | Prefix Sum / HashMap |
| "subarray sum = k" | Prefix Sum + HashMap |
| "at most K" | Sliding Window |
| "exactly K distinct" | window(≤K) − window(≤K−1) |
| "minimum/maximum in every window" | Monotonic Deque |
| "next greater/smaller" | Monotonic Stack |
| "remove digits to get smallest number" | Monotonic Stack |
| "top K" | Heap |
| "Kth largest" | Min Heap size k / Quickselect |
| "duplicates / frequencies" | HashMap / HashSet |
| "pair sum" | HashMap / Two Pointer |
| "sorted array + pair" | Two Pointer |
| "merge intervals" | Sort + Greedy |
| "meeting overlap" | Sort / Heap |
| "dependency/prerequisite" | Topological Sort |
| "can finish courses/tasks?" | Directed Cycle / Topological Sort |
| "connected components" | DFS / BFS / DSU |
| "shortest path, unweighted graph" | BFS |
| "explore all reachable nodes" | DFS / BFS |
| "cycle in undirected graph" | DFS parent / BFS parent / DSU |
| "cycle in directed graph" | DFS colors / Kahn |
| "tree" | DFS / BFS |
| "tree diameter" | Two BFS/DFS |
| "grid" | DFS / BFS / DP |
| "number of ways" | DP |
| "maximum/minimum path value" | DP |
| "transactions buy/sell" | DP state machine |
| "strictly increasing after removing one" | Greedy |
| "minimum operations" | Greedy / DP / BFS-on-state |
| "all combinations" | Backtracking |
| "minimum number of changes" | DP / BFS / Greedy |
| "binary answer: possible or impossible" | Binary Search on Answer |
| "maximize minimum" | Binary Search on Answer |
| "minimum maximum" | Binary Search on Answer |
| "tree with repeated leaf logic" | Degree / Tree DP / Greedy |
| "everyone knows X, X knows nobody" | Elimination / graph matrix (Celebrity) |
| "frequency from encoded string" | Parsing + HashMap |
| "k elements from range" | Heap / Selection |
| "circular array" | Modulo / duplicated array / House Robber II split |

### 1.B Amazon-reported live clues (full cards in Answer-BIBLE §1–§2)

| Clue they used | Think of | Bible |
| --- | --- | --- |
| similar to sum of subarray minimums | monotonic stack + contribution | §1 A1 |
| row-sorted 0/1 matrix, row with max 1s | staircase `O(m+n)` or per-row BS | §1 A3 |
| Koko / ship packages / “eat all in H hours” | BS on answer | §1 A4 |
| equal-split tree / remove one edge | subtree sums, one DFS | §1 A4 |
| rotate matrix 90° | transpose + reverse rows | §1 A6 |
| next permutation similar | pivot from right + reverse suffix | §1 A6 |
| rotten oranges / minutes until all rot | **multi-source BFS** | §1 A7 |
| distance K, **no parent map** | undirected graph then BFS, or recursive no-map | §1 A7 |
| merge k sorted lists | min-heap of k heads | §1 A8 |
| word ladder (begin → end, dict) | BFS on words, 26-letter edges | §1 A10 |
| count beautiful splits (title named, **no LC id**) | prefix/z or equal-beauty split — clarify | §1 A10 |
| string compression, wrap count at 9 | RLE, split runs `a12` → `a9a3` | §1 A11 |
| beautiful nodes + adj matrix | graph on `int[][]`, DFS/BFS | §1 A11 |
| connect ropes / sticks / garlands | min-heap, always merge two smallest | §1 B0 |
| students, enemies not same group | bipartite 2-color | §1 B0 |
| grid right/down, traps, max reward | DP paths (OA-as-R1 remap — still a live pattern) | §1 B4 |
| min ops subtract a digit of n | BFS on integer states, or greedy | §1 B4 |
| LL → height-balanced BST | mid of array after LL→array, or slow/fast | §1 Deepak |
| first missing positive | cyclic sort in-place `1..n` | §1 Deepak |
| median of stream | two heaps | §2 |
| top K frequent | HashMap + min-heap k | §2 |
| number of islands | DFS/BFS flood | §2 |
| currency converter | weighted DFS/BFS | §2 |
| clone graph | HashMap old→new + DFS/BFS | §2 |
| keys and rooms | DFS/BFS from 0 | §2 |
| delivery stations + classes + topo | **entities + Kahn** — not LC 210 stamp | §2 / §3 |
| max sum switching two sorted LLs | two-pointer on lists — **not LC 962** | §2 |
| house robber then circular | DP, then `max(rob[0..n-2], rob[1..n-1])` | §2 |
| trapping rain / stocks DP | stack / state DP | §2 |
| max rectangle of 1s | histogram + monotonic stack | §2 |
| longest subarray sum 0 | prefix + HashMap first-index | §2 |
| GetRandom O(1) | HashMap + ArrayList swap-delete | §2 |
| LRU | HashMap + DLL | §3 |
| LFU | HashMap + freq → DLL | §3 |

### 1.C Pattern vs DS (one line)

| Pattern | Default Java DS | Why |
| --- | --- | --- |
| Sliding window | two ints `L,R` + maybe HashMap | shrink when invalid |
| Prefix sum = k | `HashMap<Long,Integer>` prefix→index/count | `need = prefix - k` |
| Monotonic stack | `ArrayDeque<Integer>` (indices) | next greater in `O(n)` |
| Monotonic deque | `ArrayDeque<Integer>` (indices) | window max in `O(n)` |
| Top K / merge k / ropes | `PriorityQueue` | get-min repeatedly |
| Median stream | two `PriorityQueue` | max-low + min-high |
| Graph unweighted | `ArrayDeque` BFS + `boolean[] vis` | shortest hops |
| Graph weighted | `PriorityQueue` Dijkstra | non-neg weights |
| Topo / cycle directed | `int[] indegree` + queue Kahn | also gives order |
| DSU components | `int[] parent, rank` | union by rank + path compress |
| BS on answer | `lo, hi` + `feasible(mid)` | monotonic predicate |
| Tree parent forbidden | adj list **or** recursive return | do not store `Map parent` if they said no |
| Cache O(1) | HashMap + DLL | LRU; LFU adds freq map |

---

## 2. All Java data structures — ops + complexity

Assume **average** for HashMap/HashSet unless they ask internals.

### 2.A Primitive-backed / arrays

| DS | Get | Set / insert | Delete | Extra | When |
| --- | --- | --- | --- | --- | --- |
| `int[]` / `T[]` | O(1) index | O(1) index | O(n) shift | contiguous | default |
| `boolean[] vis` | O(1) | O(1) | — | | graph/tree visited |
| `int[][]` matrix | O(1) | O(1) | — | | grid, adj matrix |
| `char[]` | O(1) | O(1) | — | mutable string | in-place string |
| `BitSet` | O(1) | O(1) | O(1) | packed bits | flags, sieve |

### 2.B Lists

| DS | get(i) | add end | add/remove index 0 | contains | Notes |
| --- | --- | --- | --- | --- | --- |
| `ArrayList<E>` | O(1) | amort. O(1) | O(n) | O(n) | **default list** |
| `LinkedList<E>` as List | O(n) | O(1) | O(1) | O(n) | almost never as List |
| `LinkedList<E>` as Deque | — | O(1) both ends | O(1) | O(n) | OK as queue/deque |
| `ArrayDeque<E>` | no get(i) | O(1) both ends | O(1) | O(n) | **default queue / stack / deque** |
| `Stack<E>` | — | O(1) push | O(1) pop | | **legacy + synchronized** — prefer `ArrayDeque` |
| `Vector<E>` | O(1) | O(1) | O(n) | | synchronized ArrayList — skip |

**Live Code stack:** `Deque<Integer> st = new ArrayDeque<>();` `st.push(x); st.pop(); st.peek();`

**Live Code queue:** `Queue<int[]> q = new ArrayDeque<>();` `q.offer(x); q.poll(); q.peek();`

### 2.C Maps / sets

| DS | get / contains | put / add | remove | ordered? | Notes |
| --- | --- | --- | --- | --- | --- |
| `HashMap<K,V>` | avg O(1) | avg O(1) | avg O(1) | no | **default map** |
| `LinkedHashMap<K,V>` | avg O(1) | avg O(1) | avg O(1) | insertion (or access-order) | LRU-ish; still not O(1) reorder unless access-order + removeEldest |
| `TreeMap<K,V>` | O(log n) | O(log n) | O(log n) | sorted keys | `ceilingKey`, `firstKey`, range |
| `HashSet<E>` | avg O(1) | avg O(1) | avg O(1) | no | visited, unique |
| `LinkedHashSet<E>` | avg O(1) | avg O(1) | avg O(1) | insertion | unique + order |
| `TreeSet<E>` | O(log n) | O(log n) | O(log n) | sorted | `ceiling`, `higher` |
| `IdentityHashMap` | ref equality | | | | skip unless they ask |
| `WeakHashMap` | GC-sensitive | | | | skip |

**HashMap internals (asked after review-word-count, bible §5.F):** array of buckets; Java 8+ treeify at 8 collisions; hash = `key.hashCode()` mixed; load factor 0.75 → resize `2n`. Equals+hashCode must both be overridden. `HashSet` is a `HashMap` with dummy value.

### 2.D Heaps / priority

| DS | peek | offer | poll | Notes |
| --- | --- | --- | --- | --- |
| `PriorityQueue<E>` min-heap | O(1) | O(log n) | O(log n) | **default heap** |
| max-heap | O(1) | O(log n) | O(log n) | `new PriorityQueue<>(Comparator.reverseOrder())` or `(a,b) -> b - a` **overflow-safe:** `Integer.compare(b,a)` |
| heap of pairs | | | | `PriorityQueue<int[]>` with `(a,b) -> a[0]-b[0]` |
| `TreeMap` as sorted multiset | O(log n) | O(log n) | O(log n) | when you need delete-**arbitrary** key; PQ cannot delete arbitrary in O(log n) without extra map |

**PQ cannot decrease-key.** Dijkstra: push new `(dist, node)` and skip stale (`if (d != dist[u]) continue`).

### 2.E Linked structures you write by hand

| DS | find | insert known node | delete known node | When |
| --- | --- | --- | --- | --- |
| Singly LL | O(n) | O(1) after prev | O(n) need prev | merge k, reverse, cycle |
| Doubly LL + HashMap | O(1) via map | O(1) | O(1) | **LRU**, Login Tracker mentor |
| Binary tree | O(n) / O(h) BST | | | DFS/BFS |
| BST / TreeMap | O(h) | O(h) | O(h) | sorted keys |
| Trie | O(L) | O(L) | O(L) | prefix, word ladder alphabet |
| Segment tree | O(log n) | O(log n) point | — | range query (rare SDE I) |
| Fenwick / BIT | O(log n) | O(log n) | — | prefix sums updates (rare) |
| DSU | O(α(n)) find | union O(α(n)) | — | components, cycle undirected |

### 2.F Strings

| Op | Cost | Do |
| --- | --- | --- |
| `s.charAt(i)` | O(1) | |
| `s.substring(i,j)` | O(j-i) Java 7+ **copy** | avoid in inner loop |
| `s + t` in loop | O(n²) | `StringBuilder` |
| `StringBuilder.append` | amort. O(1) | then `toString()` |
| `s.toCharArray()` | O(n) | mutate locally |
| `Integer.parseInt` | O(len) | |
| `String.valueOf(x)` | O(digits) | |

### 2.G Concurrency (only if LLD follow-up)

| DS | Notes |
| --- | --- |
| `Collections.synchronizedMap` | coarse lock |
| `ConcurrentHashMap` | default concurrent map |
| `synchronized` / `ReentrantLock` | Rate Limiter single-node |
| Redis + Lua | distributed Rate Limiter (bible count = 1, **not UTA default**) |

---

## 3. Java declarations (paste at top of Live Code)

```java
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int v) { val = v; }
    ListNode(int v, ListNode n) { val = v; next = n; }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

// lists / maps / heaps
List<Integer> a = new ArrayList<>();
Deque<Integer> st = new ArrayDeque<>();          // stack
Queue<int[]> q = new ArrayDeque<>();             // BFS
Map<Integer, Integer> freq = new HashMap<>();
Set<Integer> seen = new HashSet<>();
PriorityQueue<Integer> minH = new PriorityQueue<>();
PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
TreeMap<Integer, Integer> tm = new TreeMap<>();

// iterate map
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    int k = e.getKey(), v = e.getValue();
}

// sort
Arrays.sort(arr);
Collections.sort(list);
list.sort((p, q) -> Integer.compare(p[0], q[0]));

// directions
int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
```

**Refuse:** `Stack`, `Vector`, `LinkedList` as random-access, `b - a` comparator on large ints, `==` on Integer outside −128..127 cache.

---

## 4. End-to-end templates (minimal Java)

### 4.1 Sliding window (at most K / longest valid)

```java
int left = 0, ans = 0;
Map<Character, Integer> cnt = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    cnt.put(c, cnt.getOrDefault(c, 0) + 1);
    while (/* invalid */) {
        char d = s.charAt(left++);
        cnt.put(d, cnt.get(d) - 1);
        if (cnt.get(d) == 0) cnt.remove(d);
    }
    ans = Math.max(ans, right - left + 1);
}
```

Exactly K = `atMost(K) - atMost(K - 1)`.

### 4.2 Prefix sum = k (subarray)

```java
Map<Long, Integer> first = new HashMap<>();
first.put(0L, 1); // count of prefixes; use index if you need length
long sum = 0;
int ans = 0;
for (int x : a) {
    sum += x;
    ans += first.getOrDefault(sum - k, 0);
    first.put(sum, first.getOrDefault(sum, 0) + 1);
}
```

Longest sum 0: store **first index** of each prefix, not count.

### 4.3 Monotonic stack (next greater)

```java
int n = a.length;
int[] nge = new int[n];
Arrays.fill(nge, -1);
Deque<Integer> st = new ArrayDeque<>(); // indices, decreasing values
for (int i = 0; i < n; i++) {
    while (!st.isEmpty() && a[st.peek()] < a[i]) nge[st.pop()] = a[i];
    st.push(i);
}
```

Subarray minimum contribution: next smaller left + next smaller right, then `a[i] * leftDist * rightDist`.

### 4.4 Monotonic deque (window max)

```java
Deque<Integer> dq = new ArrayDeque<>(); // indices, decreasing a[i]
for (int i = 0; i < n; i++) {
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
    while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
    dq.offerLast(i);
    if (i >= k - 1) windowMax[i - k + 1] = a[dq.peekFirst()];
}
```

### 4.5 Binary search on answer

```java
int lo = 1, hi = (int) 1e9, ans = hi;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (feasible(mid)) { ans = mid; hi = mid - 1; } // min feasible
    else lo = mid + 1;
}
return ans;
```

Koko / ship packages: `feasible` = “hours/days needed ≤ H”. Monotonic: larger capacity ⇒ easier.

### 4.6 Two heaps (median stream)

```java
PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder()); // max
PriorityQueue<Integer> high = new PriorityQueue<>(); // min
void add(int x) {
    if (low.isEmpty() || x <= low.peek()) low.offer(x);
    else high.offer(x);
    if (low.size() > high.size() + 1) high.offer(low.poll());
    if (high.size() > low.size()) low.offer(high.poll());
}
double median() {
    if (low.size() > high.size()) return low.peek();
    return (low.peek() + high.peek()) / 2.0;
}
```

### 4.7 Top K / Connect ropes

```java
PriorityQueue<Integer> min = new PriorityQueue<>();
for (int x : ropes) min.offer(x);
int cost = 0;
while (min.size() > 1) {
    int s = min.poll() + min.poll(); // use long if they said overflow
    cost += s;
    min.offer(s);
}
```

Top K frequent: count HashMap, then min-heap of size k on frequency.

### 4.8 Merge k sorted lists

```java
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode h : lists) if (h != null) pq.offer(h);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
    ListNode n = pq.poll();
    tail.next = n;
    tail = n;
    if (n.next != null) pq.offer(n.next);
}
return dummy.next;
```

### 4.9 BFS grid / rotten oranges

```java
Queue<int[]> q = new ArrayDeque<>();
int fresh = 0, minutes = 0;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
        if (g[i][j] == 2) q.offer(new int[]{i, j});
        if (g[i][j] == 1) fresh++;
    }
while (!q.isEmpty() && fresh > 0) {
    int sz = q.size();
    minutes++;
    for (int s = 0; s < sz; s++) {
        int[] c = q.poll();
        for (int[] d : DIRS) {
            int ni = c[0] + d[0], nj = c[1] + d[1];
            if (ni<0||nj<0||ni>=m||nj>=n||g[ni][nj]!=1) continue;
            g[ni][nj] = 2;
            fresh--;
            q.offer(new int[]{ni, nj});
        }
    }
}
return fresh == 0 ? minutes : -1;
```

### 4.10 DFS islands

```java
void dfs(char[][] g, int i, int j) {
    if (i<0||j<0||i>=g.length||j>=g[0].length||g[i][j]!='1') return;
    g[i][j] = '0';
    dfs(g, i+1, j); dfs(g, i-1, j); dfs(g, i, j+1); dfs(g, i, j-1);
}
```

### 4.11 Dijkstra

```java
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int d = cur[0], u = cur[1];
    if (d != dist[u]) continue;
    for (int[] e : adj.get(u)) {
        int v = e[0], w = e[1];
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.offer(new int[]{dist[v], v});
        }
    }
}
```

### 4.12 Kahn topo + bipartite

```java
// topo
int[] indeg = new int[n];
for (int u = 0; u < n; u++) for (int v : adj.get(u)) indeg[v]++;
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
    int u = q.poll();
    order.add(u);
    for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
boolean cycle = order.size() < n;

// bipartite 2-color (enemies / students)
boolean bipartite(List<List<Integer>> adj, int n) {
    int[] col = new int[n];
    Arrays.fill(col, -1);
    for (int s = 0; s < n; s++) if (col[s] == -1) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(s); col[s] = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (col[v] == -1) { col[v] = col[u] ^ 1; q.offer(v); }
                else if (col[v] == col[u]) return false;
            }
        }
    }
    return true;
}
```

### 4.13 DSU

```java
class DSU {
    int[] p, r;
    DSU(int n) { p = new int[n]; r = new int[n]; for (int i = 0; i < n; i++) p[i] = i; }
    int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }
    boolean union(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) { int t = a; a = b; b = t; }
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
}
```

### 4.14 Tree: distance K **without parent map**

Build undirected adj (parent as **DFS arg**, not a stored map), then BFS from target. Or recursive: `find` returns distance to target; when returning up, collect the other subtree at `k - dist - 1`. Full code: Answer-BIBLE §1 Dist-K.

### 4.15 Rotate image + next perm

```java
// 90° clockwise in-place
void rotate(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) { int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t; }
    for (int i = 0; i < n; i++)
        for (int l = 0, r = n - 1; l < r; l++, r--) { int t = m[i][l]; m[i][l] = m[i][r]; m[i][r] = t; }
}

void nextPermutation(int[] a) {
    int n = a.length, i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    for (int l = i + 1, r = n - 1; l < r; l++, r--) { int t = a[l]; a[l] = a[r]; a[r] = t; }
}
```

### 4.16 First missing positive (cyclic sort)

```java
int firstMissingPositive(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        while (a[i] >= 1 && a[i] <= n && a[a[i] - 1] != a[i]) {
            int t = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = t;
        }
    }
    for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
    return n + 1;
}
```

### 4.17 House Robber I / II

```java
int robLine(int[] a, int l, int r) { // inclusive
    int prev = 0, cur = 0;
    for (int i = l; i <= r; i++) {
        int next = Math.max(cur, prev + a[i]);
        prev = cur; cur = next;
    }
    return cur;
}
int robCircular(int[] a) {
    int n = a.length;
    if (n == 1) return a[0];
    return Math.max(robLine(a, 0, n - 2), robLine(a, 1, n - 1));
}
```

### 4.18 Word ladder

```java
int ladder(String begin, String end, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(end)) return 0;
    Queue<String> q = new ArrayDeque<>();
    q.offer(begin);
    int dist = 1;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int s = 0; s < sz; s++) {
            String w = q.poll();
            if (w.equals(end)) return dist;
            char[] ch = w.toCharArray();
            for (int i = 0; i < ch.length; i++) {
                char old = ch[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    ch[i] = c;
                    String nxt = new String(ch);
                    if (dict.remove(nxt)) q.offer(nxt);
                }
                ch[i] = old;
            }
        }
        dist++;
    }
    return 0;
}
```

### 4.19 Max 1s row in row-sorted 0/1 matrix — `O(m+n)`

```java
int rowWithMaxOnes(int[][] mat) {
    int m = mat.length, n = mat[0].length, c = n, row = 0;
    for (int i = 0; i < m; i++) {
        while (c > 0 && mat[i][c - 1] == 1) c--;
        if (n - c > n - /* previous best stored in c start */) { /* track best */ }
    }
    // cleaner:
    int bestRow = -1, best = 0, j = n;
    for (int i = 0; i < m; i++) {
        while (j > 0 && mat[i][j - 1] == 1) j--;
        int ones = n - j;
        if (ones > best) { best = ones; bestRow = i; }
    }
    return bestRow;
}
```

Start `j = n` at top-right; only move **left** (more 1s) or **down**. Never go right.

### 4.20 String compression wrap-at-9

```java
String compress(String s) {
    StringBuilder sb = new StringBuilder();
    int i = 0, n = s.length();
    while (i < n) {
        int j = i;
        while (j < n && s.charAt(j) == s.charAt(i)) j++;
        int cnt = j - i;
        sb.append(s.charAt(i));
        while (cnt > 0) {
            int chunk = Math.min(9, cnt);
            if (chunk > 1) sb.append(chunk); // confirm: is 'a' or 'a1' for count 1?
            else { /* single char: usually no '1' — ASK */ }
            cnt -= chunk;
            if (cnt > 0) sb.append(s.charAt(i)); // wrap: a12 → a9a3
        }
        i = j;
    }
    return sb.toString();
}
```

**Clarify:** count 1 written? wrap at 9 or at 10?

### 4.21 LRU (HashMap + DLL) — not Login Tracker

```java
class LRUCache {
    static class Node { int k, v; Node prev, next; Node(int k, int v) { this.k = k; this.v = v; } }
    int cap;
    Map<Integer, Node> map = new HashMap<>();
    Node head = new Node(0, 0), tail = new Node(0, 0);
    LRUCache(int cap) { this.cap = cap; head.next = tail; tail.prev = head; }
    void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    void addFront(Node n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    int get(int k) {
        Node n = map.get(k);
        if (n == null) return -1;
        remove(n); addFront(n);
        return n.v;
    }
    void put(int k, int v) {
        if (map.containsKey(k)) remove(map.get(k));
        Node n = new Node(k, v);
        map.put(k, n);
        addFront(n);
        if (map.size() > cap) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.k);
        }
    }
}
```

Login Tracker (`new_login` / `get_oldest_login`) is **unverified mentor-only** — same HashMap+DLL shape; do not present as a first-hand 10454435 question. See Answer-BIBLE §10.

### 4.22 Backtracking subsets / permutations

```java
void subsets(int[] a, int i, List<Integer> path, List<List<Integer>> ans) {
    if (i == a.length) { ans.add(new ArrayList<>(path)); return; }
    path.add(a[i]); subsets(a, i + 1, path, ans); path.remove(path.size() - 1);
    subsets(a, i + 1, path, ans);
}
```

### 4.23 DP knapsack-ish / unique paths

```java
// unique paths right/down
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
```

---

## 5. Algorithm complexity cheat (name out loud)

| Algorithm | Time | Space |
| --- | --- | --- |
| Binary search on array | O(log n) | O(1) |
| BS on answer + O(n) feasible | O(n log RANGE) | O(1) extra |
| Merge sort / Collections.sort (Timsort) | O(n log n) | O(n) |
| Heap sort | O(n log n) | O(1) |
| Quickselect average | O(n) | O(1) |
| Two pointers on sorted | O(n) after sort | O(1) |
| Sliding window | O(n) | O(Σ) |
| Monotonic stack/deque | O(n) | O(n) |
| DFS/BFS graph | O(V+E) | O(V) |
| Dijkstra PQ | O((V+E) log V) | O(V) |
| Bellman-Ford | O(VE) | O(V) |
| Kahn / DFS topo | O(V+E) | O(V) |
| DSU n unions | ~O(n) | O(n) |
| Trie insert all words | O(total chars) | O(total chars) |
| KMP | O(n+m) | O(m) |
| Kadane | O(n) | O(1) |
| Knapsack 0/1 | O(nW) | O(W) |
| LIS patience | O(n log n) | O(n) |
| Floyd-Warshall | O(n³) | O(n²) |

**Sort in Java:** `Arrays.sort(int[])` dual-pivot quicksort (primitive); `Arrays.sort(Object[])` Timsort O(n log n).

---

## 6. Why this DS (say it before coding)

| Need | Use | Refuse |
| --- | --- | --- |
| O(1) lookup by key | HashMap | TreeMap unless order |
| min/max repeatedly, no arbitrary delete | PriorityQueue | sorting every time |
| min + delete arbitrary | TreeMap counts | PQ |
| next greater | monotonic stack | O(n²) nested loops if n=1e5 |
| window min/max | monotonic deque | heap of window (lazy delete OK if n small) |
| FIFO level order | ArrayDeque | Stack |
| LIFO | ArrayDeque | java.util.Stack |
| shortest unweighted | BFS | DFS (wrong for shortest) |
| shortest weighted ≥0 | Dijkstra | BFS |
| order with prerequisites | Kahn | undirected DSU |
| components no graph object | DSU | if you already have adj, DFS is simpler |
| O(1) get+put cache | HashMap+DLL | LinkedHashMap only if you know access-order |
| balanced BST from sorted LL | mid split / array | random inserts O(n log n) unbalanced risk |

**Koko vs heap:** if the question is “minimum speed so hours ≤ H”, that is **monotonic feasible** → BS on answer, not a heap.

**Connect ropes vs sort once:** after merge, the new rope re-enters the set → heap, not a single sort.

---

## 7. CS one-liners they actually asked (bible §5.F)

| Topic | 15-second Java-backed answer |
| --- | --- |
| Thread vs process | Process = isolated address space; thread = shared heap, own stack. Java `Thread` / pool. Context switch threads cheaper. |
| Deadlock | 4 Coffman: mutex, hold+wait, no preemption, cycle. Fix: lock order, timeout. |
| HashMap | buckets + treeify 8; `hashCode`/`equals`; load 0.75. |
| Why PQ | get-min O(log n) vs sort O(n log n) each time; Connect Ropes / Dijkstra / Top K. |
| B-Tree vs B+ | B+ all keys in leaves + leaf linked → range scans (DB indexes). B-Tree keys in internal too. |
| Kafka order | order **inside a partition**, not across. Key → same partition. |
| REST vs GraphQL | resume has both + ProtoBuf. REST: cacheable resources. GraphQL: client-shaped payload, over-fetch less. ProtoBuf: binary RPC. Only if they ask. |

---

## 8. LLD 20-second DS pick

| Design | Core DS |
| --- | --- |
| LRU | HashMap + DLL |
| LFU | key→node, freq→DLL, minFreq |
| Rate limiter (single box) | HashMap key→window state; Token Bucket doubles | **SDE I live count = 1, OA+3 SD, not UTA** |
| Parking lot | spots by size (TreeMap/heap of free ids) + vehicle→spot |
| Logger | Strategy + levels; async queue |
| Unix find | Composite filter + recursive dir |
| Playlist O(1) insert/delete/search | HashMap + DLL (Spotify card) |
| Searchable collection | HashMap + inverted index / Trie |
| Dog check-in | HashMap dogId→record + timestamp |
| Locker | lockerId map + size queues |
| Delivery + topo | classes + Kahn |

Arijit unnamed SD: **ask** entities/scale — do not invent APIs/caching as Job 10454435.

---

## 9. Live Code dry-run + stuck

**Dry run table:** columns = `i` / stack-or-queue contents / `ans`. Use their example, 5–8 rows.

**Stuck:**
1. Write brute, state TC, say the optimal DS.
2. Implement the inner loop of optimal even if helpers are stubs.
3. If graph on a tree and they ban parent map: adj list with parent as **parameter**.

**Integer overflow:** ropes / garlands / prefix sums → `long`.

**Null:** empty list, k=0, graph disconnected, all oranges already rotten.

---

## 10. 18 Aug 60-second scan order

1. This clue table (§1)
2. Declare DS + why (§6)
3. Template (§4)
4. Full card in [`Answer-BIBLE.md`](Answer-BIBLE.md) §1 if it matches a named Rank A/B title
5. LP one-pager: Answer-BIBLE §11 cheat-sheet (resume metrics only)

Do not lead with Login Tracker. Rate Limiter is not the UTA two-DSA default.