# Later-slot / BR-shaped DSA + one OOD — new IEs (Adarsh Vishwakarma)

Notes for a **third live** (HM / Fluency) or **fourth** (Bar Raiser). R1 (13 Aug 2026) and R2 (18 Aug 2026) already happened. **Java** Live Code. Production internships were Python / TypeScript.

These are worked answers to questions **other** SDE I / UTA / AUTA candidates reported in a **parent paste**. Job **10454435** still has **no** public IE that names a live-round question. Your loop may differ. **Unnamed stays unnamed.** Do not stamp LC ids unless a candidate named them.

**Reliability.** Cards marked **paste-only** are not a Job 10454435 list until an opened URL exists. Prefer [`R3-R4-Question-Bible.md`](../R3-R4-Question-Bible.md) §18 over guessing. Cards **3–5** (most frequent subtree sum; LIP matrix; even Kth ancestor) match [GFG off-campus-2021-4](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-2021-4/) — **opened-body, year-out 2021**, truncated scrape; fuller TUF set-01 reprint locally. **Not** a 10454435 ask. Where this notebook’s research bible **already** has a URL, reliability is **opened-body**, not paste-only.

**OA is not a round.** If an IE numbered OA as “Round 1”, **their R3 is often this loop’s R2 analogue**. Card 1 (max path **between two leaves**) is still useful as a **third-live pattern**. Labeled.

**Do not mix.** Maximum-sum **switching two sorted linked lists** is already card 7c in [`02-dsa-r3r4.md`](02-dsa-r3r4.md). **Not** LC 962. Not this file.

**House Robber II** is already a full Java card in `02-dsa-r3r4.md` §C.15 — short pointer here (card 10). **Celebrity** is Standard CS in `05-dsa.html` and `02-dsa-r3r4.md` §C.17 — **still a full Java card** here because the paste named an AUTA BR variant. **Logger / rate-limit SD** (token bucket, distributed Redis) lives in [`04-lld-stack.md`](04-lld-stack.md) §2, independent SDE I count = **1**, **not** UTA. Card 17 here is the **per-message + global logger** OOD from the paste — short Java, not a second Rate Limiter ask.

**60-min Live Code:** clarify 3–6 → 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 TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

---

## 1. Binary tree Maximum Path Sum **BETWEEN TWO LEAVES** — mapped paste **their R3** / OA-as-R1 reuse for a **third live** — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Parent paste: binary tree **maximum path sum between two leaves** (their R3) in the same hour as remove-k-digits + design patterns. This is **not** “any node to any node” unless they say so.

**If they said any-node:** related pattern at the end of this card. Say out loud: *the paste asked leaves.*

**OA-as-R1 label:** if their “R3” is the second live after OA-as-R1, this card is still **pattern reuse** for **your** third live. Not a 10454435 prediction.

**Clarify out loud**
1. Both ends **must be leaves**? Internal-to-internal disallowed?
2. Node values **negative**? Empty tree / single node (no two leaves → what — `Integer.MIN_VALUE` / throw / 0)?
3. Path = node values **including** both leaves and the LCA on that path?
4. Binary only? n-ary?
5. Return the **sum**, or also the path nodes?
6. If they also want any-node (LC-124 shape): confirm before you clamp negatives to 0.

**Trick / pattern in one sentence**
For every node that has **two children**, a leaf-to-leaf path through it is `bestDown(left) + node + bestDown(right)`; `bestDown` is the max sum from this node **down to a leaf** (you cannot drop a negative child if you still need a leaf).

**Why this data structure**
- brute DS: enumerate every pair of leaves, walk up via parent map or LCA — `O(n²)` pairs, extra parent map
- optimal DS: one post-order DFS, return “gain to a leaf”, track global max when both subtrees exist
- refuse: clamping a child gain to 0 (that is the **any-node** trick). A leaf path **must** include a real leaf. Also refuse Dijkstra (tree, not a general graph).

**Brute**
Idea: collect leaves, for each pair compute path sum via LCA. Fine for n ≤ 50; dies on a large tree in 45 min if they n-scare you — still write it, then switch.

```java
public int maxLeafToLeafBrute(TreeNode root) {
    List<TreeNode> leaves = new ArrayList<>();
    collectLeaves(root, leaves);
    if (leaves.size() < 2) return Integer.MIN_VALUE; // say this out loud
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < leaves.size(); i++) {
        for (int j = i + 1; j < leaves.size(); j++) {
            TreeNode lca = lca(root, leaves.get(i), leaves.get(j));
            int sum = pathSumTo(lca, leaves.get(i))
                    + pathSumTo(lca, leaves.get(j))
                    - lca.val; // counted twice
            best = Math.max(best, sum);
        }
    }
    return best;
}

private void collectLeaves(TreeNode n, List<TreeNode> leaves) {
    if (n == null) return;
    if (n.left == null && n.right == null) {
        leaves.add(n);
        return;
    }
    collectLeaves(n.left, leaves);
    collectLeaves(n.right, leaves);
}

private TreeNode lca(TreeNode n, TreeNode a, TreeNode b) {
    if (n == null || n == a || n == b) return n;
    TreeNode L = lca(n.left, a, b), R = lca(n.right, a, b);
    if (L != null && R != null) return n;
    return L != null ? L : R;
}

/** Sum of node values from ancestor `from` down to `to` (inclusive). */
private int pathSumTo(TreeNode from, TreeNode to) {
    int[] hit = {Integer.MIN_VALUE};
    dfsSum(from, to, 0, hit);
    return hit[0];
}

private boolean dfsSum(TreeNode n, TreeNode to, int acc, int[] hit) {
    if (n == null) return false;
    acc += n.val;
    if (n == to) {
        hit[0] = acc;
        return true;
    }
    return dfsSum(n.left, to, acc, hit) || dfsSum(n.right, to, acc, hit);
}
```

TC `O(n²)` typical (pairs × path). SC `O(n)` leaves + recursion.

**Optimal**
Step-by-step:
1. Post-order. If `n` is a leaf, return `n.val` (gain from here to a leaf is itself).
2. If only one child exists, you **cannot** form a leaf-to-leaf path *through* `n`. Still return `n.val + childGain` so a parent can use this spine to reach a leaf.
3. If both children exist, candidate = `leftGain + n.val + rightGain`. Update `best`.
4. Return `n.val + max(leftGain, rightGain)` as the best spine to a leaf.

```java
class MaxPathLeaves {
    private int best = Integer.MIN_VALUE;

    public int maxPathSumLeaves(TreeNode root) {
        best = Integer.MIN_VALUE;
        leafGain(root);
        return best; // Integer.MIN_VALUE means < 2 leaves — say it
    }

    /** Max sum from n down to any leaf in n's subtree. */
    private int leafGain(TreeNode n) {
        if (n == null) return 0;
        if (n.left == null && n.right == null) return n.val;

        Integer left = n.left == null ? null : leafGain(n.left);
        Integer right = n.right == null ? null : leafGain(n.right);

        if (left != null && right != null) {
            best = Math.max(best, left + n.val + right);
            return n.val + Math.max(left, right);
        }
        // one child only: no leaf-leaf through n
        return n.val + (left != null ? left : right);
    }
}
```

**Dry run** (tiny tree)

```
      10
     /  \
    2    10
   / \     \
  20  1    -25
           /  \
          3    4
```

Leaves: 20, 1, 3, 4.

| node | leftGain | rightGain | candidate through node | return spine |
| --- | ---: | ---: | ---: | ---: |
| 20 | leaf | leaf | — | 20 |
| 1 | leaf | leaf | — | 1 |
| 2 | 20 | 1 | 20+2+1=**23** | 2+20=22 |
| 3 | leaf | | — | 3 |
| 4 | leaf | | — | 4 |
| -25 | 3 | 4 | 3-25+4=**-18** | -25+4=**-21** |
| 10 (right) | — | -21 | one child | 10-21=**-11** |
| 10 (root) | 22 | -11 | 22+10-11=**21** | 10+22=32 |

`best` sees 23, then -18, then 21 → **23** (20-2-1). The any-node answer on this GFG classic is **42** (20-2-10-10) — **different problem**. If you clamp negatives you will quote 42 and fail the leaf constraint.

**TC/SC** `O(n)` time, `O(h)` stack.

**Follow-ups they asked (paste):** remove k digits (card 2); design patterns (not this file — Logger SOLID is `04-lld-stack.md`).

**If you get stuck in Live Code**
- Brute: all leaf pairs via LCA.
- Say: “I will not use the any-node clamp; a leaf path cannot drop a child.”

### Related pattern — any node to any node (say the paste asked **leaves**)

Do **not** stamp an LC id. Only write this if they **change** the spec to “path may start and end at any node.”

```java
class MaxPathAnyNode {
    private int best = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }

    private int gain(TreeNode n) {
        if (n == null) return 0;
        int L = Math.max(0, gain(n.left));  // may drop a negative branch
        int R = Math.max(0, gain(n.right));
        best = Math.max(best, L + n.val + R);
        return n.val + Math.max(L, R);
    }
}
```

Dry run same tree: through root 20+2+10+10 = **42** if the right spine is taken without the -25. **Different from leaves.**

---

## 2. Remove k digits to form the **smallest** number — mapped paste their R3 family + bible **R2** / DesiQnA **R1** — UTA N — reliability: bible opened-body **and** paste — [LC 6630775](https://leetcode.com/discuss/post/6630775/amazon-sde1-round-2-by-harry_potter_10-zubi/) · [DesiQnA 19202](https://www.desiqna.in/19202/amazon-sde-1-recent-interview-experiences-2026-set-61) (candidate named **LC 402**)

**What they actually asked**
Paste: **remove k digits** to form the **smallest** number (with max-path-leaves). Bible: LC 6630775 R2 **Remove K Digits** (OA-as-R1 phone then this live). DesiQnA 15 Apr 2026 R1 candidate **named LC 402**. A different intern post asked **maximum** number — **not** this card. Do not stamp Job 10454435.

**Clarify out loud**
1. `num` as `String` of digits? Leading zeros in the **answer** stripped (`"0200"` + k=1 → `"200"`)?
2. Remove **exactly** k? If k ≥ n → `"0"`?
3. Smallest **numeric** value, not lexicographically with leading zeros kept?
4. Digits only, no sign?
5. In-place vs new string?

**Trick / pattern in one sentence**
Monotonic **increasing** stack: while the new digit is **smaller** than the top, pop (that peak is the cheapest deletion); strip leading zeros at the end.

**Why this data structure**
- brute DS: all subsets of k deletions, `C(n,k)` strings, sort — dies at n=10⁴
- optimal DS: `StringBuilder` as a stack; greedy left-to-right
- refuse: sorting the digits (that is not “keep order”). Heap of indices unless you are doing a different problem.

**Brute**

```java
public String removeKdigitsBrute(String num, int k) {
    if (k >= num.length()) return "0";
    String[] best = { null };
    dfs(num, 0, k, new StringBuilder(), best);
    return best[0];
}

private void dfs(String num, int i, int left, StringBuilder cur, String[] best) {
    if (left < 0) return;
    if (i == num.length()) {
        if (left != 0) return;
        String s = stripZeros(cur.toString());
        if (best[0] == null || smaller(s, best[0])) best[0] = s;
        return;
    }
    cur.append(num.charAt(i));          // keep
    dfs(num, i + 1, left, cur, best);
    cur.deleteCharAt(cur.length() - 1);
    dfs(num, i + 1, left - 1, cur, best); // delete
}

private boolean smaller(String a, String b) {
    if (a.length() != b.length()) return a.length() < b.length();
    return a.compareTo(b) < 0;
}

private String stripZeros(String s) {
    int i = 0;
    while (i < s.length() && s.charAt(i) == '0') i++;
    String t = s.substring(i);
    return t.isEmpty() ? "0" : t;
}
```

TC `O(2^n · n)`. SC `O(n)`. Fails n=10⁴.

**Optimal**
Step-by-step:
1. For each digit `c`, while k>0 and stack top > `c`, pop and k--.
2. Push `c`.
3. If k still > 0, pop from the **right** (remaining are the largest suffix).
4. Strip leading zeros. Empty → `"0"`.

```java
public String removeKdigits(String num, int k) {
    StringBuilder st = new StringBuilder();
    for (int i = 0; i < num.length(); i++) {
        char c = num.charAt(i);
        while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
            st.deleteCharAt(st.length() - 1);
            k--;
        }
        st.append(c);
    }
    while (k > 0 && st.length() > 0) {
        st.deleteCharAt(st.length() - 1);
        k--;
    }
    int i = 0;
    while (i < st.length() && st.charAt(i) == '0') i++;
    String ans = st.substring(i);
    return ans.isEmpty() ? "0" : ans;
}
```

**Dry run** `num = "1432219"`, `k = 3`

| i | c | stack after | k |
| ---: | --- | --- | ---: |
| 0 | 1 | 1 | 3 |
| 1 | 4 | 14 | 3 |
| 2 | 3 | 13 (pop 4) | 2 |
| 3 | 2 | 12 (pop 3) | 1 |
| 4 | 2 | 122 | 1 |
| 5 | 1 | 121 (pop 2) | 0 |
| 6 | 9 | 1219 | 0 |

Answer **`"1219"`**.

Second dry run `"10200"`, k=1: pop `1` → `"0200"` → strip → **`"200"`**.

**TC/SC** `O(n)` time (each index push/pop once), `O(n)` builder.

**Follow-ups:** form the **largest** number = reverse the inequality (`<` instead of `>`); split-array largest sum (bible 6630775 companion — not this card).

**If you get stuck in Live Code**
- “Delete peaks from the left: monotonic increasing stack.”
- If k remains, delete the tail.

---

## 3. Most frequent subtree sum — mapped GFG off-campus-2021-4 **R1** (with median of two sorted) — UTA N — **opened-body year-out** — [GFG 2021-4](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-2021-4/)

**What they actually asked**
Parent paste: GFG block with **median of two sorted arrays** + **most frequent subtree sum**. Do **not** stamp an LC id. Unnamed stays unnamed.

**Clarify out loud**
1. Subtree sum = node + left subtree + right subtree?
2. Return **all** sums that share the max frequency, any order?
3. Negative values? Empty tree?
4. Skewed tree / n?

**Trick / pattern in one sentence**
Post-order return the subtree sum; `HashMap<sum, freq>`; second pass (or a running `bestFreq`) collect keys with that freq.

**Why this data structure**
- brute DS: for every node, re-sum its subtree `O(n²)`
- optimal DS: one DFS + HashMap
- refuse: sorting nodes; a heap of sums (you need **all** ties)

**Brute**

```java
public int[] findFrequentTreeSumBrute(TreeNode root) {
    List<TreeNode> nodes = new ArrayList<>();
    collect(root, nodes);
    Map<Integer, Integer> freq = new HashMap<>();
    for (TreeNode n : nodes) {
        int s = sumTree(n);
        freq.merge(s, 1, Integer::sum);
    }
    return keysWithMaxFreq(freq);
}

private void collect(TreeNode n, List<TreeNode> out) {
    if (n == null) return;
    out.add(n);
    collect(n.left, out);
    collect(n.right, out);
}

private int sumTree(TreeNode n) {
    if (n == null) return 0;
    return n.val + sumTree(n.left) + sumTree(n.right);
}
```

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

**Optimal**

```java
public int[] findFrequentTreeSum(TreeNode root) {
    Map<Integer, Integer> freq = new HashMap<>();
    int[] best = { 0 };
    subtree(root, freq, best);
    List<Integer> ans = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        if (e.getValue() == best[0]) ans.add(e.getKey());
    }
    int[] a = new int[ans.size()];
    for (int i = 0; i < ans.size(); i++) a[i] = ans.get(i);
    return a;
}

private int subtree(TreeNode n, Map<Integer, Integer> freq, int[] best) {
    if (n == null) return 0;
    int s = n.val + subtree(n.left, freq, best) + subtree(n.right, freq, best);
    int f = freq.merge(s, 1, Integer::sum);
    if (f > best[0]) best[0] = f;
    return s;
}
```

**Dry run**

```
   5
  / \
 2  -3
```

| node | subtree sum | freq |
| --- | ---: | ---: |
| 2 | 2 | 2→1 |
| -3 | -3 | -3→1 |
| 5 | 5+2-3=4 | 4→1 |

All freq 1 → return `[2,-3,4]` any order.

Second tree: `5 / \ 2 -5` → sums 2, -5, 2 → **`[2]`**.

| node | s | freq after | bestFreq |
| --- | ---: | --- | ---: |
| 2 | 2 | 2:1 | 1 |
| -5 | -5 | -5:1 | 1 |
| 5 | 2 | 2:2 | **2** |

**TC/SC** `O(n)` time, `O(n)` map + stack.

**If you get stuck in Live Code**
- Brute re-sum each subtree; then “return the sum from DFS and tally.”

---

## 4. Longest increasing path in a matrix — mapped GFG off-campus-2021-4 **labeled BR** — UTA N — **opened-body year-out** — [GFG 2021-4](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-2021-4/) — do **not** stamp LC 329

**What they actually asked**
Parent paste: GFG BR **longest increasing path in a matrix** (+ sum of nodes whose Kth ancestor is even). Do **not** stamp an LC id.

**Clarify out loud**
1. 4-direction (up/down/left/right), not 8?
2. **Strictly** increasing?
3. Path may start at any cell? Return **length** (cells), not the path?
4. Empty matrix / 1×1?
5. Duplicates: equal values **cannot** continue?

**Trick / pattern in one sentence**
DAG of cells: edge if neighbor is strictly larger; longest path = DFS + memo (or topo DP on indegree).

**Why this data structure**
- brute DS: DFS from every cell with a `visited` of the **path** — exponential
- optimal DS: `memo[r][c]` = longest path **starting at** (r,c); each cell computed once
- refuse: BFS without DP (cycles of increase cannot exist, but you still recompute); Dijkstra

**Brute**

```java
public int longestIncreasingPathBrute(int[][] g) {
    int best = 0;
    boolean[][] onPath = new boolean[g.length][g[0].length];
    for (int r = 0; r < g.length; r++) {
        for (int c = 0; c < g[0].length; c++) {
            best = Math.max(best, dfsBrute(g, r, c, onPath));
        }
    }
    return best;
}

private int dfsBrute(int[][] g, int r, int c, boolean[][] onPath) {
    onPath[r][c] = true;
    int best = 1;
    int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nc < 0 || nr >= g.length || nc >= g[0].length) continue;
        if (onPath[nr][nc] || g[nr][nc] <= g[r][c]) continue;
        best = Math.max(best, 1 + dfsBrute(g, nr, nc, onPath));
    }
    onPath[r][c] = false;
    return best;
}
```

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

**Optimal**

```java
public int longestIncreasingPath(int[][] g) {
    int m = g.length, n = g[0].length;
    int[][] memo = new int[m][n];
    int best = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            best = Math.max(best, dfs(g, r, c, memo));
        }
    }
    return best;
}

private int dfs(int[][] g, int r, int c, int[][] memo) {
    if (memo[r][c] != 0) return memo[r][c];
    int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
    int best = 1;
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nc < 0 || nr >= g.length || nc >= g[0].length) continue;
        if (g[nr][nc] <= g[r][c]) continue;
        best = Math.max(best, 1 + dfs(g, nr, nc, memo));
    }
    memo[r][c] = best;
    return best;
}
```

**Dry run**

```
9 9 4
6 6 8
2 1 1
```

Path `1 → 2 → 6 → 9` length **4**.

| start | memo (longest from here) |
| --- | ---: |
| (2,1)=1 | 1+ from 2 → … → **4** |
| (2,0)=2 | 3 |
| (1,0)=6 | 2 |
| (0,0)=9 | 1 |

**TC/SC** `O(mn)` time (each cell 4 edges once), `O(mn)` memo + stack.

**If you get stuck in Live Code**
- Brute DFS; then “memoize longest-from-here; increase only, so no cycle.”
- Topo: cells with no smaller neighbor are sources; DP along increasing edges.

---

## 5. Sum of nodes whose **Kth ancestor is even** — mapped GFG off-campus-2021-4 **labeled BR** — UTA N — **opened-body year-out** — [GFG 2021-4](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-2021-4/)

**What they actually asked**
Parent paste: **sum of nodes whose Kth ancestor is even**, with a **vector of ancestors**. Do **not** stamp an LC id. Binary tree assumed unless they say n-ary.

**Clarify out loud**
1. Root’s ancestor list is empty; if depth < k, skip (do not wrap)?
2. “Even” = ancestor **value** `% 2 == 0`, or ancestor **index/level** even?
3. k is 1-based (parent is 1st ancestor)?
4. Return sum of **node values** that pass the test?
5. Unique values? Parent pointers given? (paste said **vector of ancestors** — build it on the DFS)

**Trick / pattern in one sentence**
DFS with a `List<Integer>` of ancestors from root to parent; at node, if `list.size() >= k && list.get(list.size()-k)` is even, add `node.val`; push, recurse, pop.

**Why this data structure**
- brute DS: parent map, jump k times per node — `O(nk)`
- optimal DS: ancestor vector (or a deque) so the kth ancestor is an index; `O(1)` test, `O(n)` total
- refuse: storing the full path as a string; LCA machinery (wrong question)

**Brute**

```java
public int sumKthAncestorEvenBrute(TreeNode root, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    parent.put(root, null);
    buildParent(root, parent);
    int sum = 0;
    for (TreeNode n : parent.keySet()) {
        TreeNode a = n;
        for (int i = 0; i < k && a != null; i++) a = parent.get(a);
        if (a != null && a.val % 2 == 0) sum += n.val;
    }
    return sum;
}

private void buildParent(TreeNode n, Map<TreeNode, TreeNode> parent) {
    if (n.left != null) {
        parent.put(n.left, n);
        buildParent(n.left, parent);
    }
    if (n.right != null) {
        parent.put(n.right, n);
        buildParent(n.right, parent);
    }
}
```

TC `O(nk)`. SC `O(n)`. Fine if they say k is tiny; still prefer the vector.

**Optimal**

```java
public int sumKthAncestorEven(TreeNode root, int k) {
    int[] sum = { 0 };
    dfs(root, k, new ArrayList<>(), sum);
    return sum[0];
}

private void dfs(TreeNode n, int k, List<Integer> anc, int[] sum) {
    if (n == null) return;
    if (anc.size() >= k) {
        int kth = anc.get(anc.size() - k); // 1-based: parent is last
        if (kth % 2 == 0) sum[0] += n.val;
    }
    anc.add(n.val);
    dfs(n.left, k, anc, sum);
    dfs(n.right, k, anc, sum);
    anc.remove(anc.size() - 1);
}
```

If they want **binary lifting** as a follow-up (k huge, many queries): `up[v][j]` = 2^j ancestor. Paste asked a **vector** — do not start with lifting.

**Dry run** k=1 (parent must be even)

```
      8
     / \
    3   4
   / \
  2   5
```

| node | ancestors (root→parent) | kth (parent) | even? | add |
| --- | --- | ---: | --- | ---: |
| 8 | [] | — | skip | |
| 3 | [8] | 8 | Y | **3** |
| 2 | [8,3] | 3 | N | |
| 5 | [8,3] | 3 | N | |
| 4 | [8] | 8 | Y | **4** |

Answer **7**.

**TC/SC** `O(n)` time, `O(h)` vector (not `O(n)` extra if you pop).

**If you get stuck in Live Code**
- Parent map + walk k steps.
- Then: “push on the way down, index `size-k`.”

---

## 6. Distance between two nodes in a binary tree, **no parent pointers** — mapped paste — related Dist-K, **different IO** — UTA mixed — reliability: Dist-K family opened-body in bible; **this IO paste-only** until bible has a URL — Dist-K: [LC 7406809](https://leetcode.com/discuss/post/7406809/amazon-sde-1-auta-interview-experience-s-k6t7/) · [LC 7623949](https://leetcode.com/discuss/post/7623949/amazon-sde-1-application-interview-exper-92xt/)

**What they actually asked**
Paste: **distance between two nodes**, no parent pointers. Dist-K (all nodes at distance K from a **target**) is a **related** pattern already in `02-dsa-r3r4.md` card 1 — **different IO**. Intern zigzag + path between two nodes is **INTERN** (appendix one-liner, not this card’s loop).

**Clarify out loud**
1. Nodes given as **values** or as `TreeNode` refs? Values unique?
2. Distance = number of **edges**?
3. Node missing → -1?
4. Forbidden parent `HashMap`? (Dist-K Fluency forbade it; still ask)
5. Binary?

**Trick / pattern in one sentence**
`dist(a,b) = dist(root,a) + dist(root,b) - 2*dist(root, lca)` — or one DFS that returns distance-to-target and bubbles the answer when both sides hit.

**Why this data structure**
- brute DS: undirected graph + BFS from a to b — correct, extra adj list
- optimal DS: LCA + three root-distances, **or** a single DFS with return codes
- refuse: parent map if they forbade it; Floyd-Warshall

**Brute** — adj list + BFS (legal; it is not a stored parent map)

```java
public int distBrute(TreeNode root, int a, int b) {
    Map<Integer, List<Integer>> g = new HashMap<>();
    build(root, null, g);
    return bfs(g, a, b);
}

private void build(TreeNode n, TreeNode from, Map<Integer, List<Integer>> g) {
    if (n == null) return;
    g.putIfAbsent(n.val, new ArrayList<>());
    if (from != null) {
        g.get(n.val).add(from.val);
        g.get(from.val).add(n.val);
    }
    build(n.left, n, g);
    build(n.right, n, g);
}

private int bfs(Map<Integer, List<Integer>> g, int a, int b) {
    Queue<Integer> q = new ArrayDeque<>();
    Set<Integer> seen = new HashSet<>();
    q.add(a);
    seen.add(a);
    int d = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            int u = q.poll();
            if (u == b) return d;
            for (int v : g.getOrDefault(u, new ArrayList<>())) {
                if (seen.add(v)) q.add(v);
            }
        }
        d++;
    }
    return -1;
}
```

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

**Optimal — LCA + depths**

```java
public int dist(TreeNode root, int a, int b) {
    TreeNode lca = lcaVal(root, a, b);
    if (lca == null) return -1;
    int da = depthTo(lca, a, 0);
    int db = depthTo(lca, b, 0);
    if (da < 0 || db < 0) return -1;
    return da + db;
}

private TreeNode lcaVal(TreeNode n, int a, int b) {
    if (n == null) return null;
    if (n.val == a || n.val == b) return n;
    TreeNode L = lcaVal(n.left, a, b), R = lcaVal(n.right, a, b);
    if (L != null && R != null) return n;
    return L != null ? L : R;
}

private int depthTo(TreeNode n, int t, int d) {
    if (n == null) return -1;
    if (n.val == t) return d;
    int L = depthTo(n.left, t, d + 1);
    return L >= 0 ? L : depthTo(n.right, t, d + 1);
}
```

**Optimal — one DFS** (Dist-K cousin: return distance to `a`/`b`, set answer when both found)

```java
public int distOneDfs(TreeNode root, int a, int b) {
    int[] ans = { -1 };
    find(root, a, b, ans);
    return ans[0];
}

/** Distance from n down to a or b, or -1 if neither in this subtree.
 *  When both found, writes ans. */
private int find(TreeNode n, int a, int b, int[] ans) {
    if (n == null) return -1;
    int L = find(n.left, a, b, ans);
    int R = find(n.right, a, b, ans);
    boolean here = n.val == a || n.val == b;
    if (L >= 0 && R >= 0) {           // a and b in different subtrees
        ans[0] = L + R + 2;
        return -1;                    // done bubbling
    }
    if (here && (L >= 0 || R >= 0)) { // n is one endpoint
        ans[0] = (L >= 0 ? L : R) + 1;
        return -1;
    }
    if (here) return 0;
    if (L >= 0) return L + 1;
    if (R >= 0) return R + 1;
    return -1;
}
```

**Dry run**

```
      1
     / \
    2   3
   / \
  4   5
```

dist(4,5): LCA=2, da=1, db=1 → **2**.  
dist(4,3): LCA=1, da=2, db=1 → **3**.

| call | L | R | here | ans |
| --- | ---: | ---: | --- | ---: |
| 4 | -1 | -1 | Y | return 0 |
| 5 | -1 | -1 | Y | return 0 |
| 2 | 0 | 0 | N | ans=0+0+2=**2** |

**TC/SC** `O(n)` time, `O(h)` stack. No parent map.

**If you get stuck in Live Code**
- Graph + BFS.
- Then LCA formula out loud; then one DFS if they forbade extra maps.

**Dist-K difference (say it):** Dist-K returns a **list** of values at distance K from **one** target (possibly through parent). This card returns a **single integer** between **two** named nodes.

---

## 7. Design stack `getMiddle` O(1) — mapped paste (with distance-two-nodes + Basic Calculator) — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Paste: **design a stack** with **getMiddle in O(1)** (DLL + mid pointer). Push / pop still O(1). Not Min Stack (that is `02-dsa-r3r4.md` §C.18). Not Login Tracker (unverified).

**Clarify out loud**
1. `push`, `pop`, `top`, `getMiddle` all O(1)? Delete-middle too?
2. Even size: lower or upper middle? (pick and stick)
3. Empty pop / getMiddle → throw or sentinel?
4. Integers only?
5. Thread safety? (say no unless they ask)

**Trick / pattern in one sentence**
Doubly linked list plus a **mid pointer**: after push, if size becomes odd, mid walks **forward**; after pop, if size becomes even, mid walks **back**.

**Why this data structure**
- brute DS: `ArrayList` — push/pop O(1) amortized at the end, `getMiddle` is `a.get(size/2)` which is O(1) **index** — say this out loud. They still want the DLL interview if they said “linked list / mid pointer.” ArrayList is honest if they allow arrays.
- optimal DS they asked: DLL + mid
- refuse: scanning from head each time; `java.util.Stack` as the whole answer

**Brute** — ArrayList (correct if allowed; they may reject it)

```java
class MidStackBrute {
    private final List<Integer> a = new ArrayList<>();

    void push(int x) { a.add(x); }

    int pop() {
        if (a.isEmpty()) throw new IllegalStateException("empty");
        return a.remove(a.size() - 1);
    }

    int top() { return a.get(a.size() - 1); }

    /** Even size: lower middle (index size/2 - 1 if 1-based “first middle”).
     *  Here: index (size-1)/2 — the left middle when even. */
    int getMiddle() {
        if (a.isEmpty()) throw new IllegalStateException("empty");
        return a.get((a.size() - 1) / 2);
    }
}
```

TC `O(1)` amortized push/pop/getMiddle. SC `O(n)`. ArrayList `remove(0)` would be O(n) — we only remove the end.

**Optimal — DLL + mid**

Invariant (left-middle when even):
- `size == 0`: mid = null
- `size` odd: mid is the unique middle
- `size` even: mid is the **left** of the two middles
- push at **tail** (top of stack)
- after push: if size **odd**, `mid = mid.next` (from previous even left-middle toward the new unique middle)
- after pop: if size **even**, `mid = mid.prev`

```java
class MidStack {
    private static final class Node {
        int val;
        Node prev, next;
        Node(int val) { this.val = val; }
    }

    private Node head, tail, mid;
    private int size;

    void push(int x) {
        Node n = new Node(x);
        if (tail == null) {
            head = tail = mid = n;
            size = 1;
            return;
        }
        tail.next = n;
        n.prev = tail;
        tail = n;
        size++;
        if (size % 2 == 1) mid = mid.next;
    }

    int pop() {
        if (size == 0) throw new IllegalStateException("empty");
        int v = tail.val;
        if (size == 1) {
            head = tail = mid = null;
            size = 0;
            return v;
        }
        tail = tail.prev;
        tail.next = null;
        size--;
        if (size % 2 == 0) mid = mid.prev;
        return v;
    }

    int top() {
        if (tail == null) throw new IllegalStateException("empty");
        return tail.val;
    }

    int getMiddle() {
        if (mid == null) throw new IllegalStateException("empty");
        return mid.val;
    }

    /** Optional follow-up: delete middle, still O(1). */
    int deleteMiddle() {
        if (mid == null) throw new IllegalStateException("empty");
        int v = mid.val;
        if (size == 1) {
            head = tail = mid = null;
            size = 0;
            return v;
        }
        Node p = mid.prev, nx = mid.next;
        if (p != null) p.next = nx; else head = nx;
        if (nx != null) nx.prev = p; else tail = p;
        size--;
        // after delete, pick new mid: if new size even, take prev; if odd, take next
        mid = (size % 2 == 0) ? p : nx;
        return v;
    }
}
```

**Dry run** push 1,2,3,4,5 then pop

| op | list (head→tail) | size | mid |
| --- | --- | ---: | ---: |
| push 1 | 1 | 1 | **1** |
| push 2 | 1-2 | 2 | **1** (left middle) |
| push 3 | 1-2-3 | 3 | **2** |
| push 4 | 1-2-3-4 | 4 | **2** |
| push 5 | 1-2-3-4-5 | 5 | **3** |
| pop →5 | 1-2-3-4 | 4 | **2** |

getMiddle after 5 pushes = **3**. After pop = **2**.

**TC/SC** all ops `O(1)` time, `O(n)` space.

**If you get stuck in Live Code**
- ArrayList + `get((n-1)/2)` first, then “they asked DLL: mid walks on odd/even.”
- Draw three nodes before coding the pointers.

---

## 8. Next Permutation — mapped paste AUTA R3 (GenAI+LP+**Next Permutation**) + bible **similar** AUTA R2 — UTA Y on the similar ask — reliability: paste AUTA named it; bible similar — [LC 6806195](https://leetcode.com/discuss/post/6806195/amazon-auta-interview-experience-sde-1-2-f90u/) (R2 **similar**, approach only). **No LC id stamp** (candidate on 6806195 did not name one). Prabhash R1 mixed next-perm / next-greater-same-digits.

**What they actually asked**
Paste AUTA ~1.5 YOE frontend: GenAI + LP + **Next Permutation** in **their R3**, Celebrity variant **BR**, rejected. Bible 6806195 AUTA R2 was Rotate Image + **similar to Next Permutation**. Rearrange to the **next lexicographic permutation**; if already last, wrap to the first (sorted ascending).

**Clarify out loud**
1. Mutate in place? Duplicates allowed?
2. Last permutation → reverse to ascending?
3. Array of ints vs string of digits?
4. Next greater **number** with same digits (Prabhash) vs full permutation of an array?

**Trick / pattern in one sentence**
Find the rightmost **ascent** `a[i] < a[i+1]` (pivot); swap with the rightmost successor `> a[i]`; reverse the suffix.

**Why this data structure**
- brute DS: generate all unique perms, sort, pick next — `O(n!)`
- optimal DS: in-place two pointers, no extra DS
- refuse: `Collections.sort` of all perms; recursion if they want O(n)

**Brute**

```java
public void nextPermutationBrute(int[] a) {
    List<int[]> all = new ArrayList<>();
    boolean[] used = new boolean[a.length];
    dfs(a, used, new ArrayList<>(), all);
    all.sort((x, y) -> {
        for (int i = 0; i < x.length; i++) {
            if (x[i] != y[i]) return Integer.compare(x[i], y[i]);
        }
        return 0;
    });
    // unique
    List<int[]> u = new ArrayList<>();
    for (int[] p : all) {
        if (u.isEmpty() || !Arrays.equals(u.get(u.size() - 1), p)) u.add(p);
    }
    int idx = 0;
    for (int i = 0; i < u.size(); i++) {
        if (Arrays.equals(u.get(i), a)) { idx = i; break; }
    }
    int[] nxt = u.get((idx + 1) % u.size());
    System.arraycopy(nxt, 0, a, 0, a.length);
}

private void dfs(int[] a, boolean[] used, List<Integer> cur, List<int[]> all) {
    if (cur.size() == a.length) {
        int[] p = new int[a.length];
        for (int i = 0; i < a.length; i++) p[i] = cur.get(i);
        all.add(p);
        return;
    }
    for (int i = 0; i < a.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        cur.add(a[i]);
        dfs(a, used, cur, all);
        cur.remove(cur.size() - 1);
        used[i] = false;
    }
}
```

TC `O(n! · n)`. SC `O(n!)`. Fails n=10.

**Optimal**

```java
public void nextPermutation(int[] a) {
    int n = a.length;
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--; // pivot: last ascent
    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;           // rightmost successor
        swap(a, i, j);
    }
    reverse(a, i + 1, n - 1);               // suffix was non-increasing
}

private void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

private void reverse(int[] a, int l, int r) {
    while (l < r) swap(a, l++, r--);
}
```

**Dry run** `[1,3,5,4,2]`

| step | i | a[i] | j | array |
| --- | ---: | ---: | ---: | --- |
| find pivot | 1 | 3 | | 1,**3**,5,4,2  (3<5) |
| successor | | | 3 | 4 is rightmost > 3 |
| swap | | | | `[1,4,5,3,2]` |
| reverse suffix | | | | `[1,4,2,3,5]` |

Next: `[1,4,2,3,5]`.

Last perm `[3,2,1]`: i=-1, reverse all → `[1,2,3]`.

**TC/SC** `O(n)` time, `O(1)` extra.

**If you get stuck in Live Code**
- “Find the first place from the right that can increase; swap the smallest larger; reverse the tail.”
- Duplicates: `>=` / `<=` already skip equals.

---

## 9. Celebrity problem (two-pointer) — mapped paste **AUTA BR variant** — Standard CS in `05-dsa.html` / `02-dsa-r3r4.md` §C.17 — GFG [off-campus-10](https://www.geeksforgeeks.org/interview-experiences/amazon-interview-experience-for-sde-1-off-campus-10/) (year-out R1 approach). Paste AUTA BR = **paste-only** for that 2026 frontend loop (rejected). **No 2026 AUTA BR URL in the research bible.** Do not invent one. Do not stamp LC 277 as an asked-id for Job 10454435.

**What they actually asked**
Paste: AUTA ~1.5 YOE, **Celebrity variant** on **BR**. Classic: among n people, celebrity is known by everyone and knows no one. API `knows(i,j)` or a matrix. GFG off-campus-10 had Celebrity **approach** on R1 (with Diameter, Islands) — year-out, not UTA-default.

**Clarify out loud**
1. Celebrity = known by **all**, knows **none**? Exactly one, or none → -1?
2. `knows(a,b)` API vs `int[][] m` where `m[i][j]==1` means i knows j?
3. `knows(i,i)`? n=1 → 0?
4. Directed? (yes)

**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 survivor in O(n).

**Why this data structure**
- brute DS: for each person, n queries both ways — `O(n²)` `knows` calls
- optimal DS: no extra DS, two indices, then one verify pass — `O(n)` queries
- refuse: building an adjacency graph / 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;
}

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

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

**Optimal — elimination then verify** (same as `02-dsa`; two-pointer twin below)

```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;
}
```

**Optimal — two pointers** (matches `05-dsa.html`; paste “variant” if they hand a matrix)

```java
public int celebrityMatrix(int[][] m) {
    int n = m.length, i = 0, j = n - 1;
    while (i < j) {
        if (m[i][j] == 1) i++; // i knows j → i not celeb
        else j--;              // i does not know j → j not celeb
    }
    int cand = i;
    for (int k = 0; k < n; k++) {
        if (k == cand) continue;
        if (m[cand][k] == 1 || m[k][cand] == 0) return -1;
    }
    return cand;
}
```

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

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

Elimination `cand=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**.

Two-pointer: i=0,j=2; m[0][2]=1 → i=1; m[1][2]=1 → i=2. Same candidate.

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

**If you get stuck in Live Code**
- Brute each person.
- “knows() kills the knower.” Stack: push 0..n-1, pop two, push survivor.

**Paste AUTA BR:** if they change the definition (e.g. “knows at most k”), **stop** and clarify. Do not force classic celebrity. Unnamed stays unnamed.

---

## 10. House Robber II variation — **short pointer** — already full Java in [`02-dsa-r3r4.md`](02-dsa-r3r4.md) §C.15

**Already in fragment 02.** Do not duplicate a third copy here.

**Mapped:** 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 — not this loop).

**Trick:** linear `dp[i] = max(skip, take + dp[i-2])`; circular = `max(rob[0..n-2], rob[1..n-1])`. n=1 is the only split you must not do.

**Open:** `02-dsa-r3r4.md` card 15 for brute + optimal + dry run `[2,3,2]` → **3**.

**If they paste a “variation”** (houses with ranges, or two streets): still rob linear on the allowed index set; do not invent LC ids.

---

## 11. Count of Smaller Numbers After Self — candidate named **LC 315** — mapped paste **Hyderabad onsite R2** — **NMF-possible** (India onsite group, not UTA two-DSA default) — **paste-only** until bible has a URL

**What they actually asked**
Paste Hyderabad: HM resume; **Count of Smaller Numbers After Self** (candidate **named LC 315**); Amazon Locker LLD; BR LP. Flag: **NMF-possible** Hyderabad onsite group. Not UTA Zoom two-DSA. Not Job 10454435. Locker Java is in `04-lld-stack.md` §1.1.

**Clarify out loud**
1. For each `a[i]`, count of `a[j]` with `j > i` and `a[j] < a[i]`?
2. n up to 10⁵? (then Fenwick / merge, not `O(n²)`)
3. Duplicates: strictly `<`?
4. Negatives? Coordinate compress?

**Trick / pattern in one sentence**
Merge-sort inversion count, but **per index**; or Fenwick/BIT on compressed ranks, walk **right to left**, query rank-1, then update.

**Why this data structure**
- brute DS: nested loops `O(n²)`
- optimal DS: (A) Fenwick of frequencies on compressed values (B) merge-sort counting how many from the right half jump before `a[i]`
- refuse: `TreeSet` with `headSet` if they n-scare you (log, but duplicates need a multiset / policy); Java `TreeMap` is OK as a mid step

**Brute**

```java
public List<Integer> countSmallerBrute(int[] a) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < a.length; i++) {
        int c = 0;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[i]) c++;
        }
        ans.add(c);
    }
    return ans;
}
```

TC `O(n²)`. SC `O(1)` extra. Fails n=10⁵.

**Optimal — Fenwick (BIT)**

```java
public List<Integer> countSmallerFenwick(int[] a) {
    int n = a.length;
    int[] sorted = a.clone();
    Arrays.sort(sorted);
    Map<Integer, Integer> rank = new HashMap<>();
    int r = 1;
    for (int v : sorted) {
        if (!rank.containsKey(v)) rank.put(v, r++);
    }
    Fenwick bit = new Fenwick(r);
    Integer[] ans = new Integer[n];
    for (int i = n - 1; i >= 0; i--) {
        int rk = rank.get(a[i]);
        ans[i] = bit.sum(rk - 1); // strictly smaller
        bit.add(rk, 1);
    }
    return Arrays.asList(ans);
}

static final class Fenwick {
    private final int[] t;
    Fenwick(int n) { t = new int[n + 2]; }
    void add(int i, int d) {
        for (; i < t.length; i += i & -i) t[i] += d;
    }
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }
}
```

**Optimal — merge sort count**

```java
public List<Integer> countSmallerMerge(int[] a) {
    int n = a.length;
    int[] idx = new int[n], tmp = new int[n], cnt = new int[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    mergeSort(a, idx, tmp, cnt, 0, n - 1);
    List<Integer> ans = new ArrayList<>(n);
    for (int c : cnt) ans.add(c);
    return ans;
}

private void mergeSort(int[] a, int[] idx, int[] tmp, int[] cnt, int l, int r) {
    if (l >= r) return;
    int m = (l + r) >>> 1;
    mergeSort(a, idx, tmp, cnt, l, m);
    mergeSort(a, idx, tmp, cnt, m + 1, r);
    int i = l, j = m + 1, k = l;
    int jumped = 0; // how many from right half already taken (all < current left)
    while (i <= m && j <= r) {
        if (a[idx[j]] < a[idx[i]]) {
            tmp[k++] = idx[j++];
            jumped++;
        } else {
            cnt[idx[i]] += jumped;
            tmp[k++] = idx[i++];
        }
    }
    while (i <= m) {
        cnt[idx[i]] += jumped;
        tmp[k++] = idx[i++];
    }
    while (j <= r) tmp[k++] = idx[j++];
    System.arraycopy(tmp, l, idx, l, r - l + 1);
}
```

**Dry run** `[5,2,6,1]`

Right to left Fenwick (ranks 1,2,5,6 → 1,2,3,4):

| i | a[i] | rank | query(<rank) | bit after add |
| ---: | ---: | ---: | ---: | --- |
| 3 | 1 | 1 | 0 | {1:1} |
| 2 | 6 | 4 | 1 | {1:1,4:1} |
| 1 | 2 | 2 | 1 | {1:1,2:1,4:1} |
| 0 | 5 | 3 | 2 | … |

Answer `[2,1,1,0]`.

**TC/SC** Fenwick `O(n log n)` time, `O(n)` space. Merge same.

**If you get stuck in Live Code**
- Nested loops; then “inversions by index: merge or BIT right-to-left.”
- Compress ranks **before** Fenwick or negatives break indices.

**NMF label (say if they ask “will my loop get this?”):** Hyderabad **onsite** group in the paste. UTA Zoom two-DSA did not need this. Still a fair later-slot if they want a hard count.

---

## 12. Knight moves **generalized** / large board lazy neighbors — **pattern card**, exact prompt **UNNAMED** — mapped paste Zoom LiveCode + bible Minimum Knight Moves **LC-linked** R2 — UTA N — reliability: standard knight [LC 6629948](https://leetcode.com/discuss/post/6629948/amazon-sde-1-20232024-graduate-round-2-b-v6wy/) opened-body; **10000×10000 pluggable piece = paste-only unnamed**

**What they actually asked**
Paste recent Zoom LiveCode: **knight-moves generalized**, board **10000×10000**, **pluggable piece** (custom deltas). Bible 6629948 R2 was **Minimum Knight Moves** (candidate LC-linked) + Validate Sum Tree — **different**, smaller implicit board. Do **not** stamp an LC id on the unnamed 10000 board. Do not guess.

**Clarify out loud**
1. Start and end coordinates? 0-indexed? Obstacles?
2. Piece deltas injected (`int[][] moves`) vs chess knight only?
3. Board `N` up to 10⁴ — **cannot** allocate `boolean[N][N]`?
4. Infinite vs bounded? Blocked cells as a set?
5. Return min steps, or -1 if impossible?

**Trick / pattern in one sentence**
BFS on **implicit** graph: neighbors = `pos + delta` if in bounds; `visited` is a `HashSet` of packed keys (or `long`), **never** an N×N array; bidirectional BFS if they push N=1e4.

**Why this data structure**
- brute DS: `boolean[N][N]` + BFS — **memory-fails** at 10000²
- optimal DS: lazy neighbor generation + HashSet visited; optional bidirectional BFS / A*
- refuse: DFS; Dijkstra unless weights exist; DP on whole board

**Pattern — do not claim this was the unnamed prompt**

```java
public int minMoves(int n, int sr, int sc, int er, int ec, int[][] deltas) {
    if (sr == er && sc == ec) return 0;
    long start = pack(sr, sc), goal = pack(er, ec);
    Queue<Long> q = new ArrayDeque<>();
    Set<Long> seen = new HashSet<>();
    q.add(start);
    seen.add(start);
    int steps = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            long cur = q.poll();
            int r = (int) (cur >> 32), c = (int) cur;
            for (int[] d : deltas) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                long key = pack(nr, nc);
                if (!seen.add(key)) continue;
                if (key == goal) return steps + 1;
                q.add(key);
            }
        }
        steps++;
    }
    return -1;
}

private long pack(int r, int c) {
    return (((long) r) << 32) ^ (c & 0xffffffffL);
}
```

Chess knight deltas (only if they did **not** inject a piece):

```java
static final int[][] KNIGHT = {
    { -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1 },
    { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }
};
```

**Bidirectional BFS sketch** (if one-sided BFS is too wide)

```java
public int minMovesBi(int n, int sr, int sc, int er, int ec, int[][] deltas) {
    if (sr == er && sc == ec) return 0;
    Set<Long> a = new HashSet<>(), b = new HashSet<>();
    Queue<Long> qa = new ArrayDeque<>(), qb = new ArrayDeque<>();
    long s = pack(sr, sc), t = pack(er, ec);
    qa.add(s); a.add(s);
    qb.add(t); b.add(t);
    int da = 0, db = 0;
    while (!qa.isEmpty() && !qb.isEmpty()) {
        if (qa.size() <= qb.size()) {
            da++;
            if (expand(n, qa, a, b, deltas)) return da + db;
        } else {
            db++;
            if (expand(n, qb, b, a, deltas)) return da + db;
        }
    }
    return -1;
}

private boolean expand(int n, Queue<Long> q, Set<Long> mine, Set<Long> other,
                       int[][] deltas) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
        long cur = q.poll();
        int r = (int) (cur >> 32), c = (int) cur;
        for (int[] d : deltas) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
            long key = pack(nr, nc);
            if (other.contains(key)) return true;
            if (mine.add(key)) q.add(key);
        }
    }
    return false;
}
```

**Dry run** n=8, knight, (0,0) → (1,2): one hop. Table:

| steps | queue |
| ---: | --- |
| 0 | (0,0) |
| 1 | (2,1),(1,2),… → hit (1,2) → **1** |

**TC/SC** O(visited × |deltas|). Visited ≪ N² if the path is short. SC O(visited).

**If you get stuck in Live Code**
- BFS, HashSet, pack (r,c).
- “I will not new boolean[10000][10000].”

**Unnamed exact:** if they change deltas mid-interview, keep the same BFS; only the `deltas` array changes. That **is** the pluggable piece.

---

## 13. Partition Equal Subset Sum / Target Sum **WITH return combination** — mapped paste **R1** Zoom LiveCode — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Paste recent Zoom LiveCode **R1**: **Partition / target-sum with combination return** (not boolean-only). Do **not** stamp LC 416 / 494. Unnamed stays unnamed. Follow-up in the same paste hour: project+AI deep dive; BFS distance threshold (rotten family — already in banks).

**Clarify out loud**
1. **Partition:** split into two subsets with **equal sum** — return **one** subset (indices or values)?
2. **Target sum:** assign `+` / `-` so signed sum equals target — return **one** sign pattern?
3. Duplicates? Empty? Odds (partition impossible)?
4. Any valid combination, or all?

**Trick / pattern in one sentence**
Boolean DP `can[s]` = whether sum s is reachable; keep `prev[s]` parent (index / last add) so you can **walk back** the combination. Target-sum is the same DP on `sum - 2*neg = target`.

**Why this data structure**
- brute DS: 2^n subsets
- optimal DS: 0/1 knapsack bitset or `boolean[]` of size `total/2`, plus parent pointers
- refuse: returning only `true` if they asked for the subset; greedy sort (wrong)

**Brute — partition, return subset values**

```java
public List<Integer> partitionSubsetBrute(int[] a) {
    int total = 0;
    for (int x : a) total += x;
    if (total % 2 != 0) return null;
    List<Integer> path = new ArrayList<>();
    if (dfs(a, 0, total / 2, path)) return path;
    return null;
}

private boolean dfs(int[] a, int i, int left, List<Integer> path) {
    if (left == 0) return true;
    if (i == a.length || left < 0) return false;
    path.add(a[i]);
    if (dfs(a, i + 1, left - a[i], path)) return true;
    path.remove(path.size() - 1);
    return dfs(a, i + 1, left, path);
}
```

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

**Optimal — partition with reconstruction**

```java
public List<Integer> partitionSubset(int[] a) {
    int total = 0;
    for (int x : a) total += x;
    if ((total & 1) != 0) return null;
    int T = total / 2;
    boolean[] can = new boolean[T + 1];
    int[] takeIdx = new int[T + 1]; // last index used to reach s; -1 none
    Arrays.fill(takeIdx, -1);
    can[0] = true;
    for (int i = 0; i < a.length; i++) {
        int v = a[i];
        for (int s = T; s >= v; s--) {
            if (!can[s] && can[s - v]) {
                can[s] = true;
                takeIdx[s] = i;
            }
        }
    }
    if (!can[T]) return null;
    boolean[] used = new boolean[a.length];
    int s = T;
    while (s > 0) {
        int i = takeIdx[s];
        if (i < 0) return null; // should not happen
        used[i] = true;
        s -= a[i];
    }
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < a.length; i++) if (used[i]) subset.add(a[i]);
    return subset;
}
```

**Target sum — return one sign pattern** (`+` / `-` per index). Same knapsack: positives sum to `(total+target)/2`.

```java
/** Reach sum T; return indices used (0/1 knapsack). */
public List<Integer> partitionToSumIndices(int[] a, int T) {
    if (T < 0) return null;
    boolean[] can = new boolean[T + 1];
    int[] takeIdx = new int[T + 1];
    Arrays.fill(takeIdx, -1);
    can[0] = true;
    for (int i = 0; i < a.length; i++) {
        int v = a[i];
        for (int s = T; s >= v; s--) {
            if (!can[s] && can[s - v]) {
                can[s] = true;
                takeIdx[s] = i;
            }
        }
    }
    if (!can[T]) return null;
    List<Integer> idx = new ArrayList<>();
    int s = T;
    while (s > 0) {
        int i = takeIdx[s];
        idx.add(i);
        s -= a[i];
    }
    Collections.reverse(idx);
    return idx;
}

public char[] targetSigns(int[] a, int target) {
    int total = 0;
    for (int x : a) total += x;
    if (((total + target) & 1) != 0) return null;
    int P = (total + target) / 2;
    List<Integer> plusIdx = partitionToSumIndices(a, P);
    if (plusIdx == null) return null;
    boolean[] plus = new boolean[a.length];
    for (int i : plusIdx) plus[i] = true;
    char[] signs = new char[a.length];
    for (int i = 0; i < a.length; i++) signs[i] = plus[i] ? '+' : '-';
    return signs;
}
```

**Dry run** partition `[1,5,11,5]`, total 22, T=11

| i | v | can after (sums that became true) |
| ---: | ---: | --- |
| 0 | 1 | 0,1 |
| 1 | 5 | 0,1,5,6 |
| 2 | 11 | 0,1,5,6,11,… |
| 3 | 5 | … |

`can[11]` true via 11 itself → subset **`[11]`**. Other valid: `[1,5,5]`. Either is fine unless they want all.

Target `[1,1,1,1,1]`, target 3 → P=(5+3)/2=4 → four plus, one minus. Signs e.g. `++++-`.

**TC/SC** `O(n·T)` time, `O(T)` DP. T = total/2. If they say 10^15, classical DP **dies** — that is a different paste (Ansuman subset-sum 10^15). Say so; do not force knapsack.

**If you get stuck in Live Code**
- DFS that **appends** to a list (brute but returns a combo).
- Then 0/1 DP + `takeIdx` walk-back.

---

## 14. Device capability LLD — **OOD, not DSA** — mapped paste **Round 2 LLD** — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Paste: **device capability LLD** — Java interfaces **`PowerAware`**, **`DisplayCapable`**, **`SpeakerCapable`**, **Tablet composition vs god interface**. Their Round 2 LLD. This is **Interface Segregation**, not a graph algorithm.

**Clarify out loud**
1. Devices: Phone, Tablet, Monitor, Speaker, smartwatch?
2. Methods: power on/off, brightness, volume, battery %?
3. Can a Monitor be PowerAware + Display without Speaker?
4. Persistence? (in-memory for 40 min)
5. SOLID out loud?

**Trick / pattern in one sentence**
**ISP:** small capability interfaces; a Tablet **implements** the ones it has (or **composes** `Display` + `Speaker` + `Battery` objects). A `GodDevice` with camera+gps+nfc+speaker+display is the fail.

**Why this shape**
- brute / fail: `abstract class Device { power(); display(); speak(); takePhoto(); }` — Monitor is forced to `speak()`
- optimal: interfaces per capability; composition for shared battery/volume
- refuse: one enum of 40 device types with switch; inheritance `Tablet extends Phone`

**Brute — god interface (write this only to cross it out)**

```java
interface GodDevice {
    void powerOn();
    void powerOff();
    void show(String pixels);
    void play(String pcm);
    void zoomCamera();
    void setGps(double lat, double lon);
}
```

Monitor must stub `play` / `zoomCamera`. **Liskov fail.**

**Optimal — segregated interfaces + composition**

```java
interface PowerAware {
    void powerOn();
    void powerOff();
    boolean isOn();
}

interface DisplayCapable {
    void show(String content);
    void setBrightness(int pct);
}

interface SpeakerCapable {
    void play(String audio);
    void setVolume(int pct);
}

final class Battery {
    private int pct = 100;
    int pct() { return pct; }
    void drain(int d) { pct = Math.max(0, pct - d); }
}

final class DisplayPanel implements DisplayCapable {
    private int brightness = 50;
    public void show(String content) { /* draw */ }
    public void setBrightness(int pct) { brightness = Math.max(0, Math.min(100, pct)); }
}

final class SpeakerDriver implements SpeakerCapable {
    private int volume = 50;
    public void play(String audio) { /* pcm */ }
    public void setVolume(int pct) { volume = Math.max(0, Math.min(100, pct)); }
}

/** Monitor: power + display. No speaker. */
final class Monitor implements PowerAware, DisplayCapable {
    private boolean on;
    private final DisplayPanel panel = new DisplayPanel();

    public void powerOn() { on = true; }
    public void powerOff() { on = false; }
    public boolean isOn() { return on; }
    public void show(String content) {
        if (!on) throw new IllegalStateException("off");
        panel.show(content);
    }
    public void setBrightness(int pct) { panel.setBrightness(pct); }
}

/** Passive speaker brick: power + speaker. No display. */
final class SpeakerBox implements PowerAware, SpeakerCapable {
    private boolean on;
    private final SpeakerDriver spk = new SpeakerDriver();

    public void powerOn() { on = true; }
    public void powerOff() { on = false; }
    public boolean isOn() { return on; }
    public void play(String audio) {
        if (!on) throw new IllegalStateException("off");
        spk.play(audio);
    }
    public void setVolume(int pct) { spk.setVolume(pct); }
}

/** Tablet: power + display + speaker. Composes panel + speaker; does not extend Monitor. */
final class Tablet implements PowerAware, DisplayCapable, SpeakerCapable {
    private boolean on;
    private final Battery battery = new Battery();
    private final DisplayPanel panel = new DisplayPanel();
    private final SpeakerDriver spk = new SpeakerDriver();

    public void powerOn() { on = true; }
    public void powerOff() { on = false; }
    public boolean isOn() { return on; }

    public void show(String content) {
        if (!on) throw new IllegalStateException("off");
        panel.show(content);
        battery.drain(1);
    }
    public void setBrightness(int pct) { panel.setBrightness(pct); }

    public void play(String audio) {
        if (!on) throw new IllegalStateException("off");
        spk.play(audio);
        battery.drain(2);
    }
    public void setVolume(int pct) { spk.setVolume(pct); }

    int batteryPct() { return battery.pct(); }
}
```

**Client that should not care about speakers**

```java
void splash(DisplayCapable d, String msg) {
    d.show(msg);
}

// splash(monitor, "hello"); splash(tablet, "hello");
// SpeakerBox does not compile here — that is the point.
```

**SOLID (say it)**
- **S:** `DisplayPanel` draws; `Battery` counts charge; `Tablet` wires.
- **O:** add `CameraCapable` as a **new** interface; `Phone` implements it; `Monitor` unchanged.
- **L:** any `DisplayCapable` can `show`; a stub that throws on a legal show is not a display.
- **I:** no `GodDevice`.
- **D:** UI depends on `DisplayCapable`, not `Tablet`.

**Dry run**
| type | Power | Display | Speaker |
| --- | --- | --- | --- |
| Monitor | Y | Y | **N** |
| SpeakerBox | Y | N | Y |
| Tablet | Y | Y | Y |

Call `splash(speakerBox)` → **compile error**. Good.

**If you get stuck in Live Code**
- Write the three interfaces first, then Monitor (2), then Tablet (3).
- “I will not `Tablet extends Monitor` just to reuse `show`.”

**Not** Amazon retail HLD. **Not** Rate Limiter (count = 1, not UTA).

---

## 15. Min-heap assign partitions to servers (min load) — mapped paste **new-grad R1** — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Paste new-grad: **min-heap partition assignment**; later loyal-customer logs; BR LP-only; log rate limiter OOD. Assign each partition (size / load) to the current **minimum-load** server.

**Clarify out loud**
1. `m` servers, `n` partitions with weights `w[i]`?
2. Assign **all** partitions; return assignment `serverOf[i]` and/or final loads?
3. Servers start at 0? Identical capacity?
4. Offline (all weights known) vs stream?
5. Ties: lowest server id?

**Trick / pattern in one sentence**
Min-heap of `(load, serverId)`; for each partition (optionally largest-first), pop the lightest server, add weight, push back.

**Why this data structure**
- brute DS: for each partition scan all servers for min load — `O(nm)`
- optimal DS: `PriorityQueue` — `O(n log m)`
- refuse: random assignment; max-heap (that is worst-fit)

**Brute**

```java
public int[] assignBrute(int[] weights, int m) {
    int[] load = new int[m];
    int[] where = new int[weights.length];
    for (int i = 0; i < weights.length; i++) {
        int best = 0;
        for (int s = 1; s < m; s++) {
            if (load[s] < load[best] || (load[s] == load[best] && s < best)) best = s;
        }
        load[best] += weights[i];
        where[i] = best;
    }
    return where;
}
```

TC `O(nm)`. SC `O(m)`.

**Optimal**

```java
public int[] assignMinLoad(int[] weights, int m) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
        if (a[0] != b[0]) return Integer.compare(a[0], b[0]); // load
        return Integer.compare(a[1], b[1]);                   // id
    });
    for (int s = 0; s < m; s++) pq.add(new int[] { 0, s });
    int[] where = new int[weights.length];
    for (int i = 0; i < weights.length; i++) {
        int[] srv = pq.poll();
        srv[0] += weights[i];
        where[i] = srv[1];
        pq.add(srv);
    }
    return where;
}

/** Optional: LPT — sort weights descending first (better makespan, still heuristic). */
public int[] assignLpt(int[] weights, int m) {
    Integer[] idx = new Integer[weights.length];
    for (int i = 0; i < weights.length; i++) idx[i] = i;
    Arrays.sort(idx, (i, j) -> Integer.compare(weights[j], weights[i]));
    int[] where = new int[weights.length];
    int[] mapped = assignMinLoad(reorder(weights, idx), m);
    for (int k = 0; k < idx.length; k++) where[idx[k]] = mapped[k];
    return where;
}

private int[] reorder(int[] w, Integer[] idx) {
    int[] b = new int[w.length];
    for (int i = 0; i < w.length; i++) b[i] = w[idx[i]];
    return b;
}
```

**Dry run** weights `[4,2,7,1]`, m=2

| i | w | heap before (load,id) | assign | heap after |
| ---: | ---: | --- | ---: | --- |
| 0 | 4 | (0,0),(0,1) | 0 | (4,0),(0,1) |
| 1 | 2 | (0,1),(4,0) | 1 | (2,1),(4,0) |
| 2 | 7 | (2,1),(4,0) | 1 | (9,1),(4,0) |
| 3 | 1 | (4,0),(9,1) | 0 | (5,0),(9,1) |

Assignment `[0,1,1,0]`. Loads 5 and 9.

**TC/SC** `O(n log m)` time, `O(m)` heap.

**If you get stuck in Live Code**
- Scan min each time.
- Then “min-heap of loads.”

---

## 16. Loyal customers from two days of logs — mapped paste **new-grad R2** — UTA unknown — **paste-only** until bible has a URL

**What they actually asked**
Paste new-grad **R2**: **loyal customers** from **two days of logs** (sets/maps). Typical: ids that appear on **both** days. Follow-up often: bought **≥2 distinct products each day**.

**Clarify out loud**
1. Log line = `customerId` or `(customerId, productId)`?
2. Loyal = present on **day1 AND day2**?
3. Distinct products ≥ 2 **per day**?
4. Order of output? Duplicates in a day’s log?
5. n large — stream vs load both days?

**Trick / pattern in one sentence**
`HashSet` of day-1 ids (or `Map<id, Set<product>>`); scan day-2; intersect.

**Why this data structure**
- brute DS: for each day-1 id, scan all of day-2 — `O(n²)`
- optimal DS: HashSet / HashMap
- refuse: sorting both and two-pointer is OK (`O(n log n)`) if they ban hash; nested lists

**Brute**

```java
public List<Integer> loyalBrute(int[] day1, int[] day2) {
    Set<Integer> out = new LinkedHashSet<>();
    for (int a : day1) {
        for (int b : day2) {
            if (a == b) out.add(a);
        }
    }
    return new ArrayList<>(out);
}
```

TC `O(n·m)`. SC `O(min(n,m))`.

**Optimal — ids only**

```java
public List<Integer> loyalCustomers(int[] day1, int[] day2) {
    Set<Integer> s1 = new HashSet<>();
    for (int id : day1) s1.add(id);
    Set<Integer> loyal = new HashSet<>();
    for (int id : day2) {
        if (s1.contains(id)) loyal.add(id);
    }
    return new ArrayList<>(loyal);
}
```

**Optimal — ≥2 distinct products each day**

```java
static final class Event {
    final int customerId, productId;
    Event(int customerId, int productId) {
        this.customerId = customerId;
        this.productId = productId;
    }
}

public List<Integer> loyalTwoProducts(List<Event> day1, List<Event> day2) {
    Map<Integer, Set<Integer>> m1 = index(day1);
    Map<Integer, Set<Integer>> m2 = index(day2);
    List<Integer> ans = new ArrayList<>();
    for (int id : m1.keySet()) {
        if (m1.get(id).size() >= 2
                && m2.containsKey(id)
                && m2.get(id).size() >= 2) {
            ans.add(id);
        }
    }
    return ans;
}

private Map<Integer, Set<Integer>> index(List<Event> day) {
    Map<Integer, Set<Integer>> m = new HashMap<>();
    for (Event e : day) {
        m.computeIfAbsent(e.customerId, k -> new HashSet<>()).add(e.productId);
    }
    return m;
}
```

**Dry run**
Day1 ids `[1,2,2,3]`, day2 `[2,3,4]` → loyal **`[2,3]`**.

Products follow-up:
| id | day1 products | day2 | loyal? |
| ---: | --- | --- | --- |
| 1 | {A} | — | N |
| 2 | {A,B} | {A,C} | **Y** |
| 3 | {X,Y} | {X} | N (day2 only 1) |

**TC/SC** `O(n)` time, `O(n)` sets.

**If you get stuck in Live Code**
- Two HashSets, intersect.
- Then “map to product sets if they want count ≥ 2.”

---

## 17. Logger rate limiter **per-message + global** — mapped paste new-grad BR-adjacent OOD — **short Java** — SD family already in [`04-lld-stack.md`](04-lld-stack.md) §2

**Do not duplicate** the token-bucket / sliding-window / Redis Lua **Second Technical SD**. Independent SDE I live-round count = **1**, **not** UTA. Mentor / YouTube are not a second ask.

**What they actually asked (paste)**
**Log rate limiter OOD**: per-message (same message at most once per T seconds) **and** a **global** cap (at most G logs per second across all messages).

**Clarify:** T=10 default? Global G? Return bool `shouldPrint`? Timestamps non-decreasing?

**Trick:** `HashMap<String, lastTs>` for per-message **and** a deque of recent global timestamps (or a counter + window start). Allow iff **both** pass.

```java
final class MessageAndGlobalLogger {
    private final int perMessageGap;   // e.g. 10
    private final int globalMax;       // e.g. 5
    private final int globalWindow;    // e.g. 1 second
    private final Map<String, Integer> last = new HashMap<>();
    private final Deque<Integer> recent = new ArrayDeque<>(); // global stamps

    MessageAndGlobalLogger(int perMessageGap, int globalMax, int globalWindow) {
        this.perMessageGap = perMessageGap;
        this.globalMax = globalMax;
        this.globalWindow = globalWindow;
    }

    public boolean shouldPrint(int ts, String msg) {
        while (!recent.isEmpty() && ts - recent.peekFirst() >= globalWindow) {
            recent.pollFirst();
        }
        if (recent.size() >= globalMax) return false;
        Integer prev = last.get(msg);
        if (prev != null && ts - prev < perMessageGap) return false;
        last.put(msg, ts);
        recent.addLast(ts);
        return true;
    }
}
```

**Dry run** gap=10, globalMax=2, window=1  
`(1,"a")` Y; `(1,"b")` Y; `(1,"c")` **N** global; `(12,"a")` Y if window expired.

TC `O(1)` amortized per call (deque drops old). SC `O(#unique messages + G)`.

**If they want distributed / token bucket:** stop and open `04-lld-stack.md` §2. Do not present that SD as UTA-default. Ylogx Redis is **−35% cache**, not this limiter.

---

## 18. Basic Calculator then **OOD-extend** — **pattern** — intern analogue bible [DevBrainiac 129](https://devbrainiac.com/blogs/129/amazon-sde-intern-interview-experience-2-rounds-4-coding-problems-selected/) Basic Calculator II `3+2*2`→7 (INTERN, OA-as-R1). Paste: **Basic Calculator then OOD extend** with getMiddle / dist-two-nodes. FTE later-slot = **paste-only** until bible has a URL. Do not stamp LC 224/227 as asked-ids unless they name them.

**What they actually asked**
Evaluate an expression string; then **extend** with objects (new operators, variables) without rewriting the parser as a god switch.

**Clarify out loud**
1. `+ - * /` only? Parentheses? Unary minus?
2. Integers, truncate toward zero?
3. Spaces? Empty?
4. OOD follow-up: add `^`, functions, variables?

**Trick / pattern in one sentence**
Calculator II: one pass, `lastSign` + stack (push on `+`, subtract-push on `-`, pop-multiply on `*`). OOD: `Expr` tree, `Operator` strategy — parser stays, new op is a class.

**Why this data structure**
- brute DS: `eval` / recursion on every split — messy with `*` precedence
- optimal DS: stack of terms so `*` binds tighter without two full passes
- refuse: `scriptEngine`; regex replace

**Brute — Calculator II no parens** (split on `+`/`-` then evaluate `*`/`/` inside — OK as first talk)

```java
public int calculateBrute(String s) {
    s = s.replace(" ", "");
    List<String> terms = new ArrayList<>();
    List<Character> ops = new ArrayList<>();
    int i = 0;
    while (i < s.length()) {
        int j = i;
        while (j < s.length() && s.charAt(j) != '+' && s.charAt(j) != '-') j++;
        terms.add(s.substring(i, j));
        if (j < s.length()) ops.add(s.charAt(j));
        i = j + 1;
    }
    int acc = evalMulDiv(terms.get(0));
    for (int k = 0; k < ops.size(); k++) {
        int v = evalMulDiv(terms.get(k + 1));
        acc = ops.get(k) == '+' ? acc + v : acc - v;
    }
    return acc;
}

private int evalMulDiv(String t) {
    int acc = 1, num = 0;
    char op = '*';
    t = t + "*1"; // flush
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        else {
            if (op == '*') acc *= num;
            else acc /= num;
            op = c;
            num = 0;
        }
    }
    return acc;
}
```

**Optimal — one stack (Calculator II)**

```java
public int calculate(String s) {
    Deque<Integer> st = new ArrayDeque<>();
    int num = 0;
    char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) num = num * 10 + (c - '0');
        boolean end = i == s.length() - 1;
        if ((!Character.isDigit(c) && c != ' ') || end) {
            if (sign == '+') st.push(num);
            else if (sign == '-') st.push(-num);
            else if (sign == '*') st.push(st.pop() * num);
            else if (sign == '/') st.push(st.pop() / num);
            sign = c;
            num = 0;
        }
    }
    int sum = 0;
    for (int v : st) sum += v;
    return sum;
}
```

**Dry run** `3+2*2`

| i | c | num | sign | stack |
| ---: | --- | ---: | --- | --- |
| 0 | 3 | 3 | + | |
| 1 | + | 0 | + | **[3]**  (flush +3) |
| 2 | 2 | 2 | + | |
| 3 | * | 0 | * | **[3,2]** |
| 4 | 2 | 2 | * | |
| end | | | | pop 2 * 2 → **[3,4]** |

Sum **7**.

**OOD extend** — do not grow a 40-case switch. Parse to `Expr`; operators are strategies.

```java
interface Expr {
    int eval();
}

final class NumberExpr implements Expr {
    private final int v;
    NumberExpr(int v) { this.v = v; }
    public int eval() { return v; }
}

interface BinaryOp {
    int apply(int a, int b);
}

final class Add implements BinaryOp { public int apply(int a, int b) { return a + b; } }
final class Sub implements BinaryOp { public int apply(int a, int b) { return a - b; } }
final class Mul implements BinaryOp { public int apply(int a, int b) { return a * b; } }
final class Div implements BinaryOp { public int apply(int a, int b) { return a / b; } }

final class BinaryExpr implements Expr {
    private final Expr left, right;
    private final BinaryOp op;
    BinaryExpr(Expr left, BinaryOp op, Expr right) {
        this.left = left;
        this.op = op;
        this.right = right;
    }
    public int eval() { return op.apply(left.eval(), right.eval()); }
}

/** Add '^' later: new Pow implements BinaryOp; parser maps '^' → new Pow().
 *  Logger-style OCP: Calculator facade does not grow a case for Pow. */
final class Pow implements BinaryOp {
    public int apply(int a, int b) {
        int p = 1;
        for (int i = 0; i < b; i++) p *= a; // Live-Code; say overflow
        return p;
    }
}
```

Parentheses / Calculator I: recursive descent `parseExpr` / `parseTerm` / `parseFactor`, each returning `Expr`. Same tree, `eval()` at the root.

**If you get stuck in Live Code**
- Stack + lastSign for `* /`.
- Then “new operator = new `BinaryOp` class, not a new `else if` in `calculate`.”

---

## INTERN appendix (not full cards)

Intern-only, already weak for this UTA FTE later-slot. **One-liners.** Do not spend the hour here.

| Title | Line |
| --- | --- |
| **Chocolate distribution** | Sort boxes; min `a[i+m-1] - a[i]` over windows of size m (kids). Greedy after sort. `O(n log n)`. |
| **Nuts and bolts** | Match nuts[] to bolts[] with a pivot compare (quick-partition both arrays with the other as pivot). Expected `O(n log n)`. Do not invent an LC id. |
| Zigzag + path between two nodes | INTERN paste. Path = card 6 IO; zigzag = level-order flip `Deque`. |
| Kosaraju / production-ready function / GenAI applications / resume deep dive | INTERN paste. Not a DSA card. |
| House Robber II intern named | Pointer: `02-dsa-r3r4.md` §C.15. |
| Basic Calculator II intern | Card 18 pattern; DevBrainiac 129 OA-as-R1. |

---

## NOT MY FORMAT (one line each)

| Paste block | Flag |
| --- | --- |
| Hyderabad onsite HM + **LC 315** + Locker + BR LP | **NMF-possible** India onsite; Locker already in `04-lld`. Card 11 still full because they named LC 315. |
| US 3×60 / USA 2025 NDA / Chime 4-round / USA 4-round reject | **NMF** US. Heap grilling / log parser SD — not UTA two-DSA. |
| FTC 5-round / FTC 1-year Kahn + kth largest | **NMF** FTC. kth largest already in fragment 02. |
| Playlist mixing LLD / split payment HLD / 5 YOE tester | **NMF** experienced / HLD. |
| SDE-2 HLD | **NMF**. Do not whiteboard Amazon retail. |

---

*End of 09. Job 10454435 still none. Unnamed stays unnamed. No LC 962 on max-sum lists. Login Tracker unverified. Rate Limiter SDE I count = 1, not UTA. OA is not a round.*