Java Live Code. Job 10454435 still none. Unnamed stays unnamed. Full cards for R1/R2 families remain in Answer-BIBLE.md. Later-slot Java (Distance K, max-sum LL): _answers/02-dsa-r3r4.md. Pasted-IE cards (two-leaves path, remove-k-digits, Celebrity BR variant): _answers/09-dsa-new-ies.md. Scan sheet: Cheat-Sheet.md. This chapter is the later-slot pack: Fluency-as-DSA, HM coding, BR coding, and OA-as-R1 patterns worth keeping warm. Labels: IE-asked Standard CS.
Out loud every time: clarify → brute DS → optimal DS + why → code → dry run → TC/SC. ArrayDeque for stack/queue. Max-heap: Comparator.reverseOrder() or Integer.compare(b,a).
LC 7623949 slot labeled GenAI Fluency — this was DSA. Same constraint: AUTA LC 7406809.
Clarify: binary vs n-ary? Return list vs print? “No parent mapping” = no Map<TreeNode,TreeNode>. Passing parent as an argument is still allowed. Target exists? K=0 returns the target itself?
Trick: first walk builds an undirected graph (child edges plus parent edges) without storing a parent map as a field if they forbid it — or recurse with (node, parent, dist) from target after you find it. BFS from target to distance K is the clean O(n) version if graph convert is allowed.
// Build undirected adj, then BFS. If they forbid a parent Map, still OK:
// adj is not a parent map.
void connect(TreeNode u, TreeNode v, Map<TreeNode, List<TreeNode>> adj) {
adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
void build(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> adj) {
if (node == null) return;
if (parent != null) connect(node, parent, adj);
build(node.left, node, adj);
build(node.right, node, adj);
}
List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
Map<TreeNode, List<TreeNode>> adj = new HashMap<>();
build(root, null, adj);
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> q = new ArrayDeque<>();
Set<TreeNode> seen = new HashSet<>();
q.offer(target); seen.add(target);
int d = 0;
while (!q.isEmpty()) {
int sz = q.size();
if (d == k) {
for (TreeNode n : q) ans.add(n.val);
return ans;
}
for (int i = 0; i < sz; i++) {
TreeNode u = q.poll();
for (TreeNode v : adj.getOrDefault(u, List.of())) {
if (seen.add(v)) q.offer(v);
}
}
d++;
}
return ans;
}
TC/SC O(n). If they forbid converting to a graph: DFS from target with parent argument to go up, and a separate downward DFS. If they still want Fluency after the code: one IQVIA sentence, then stop.
If they probe “why not parent HashMap”: because they banned it. Adj list of neighbors is a graph, not a parent map. If they ban that too, parent-as-argument recursion.
LC 6800853 AUTA. OA-as-R1 flag: their R3 may be your already-done second live. Still the right DP family for a later hour. Right/down only unless they say 4-dir (then it is graph, not this DP).
int pathCount(int[][] g) {
int n = g.length, m = g[0].length;
if (g[0][0] == -1 || g[n-1][m-1] == -1) return 0;
int[][] dp = new int[n][m];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == -1) { dp[i][j] = 0; continue; }
if (i > 0) dp[i][j] += dp[i-1][j];
if (j > 0) dp[i][j] += dp[i][j-1];
}
}
return dp[n-1][m-1];
}
int maxReward(int[][] g) { // cells >= 0 reward, -1 trap
int n = g.length, m = g[0].length;
int NEG = Integer.MIN_VALUE / 4;
int[][] dp = new int[n][m];
for (int[] row : dp) Arrays.fill(row, NEG);
if (g[0][0] == -1) return -1;
dp[0][0] = g[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == -1) continue;
if (i > 0 && dp[i-1][j] != NEG)
dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + g[i][j]);
if (j > 0 && dp[i][j-1] != NEG)
dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + g[i][j]);
}
}
return dp[n-1][m-1] == NEG ? -1 : dp[n-1][m-1];
}
Do not BFS this. Number of ways / max on a DAG of right+down is DP. Follow-up they used: count, then rewards. TC O(nm).
Same LC 6800853 AUTA (OA-as-R1 flag). State is the integer itself. Greedy “always subtract the max digit” is plausible; prove or BFS/DP on values down to 0.
int minOps(int n) {
if (n == 0) return 0;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE / 4);
dp[0] = 0;
for (int x = 1; x <= n; x++) {
for (int t = x; t > 0; t /= 10) {
int d = t % 10;
if (d > 0) dp[x] = Math.min(dp[x], dp[x - d] + 1);
}
}
return dp[n];
}
If n is huge (10^18), DP array dies — then BFS from n with a set, or digit-greedy with a proof. Ask constraints first.
LC 7724048 R3/HM. Same slot as LLM questions. Time may be tight — they may accept algorithm only. Still write it.
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>(); // indices, decreasing values
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && nums[st.peek()] < nums[i])
ans[st.pop()] = nums[i];
st.push(i);
}
return ans;
}
Circular (NGE II): loop i = 0 .. 2n-1, index i % n, do not push on second pass. TC O(n).
If they ask Next Permutation in the same family: pivot from the right, smallest larger swap, reverse suffix. AUTA LC 6806195 R2 had Next Permutation similar.
LC 7850431 R3 — dynamic k-th largest (k changes). Same slot as GenAI should/should-not. Min-heap of size k. If k changes, rebuild or use a policy they define — clarify.
class KthLargest {
private final int k;
private final PriorityQueue<Integer> pq; // min-heap
KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<>();
for (int x : nums) add(x);
}
int add(int val) {
pq.offer(val);
if (pq.size() > k) pq.poll();
return pq.peek();
}
}
If they want kth largest of each prefix from index k to n: stream the same heap. TC O(n log k).
Course Schedule II is linked on some posts; bible says do not stamp LC 210 onto LC 6369243 (that one is delivery stations + classes + topo). You still must write both approaches and compare.
boolean canFinishKahn(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
int[] indeg = new int[n];
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; } // clarify direction
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
int seen = 0;
while (!q.isEmpty()) {
int u = q.poll(); seen++;
for (int v : g.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return seen == n;
}
DFS colors: 0 white, 1 gray (on stack = cycle), 2 black. Kahn gives the order for free and is easier to debug in Live Code. DFS is O(1) extra beyond recursion if you do not need the order. Recursion depth can blow for n huge — say that.
LC 6806195 AUTA Bar Raiser coding. Odd-count = k. At-most trick: atMost(k) - atMost(k-1).
int atMost(int[] a, int k) {
int i = 0, ans = 0, odd = 0;
for (int j = 0; j < a.length; j++) {
if (a[j] % 2 == 1) odd++;
while (odd > k) {
if (a[i++] % 2 == 1) odd--;
}
ans += j - i + 1;
}
return ans;
}
int numberOfSubarrays(int[] a, int k) {
return atMost(a, k) - atMost(a, k - 1);
}
LC 8362604 HM: Combine Garlands (ropes concept). Min-heap, always merge two smallest. Overflow → long.
int connectSticks(int[] sticks) {
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int s : sticks) pq.offer((long) s);
long cost = 0;
while (pq.size() > 1) {
long a = pq.poll(), b = pq.poll();
cost += a + b;
pq.offer(a + b);
}
return (int) cost;
}
Same LC 8362604 HM. Sliding window + 26-count.
List<Integer> findAnagrams(String s, String p) {
int[] need = new int[26], win = new int[26];
for (char c : p.toCharArray()) need[c - '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;
}
Ravi’s Round-3 mention (mentor). Meeting Rooms II is the same sweep. Not a Job 10454435 prediction.
int[][] merge(int[][] a) {
Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
List<int[]> out = new ArrayList<>();
for (int[] iv : a) {
if (out.isEmpty() || out.get(out.size()-1)[1] < iv[0]) out.add(iv.clone());
else out.get(out.size()-1)[1] = Math.max(out.get(out.size()-1)[1], iv[1]);
}
return out.toArray(new int[0][]);
}
int minPlatforms(int[] arr, int[] dep) {
Arrays.sort(arr); Arrays.sort(dep);
int i = 0, j = 0, cur = 0, max = 0, n = arr.length;
while (i < n && j < n) {
if (arr[i] <= dep[j]) { cur++; max = Math.max(max, cur); i++; }
else { cur--; j++; }
}
return max;
}
Bhavya Hyd Interview 2 (not Login Tracker). HashMap + doubly linked list. O(1) get/put.
class LRUCache {
static class Node { int k, v; Node prev, next; Node(int k, int v) { this.k=k; this.v=v; } }
private final int cap;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0,0), tail = new Node(0,0);
LRUCache(int capacity) {
cap = capacity; 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 key) {
Node n = map.get(key);
if (n == null) return -1;
remove(n); addFront(n); return n.v;
}
void put(int key, int value) {
if (map.containsKey(key)) remove(map.get(key));
Node n = new Node(key, value);
map.put(key, n); addFront(n);
if (map.size() > cap) {
Node lru = tail.prev; remove(lru); map.remove(lru.k);
}
}
}
Login Tracker mentor (unverified): same DLL, newLogin moves to tail, getOldest peeks head. Do not claim a first-hand UTA ask.
Older Amazon/GFG classic. Two-pointer elimination, then verify. Do not cite an unverified 2026 Hyderabad AUTA BR URL.
int celebrity(int[][] m) {
int n = m.length, i = 0, j = n - 1;
while (i < j) {
if (m[i][j] == 1) i++; // i knows j → i not celeb
else j--; // i does not know j → j not celeb
}
for (int k = 0; k < n; k++) {
if (k == i) continue;
if (m[i][k] == 1 || m[k][i] == 0) return -1;
}
return i;
}
Family of Longest Substring Without Repeating (already in your R1/R2 bank). HashMap + two pointers.
int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> freq = new HashMap<>();
int i = 0, best = 0;
for (int j = 0; j < s.length(); j++) {
freq.merge(s.charAt(j), 1, Integer::sum);
while (freq.size() > k) {
char c = s.charAt(i++);
freq.put(c, freq.get(c) - 1);
if (freq.get(c) == 0) freq.remove(c);
}
best = Math.max(best, j - i + 1);
}
return best;
}
LC 6881058 Bar Raiser (post is BR-only). Family of switching lists at equal-value nodes. Not LC 962. Not LC 6369243 (that post stays unnamed). Full Java: _answers/02-dsa-r3r4.md card 7c.
Clarify: both lists sorted? Common means equal val (switch points)? Return a new list or relink? Duplicate commons?
// Walk both lists. Between commons, keep the segment with larger sum.
// Add the common node once. After the last common, keep the larger tail.
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;
}
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;
}
Example: 1-3-30-90-120-240-511 vs 0-3-12-32-90-125-240-250 → 1-3-12-32-90-125-240-511.
Not a Job 10454435 list. Fluency default remains Distance K (this chapter). OA-as-R1: their “R3” may be your already-done R2. Full brute+optimal Java is in the fragment (~2k lines).
| # | Title | Reliability |
|---|---|---|
| 1 | Max path sum between two leaves | paste-only (OA numbering unknown) |
| 2 | Remove k digits → smallest number | bible R2 + DesiQnA named LC 402 |
| 3–5 | Most frequent subtree sum; LIP matrix; even Kth ancestor | GFG 2021-4 opened, year-out |
| 6 | Distance two nodes, no parent pointers | Dist-K family opened; this IO paste-only |
| 7 | Stack getMiddle O(1) | paste-only |
| 8 | Next Permutation | paste GenAI slot; bible similar on AUTA R2 |
| 9 | Celebrity two-pointer | Standard CS; 2026 AUTA BR = paste-only |
| 11 | LC 315 (candidate named) | Hyderabad onsite, NMF-possible |
| 12 | Knight generalized 10k board | unnamed paste; LC 6629948 is their R2 knight |
| 13–16 | Subset combination; min-heap servers; loyal-customer logs | paste-only / US NMF mix |
| 14 | Device capabilities (small interfaces) | OOD, their R2 analogue |
| 17 | Logger per-message + global | short Java; Rate Limiter count stays 1 |
House Robber II = fragment 02. Max-sum switching lists = card 7c above, not this file. Intern chocolate/nuts-bolts = appendix only.
Also keep warm from Answer-BIBLE §1: merge k lists, rotten oranges multi-source BFS, max rectangle histogram, House Robber II, Open the Lock BFS, sliding window maximum deque. Igreaper Rotten + Maximal Rectangle was OA-as-R1 “R3” = your R2 analogue.