# Amazon SDE I / AUTA APJ — R3/R4 DSA answers (Adarsh Vishwakarma)

Notes for a **third live** (HM / GenAI Fluency) and a **possible fourth** (Bar Raiser). R1 (13 Aug 2026) and R2 (18 Aug 2026) already happened. **Java** Live Code. Production internships were Python / TypeScript (plus ROS2 on Horizon) — DSA here is Java.

These are worked answers to questions **other** SDE I / UTA / AUTA candidates reported. Job **10454435** still has **no** public IE that names a live-round question. Your loop may differ. Unnamed stays unnamed. OA is not a round.

**OA-as-R1 trap (pattern reuse only):** if someone numbered OA as “Round 1”, **their R3 is often this loop’s R2 analogue**, not your upcoming R3. Cards in §B are still useful as a third-live pattern. They are labeled.

**Not in this file as full code**
- **Login Tracker** (`new_login` / `get_oldest_login`): **unverified**. Mentor-only (`amazon-sde1-interview-prep.md`). Same HashMap+DLL shape as LRU below. Do not present as a 10454435 question. See § OPTIONAL MENTOR at the end.
- **Rate Limiter:** independent SDE I live-round count = **1**, OA+3 Second Technical **SD**, **not** UTA two-DSA. Java/LLD lives in the LLD fragment, not here.

**60-min Live Code:** clarify 3–6 questions → brute DS → optimal DS + why → Java → dry-run table → TC/SC. If stuck: brute on the board, name the optimal DS, then the hot loop.

Shared helpers:

```java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
```

---

## A. True later-slot / Fluency (named IE)

---

### 1. All Nodes Distance K **without parent map** — mapped R2 (7406809) + R3 labeled GenAI Fluency (7623949) — AUTA Y on 7406809 — [LC 7406809](https://leetcode.com/discuss/post/7406809/amazon-sde-1-auta-interview-experience-s-k6t7/) · reprint [LC 7623949](https://leetcode.com/discuss/post/7623949/amazon-sde-1-application-interview-exper-92xt/)

**What they actually asked**
LC 7406809 AUTA R2: **All nodes distance K**, **without parent map**, recursive (candidate LC-linked the family). LC 7623949 labeled the slot **GenAI Fluency** but the work was this DSA (no parent mapping, O(n)). Same constraint, two loops. If the invite says Fluency and they paste a tree: **write the tree first**.

**Clarify out loud**
1. Binary tree, target as node object (or value?), integer `k`?
2. Return values at distance `k` (any order)?
3. **Forbidden:** `HashMap<TreeNode, TreeNode>` parent map?
4. Unique values? `k = 0` → `[target]`?
5. Distance through parent counts?
6. If this is the “Fluency” hour: do they still want a GenAI sentence after code?

**Trick / pattern in one sentence**
Distance-K is BFS on the **undirected** tree; you may build an adjacency list (not a parent map) **or** recurse: after finding target, walk down `k` and, on the way up, walk the sibling with remaining distance.

**Why this data structure**
- brute DS: undirected graph, then from **every** node BFS to target — `O(n²)`
- optimal DS: (A) adj list + one BFS from target; (B) no extra parent map — DFS return-distance + `collectDown`
- refuse: the forbidden parent HashMap if they restated the constraint; Dijkstra (unweighted)

**Brute**
Honest Live-Code brute: graph once, then BFS from every node.

```java
public List<Integer> distanceKBrute(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, List<TreeNode>> g = new HashMap<>();
    buildUndirected(root, null, g);
    List<Integer> ans = new ArrayList<>();
    for (TreeNode start : g.keySet()) {
        if (bfsDist(start, target, g) == k) ans.add(start.val);
    }
    return ans;
}

private int bfsDist(TreeNode start, TreeNode target,
                    Map<TreeNode, List<TreeNode>> g) {
    Queue<TreeNode> q = new ArrayDeque<>();
    Set<TreeNode> seen = new HashSet<>();
    q.add(start);
    seen.add(start);
    int d = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            if (cur == target) return d;
            for (TreeNode nei : g.getOrDefault(cur, new ArrayList<>())) {
                if (seen.add(nei)) q.add(nei);
            }
        }
        d++;
    }
    return -1;
}
```
TC `O(n²)`. SC `O(n)`. Fails a large tree in 45 min only if they n-scare you — still write it, then switch.

**Optimal — version 1: DFS builds undirected graph, then BFS (no parent HashMap)**

```java
public List<Integer> distanceKViaGraph(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
    buildUndirected(root, null, graph);
    List<Integer> ans = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<>();
    Set<TreeNode> seen = new HashSet<>();
    queue.add(target);
    seen.add(target);
    int dist = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        if (dist == k) {
            for (TreeNode node : queue) ans.add(node.val);
            return ans;
        }
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            for (TreeNode nei : graph.getOrDefault(cur, new ArrayList<>())) {
                if (seen.add(nei)) queue.add(nei);
            }
        }
        dist++;
    }
    return ans;
}

private void buildUndirected(TreeNode node, TreeNode from,
                             Map<TreeNode, List<TreeNode>> graph) {
    if (node == null) return;
    graph.putIfAbsent(node, new ArrayList<>());
    if (from != null) {
        graph.get(node).add(from);
        graph.get(from).add(node);
    }
    buildUndirected(node.left, node, graph);
    buildUndirected(node.right, node, graph);
}
```

`from` is a **call parameter**, not a stored parent map.

**Optimal — version 2: recursive, no parent map, no graph (matches 7406809 “recursive / no parent map”)**

```java
public List<Integer> distanceKNoParentMap(TreeNode root, TreeNode target, int k) {
    List<Integer> ans = new ArrayList<>();
    find(root, target, k, ans);
    return ans;
}

/** @return distance from node down to target, or -1 if target not in this subtree */
private int find(TreeNode node, TreeNode target, int k, List<Integer> ans) {
    if (node == null) return -1;
    if (node == target) {
        collectDown(node, k, ans);
        return 0;
    }
    int left = find(node.left, target, k, ans);
    if (left != -1) {
        if (left + 1 == k) ans.add(node.val);
        collectDown(node.right, k - left - 2, ans);
        return left + 1;
    }
    int right = find(node.right, target, k, ans);
    if (right != -1) {
        if (right + 1 == k) ans.add(node.val);
        collectDown(node.left, k - right - 2, ans);
        return right + 1;
    }
    return -1;
}

private void collectDown(TreeNode node, int dist, List<Integer> ans) {
    if (node == null || dist < 0) return;
    if (dist == 0) {
        ans.add(node.val);
        return;
    }
    collectDown(node.left, dist - 1, ans);
    collectDown(node.right, dist - 1, ans);
}
```

Dry run — target = 5, k = 2:

```
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
```

| call | return dist to 5 | extra collect | ans |
| --- | ---: | --- | --- |
| find(5) | 0 | down k=2 → 7,4 | 7,4 |
| find(3) left=0 | 1 | `left+1==k`? no; collectDown(1, 0) → **1** | 7,4,1 |

Nodes at dist 2: `7, 4, 1`.

TC `O(n)`. SC `O(h)` recursion (v2) or `O(n)` graph (v1).

Follow-ups they asked: 7406809 BR was a **different** tree-path print (card 6); O(n) required; Fluency reprint is the same constraint.

**If you get stuck in Live Code**
- Say you would store parents, then immediately switch to `buildUndirected` if they ban the map.
- If graph is “too much space,” code `find` + `collectDown` only.

---

### 2. Next Greater Element — mapped R3 HM — UTA N — [LC 7724048](https://leetcode.com/discuss/post/7724048/amazon-sde-1-interview-experience-by-ano-t6fz/)

**What they actually asked**
Snippet: **Next Greater Element** on R3 HM with GenAI (LLM use/verify). Same IE: Aggressive Cows on R2, Detonate Bombs on R1. **Variation — do not stamp LC 496 / 503 / 556 as the asked id.** Ask which variant.

**Clarify out loud**
1. Next greater to the **right** for every index? Or nums1 subset of nums2 (two arrays)?
2. Circular (wrap around)?
3. Strictly greater? Return value or index? Missing → `-1`?
4. Same digits next permutation instead? (Prabhash R1 mixed NGE / next perm — different IE)

**Trick / pattern in one sentence**
Monotonic **decreasing** stack of candidates; each index pops until it sees a strictly greater value.

**Why this data structure**
- brute: nested `j > i` scan
- optimal: `ArrayDeque` of values (or indices); each element pushed/popped once
- refuse: sort — loses positions; heap — wrong order

**Brute**

```java
public int[] ngeBrute(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[i]) {
                ans[i] = a[j];
                break;
            }
        }
    }
    return ans;
}
```
TC `O(n²)`. SC `O(1)` extra. Fails n ~ 1e5.

**Optimal** — right-to-left, stack holds values still looking for a greater to their right (actually: stack holds increasing-to-the-right candidates).

```java
public int[] nextGreater(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Deque<Integer> st = new ArrayDeque<>(); // values, decreasing toward top
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && st.peek() <= a[i]) st.pop();
        ans[i] = st.isEmpty() ? -1 : st.peek();
        st.push(a[i]);
    }
    return ans;
}
```

Circular follow-up (if they say wrap): loop `i = 2n-1 .. 0`, use `a[i % n]`, write `ans` only when `i < n`.

Dry run `[2,1,2,4,3]`:

| i | a[i] | stack after pop | ans[i] | stack after push |
| ---: | ---: | --- | ---: | --- |
| 4 | 3 | empty | -1 | 3 |
| 3 | 4 | empty (3 popped) | -1 | 4 |
| 2 | 2 | 4 | 4 | 4,2 |
| 1 | 1 | 4,2 | 2 | 4,2,1 |
| 0 | 2 | 4 (2,1 popped) | 4 | 4,2 |

Answer `[4, 2, 4, -1, -1]`.

TC `O(n)`. SC `O(n)`.

Follow-ups: circular; next **smaller**; Daily Temperatures (store indices, `ans[i] = j - i`); GenAI slot still wants this code first.

**If you get stuck in Live Code**
- Nested loop brute, then “stack pops while top ≤ current.”
- If the stack comparator feels inverted, dry-run one example before coding.

---

### 3. Dynamic k-th largest / k changes — mapped R3 — UTA N — [LC 7850431](https://leetcode.com/discuss/post/7850431/amazon-sde-1-interview-experience-by-imx-xitu/)

**What they actually asked**
Snippet: **dynamic k-th largest where k changes**. Same loop as Cheapest Flights–like + power allocation (R1) and Connect Sticks + sum-0 (R2). GenAI slot also had this DSA.

**Clarify out loud**
1. Ops: `add` only, or add/remove, and a separate `setK`?
2. k can grow larger than current size? Duplicates?
3. Need exact k-th after every op, or batch queries?
4. 1-based k-th **largest** (not smallest)?

**Trick / pattern in one sentence**
Min-heap of the current “top k” plus a sorted remainder so `setK` can move elements without a full sort.

**Why this data structure**
- brute: keep all numbers, sort after every query
- optimal: min-heap of size k + `TreeMap` (multiset) of the rest; largest of rest = `rest.lastKey()`
- refuse: re-sort from scratch if they want many updates; max-heap of everything when k ≪ n and k is static (static is card 7)

**Brute**

```java
class KthDynamicBrute {
    List<Integer> a = new ArrayList<>();
    int k;
    KthDynamicBrute(int k, int[] nums) {
        this.k = k;
        for (int x : nums) a.add(x);
    }
    void add(int val) { a.add(val); }
    void setK(int newK) { k = newK; }
    int kth() {
        List<Integer> b = new ArrayList<>(a);
        Collections.sort(b, Collections.reverseOrder());
        return b.get(k - 1);
    }
}
```
TC query `O(n log n)`. Fails many updates.

**Optimal**

```java
class KthDynamic {
    int k;
    PriorityQueue<Integer> top = new PriorityQueue<>(); // min of current k largest
    TreeMap<Integer, Integer> rest = new TreeMap<>();   // remaining multiset
    int restSize = 0;

    KthDynamic(int k, int[] nums) {
        this.k = k;
        for (int x : nums) add(x);
    }

    void inc(int x) { rest.merge(x, 1, Integer::sum); }
    void dec(int x) {
        int c = rest.get(x);
        if (c == 1) rest.remove(x); else rest.put(x, c - 1);
    }

    void add(int val) {
        top.offer(val);
        if (top.size() > k) {
            inc(top.poll());
            restSize++;
        }
    }

    void setK(int newK) {
        while (top.size() < newK && restSize > 0) {
            int x = rest.lastKey();
            dec(x); restSize--;
            top.offer(x);
        }
        while (top.size() > newK && !top.isEmpty()) {
            inc(top.poll()); restSize++;
        }
        k = newK; // if newK > n, peek is undefined — say so
    }

    int kth() { return top.peek(); }
}
```

Dry run nums = `[4,5,8,2]`, k = 3, then add 3, then setK(2):

| after | top min-heap (size k) | rest | kth |
| --- | --- | --- | ---: |
| init k=3 | 4,5,8 | 2 | 4 |
| +3 | 4,5,8 | 2,3 | 4 |
| setK(2) | 5,8 | 2,3,4 | 5 |

TC: add `O(log n)`, setK `O(|Δk| log n)`, kth `O(1)`. SC `O(n)`.

Follow-ups: remove; stream of queries; if k only grows, you can skip the shrink loop.

**If you get stuck in Live Code**
- Brute sort; then “size-k heap, rest in a TreeMap for k changes.”
- If TreeMap feels heavy, `PriorityQueue` max-heap for rest works if you are careful with duplicates (TreeMap is cleaner).

---

### 4a. Variation of Find All Anagrams — mapped R3 HM — AUTA Y — [LC 8362604](https://leetcode.com/discuss/post/8362604/amazon-sde-1-interview-experience-auta-a-5wmt/)

**What they actually asked**
AUTA APAC 2026 HM (15 Apr): **Variation of Find All Anagrams**, same hour as Combine Garlands. **Variation — do not stamp exact LC 438 as asked.** Overflow note on the ropes problem, not this one.

**Clarify out loud**
1. Window of `p.length()`, all start indices of anagrams of `p` in `s`? Extra constraint (unicode, case, min window instead of starts)?
2. Lowercase a–z only?
3. Empty `p` / `s` shorter than `p`?

**Trick / pattern in one sentence**
Fixed-size window; 26-letter counts match (or a `need==0` counter).

**Why this data structure**
- brute: sort every window
- optimal: `int[26]` sliding counts
- refuse: regex; HashMap of sorted strings if they want O(n)

**Brute**

```java
public List<Integer> anagramsBrute(String s, String p) {
    char[] need = p.toCharArray();
    Arrays.sort(need);
    String key = new String(need);
    List<Integer> ans = new ArrayList<>();
    int m = p.length();
    for (int i = 0; i + m <= s.length(); i++) {
        char[] w = s.substring(i, i + m).toCharArray();
        Arrays.sort(w);
        if (key.equals(new String(w))) ans.add(i);
    }
    return ans;
}
```
TC `O((n−m) m log m)`. SC `O(m)`.

**Optimal**

```java
public List<Integer> findAnagrams(String s, String p) {
    int[] need = new int[26], win = new int[26];
    for (int i = 0; i < p.length(); i++) need[p.charAt(i) - 'a']++;
    List<Integer> ans = new ArrayList<>();
    int m = p.length();
    for (int i = 0; i < s.length(); i++) {
        win[s.charAt(i) - 'a']++;
        if (i >= m) win[s.charAt(i - m) - 'a']--;
        if (i >= m - 1 && Arrays.equals(need, win)) ans.add(i - m + 1);
    }
    return ans;
}
```

Dry run s=`cbaebabacd` p=`abc`:

| i | window | match | starts |
| ---: | --- | --- | --- |
| 2 | cba | yes | 0 |
| 3 | bae | no | 0 |
| 8 | bac | yes | 0,6 |
| 9 | acd | no | 0,6 |

Answer `[0, 6]`.

TC `O(n)`. SC `O(1)`.

**If you get stuck in Live Code**
- Sort windows; then 26-count.
- If they add “at most k extras,” it becomes a variable window — ask before coding.

---

### 4b. Combine Garlands (ropes concept) — mapped R3 HM — AUTA Y — [LC 8362604](https://leetcode.com/discuss/post/8362604/amazon-sde-1-interview-experience-auta-a-5wmt/)

**What they actually asked**
Same HM: **Minimum Cost to Combine Garlands** (ropes concept); overflow → **long**. Connect Ropes/Sticks itself was their R2 (same IE) / GFG 2025 our-R2 analogue — same heap, different slot.

**Clarify out loud**
1. Cost of combining `a,b` is `a+b`, put `a+b` back?
2. Minimize **sum of those costs** (not the final length)?
3. n=1 → 0? Always combine **two** smallest?
4. They said overflow — use `long`.

**Trick / pattern in one sentence**
Always combine the two currently shortest — Huffman / min-heap; same as Connect Sticks.

**Why this data structure**
- brute: rescan min two each merge `O(n²)`, or all parenthesizations (factorial)
- optimal: `PriorityQueue<Long>`
- refuse: sort once and only merge adjacent (wrong unless they said a line of garlands, not a pile)

**Brute** — ArrayList, pull two mins each time.

```java
public long combineGarlandsBrute(int[] len) {
    List<Long> a = new ArrayList<>();
    for (int x : len) a.add((long) x);
    long cost = 0;
    while (a.size() > 1) {
        Collections.sort(a);
        long x = a.remove(0), y = a.remove(0);
        cost += x + y;
        a.add(x + y);
    }
    return cost;
}
```
TC `O(n² log n)`. SC `O(n)`.

**Optimal**

```java
public long combineGarlands(int[] len) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int x : len) pq.offer((long) x);
    long cost = 0;
    while (pq.size() > 1) {
        long a = pq.poll(), b = pq.poll();
        cost += a + b;
        pq.offer(a + b);
    }
    return cost;
}
```

Dry run `[4, 3, 2, 6]`:

| heap | poll | merge | total |
| --- | --- | ---: | ---: |
| 2,3,4,6 | 2+3 | 5 | 5 |
| 4,5,6 | 4+5 | 9 | 14 |
| 6,9 | 6+9 | 15 | **29** |

TC `O(n log n)`. SC `O(n)`.

**If you get stuck in Live Code**
- “Same as Connect Sticks, watch `int` overflow.”
- Sort + reinsert with ArrayList if the heap API blanks.

---

### 5. Count Number of Nice Subarrays — mapped BR — AUTA Y — [LC 6806195](https://leetcode.com/discuss/post/6806195/amazon-auta-interview-experience-sde-1-2-f90u/)

**What they actually asked**
AUTA Bengaluru BR (after R2 Rotate Image / Next Perm similar): **Count Number of Nice Subarrays** (LC linked). Named LPs in the same hour (feedback; critical issues; went beyond task).

**Clarify out loud**
1. Nice = **exactly** `k` odd numbers in a contiguous subarray?
2. Evens are free (do not break the window)?
3. Return count of subarrays, not the subarrays themselves?

**Trick / pattern in one sentence**
Odd=1 even=0; count subarrays with sum `k` = `atMost(k) − atMost(k−1)` (or prefix HashMap).

**Why this data structure**
- brute: all subarrays, count odds
- optimal: sliding window `atMost`, or `Map<prefixOdd, count>`
- refuse: DP `O(n²)`

**Brute**

```java
public int niceBrute(int[] a, int k) {
    int n = a.length, ans = 0;
    for (int i = 0; i < n; i++) {
        int odd = 0;
        for (int j = i; j < n; j++) {
            if ((a[j] & 1) == 1) odd++;
            if (odd == k) ans++;
        }
    }
    return ans;
}
```
TC `O(n²)`. SC `O(1)`.

**Optimal**

```java
public int numberOfSubarrays(int[] a, int k) {
    return atMostOdd(a, k) - atMostOdd(a, k - 1);
}

private int atMostOdd(int[] a, int k) {
    if (k < 0) return 0;
    int l = 0, odd = 0, ans = 0;
    for (int r = 0; r < a.length; r++) {
        if ((a[r] & 1) == 1) odd++;
        while (odd > k) {
            if ((a[l++] & 1) == 1) odd--;
        }
        ans += r - l + 1;
    }
    return ans;
}
```

Prefix-map alternative (say it if they dislike two passes):

```java
public int nicePrefix(int[] a, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);
    int odd = 0, ans = 0;
    for (int x : a) {
        odd += (x & 1);
        ans += freq.getOrDefault(odd - k, 0);
        freq.merge(odd, 1, Integer::sum);
    }
    return ans;
}
```

Dry run `[1,1,2,1,1]`, k=3 → **2** (`[1,1,2,1]` and `[1,2,1,1]`).

| r | a[r] | odd | atMost(3) window | atMost(2) window |
| ---: | ---: | ---: | --- | --- |
| 0 | 1 | 1 | [0..0] | [0..0] |
| 1 | 1 | 2 | [0..1] | [0..1] |
| 2 | 2 | 2 | [0..2] | [0..2] |
| 3 | 1 | 3 | [0..3] | [1..3] |
| 4 | 1 | 4 → shrink | [1..4] | [2..4] |

`atMost(3)−atMost(2) = 2`.

TC `O(n)`. SC `O(1)` window / `O(n)` prefix map.

**If you get stuck in Live Code**
- Brute i,j; then “exactly k = atMost k minus atMost k−1.”
- Prefix odds + HashMap if the two-window trick blanks.

---

### 6. Tree path A/B/C print — mapped AUTA BR — [LC 7406809](https://leetcode.com/discuss/post/7406809/amazon-sde-1-auta-interview-experience-s-k6t7/) — **UNNAMED details, no LC id**

**What they actually asked**
Opened body: BR **tree path src→target print A/B/C**; extra space → **LCA+DFS**. Research index: **A/B/C print (left/right/parent)**. Couple LP UNNAMED “formality.” Same loop as Distance K on R2.

**If unnamed:** stop guessing a LeetCode id. Do **not** stamp LC 2096 / 236 / 863.

**Clarify out loud**
1. Two nodes (`src`, `target`) or three (`A,B,C`)?
2. Print **node values**, or **direction letters** (left / right / parent)?
3. Is `A/B/C` their encoding for L / R / P? (ask — do not assume)
4. Extra space allowed on the follow-up (they said LCA+DFS)?
5. Parent pointers already on the node, or binary tree only?

**Trick / pattern in one sentence**
Path src→target = src **up to LCA** (parent steps) then **down** to target (left/right); extra space → store root→src and root→target lists, then splice at LCA.

**Why this data structure**
- brute: DFS from every node hoping to hit both — messy
- optimal: two root-to-node paths (`List<TreeNode>`) + first mismatch = LCA; or parent-as-DFS-arg (same spirit as Dist-K, still not a stored parent map unless they allow it on BR)
- refuse: inventing an LC slug; Dist-K collect-down is a **different** BR prompt

**Brute** — all-pairs: path from root to every node, then for src/target combine (still O(n) per query if you rebuild). Honest brute for one pair: DFS collect path, restart.

```java
public List<Integer> pathValuesBrute(TreeNode root, TreeNode src, TreeNode target) {
    List<TreeNode> toSrc = new ArrayList<>();
    List<TreeNode> toTgt = new ArrayList<>();
    dfsPath(root, src, new ArrayList<>(), toSrc);
    dfsPath(root, target, new ArrayList<>(), toTgt);
    return spliceViaLca(toSrc, toTgt);
}

private boolean dfsPath(TreeNode node, TreeNode goal,
                        List<TreeNode> cur, List<TreeNode> out) {
    if (node == null) return false;
    cur.add(node);
    if (node == goal) {
        out.addAll(cur);
        return true;
    }
    if (dfsPath(node.left, goal, cur, out) || dfsPath(node.right, goal, cur, out)) return true;
    cur.remove(cur.size() - 1);
    return false;
}
```
TC `O(n)` for one pair. SC `O(n)`.

**Optimal — extra space: LCA + lists (what they offered as follow-up)**

```java
public List<Integer> pathSrcToTarget(TreeNode root, TreeNode src, TreeNode target) {
    List<TreeNode> toSrc = new ArrayList<>();
    List<TreeNode> toTgt = new ArrayList<>();
    dfsPath(root, src, new ArrayList<>(), toSrc);
    dfsPath(root, target, new ArrayList<>(), toTgt);
    return spliceViaLca(toSrc, toTgt);
}

private List<Integer> spliceViaLca(List<TreeNode> toSrc, List<TreeNode> toTgt) {
    int i = 0;
    int lim = Math.min(toSrc.size(), toTgt.size());
    while (i < lim && toSrc.get(i) == toTgt.get(i)) i++;
    int lcaIdx = i - 1;
    List<Integer> ans = new ArrayList<>();
    for (int j = toSrc.size() - 1; j >= lcaIdx; j--) ans.add(toSrc.get(j).val);
    for (int j = lcaIdx + 1; j < toTgt.size(); j++) ans.add(toTgt.get(j).val);
    return ans;
}

/** Direction string if they want L/R/P (ask whether A/B/C maps to these). */
public String pathDirections(TreeNode root, TreeNode src, TreeNode target) {
    List<TreeNode> toSrc = new ArrayList<>();
    List<TreeNode> toTgt = new ArrayList<>();
    dfsPath(root, src, new ArrayList<>(), toSrc);
    dfsPath(root, target, new ArrayList<>(), toTgt);
    int i = 0;
    int lim = Math.min(toSrc.size(), toTgt.size());
    while (i < lim && toSrc.get(i) == toTgt.get(i)) i++;
    int lcaIdx = i - 1;
    StringBuilder sb = new StringBuilder();
    for (int j = toSrc.size() - 1; j > lcaIdx; j--) sb.append('P'); // parent / up
    for (int j = lcaIdx; j < toTgt.size() - 1; j++) {
        TreeNode cur = toTgt.get(j), nxt = toTgt.get(j + 1);
        sb.append(cur.left == nxt ? 'L' : 'R');
    }
    return sb.toString();
}
```

Dry run — same tree as Dist-K. src=6 target=4. Root-path 6: `3-5-6`. Root-path 4: `3-5-2-4`. LCA=5.

| step | nodes | letters |
| --- | --- | --- |
| up from 6 to 5 | 6 → 5 | P |
| down 5 → 2 → 4 | 5,2,4 | R, L |

Value path: `6, 5, 2, 4`. Direction: `PRL` (if P=parent, R=right, L=left). If they named A/B/C instead of L/R/P, substitute after they define the alphabet.

TC `O(n)`. SC `O(n)` lists (the extra space they allowed).

Follow-ups: no extra space (threaded / Dist-K-style return-distance is harder for a **print path** — say LCA lists first); three nodes A,B,C = two paths or the unique connecting subtree.

**If you get stuck in Live Code**
- Collect root→src and root→target, walk until they diverge — that is the LCA.
- If they only want values, skip the letter encoding.

---

### 7a. Top-K Frequent Elements — mapped R1 — pattern reuse for R3 heap — AUTA Y — [LC 7406809](https://leetcode.com/discuss/post/7406809/amazon-sde-1-auta-interview-experience-s-k6t7/)

**What they actually asked**
AUTA Nov 2025 **R1** (with subsets). Still the heap you want on a later live if they say “top k / most frequent / stream k.” Sachin LinkedIn R1 Q2 “m most frequent” is the same pattern (no LC id on that Q2).

**Clarify out loud**
1. Ties: any k, or deterministic order?
2. Elements or `(value, count)` pairs? Stream vs static array?

**Trick / pattern in one sentence**
Count with HashMap, then a **size-k min-heap** of frequencies — do not full-sort unless n is tiny.

**Why this data structure**
- brute: sort all uniques by count `O(u log u)`
- optimal: HashMap + min-heap of size k (or bucket sort by count)
- refuse: max-heap of everything when k ≪ u

**Brute**

```java
public int[] topKBrute(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    List<int[]> pairs = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        pairs.add(new int[]{e.getKey(), e.getValue()});
    }
    pairs.sort((a, b) -> Integer.compare(b[1], a[1]));
    int[] ans = new int[k];
    for (int i = 0; i < k; i++) ans[i] = pairs.get(i)[0];
    return ans;
}
```
TC `O(n + u log u)`. SC `O(u)`.

**Optimal**

```java
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        pq.offer(new int[]{e.getKey(), e.getValue()});
        if (pq.size() > k) pq.poll();
    }
    int[] ans = new int[k];
    for (int i = k - 1; i >= 0; i--) ans[i] = pq.poll()[0];
    return ans;
}
```

Dry run nums=`[1,1,1,2,2,3]`, k=2:

| unique | freq | heap after offer (size≤2) |
| ---: | ---: | --- |
| 1 | 3 | (1,3) |
| 2 | 2 | (2,2),(1,3) |
| 3 | 1 | offer (3,1) → poll (3,1) → (2,2),(1,3) |

Answer `{1, 2}` (order by popping min-heap).

TC `O(n + u log k)`. SC `O(u)`.

**If you get stuck in Live Code**
- Sort uniques by count; then “heap of size k.”
- Bucket `List<Integer>[n+1]` if they want O(n) after the count.

---

### 7b. Merge k sorted linked lists — mapped R2 — pattern reuse for R3 heap — AUTA Y — [LC 7563011](https://leetcode.com/discuss/post/7563011/amazon-sde-1-interview-experience-by-ano-duqw/)

**What they actually asked**
AUTA Bengaluru R2 **1 Aug 2025**: **Merge k sorted linked lists**. Reprint family: Bhavya Hyd R1 Merge K; LC 7623949 also had merge 2/k in another slot. Heap is the R3-relevant skill.

**Clarify out loud**
1. `k` lists, each already sorted ascending? Empty lists / `k=0`?
2. Mutate vs new list? Singly `ListNode`?

**Trick / pattern in one sentence**
Always take the current smallest head among k lists — **min-heap of list heads**, `log k` per node.

**Why this data structure**
- brute: merge lists one-by-one (two-pointer), no heap
- optimal: `PriorityQueue<ListNode>` by `val`
- refuse: dump all values into an array and sort (they may accept as first code; say you are throwing away “already sorted”)

**Brute**

```java
public ListNode mergeKListsBrute(ListNode[] lists) {
    ListNode merged = null;
    for (ListNode list : lists) merged = mergeTwo(merged, list);
    return merged;
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}
```
TC `O(k n)` total nodes n (costs grow 2n+3n+…). SC `O(1)` extra.

**Optimal**

```java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> minHeap =
            new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
    for (ListNode head : lists) {
        if (head != null) minHeap.add(head);
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) minHeap.add(node.next);
    }
    return dummy.next;
}
```

Dry run `[1→4→5]`, `[1→3→4]`, `[2→6]`:

| heap heads | poll | emit |
| --- | ---: | --- |
| 1,1,2 | 1 (L0) | 1 |
| 4,1,2 | 1 (L1) | 1→1 |
| 4,3,2 | 2 | 1→1→2 |
| 4,3,6 | 3 | …→3 |
| 4,4,6 | 4 | …→4 |
| 5,4,6 | 4 | …→4 |
| 5,6 | 5 | …→5 |
| 6 | 6 | 1→1→2→3→4→4→5→6 |

TC `O(n log k)`. SC `O(k)`.

Follow-ups: divide-and-conquer merge (also `O(n log k)`); k sorted **arrays**; iterator of k streams.

**If you get stuck in Live Code**
- Merge two at a time.
- If heap comparator NPEs, skip null heads when offering.

---

### 7c. Maximum Sum Linked List from two sorted lists with common nodes — mapped BR / R4 analogue — AUTA N — [LC 6881058](https://leetcode.com/discuss/post/6881058/amazon-sde-1-interview-experience-bar-ra-ayfb/)

**What they actually asked**
SDE-1 Bangalore **Bar Raiser** (post is BR-only; earlier lives **I could not verify**): construct a **Maximum Sum Linked List** out of two **sorted** linked lists having some **common nodes**. Do **not** stamp LC 962. LC 6369243 mentioned a similar family without this title — leave that unnamed.

**Clarify out loud**
1. Both lists already sorted ascending? Common = equal `val` (switch points)?
2. Build a new list vs relink existing nodes?
3. A common value appears once in the answer? Empty list / no commons?
4. Values fit in `int` or use `long` for segment sums?

**Trick / pattern in one sentence**
Walk both lists like merge. Between two common nodes, **keep the heavier segment**; add the common node once; after the last common, keep the heavier tail.

**Why this data structure**
- brute: generate every switch combination (exponential)
- optimal: two pointers, `O(n+m)` — greedy is correct because lists are sorted so the next common is the only legal switch
- refuse: convert to arrays and forget the common-node rule (you would double-count 3 / 90 / 240)

**Brute (copy values; fine on Live Code)**

```java
private ListNode appendHeavier(ListNode tail, List<Integer> a, List<Integer> b) {
    int sa = 0, sb = 0;
    for (int x : a) sa += x;
    for (int x : b) sb += x;
    for (int x : (sa >= sb ? a : b)) {
        tail.next = new ListNode(x);
        tail = tail.next;
    }
    return tail;
}

public ListNode maxSumList(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    List<Integer> segA = new ArrayList<>(), segB = new ArrayList<>();
    ListNode p = a, q = b;
    while (p != null && q != null) {
        if (p.val < q.val) {
            segA.add(p.val);
            p = p.next;
        } else if (q.val < p.val) {
            segB.add(q.val);
            q = q.next;
        } else {
            tail = appendHeavier(tail, segA, segB);
            tail.next = new ListNode(p.val);
            tail = tail.next;
            segA.clear();
            segB.clear();
            p = p.next;
            q = q.next;
        }
    }
    while (p != null) { segA.add(p.val); p = p.next; }
    while (q != null) { segB.add(q.val); q = q.next; }
    appendHeavier(tail, segA, segB);
    return dummy.next;
}
```

Dry run `1→3→30→90→120→240→511` vs `0→3→12→32→90→125→240→250`:

| commons | L1 segment | L2 segment | keep |
| --- | --- | --- | --- |
| →3 | 1 | 0 | 1 then 3 |
| →90 | 30 | 12+32=44 | 12,32 then 90 |
| →240 | 120 | 125 | 125 then 240 |
| tail | 511 | 250 | 511 |

Answer `1→3→12→32→90→125→240→511`.

TC `O(n+m)`. SC `O(n+m)` for the new list (segments are extra; can relink in `O(1)` extra as a follow-up).

**If you get stuck in Live Code**
- “Same as merge, but at equals I pick the fatter side since last switch.”
- Do not invent LC 962 Maximum Width Ramp.

---

## B. OA-as-R1 / pattern reuse for a third live

Label: **their R3 = our R2 analogue** on these IEs. Still the DP / BFS / parse you may see on a later hour. Not a forecast for Job 10454435.

---

### 8. Grid: count paths avoiding -1 traps, then max reward — mapped **our R2** after FLAG remap — AUTA Y — [LC 6800853](https://leetcode.com/discuss/post/6800853/amazon-interview-experience-sde1-by-anon-vdbd/)

**What they actually asked**
AUTA. **OA-as-R1:** candidate R3 → **our R2**. n×n grid, cells **traps -1 / 0**, moves **right/down**, count paths; **follow-up max reward**.

**Clarify out loud**
1. Start `(0,0)` to `(n-1,n-1)`, only right and down?
2. `-1` blocked? Start/end trap → 0 paths?
3. Follow-up: cells hold rewards; maximize sum, still skip `-1`? Unreachable → 0 or `-1`? Mod?

**Trick / pattern in one sentence**
DAG of only right/down → **2D DP**: paths add from up+left; max reward takes `max` of up/left plus cell.

**Why this data structure**
- brute: DFS all paths
- optimal: `dp[r][c]` (or 1D rolling)
- refuse: Dijkstra (no left/up; count is not shortest-path); 4-dir BFS unless they add moves

**Brute**

```java
public int countPathsBrute(int[][] grid) {
    return dfs(grid, 0, 0);
}

private int dfs(int[][] grid, int r, int c) {
    int n = grid.length;
    if (r >= n || c >= n || grid[r][c] == -1) return 0;
    if (r == n - 1 && c == n - 1) return 1;
    return dfs(grid, r + 1, c) + dfs(grid, r, c + 1);
}
```
TC exponential. SC `O(n)` recursion.

**Optimal — count paths**

```java
public int countPaths(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == -1 || grid[n - 1][n - 1] == -1) return 0;
    int[][] dp = new int[n][n];
    dp[0][0] = 1;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == -1) { dp[r][c] = 0; continue; }
            if (r == 0 && c == 0) continue;
            int fromUp = r > 0 ? dp[r - 1][c] : 0;
            int fromLeft = c > 0 ? dp[r][c - 1] : 0;
            dp[r][c] = fromUp + fromLeft;
        }
    }
    return dp[n - 1][n - 1];
}
```

**Follow-up — max reward** (`-1` still blocked). Confirm unreachable policy.

```java
public int maxReward(int[][] grid) {
    int n = grid.length;
    int[][] dp = new int[n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE / 4);
    if (grid[0][0] == -1) return 0;
    dp[0][0] = grid[0][0];
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == -1) continue;
            if (r > 0 && dp[r - 1][c] > Integer.MIN_VALUE / 8) {
                dp[r][c] = Math.max(dp[r][c], dp[r - 1][c] + grid[r][c]);
            }
            if (c > 0 && dp[r][c - 1] > Integer.MIN_VALUE / 8) {
                dp[r][c] = Math.max(dp[r][c], dp[r][c - 1] + grid[r][c]);
            }
        }
    }
    return Math.max(0, dp[n - 1][n - 1]);
}
```

Dry run count:

```
0  0 -1
0 -1  0
0  0  0
```

| cell | dp count |
| --- | ---: |
| (0,0) | 1 |
| (0,1) | 1 |
| (0,2) | 0 trap |
| (1,0) | 1 |
| (1,1) | 0 trap |
| (2,0) | 1 |
| (2,1) | 1 |
| (2,2) | 1 |

One path: down, down, right, right.

TC `O(n²)`. SC `O(n²)` (`O(n)` rolling).

**If you get stuck in Live Code**
- Recursion + `memo[r][c]`.
- For max, copy the count loops and switch `+` to `max`.

---

### 9. Min ops reduce n to 0 subtracting a digit of n — same IE 6800853 — **our R2 analogue** (OA-as-R1)

**What they actually asked**
Same LC 6800853 their R3 / **our R2**: **minimum operations**: subtract **a digit of the current n** until 0. Sample **27 → 5**.

**Clarify out loud**
1. Each op: pick a digit that **appears in the current decimal representation**, subtract it?
2. Skip digit `0` (no-op)? n up to? (`n ≤ 1e6` DP is fine; `long` n is not `dp[n]`)
3. Return ops count only?

**Trick / pattern in one sentence**
From n you can go to `n−d` for each non-zero digit `d` of n; min ops is shortest path on `0..n` (DP). Greedy subtract max digit matches the 27→5 sample — verify with DP if they doubt it.

**Why this data structure**
- brute: BFS from n to 0
- optimal for small n: `int[] dp`; greedy max-digit if they accept after a check
- refuse: subtracting n’s **original** digits only (digits change after each subtract)

**Brute — BFS**

```java
public int minOpsBfs(int n) {
    if (n == 0) return 0;
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] seen = new boolean[n + 1];
    queue.add(n);
    seen[n] = true;
    int ops = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int cur = queue.poll();
            if (cur == 0) return ops;
            int t = cur;
            while (t > 0) {
                int d = t % 10;
                t /= 10;
                if (d == 0) continue;
                int next = cur - d;
                if (next >= 0 && !seen[next]) {
                    seen[next] = true;
                    queue.add(next);
                }
            }
        }
        ops++;
    }
    return -1;
}
```
TC `O(n log n)`-ish visits. SC `O(n)`.

**Optimal — DP (safe) and greedy (sample)**

```java
public int minOpsDp(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE / 4);
    dp[0] = 0;
    for (int x = 1; x <= n; x++) {
        int t = x;
        while (t > 0) {
            int d = t % 10;
            t /= 10;
            if (d > 0) dp[x] = Math.min(dp[x], dp[x - d] + 1);
        }
    }
    return dp[n];
}

public int minOpsGreedyMaxDigit(int n) {
    int ops = 0;
    while (n > 0) {
        int maxDigit = 0, t = n;
        while (t > 0) {
            maxDigit = Math.max(maxDigit, t % 10);
            t /= 10;
        }
        n -= maxDigit;
        ops++;
    }
    return ops;
}
```

Dry run **27 → 5** (greedy max digit):

| n | max digit | n after | ops |
| ---: | ---: | ---: | ---: |
| 27 | 7 | 20 | 1 |
| 20 | 2 | 18 | 2 |
| 18 | 8 | 10 | 3 |
| 10 | 1 | 9 | 4 |
| 9 | 9 | 0 | **5** |

TC DP `O(n log n)`. SC `O(n)`. Greedy `O(ops · log n)` time, `O(1)` space.

**If you get stuck in Live Code**
- Simulate greedy on 27, then write the while-loop.
- If n is 10^12, do **not** allocate `dp[n]`; stay greedy or digit DP — say you cannot BFS.

---

### 10. Encoded string frequency `1226#24#(2)` — mapped **our R1** analogue (OA-as-R1) — AUTA Y — [LC 6800853](https://leetcode.com/discuss/post/6800853/amazon-interview-experience-sde1-by-anon-vdbd/)

**What they actually asked**
Same IE, **candidate R2 → our R1**: encoded string `1226#24#(2)` → **freq of letters**. Grammar was **not fully specified** — confirm before coding. Pattern reuse if a later hour is “parse then count.”

**Clarify out loud**
1. `1`–`9` → a–i; `10#`–`26#` → j–z?
2. `(k)` = frequency of the **previous token**?
3. Output map letter → count? Unknown letters?

**Trick / pattern in one sentence**
This is a **parse**, then HashMap; do not start with HashMap.

**Why this data structure**
- brute: hand-parse only the sample
- optimal: index `i`, parse number, optional `#`, optional `(freq)`
- refuse: inventing an LC id; regex guesses

**Brute** — walk the given example only (fails other encodings).

```java
public Map<Character, Integer> freqExampleOnly() {
    Map<Character, Integer> m = new HashMap<>();
    m.put('a', 1); m.put('b', 1); m.put('z', 1); m.put('x', 2); // 1226#24#(2)
    return m;
}
```

**Optimal** — grammar **assumed from the example (state it):** `d` = a–i; `dd#` = j–z; `(k)` multiplies the token just parsed.

```java
public Map<Character, Integer> freqEncoded(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int i = 0, n = s.length();
    while (i < n) {
        int code, j;
        if (i + 2 < n && Character.isDigit(s.charAt(i))
                && Character.isDigit(s.charAt(i + 1)) && s.charAt(i + 2) == '#') {
            code = Integer.parseInt(s.substring(i, i + 2));
            j = i + 3;
        } else {
            code = s.charAt(i) - '0';
            j = i + 1;
        }
        int times = 1;
        if (j < n && s.charAt(j) == '(') {
            int k = j + 1;
            while (k < n && s.charAt(k) != ')') k++;
            times = Integer.parseInt(s.substring(j + 1, k));
            j = k + 1;
        }
        map.merge((char) ('a' + code - 1), times, Integer::sum);
        i = j;
    }
    return map;
}
```

Dry run `1226#24#(2)`:

| token | letter | count |
| --- | --- | ---: |
| 1 | a | 1 |
| 2 | b | 1 |
| 26# | z | 1 |
| 24#(2) | x | 2 |

TC `O(n)`. SC `O(1)` alphabet.

**If you get stuck in Live Code**
- Tokenize the example on the whiteboard first, then write the index loop.
- Prefer two-digit+`#` **before** a single digit (greedy longest).

---

### 11a. Rotten Oranges variant — igreaper **their R3 = our R2 analogue** — also AUTA 7406809 R2 — [igreaper](https://igreaper.medium.com/amazon-sde-1-interview-experience-a69578a4f699) · [LC 7406809](https://leetcode.com/discuss/post/7406809/amazon-sde-1-auta-interview-experience-s-k6t7/)

**What they actually asked**
igreaper: candidate R3 (with Max Rectangle) → **our R2**. GFG Off-Campus 2025 same remap. LC 7406809 AUTA: **Rotten oranges variation** on a true two-live R2 (not OA-as-R1). Ask what the variation is (8-dir, no mutate, leftover count) — do not invent a second problem.

**Clarify out loud**
1. `0` empty, `1` fresh, `2` rotten?
2. 4-dir or 8-dir?
3. One minute = all currently rotten infect neighbors simultaneously?
4. Return minutes, or `-1` if a fresh orange never rots? Mutate the grid? No fresh → `0`?

**Trick / pattern in one sentence**
All initially rotten oranges are **one BFS wave**; minutes = BFS level; leftover fresh → `-1`.

**Why this data structure**
- brute: while something changed, scan whole grid
- optimal: **queue** of rotten cells (multi-source BFS)
- refuse: DFS from one rotten (wrong simultaneity); Dijkstra (unweighted)

**Brute**

```java
public int orangesRottingBrute(int[][] grid) {
    int minutes = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (true) {
        List<int[]> willRot = new ArrayList<>();
        int fresh = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] != 1) continue;
                fresh++;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < 0 || nc < 0 || nr >= grid.length || nc >= grid[0].length) continue;
                    if (grid[nr][nc] == 2) { willRot.add(new int[]{r, c}); break; }
                }
            }
        }
        if (willRot.isEmpty()) return fresh == 0 ? minutes : -1;
        for (int[] cell : willRot) grid[cell[0]][cell[1]] = 2;
        minutes++;
    }
}
```
TC `O(m²n²)` worst. SC `O(mn)`.

**Optimal**

```java
public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.add(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
        }
    }
    if (fresh == 0) return 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (grid[nr][nc] != 1) continue;
                grid[nr][nc] = 2;
                fresh--;
                queue.add(new int[]{nr, nc});
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}
```

Dry run:

```
2 1 1
1 1 0
0 1 1
```

| minute | queue (just infected / initial) | fresh left |
| ---: | --- | ---: |
| 0 | (0,0) | 6 |
| 1 | (0,1),(1,0) | 4 |
| 2 | (0,2),(1,1) | 2 |
| 3 | (1,2),(2,1) | 1 |
| 4 | (2,2) | 0 |

Answer **4**.

TC `O(mn)`. SC `O(mn)`.

**If you get stuck in Live Code**
- Scan-until-stable brute; then put initial `2`s in a queue.
- If minutes are off by one, only increment after a level that actually rotted something.

---

### 11b. Maximal Rectangle all 1s — igreaper **their R3 = our R2 analogue** — [igreaper](https://igreaper.medium.com/amazon-sde-1-interview-experience-a69578a4f699)

**What they actually asked**
Same igreaper hour as Rotten: **Maximum Rectangle Area with all 1’s**. Kafka / B+ Tree CS in that slot too (fundamentals fragment, not this card).

**Clarify out loud**
1. Largest **area** rectangle of 1s in a binary matrix? (histogram stack)
2. Or largest **square**? (different DP — ask)

**Trick / pattern in one sentence**
For each row, treat consecutive 1s as histogram heights; largest rectangle in histogram via monotonic stack.

**Why this data structure**
- brute: check all rectangles
- optimal: `O(mn)` heights + `O(n)` stack per row
- refuse: only maximal-square DP unless they said square

**Brute**

```java
public int maximalRectangleBrute(char[][] g) {
    int m = g.length, n = g[0].length, best = 0;
    for (int r1 = 0; r1 < m; r1++) {
        for (int r2 = r1; r2 < m; r2++) {
            for (int c1 = 0; c1 < n; c1++) {
                for (int c2 = c1; c2 < n; c2++) {
                    if (allOnes(g, r1, r2, c1, c2)) {
                        best = Math.max(best, (r2 - r1 + 1) * (c2 - c1 + 1));
                    }
                }
            }
        }
    }
    return best;
}

private boolean allOnes(char[][] g, int r1, int r2, int c1, int c2) {
    for (int i = r1; i <= r2; i++)
        for (int j = c1; j <= c2; j++)
            if (g[i][j] != '1') return false;
    return true;
}
```
TC `O(m²n² · mn)`. Fails.

**Optimal**

```java
public int maximalRectangle(char[][] g) {
    int m = g.length, n = g[0].length, best = 0;
    int[] h = new int[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) h[j] = g[i][j] == '1' ? h[j] + 1 : 0;
        best = Math.max(best, largestRectangle(h));
    }
    return best;
}

private int largestRectangle(int[] h) {
    int n = h.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        int cur = i == n ? 0 : h[i];
        while (!st.isEmpty() && cur < h[st.peek()]) {
            int height = h[st.pop()];
            int L = st.isEmpty() ? -1 : st.peek();
            best = Math.max(best, height * (i - L - 1));
        }
        st.push(i);
    }
    return best;
}
```

Dry run matrix:

```
1 1
1 1
```

| after row | heights | largest hist |
| ---: | --- | ---: |
| 0 | 1,1 | 2 |
| 1 | 2,2 | **4** |

TC `O(mn)`. SC `O(n)`.

**If you get stuck in Live Code**
- “Histogram per row, monotonic stack.”
- If stack blanks, compute largest rectangle with `min` scan `O(n²)` per row first.

---

### 12. Unique Paths II / obstacle grid DP — **Standard CS** companion to (8) — similar-not-exact [Swati](https://www.linkedin.com/posts/99swati_my-amazon-sde-1-interview-experience-verdict-activity-7408841159445319680-zeeT) · family [LC 7035289](https://leetcode.com/discuss/post/7035289/amazon-sde-1-offer-by-anonymous_user-3efp/) BR Unique Paths–like

**What they actually asked**
**Not stamped as exact Unique Paths II** on a 2026 AUTA later-slot. Swati: **similar to** Unique Paths (among others). LC 7035289 AUTA BR: **Unique Paths–like max points right/down only**. Card 8 is the IE-named trap/`-1` version. This card is the **1 = obstacle** textbook companion. Do not invent an LC id as “asked.”

**Clarify out loud**
1. `1` obstacle or `-1` trap? Right/down only?
2. Count paths or max score (7035289 BR)?
3. Start blocked → 0?

**Trick / pattern in one sentence**
Same DP as card 8; zero a cell if it is an obstacle, then `dp[j] += dp[j-1]` on a rolling row.

**Why this data structure**
- brute: DFS
- optimal: 1D `dp[n]`
- refuse: Dijkstra for unweighted count

**Brute** — same DFS as card 8 with `g[r][c]==1` blocked.

```java
public int uniquePathsBrute(int[][] g) {
    return dfs(g, 0, 0);
}

private int dfs(int[][] g, int r, int c) {
    int m = g.length, n = g[0].length;
    if (r >= m || c >= n || g[r][c] == 1) return 0;
    if (r == m - 1 && c == n - 1) return 1;
    return dfs(g, r + 1, c) + dfs(g, r, c + 1);
}
```
TC exponential.

**Optimal**

```java
public int uniquePathsWithObstacles(int[][] g) {
    int m = g.length, n = g[0].length;
    if (g[0][0] == 1) return 0;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}
```

Max-points follow-up (7035289 BR family): same loops, `dp[j] = grid[i][j] + max(fromUp, fromLeft)`, skip obstacles — same idea as card 8 `maxReward`.

Dry run:

```
0 0 0
0 1 0
0 0 0
```

| i,j | dp row |
| --- | --- |
| after r0 | 1,1,1 |
| after r1 | 1,0,1 |
| after r2 | 1,1,2 |

Answer **2**.

TC `O(mn)`. SC `O(n)`.

**If you get stuck in Live Code**
- 2D `dp[m][n]` first, then compress.
- If they say max points, switch `+` of two parents to `max`.

---

## C. High-evidence patterns for a third live

IE-asked when the bible has a URL; otherwise **Standard CS**. Still not a 10454435 forecast.

---

### 13. Course Schedule II / directed cycle — mapped later live / unlabeled — UTA N — [LC 6282609](https://leetcode.com/discuss/post/6282609/) **LC 210 linked on this post only** · reprint similar [LC 6425074](https://leetcode.com/discuss/post/6425074/amazon-sde-1-bangalore-by-anonymous_user-6w45/)

**What they actually asked**
Course Schedule II. 6282609 body Cloudflare this pass; SERP has LC **210** linked **on that post**. 6425074 R2: **similar to Course Schedule II (LC linked)**. GFG sde1-off-campus R2 also named Course Schedule.

**Do not attach this to LC 6369243** (delivery stations + parcels + classes + topo + max-sum switching two sorted LLs — **not** 962, **not** 210).

**Clarify out loud**
1. `prerequisites[i] = [a,b]` means **b before a**?
2. Any valid order or unique? Cycle → empty array?

**Trick / pattern in one sentence**
Kahn: indegree-0 queue, emit order, fail if `order.length < n`. DFS colors: gray back-edge = cycle; reverse postorder = topo. **Say both** and pick one to type.

**Why this data structure**
- brute: DFS all topological permutations `O(n!)`
- optimal: adj list + (queue indegree **or** 3-color DFS)
- refuse: copying this onto delivery-stations 6369243

**Brute** — backtrack permutations (do not type n! unless n ≤ 8). Sketch: try each unused course whose preds are done.

**Optimal A — Kahn (queue)**

```java
public int[] findOrderKahn(int n, int[][] pre) {
    List<Integer>[] g = new List[n];
    int[] indeg = new int[n];
    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
    for (int[] p : pre) {
        g[p[1]].add(p[0]); // b → a
        indeg[p[0]]++;
    }
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int[] ord = new int[n];
    int k = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        ord[k++] = u;
        for (int v : g[u]) if (--indeg[v] == 0) q.offer(v);
    }
    return k == n ? ord : new int[0];
}
```

**Optimal B — DFS colors (white/gray/black)**

```java
public int[] findOrderDfs(int n, int[][] pre) {
    List<Integer>[] g = new List[n];
    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
    for (int[] p : pre) g[p[1]].add(p[0]);
    int[] color = new int[n]; // 0 white, 1 gray, 2 black
    List<Integer> post = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (color[i] == 0 && !dfs(i, g, color, post)) return new int[0];
    }
    Collections.reverse(post); // reverse finish times
    int[] ord = new int[n];
    for (int i = 0; i < n; i++) ord[i] = post.get(i);
    return ord;
}

private boolean dfs(int u, List<Integer>[] g, int[] color, List<Integer> post) {
    color[u] = 1; // gray = on stack
    for (int v : g[u]) {
        if (color[v] == 1) return false;      // back edge → cycle
        if (color[v] == 0 && !dfs(v, g, color, post)) return false;
    }
    color[u] = 2;
    post.add(u);
    return true;
}
```

**Compare out loud**
- Kahn: “who has no remaining prereq?” — natural for Course Schedule; cycle ⇔ not all n emitted.
- DFS colors: cycle ⇔ visit a **gray** node; order is reverse postorder. Use if they ban a queue or ask “detect the cycle.”
- Same TC/SC. Do not mix: Kahn does not need colors; DFS does not need indegree.

Dry run n=4, pre `[1,0],[2,0],[3,1],[3,2]` (0 before 1 and 2; 1 and 2 before 3):

| Kahn queue | emit | indeg after |
| --- | ---: | --- |
| 0 | 0 | 1 and 2 drop to 0 |
| 1,2 | 1 then 2 | 3 drops |
| 3 | 3 | done |

One valid: `0,1,2,3`. DFS postorder example: 3,1,2,0 → reverse `0,2,1,3` (also valid).

TC `O(n+E)`. SC `O(n+E)`.

**If you get stuck in Live Code**
- Type Kahn first (fewer moving parts).
- If they say cycle detect only, DFS gray back-edge is enough (Course Schedule I).

---

### 14. Sliding Window Maximum (deque) — mapped R1 story wrap [GFG sde1-off-campus](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde1-off-campus/) · also their R3 on [1-year-experienced-2](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-1-year-experienced-2/)

**What they actually asked**
GFG sde1-off-campus: R1 **Sliding Window Maximum (story wrap)** — warehouse / delivery / “max in each window of k days” dressing. GFG 1-year-experienced-2: **Sliding window maximum** on Technical Interview 2 (their R3). Shiwangi UTA R4: medium Sliding Window **UNNAMED** (do not stamp this id).

**Clarify out loud**
1. Array `a`, window size `k`, return max of every window `a[i..i+k-1]`?
2. k=1? k=n? Empty?
3. Story wrap: confirm it is still “max in each contiguous window of k.”

**Trick / pattern in one sentence**
Monotonic **decreasing deque of indices**; front is the window max; drop indices `≤ i-k`.

**Why this data structure**
- brute: scan each window `O(nk)`
- optimal: `ArrayDeque` indices, values decreasing toward the back
- refuse: heap of window (lazy delete `O(n log n)` — mention, then deque); `Stack` class

**Brute**

```java
public int[] maxSlidingBrute(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {
        int m = a[i];
        for (int j = i + 1; j < i + k; j++) m = Math.max(m, a[j]);
        ans[i] = m;
    }
    return ans;
}
```
TC `O(nk)`. SC `O(1)` extra.

**Optimal**

```java
public int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>(); // indices, a[idx] decreasing
    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) ans[i - k + 1] = a[dq.peekFirst()];
    }
    return ans;
}
```

Dry run `a=[1,3,-1,-3,5,3,6,7]`, k=3:

| i | a[i] | deque idx (vals) | window max |
| ---: | ---: | --- | ---: |
| 0 | 1 | 0 (1) | — |
| 1 | 3 | 1 (3) | — |
| 2 | -1 | 1,2 (3,-1) | **3** |
| 3 | -3 | 1,2,3 (3,-1,-3) | **3** |
| 4 | 5 | 4 (5) | **5** |
| 5 | 3 | 4,5 (5,3) | **5** |
| 6 | 6 | 6 (6) | **6** |
| 7 | 7 | 7 (7) | **7** |

Answer `[3,3,5,5,6,7]`.

TC `O(n)`. SC `O(k)`.

**If you get stuck in Live Code**
- Brute scan; then “deque drops smaller tails, front is max.”
- If they want window **minimum**, reverse the `<=` to `>=`.

---

### 15. House Robber I → II (circular) — mapped R1 named + Sachin R2 **LC 213** — UTA N — [LC 8029194](https://leetcode.com/discuss/post/8029194/amazon-interview-sde-1-selected-by-anony-qatd/) · [Sachin](https://www.linkedin.com/posts/sachinchoudhary0_amazon-interview-experience-sde1-applied-activity-7465822262709886976-lgWi)

**What they actually asked**
LC 8029194 onsite Mar 2026 BLR **R1**: House Robber then House Robber II circular (**named**). Sachin ~May 2026 **R2 LC 213**. IE.in intern also named HR II (INTERN appendix — not this card’s loop).

**Clarify out loud**
1. Cannot rob adjacent; circular means first and last are adjacent?
2. Negative money? Empty / one house?

**Trick / pattern in one sentence**
Linear: `dp[i] = max(skip, take + dp[i-2])`; circular = max(rob `[0..n-2]`, rob `[1..n-1]`).

**Why this data structure**
- brute: 2^n subsets
- optimal: O(n) two variables
- refuse: heap

**Brute**

```java
public int robBrute(int[] a, int i, int last) {
    if (i > last) return 0;
    return Math.max(robBrute(a, i + 1, last), a[i] + robBrute(a, i + 2, last));
}
```
TC `O(2^n)`. SC `O(n)` stack.

**Optimal**

```java
public int robLinear(int[] a, int l, int r) { // inclusive
    int prev2 = 0, prev1 = 0;
    for (int i = l; i <= r; i++) {
        int cur = Math.max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

public int rob(int[] a) { // House Robber I
    return robLinear(a, 0, a.length - 1);
}

public int rob2(int[] a) { // House Robber II
    int n = a.length;
    if (n == 1) return a[0];
    return Math.max(robLinear(a, 0, n - 2), robLinear(a, 1, n - 1));
}
```

Dry run `[2,3,2]` circular:

| range | linear rob |
| --- | ---: |
| [2,3] houses 0..1 | 3 |
| [3,2] houses 1..2 | 3 |

Answer **3** (cannot take both 2s).

TC `O(n)`. SC `O(1)`.

**If you get stuck in Live Code**
- Linear first, then “drop first or drop last.”
- n=1 is the only special case you must not split.

---

### 16a. Merge Intervals — mapped R1 — UTA N — [GFG fresher](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde1-fresher-off-campus/)

**What they actually asked**
GFG SDE1 fresher R1: **Merge Intervals** (with Burning Tree). Interval family with platforms / meeting rooms (next card).

**Clarify out loud**
1. `[start,end]` inclusive? Touching merge (`[1,2][2,3]`)?
2. Unsorted input?

**Trick / pattern in one sentence**
Sort by start; if `cur.start <= last.end` extend `end`.

**Why this data structure**
- brute: pairwise merge until stable `O(n²)`
- optimal: sort then linear scan
- refuse: heap unless they also want “min rooms” (that heap is card 16b)

**Brute**

```java
public int[][] mergeBrute(int[][] iv) {
    List<int[]> a = new ArrayList<>(Arrays.asList(iv));
    boolean merged = true;
    while (merged) {
        merged = false;
        for (int i = 0; i < a.size() && !merged; i++) {
            for (int j = i + 1; j < a.size(); j++) {
                if (overlap(a.get(i), a.get(j))) {
                    int[] x = a.get(i), y = a.get(j);
                    a.set(i, new int[]{Math.min(x[0], y[0]), Math.max(x[1], y[1])});
                    a.remove(j);
                    merged = true;
                    break;
                }
            }
        }
    }
    return a.toArray(new int[0][]);
}

private boolean overlap(int[] x, int[] y) {
    return x[0] <= y[1] && y[0] <= x[1];
}
```
TC `O(n²)` typical. SC `O(n)`.

**Optimal**

```java
public int[][] merge(int[][] iv) {
    Arrays.sort(iv, Comparator.comparingInt(a -> a[0]));
    List<int[]> out = new ArrayList<>();
    int[] cur = iv[0];
    for (int i = 1; i < iv.length; i++) {
        if (iv[i][0] <= cur[1]) cur[1] = Math.max(cur[1], iv[i][1]);
        else { out.add(cur); cur = iv[i]; }
    }
    out.add(cur);
    return out.toArray(new int[0][]);
}
```

Dry run `[1,3][2,6][8,10]`:

| i | cur | action |
| ---: | --- | --- |
| 1 | [1,3] | overlap 2 → [1,6] |
| 2 | [1,6] | 8>6 emit [1,6], cur=[8,10] |

Answer `[1,6],[8,10]`.

TC `O(n log n)`. SC `O(n)`.

**If you get stuck in Live Code**
- Sort by start, then one linear merge.

---

### 16b. Minimum Platforms / Meeting Rooms II — **IE:** [Prabhash](https://www.linkedin.com/posts/prabhash-jena_amazoninterview-sde1-interviewexperience-activity-7354481801756622848-C4v6) R1 · GFG [off-campus-10](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-10/) their R3 · **mentor:** Ravi extra-DSA same sweep (`amazon-sde1-interview-prep.md`) — GFG classic framing

**What they actually asked**
Prabhash LinkedIn Apr 2025 **R1 (IE)**: **min platforms** (with next perm / next greater same digits). GFG off-campus-10 **their R3**: min platforms (year-out, not UTA). **Mentor (not evidence):** Ravi listed Meeting Rooms I/II and Min Platforms as the same sweep. Platforms is a GFG classic; Meeting Rooms II is the interval-heap twin. Do not invent a 2026 AUTA URL.

**Clarify out loud**
1. Arrival[] / departure[] of trains; how many platforms so no two overlap?
2. Inclusive endpoints (depart 10:00, arrive 10:00 → extra platform)? Same as “min meeting rooms”?

**Trick / pattern in one sentence**
Sort arrivals and departures; two-pointer sweep; `cur` trains at the station. Heap of end times is the same number.

**Why this data structure**
- brute: for each train count overlaps `O(n²)`
- optimal: sort + two pointers, or min-heap of end times (Meeting Rooms II)
- refuse: merge-intervals (that answers “combined range,” not concurrency)

**Brute**

```java
public int platformsBrute(int[] arr, int[] dep) {
    int n = arr.length, best = 0;
    for (int i = 0; i < n; i++) {
        int cur = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] <= arr[i] && dep[j] >= arr[i]) cur++;
        }
        best = Math.max(best, cur);
    }
    return best;
}
```
TC `O(n²)`. SC `O(1)`.

**Optimal — two pointers (platforms)**

```java
public int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, cur = 0, best = 0;
    while (i < arr.length) {
        if (arr[i] <= dep[j]) { cur++; best = Math.max(best, cur); i++; }
        else { cur--; j++; }
    }
    return best;
}
```

**Optimal — min-heap (Meeting Rooms II / mentor twin)**

```java
public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>(); // end times
    for (int[] iv : intervals) {
        if (!ends.isEmpty() && ends.peek() < iv[0]) ends.poll(); // confirm < vs <=
        ends.offer(iv[1]);
    }
    return ends.size();
}
```

Dry run arr `900,940,950,1100` dep `910,1200,1120,1130` → **3**.

| event | cur |
| --- | ---: |
| 900 arr | 1 |
| 910 dep | 0 |
| 940 arr | 1 |
| 950 arr | 2 |
| 1100 arr | 3 |
| 1120 dep | 2 |
| … | … |

TC `O(n log n)`. SC `O(1)` extra besides sort / `O(n)` heap.

**If you get stuck in Live Code**
- “Line sweep: sort starts and ends.”
- Heap of departures if they hand you `[start,end]` pairs instead of two arrays.

---

### 17. Celebrity Problem — **Standard CS / older Amazon classic** — GFG [off-campus-10](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-10/) (year-out remainder, not 2026 AUTA)

**What they actually asked**
GFG off-campus-10 R1: **Celebrity approach** (with Diameter, Islands). Older remainder table also lists Celebrity. **No 2026 first-hand AUTA/Hyderabad BR URL in the research bible.** Do not invent one. LC 277 is premium **Standard CS** for the `knows(i,j)` API — not an asked-id stamp for Job 10454435.

**Clarify out loud**
1. Celebrity = known by everyone, knows no one? `knows(i,j)` API vs matrix?
2. Exactly one or “none → -1”? n=1?

**Trick / pattern in one sentence**
Two pointers (or a stack) **eliminate**: if A knows B, A is not celebrity; else B is not; verify the candidate in O(n).

**Why this data structure**
- brute: for each person, n knows-queries both ways `O(n²)`
- optimal: one elimination pass `O(n)` then verify `O(n)` — still `O(n)` queries
- refuse: building a graph and SCC unless they changed the definition

**Brute**

```java
public int celebrityBrute(int n) {
    for (int cand = 0; cand < n; cand++) {
        boolean ok = true;
        for (int i = 0; i < n; i++) {
            if (i == cand) continue;
            if (knows(cand, i) || !knows(i, cand)) { ok = false; break; }
        }
        if (ok) return cand;
    }
    return -1;
}
```
TC `O(n²)` `knows` calls.

**Optimal**

```java
public int findCelebrity(int n) {
    int cand = 0;
    for (int i = 1; i < n; i++) {
        if (knows(cand, i)) cand = i; // cand knows i → cand out
    }
    for (int i = 0; i < n; i++) {
        if (i == cand) continue;
        if (knows(cand, i) || !knows(i, cand)) return -1;
    }
    return cand;
}

// given by interviewer — do not reinvent
boolean knows(int a, int b) { return false; }
```

Dry run n=3. Matrix (`1` = row knows col):

```
0 1 1
0 0 1
0 0 0
```

| i | cand | knows(cand,i)? | new cand |
| ---: | ---: | --- | ---: |
| 1 | 0 | yes | 1 |
| 2 | 1 | yes | 2 |

Verify 2: does not know 0 or 1; both know 2 → **2**.

TC `O(n)` queries. SC `O(1)`.

**If you get stuck in Live Code**
- Brute check each person; then “eliminate: knows() kills the knower.”
- Stack version: push 0..n-1, pop two, push the survivor — same idea.

---

### 18. Min Stack — older GFG remainder **IE** [sde-1-27](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-27/) R1 “minStack one stack” · **Standard CS** LC 155 family

**What they actually asked**
sde-1-27 R1: **minStack one stack** (with group anagrams). Year-out, not UTA-default. Recurring design-adjacent DS for a later live. Two-stack is the Live-Code default; one-stack encoding is what that IE named.

**Clarify out loud**
1. `push` / `pop` / `top` / `getMin` all O(1)?
2. One stack only, or aux stack OK?
3. Duplicates of the min? Empty pop?

**Trick / pattern in one sentence**
Aux stack of mins (clear), or encode `2*x - min` on the same stack when a new min arrives.

**Why this data structure**
- brute: `ArrayList` + scan for min each `getMin`
- optimal: two `ArrayDeque`s, or one stack + encoded min
- refuse: `java.util.Stack` (legacy); sorting

**Brute**

```java
class MinStackBrute {
    List<Integer> a = new ArrayList<>();
    void push(int x) { a.add(x); }
    void pop() { a.remove(a.size() - 1); }
    int top() { return a.get(a.size() - 1); }
    int getMin() {
        int m = a.get(0);
        for (int x : a) m = Math.min(m, x);
        return m;
    }
}
```
TC `getMin` `O(n)`. Fails if they want O(1).

**Optimal — two stacks (say this first unless they ban the aux)**

```java
class MinStackTwo {
    Deque<Integer> st = new ArrayDeque<>();
    Deque<Integer> mins = new ArrayDeque<>();
    void push(int x) {
        st.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    void pop() { st.pop(); mins.pop(); }
    int top() { return st.peek(); }
    int getMin() { return mins.peek(); }
}
```

**Optimal — one stack (sde-1-27 constraint)**

```java
class MinStackOne {
    Deque<Long> st = new ArrayDeque<>();
    long min;
    void push(int x) {
        if (st.isEmpty()) { st.push((long) x); min = x; }
        else if (x >= min) st.push((long) x);
        else { st.push(2L * x - min); min = x; }
    }
    void pop() {
        long t = st.pop();
        if (t < min) min = 2 * min - t;
    }
    int top() {
        long t = st.peek();
        return (int) (t < min ? min : t);
    }
    int getMin() { return (int) min; }
}
```

Dry run push -2, 0, -3; getMin; pop; getMin:

| op | st (two-stack mins) | getMin |
| --- | --- | ---: |
| push -2 | st[-2] mins[-2] | -2 |
| push 0 | st[-2,0] mins[-2,-2] | -2 |
| push -3 | st[-2,0,-3] mins[-2,-2,-3] | **-3** |
| pop | st[-2,0] mins[-2,-2] | **-2** |

TC O(1) all ops. SC `O(n)`.

**If you get stuck in Live Code**
- Two stacks. If they insist on one, encode `2*x-min` and dry-run one new-min push/pop.

---

### 19. LRU Cache — mapped Interview 2 Hyd — not UTA/AUTA — [Bhavya](https://www.linkedin.com/posts/bhavya-77816218a_amazon-interviewexperience-sde1-activity-7473680829714546688-jeL9) — **NOT Login Tracker** · recurring (Roundz NMF R4/BR LRU; Reddit LFU different IE)

**What they actually asked**
Hyderabad onsite Interview 2: LP + **LRU Cache** + design principles / basic SD UNNAMED. HM Spring login is a **different** prompt. Login Tracker (`new_login` / `get_oldest_login`) is **unverified mentor-only**.

**Clarify out loud**
1. Capacity in entries? `get` miss → `-1`? `get` counts as use?
2. Thread-safe? TTL? `int` keys or generic?

**Trick / pattern in one sentence**
HashMap to node + dummy-headed doubly linked list; move-to-front on get/put; evict `tail.prev`.

**Why this data structure**
- brute: `ArrayList` of pairs, scan for key `O(n)`
- optimal: `HashMap` + DLL — get/put O(1)
- refuse: `TreeMap` by timestamp; treating this as Login Tracker

**Brute**

```java
class LRUBrute {
    int cap;
    List<int[]> a = new ArrayList<>(); // [key, value], index 0 = LRU
    LRUBrute(int cap) { this.cap = cap; }
    int get(int k) {
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i)[0] == k) {
                int[] n = a.remove(i);
                a.add(n);
                return n[1];
            }
        }
        return -1;
    }
    void put(int k, int v) {
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i)[0] == k) { a.remove(i); break; }
        }
        a.add(new int[]{k, v});
        if (a.size() > cap) a.remove(0);
    }
}
```
TC `O(n)` get/put. Fails if they want O(1).

**Optimal**

```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)) {
            Node n = map.get(k);
            n.v = v;
            remove(n);
            addFront(n);
            return;
        }
        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);
        }
    }
}
```

`LinkedHashMap` `accessOrder=true` + `removeEldestEntry` is a one-liner to **mention**, then still write pointers if they want to see the DLL.

Dry run capacity=2: `put(1,1) put(2,2) get(1) put(3,3)`

| op | order MRU→LRU | map |
| --- | --- | --- |
| put 1 | 1 | {1} |
| put 2 | 2,1 | {1,2} |
| get 1 | 1,2 | {1,2} |
| put 3 | 3,1 | {1,3} (2 evicted) |

`get(2)` → `-1`. `get(1)` → 1.

TC O(1) get/put. SC `O(capacity)`.

Follow-ups: thread-safety sentence (`synchronized` on the cache); TTL on node; LFU is a **different** IE (Reddit 1idtlan), not this card.

**If you get stuck in Live Code**
- HashMap to node; on get, splice to head; on overflow, drop `tail.prev`.
- Dummy head/tail so you never special-case empty.

---

### 20. Open the Lock — mapped R1 **similar to** — UTA N — [LC 7623949](https://leetcode.com/discuss/post/7623949/amazon-sde-1-application-interview-exper-92xt/) — same IE as Distance K Fluency

**What they actually asked**
Snippet: **similar to Open the Lock** on R1. Same IE: Fluency slot was Distance K (card 1). **Similar-not-exact.** Still the BFS-on-states pattern for a later live (Word Ladder family is AUTA R2 / GFG R4 CAT→MEN — same idea, different alphabet).

**Clarify out loud**
1. 4 wheels `0000`→target? Deadends? Wrap 9↔0?
2. Moves = +1/−1 per wheel? Return min turns or `-1`?

**Trick / pattern in one sentence**
Unweighted graph of 10000 codes; **BFS** from `0000`; skip deadends.

**Why this data structure**
- brute: DFS with depth cap (misses shortest / TLE)
- optimal: queue + `Set` visited/dead
- refuse: Dijkstra — every turn costs 1

**Brute** — DFS (not shortest-safe without extra work).

```java
public int openLockDfs(String[] deadends, String target) {
    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    int[] best = {Integer.MAX_VALUE / 4};
    dfs("0000".toCharArray(), target, dead, new HashSet<>(), 0, best);
    return best[0] >= Integer.MAX_VALUE / 8 ? -1 : best[0];
}

private void dfs(char[] cur, String target, Set<String> dead, Set<String> vis,
                 int depth, int[] best) {
    String s = new String(cur);
    if (dead.contains(s) || !vis.add(s) || depth >= best[0]) return;
    if (s.equals(target)) { best[0] = depth; return; }
    for (int i = 0; i < 4; i++) {
        char orig = cur[i];
        for (int d : new int[]{1, -1}) {
            cur[i] = (char) ('0' + (orig - '0' + d + 10) % 10);
            dfs(cur, target, dead, vis, depth + 1, best);
            cur[i] = orig;
        }
    }
    vis.remove(s); // if you want other paths; this explodes
}
```
Do not ship this. Type BFS.

**Optimal**

```java
public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    if (dead.contains("0000")) return -1;
    Queue<String> q = new ArrayDeque<>();
    Set<String> vis = new HashSet<>();
    q.offer("0000");
    vis.add("0000");
    int steps = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int s = 0; s < sz; s++) {
            String u = q.poll();
            if (u.equals(target)) return steps;
            char[] c = u.toCharArray();
            for (int i = 0; i < 4; i++) {
                char orig = c[i];
                for (int d : new int[]{1, -1}) {
                    c[i] = (char) ('0' + (orig - '0' + d + 10) % 10);
                    String v = new String(c);
                    if (!dead.contains(v) && vis.add(v)) q.offer(v);
                    c[i] = orig;
                }
            }
        }
        steps++;
    }
    return -1;
}
```

Dry run target `0202`, no deadends. Neighbors of `0000` = eight codes (`1000,9000,0100,…`). BFS layers until `0202`. One shortest length on the classic sample is **6**.

| steps | example nodes in layer |
| ---: | --- |
| 0 | 0000 |
| 1 | 1000,9000,0100,0900,0010,0090,0001,0009 |
| … | … |
| 6 | 0202 reached |

TC `O(10⁴ · 8)`. SC `O(10⁴)`.

**If you get stuck in Live Code**
- “Each wheel ±1, BFS like Word Ladder.”
- Bidirectional BFS is a follow-up, not the first code.

---

## OPTIONAL MENTOR (not evidence)

**Login Tracker** (`new_login` / `get_oldest_login`): **I could not verify** as an SDE I live question. Mentor file only. Closest public: **LRU** (this file, card 19); GetRandom O(1); Bhavya HM Spring login layers (not a tracker); intern eviction DS. prachub login/firstUser is labeled **Oracle**.

If it ever appeared: HashMap + DLL, oldest at `head.next`, refresh = move to tail — **same code shape as LRU**, different method names. Do **not** lead a later-round hour with it.

**Rate Limiter:** skip here. Count = **1**, asked as Second Technical **SD** (IE.in 2025-grad, 13 Feb 2025), **not** UTA two-DSA. Point to the LLD fragment.

**LC 6369243** (not a card above): delivery stations + classes + topo, and max-sum switching two sorted linked lists. **Not** LC 962. **Not** LC 210. The **named** BR wording is card **7c** on **LC 6881058** only. Course Schedule II is card 13 on **6282609 / 6425074** only.

---

*End of `02-dsa-r3r4.md`. Java brute + optimal for listed R3/R4 / Fluency / pattern-reuse cards. Job 10454435: still none. Login Tracker: unverified. Rate Limiter SDE I count: 1 (not UTA).*