5. DSA for R3 and possible R4

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.

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)

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”)

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

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.

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

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).

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]:

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.

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

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

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):

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).

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

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

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:

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.

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.

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

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]:

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.

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

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

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):

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]).

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.

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.

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)

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.

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.

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

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

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:

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.

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

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

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]:

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.

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)

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:

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.

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

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

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.

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

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.

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

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)

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):

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.

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).

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.

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):

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).

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

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

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

Answer 4.

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

If you get stuck in Live Code

• Scan-until-stable brute; then put initial 2s in a queue.
• If minutes are off by one, only increment after a level that actually rotted something.

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

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

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

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.

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.

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

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

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.

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)

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)

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):

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).

public int[] findOrderBrute(int n, int[][] pre) {
    boolean[][] need = new boolean[n][n];
    for (int[] p : pre) need[p[0]][p[1]] = true;
    int[] order = new int[n];
    boolean[] used = new boolean[n];
    return buildOrder(0, order, used, need) ? order : new int[0];
}
private boolean buildOrder(int pos, int[] order, boolean[] used, boolean[][] need) {
    if (pos == order.length) return true;
    for (int c = 0; c < order.length; c++) {
        if (used[c] || !ready(c, used, need)) continue;
        used[c] = true; order[pos] = c;
        if (buildOrder(pos + 1, order, used, need)) return true;
        used[c] = false;
    }
    return false;
}
private boolean ready(int c, boolean[] used, boolean[][] need) {
    for (int p = 0; p < used.length; p++) if (need[c][p] && !used[p]) return false;
    return true;
}

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

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

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:

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 >=.

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

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

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:

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.

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

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

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]:

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.

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

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)

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)

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.

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.

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

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

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

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.

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 ArrayDeques, or one stack + encoded min
• refuse: java.util.Stack (legacy); sorting

Brute

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)

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)

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:

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.

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

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

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)

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.

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).

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

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.

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.

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.

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.

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.

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.”

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.

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

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".

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

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.

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

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

private int[] keysWithMaxFreq(Map<Integer, Integer> freq) {
    int best = 0;
    for (int count : freq.values()) best = Math.max(best, count);
    List<Integer> keys = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        if (entry.getValue() == best) keys.add(entry.getKey());
    }
    int[] answer = new int[keys.size()];
    for (int i = 0; i < keys.size(); i++) answer[i] = keys.get(i);
    return answer;
}

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

Optimal

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

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

Second tree: 5 / \ 2 -5 → sums 2, -5, 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.”

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

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

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.

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.

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

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

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

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.”

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 at Distance K, no parent map — 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)

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

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)

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.

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.

What they actually asked

Paste: design a stack with getMiddle in O(1) (DLL + mid pointer). Push / pop still O(1). Not Min Stack (see Min Stack). 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)

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

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

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.

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

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

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]

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.

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

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)

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

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):

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.

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

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):

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)

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:

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.

public int minMovesFullBoard(int n, int sr, int sc, int er, int ec, int[][] moves) {
    boolean[][] seen = new boolean[n][n];
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[] {sr, sc}); seen[sr][sc] = true;
    int d = 0;
    while (!q.isEmpty()) {
        for (int z = q.size(); z > 0; z--) {
            int[] x = q.poll();
            if (x[0] == er && x[1] == ec) return d;
            for (int[] mv : moves) {
                int r = x[0] + mv[0], c = x[1] + mv[1];
                if (r < 0 || c < 0 || r >= n || c >= n || seen[r][c]) continue;
                seen[r][c] = true; q.add(new int[] {r, c});
            }
        }
        d++;
    }
    return -1;
}

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

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

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.

/** 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

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.

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)

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

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

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

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).

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

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

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

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.”

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

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

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

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:

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.”

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.

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.

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)

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)

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

Sum 7.

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

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.”