User-table cards
Every row is a full card: why the wording forces the pattern, what brute enumerates and why it is brute, optimal Java DS + time + space, when the clue is a liar.
Templates from Cheat-Sheet §4 when one exists.
Amazon examples only when §5.A, TUF questions-asked.md, or chapter 05 already named them.
"contiguous subarray/substring" → Sliding Window / Prefix Sum Standard CS
Why you think of this. Contiguous means one interval [L,R] in the original order — not a subsequence you may skip. If the predicate is monotonic when you extend or shrink (longer is “more invalid,” shorter is “more valid”), a sliding window is legal. If they want an exact numeric target and values can be negative or zero, the invariant is a prefix difference prefix[R] − prefix[L−1], not a shrink.
Brute. All pairs of ends: for each L, expand R and rescan or re-add. Time O(n²) (or O(n³) if you rescan the segment). Space O(1). It is brute because adjacent intervals share n−1 elements and you recompute them from scratch.
Optimal. Window: two ints L,R plus a freq HashMap if the predicate is a count. Exact sum: HashMap<Long,Integer> prefix→count or first index. Time O(n). Space O(n) or O(Σ).
int left = 0, ans = 0;
Map<Character, Integer> cnt = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
while (/* invalid */) {
char d = s.charAt(left++);
cnt.put(d, cnt.get(d) - 1);
if (cnt.get(d) == 0) cnt.remove(d);
}
ans = Math.max(ans, right - left + 1);
}
Liar / neighbor. Subsequence is DP or two-pointer on a sorted copy — the window assumes no holes. “Contiguous” + exact k with negatives is prefix+map, not this shrink loop.
Amazon IE example: Count Number of Nice Subarrays, AUTA BR, LC 6806195 — chapter 05. Count Complete Subarrays, GFG 2025 R1 (OA-as-R1 remap). Longest subarray sum = 0, LC 7850431 R2. Other loops; not Job 10454435.
"longest/shortest subarray satisfying condition" → Sliding Window Standard CS
Why you think of this. You want the extreme length of one contiguous interval whose running state is valid. Longest: expand R always, shrink L until valid, then record R−L+1. Shortest: expand until valid, then shrink while still valid, record the tight length. The predicate must be monotonic — adding an element never helps a “too-full” window become valid.
Brute. For every L, grow R until the condition flips; or check all O(n²) intervals. Time O(n²). Space O(1) or O(Σ) for a freq map you rebuild. Brute because each L restarts the count you already had at L−1.
Optimal. Two pointers + the smallest state that decides validity (int sum, HashMap distinct, int[] last-seen). Each index enters and leaves at most once. Time O(n). Space O(Σ).
int left = 0, best = Integer.MAX_VALUE; // shortest valid
for (int right = 0; right < n; right++) {
add(a[right]);
while (valid()) {
best = Math.min(best, right - left + 1);
remove(a[left++]);
}
}
return best == Integer.MAX_VALUE ? 0 : best;
Liar / neighbor. “Longest subsequence” is LIS / DP, not a window. “Shortest subarray with exact sum k” and negatives → prefix+map of first index, because shrinking can jump over the only hit. Count of such subarrays is a different IO than longest/shortest.
Amazon IE example: Longest Repeating Character Replacement variation, candidate linked LC 424, Prince R1 (Job 3057703 on that post — not 10454435). Nice Subarrays is a count, not a longest — see exactly K.
"exact sum" → Prefix Sum / HashMap Standard CS
Why you think of this. Exact is a difference of two prefixes, not a “too big / shrink” rule. If prefix[R] − prefix[L−1] = target, then prefix[L−1] = prefix[R] − target. A HashMap remembers which prefix values you have already seen (count, or first index for length). All-positive + exact can still use a window; the wording “exact” alone does not license shrink until you know the sign.
Brute. All L,R, sum the segment. Time O(n²) with a running add, O(n³) if you rescan. Space O(1). Brute because you ignore that every sum is a prefix subtraction.
Optimal. HashMap<Long,Integer>: key = prefix, value = count (how many) or first index (longest/shortest). Seed 0 → 1 (or index −1) so a prefix that itself equals the target counts. Time O(n) average. Space O(n).
Map<Long, Integer> first = new HashMap<>();
first.put(0L, 1);
long sum = 0;
int ans = 0;
for (int x : a) {
sum += x;
ans += first.getOrDefault(sum - k, 0);
first.put(sum, first.getOrDefault(sum, 0) + 1);
}
Liar / neighbor. “At most sum K” with positives is a window. Pair sum of two elements is two-sum, not a subarray. Subsequence sum is knapsack DP.
Amazon IE example: longest subarray sum = 0, LC 7850431 R2. TUF live: Maximum Size Subarray Sum Equals k; Count Subarrays with Given Sum. Do not invent a numeric id if they only said “exact sum.”
"subarray sum = k" → Prefix Sum + HashMap Standard CS
Why you think of this. A subarray is contiguous, and “= k” is exact. The count of earlier prefixes equal to currentPrefix − k is the count of valid L for this R. Use long keys — Java int prefixes overflow on n·1e9.
Brute. Nested L,R with a running sum. Time O(n²). Space O(1). Dies at n = 1e5. It is brute because you do not reuse prefix values.
Optimal. One pass, HashMap<Long,Integer> prefix→how many times seen so far (update after the query so you do not pair an index with itself unless k=0 is intended). Time O(n) average. Space O(n).
Map<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1);
long prefix = 0;
int ans = 0;
for (int x : a) {
prefix += x;
ans += seen.getOrDefault(prefix - k, 0);
seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
}
return ans;
Liar / neighbor. All-positive + “longest / shortest with sum ≥ k” can be a window. Sum = k on a subsequence is subset-sum DP. Longest sum 0 stores first index, not count — Cheat-Sheet §4.2.
Amazon IE example: longest subarray sum = 0, LC 7850431 R2 (first-index map). TUF Count Subarrays with Given Sum; Maximum Size Subarray Sum Equals k. Other loops; not Job 10454435.
"at most K" → Sliding Window Standard CS
Why you think of this. “At most” is a budget you may undershoot. Adding an element spends budget; removing refunds it. Once the window is over budget, every larger window that keeps the same L is also invalid — so you may slide L forward and never put it back. That monotonicity is the whole pattern.
Brute. All intervals, count the resource (distinct, replacements, odds, sum). Time O(n²). Space O(Σ) if you rebuild a set each time. Brute because validity of [L,R] is determined by [L,R−1] plus one add.
Optimal. L,R + a counter (int or HashMap). Expand R; while over K, evict a[L++]. For count of at-most-K windows, add R−L+1 after each shrink. Time O(n). Space O(Σ).
int atMost(int[] a, int k) {
int left = 0, ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int right = 0; right < a.length; right++) {
cnt.put(a[right], cnt.getOrDefault(a[right], 0) + 1);
while (cnt.size() > k) {
int d = a[left++];
cnt.put(d, cnt.get(d) - 1);
if (cnt.get(d) == 0) cnt.remove(d);
}
ans += right - left + 1;
}
return ans;
}
Liar / neighbor. “Exactly K” is not this return value — subtract atMost(K−1). “At least K” is often total − atMost(K−1) or a different shrink. Exact sum k with negatives is not at-most-window.
Amazon IE example: Nice Subarrays uses at-most-K odds as the building block — chapter 05, LC 6806195. Longest Repeating Character Replacement variation (at most K replacements), Prince, LC 424 linked.
"exactly K distinct" → window(≤K) − window(≤K−1) Standard CS
Why you think of this. Exactly-K is not monotonic by itself: growing a window can go from K to K+1 (bad) or stay at K (still exact). The count of windows with at most K distinct is monotonic, and exactly(K) = atMost(K) − atMost(K−1). Same identity for exactly-K odds, exactly-K zeros, etc.
Brute. For every L,R build a set. Time O(n²). Space O(Σ). Brute because you re-count distinct from scratch and because you treat “exact” as a third loop instead of a difference of two legal windows.
Optimal. Two calls of the at-most window above (or one function with parameter K). Time O(n). Space O(Σ).
int exactlyKDistinct(int[] a, int k) {
if (k <= 0) return 0;
return atMost(a, k) - atMost(a, k - 1);
}
Liar / neighbor. Longest window with exactly K distinct is a different IO — you may shrink to restore K and track max length, still one window, no subtraction. Do not subtract if they asked for the longest, not the count.
Amazon IE example: Count Number of Nice Subarrays (exactly K odd) — LC 6806195, chapter 05. Count Complete Subarrays, GFG 2025 R1 (OA-as-R1). Variation of Find All Anagrams is a fixed-window freq twin — chapter 05, LC 8362604 AUTA HM, not this subtract formula.
"minimum/maximum in every window" → Monotonic Deque Standard CS
Why you think of this. You need the extreme of each contiguous block of width k (or variable, but still a sliding interval). A heap of the window works but pays log and lazy deletes. A deque of indices in decreasing a[i] stores only candidates that could still be the max: a new larger value kills everyone behind it; an index that left the window dies at the front.
Brute. For each window start, scan k elements. Time O(nk). Space O(1). Brute because you re-scan k−1 shared cells every step. Dies when n and k are both large.
Optimal. ArrayDeque<Integer> of indices, decreasing values for max (increasing for min). Each index is offered and polled at most once. Time O(n). Space O(k).
Deque<Integer> dq = new ArrayDeque<>(); // indices, decreasing a[i]
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) windowMax[i - k + 1] = a[dq.peekFirst()];
}
Liar / neighbor. Next greater element (not “in every window”) is a monotonic stack, one answer per index, not per window. Heap of size k is correct but slower — say that if they ask “why not PQ.”
Amazon IE example: Sliding Window Maximum (deque) — GFG sde1-off-campus story wrap and their R3 on 1-year-experienced-2 — chapter 05. Not a 10454435 forecast.
"next greater/smaller" → Monotonic Stack Standard CS
Why you think of this. For each i you want the nearest j > i with a[j] > a[i] (or <). While a decreasing stack of unresolved indices sits there, a new larger value is exactly the “next greater” of everyone smaller on top. Each index pops at most once — that is the O(n) invariant. Store indices so you can write into ans[i].
Brute. For each i, scan i+1..n−1. Time O(n²). Space O(1) extra. Brute because you restart the scan and ignore that a later greater also serves earlier smaller values.
Optimal. ArrayDeque<Integer> indices, decreasing values for next greater. Time O(n). Space O(n).
int n = a.length;
int[] nge = new int[n];
Arrays.fill(nge, -1);
Deque<Integer> st = new ArrayDeque<>(); // indices, decreasing values
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && a[st.peek()] < a[i]) nge[st.pop()] = a[i];
st.push(i);
}
Liar / neighbor. Window maximum is a deque with an expiry i−k, not “next.” Next greater frequency (older GFG remainder) compares counts, not values. Circular next-greater walks 2n with i % n — see circular. Contribution of subarray minima uses next-smaller left and right, not only next-greater.
Amazon IE example: Next Greater Element, mapped R3 HM, LC 7724048 — chapter 05. Daily Temperatures–like monotonic stack, Naina UTA R1. TUF live: Next Greater Element. similar to Sum of Subarray Minimums, Akash AUTA R2 (contribution, not NGE IO).
"remove digits to get smallest number" → Monotonic Stack Standard CS
Why you think of this. You may delete k digits; the remaining digits stay in order (a subsequence of the digit string). The smallest number is the lexicographically smallest increasing-as-much-as-possible stack: while the previous digit is larger than the current one and you still have removals, pop. Leading zeros are stripped at the end. This is “next smaller to the left” in disguise — a greedy monotonic stack, not a heap of digits (heap would reorder).
Brute. Choose which k positions to delete, compare remaining strings. Time O(C(n,k)·n). Space O(n). Brute because most deletions are dominated: if a[i] > a[i+1], you should delete a[i] before later equal choices.
Optimal. ArrayDeque<Character> or StringBuilder as a stack. Time O(n). Space O(n).
Deque<Character> st = new ArrayDeque<>();
int rem = k;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
while (rem > 0 && !st.isEmpty() && st.peek() > c) { st.pop(); rem--; }
st.push(c);
}
while (rem-- > 0) st.pop();
StringBuilder sb = new StringBuilder();
for (char c : st) sb.append(c); // ArrayDeque iterates bottom→top
while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.toString();
Liar / neighbor. “Smallest number by rearranging” is sort, not stack. Remove k to get the largest number flips the inequality. Connect-ropes / digit DP is a different “minimum number” wording.
Amazon IE example: Remove K Digits, LC 6630775 R2 (OA-as-R1 phone on that post) — chapter 05. Candidate on DesiQnA named LC 402. Do not stamp 402 unless they name it.
"top K" → Heap Standard CS
Why you think of this. You need the K best by some score (frequency, value, distance), not a full sort of n if they only want K. A min-heap of size K keeps the current K winners; a new item beats the root and the root falls out. Full sort is correct and O(n log n); heap is O(n log K). HashMap first if the score is a frequency.
Brute. Sort all unique keys by score and take K. Time O(n + u log u). Space O(u). It is brute-ish when u ≈ n and K ≪ n — you paid a full sort to throw away n−K rows.
Optimal. HashMap to count if needed, then PriorityQueue min-heap of size K (pair or custom compare). Time O(n log K). Space O(u + K).
Map<Integer, Integer> freq = new HashMap<>();
for (int x : a) freq.put(x, freq.getOrDefault(x, 0) + 1);
PriorityQueue<int[]> min = new PriorityQueue<>((p, q) -> Integer.compare(p[1], q[1]));
for (var e : freq.entrySet()) {
min.offer(new int[]{e.getKey(), e.getValue()});
if (min.size() > k) min.poll();
}
Liar / neighbor. One-shot Kth largest without the other K−1 values is quickselect / size-K heap — same heap, different IO. Merge K sorted lists is a heap of K heads, not “top K values from one array.” Connect ropes is a heap but you merge until one remains, not stop at K.
Amazon IE example: Top K Frequent Elements, LC linked, AUTA R1 LC 7406809 — chapter 05. TUF live Top K Frequent Elements. Combine Garlands / Connect Sticks is the ropes neighbor — chapter 05.
"Kth largest" → Min Heap / Quickselect Standard CS
Why you think of this. You want one order statistic, not a sorted array. A min-heap of size K: the root is the Kth largest among what you have seen (K largest sit in the heap; the smallest of those is the Kth). Quickselect partitions like quicksort and is average O(n). If K changes online (inserts), you keep the heap between queries.
Brute. Sort descending, pick index K−1. Time O(n log n) per query. Space O(n) if you copy. Brute when they stream updates or n is 1e5 and they want average linear.
Optimal. PriorityQueue min-heap size K — Time O(n log K), Space O(K). Quickselect — Time average O(n), worst O(n²) unless you shuffle, Space O(1) extra. Dynamic: same heap, offer/poll on each add.
PriorityQueue<Integer> min = new PriorityQueue<>();
for (int x : a) {
min.offer(x);
if (min.size() > k) min.poll();
}
return min.peek(); // kth largest
Liar / neighbor. Top K frequent is “K items,” not “the Kth score.” Median is two heaps, not size K. “Kth ancestor” is binary lifting / parent jump — a tree clue, not this heap.
Amazon IE example: dynamic k-th largest (k changes), mapped R3, LC 7850431 — chapter 05. Median of Data Stream is the two-heap sibling — LC 8362604 AUTA R1.
"duplicates / frequencies" → HashMap / HashSet Standard CS
Why you think of this. You need O(1) “have I seen this key” or “how many times.” A Set answers existence; a Map answers count. Sort+scan is O(n log n) and loses original index unless you store pairs. Frequency is the first hop before top-K, anagrams, or “first unique.”
Brute. For each i, scan 0..i−1. Time O(n²). Space O(1). Brute because equality is a hash, not a linear search.
Optimal. HashSet for seen; HashMap<T,Integer> for counts; int[256] or int[26] if the alphabet is tiny. Time O(n) average. Space O(u).
Map<Integer, Integer> freq = new HashMap<>();
for (int x : a) freq.put(x, freq.getOrDefault(x, 0) + 1);
Set<Integer> seen = new HashSet<>();
for (int x : a) if (!seen.add(x)) { /* duplicate */ }
Liar / neighbor. Duplicate in a window of size k is Map + sliding expire, not a global set. Anagrams group by sorted key or count-signature, not “any duplicate.” Longest consecutive sequence is HashSet of values then stretch — still a set, but the stretch is the real work.
Amazon IE example: Top K Frequent (count then heap), LC 7406809. Group anagrams small modifications, Sachin named LC 49. count good-review words; sort reviews, LC 6570344 R1 (HashMap internals asked after — bible §5.F).
"pair sum" → HashMap / Two Pointer Standard CS
Why you think of this. Two indices, one target. If the array is unsorted and you may not reorder, store target − a[i] in a HashMap as you walk (one pass). If you may sort, or it already is sorted, two pointers from the ends: too small → left++, too big → right--. The map remembers complements; the pointers use monotonicity of a sorted sum.
Brute. All pairs. Time O(n²). Space O(1). Brute because each i only needs “does complement exist,” not a full scan.
Optimal. Unsorted: HashMap<Integer,Integer> value→index. Time O(n) average, Space O(n). Sorted: two ints. Time O(n) after sort O(n log n), Space O(1).
Map<Integer, Integer> idx = new HashMap<>();
for (int i = 0; i < a.length; i++) {
Integer j = idx.get(target - a[i]);
if (j != null) return new int[]{j, i};
idx.put(a[i], i);
}
Liar / neighbor. Pair is two elements, not a subarray of length ≥ 3 — that is prefix-sum. Three-sum is sort + pair. Pair sum modulo m is Map of remainders. Closest pair-sum (older GFG remainder) is two-pointer after sort, not “any pair = k.”
Amazon IE example: older GFG remainder lists closest pair-sum (year-out, not UTA-default). Vaishali R2 “array two-pointer” is unnamed — do not stamp an LC id. TUF / bible do not name a classic two-sum title as a 2025–26 live in §5.A.
"sorted array + pair" → Two Pointer Standard CS
Why you think of this. Sorted + two ends: if a[L]+a[R] is short, every pair that still uses L needs a larger partner — L must advance. If it is large, R must retreat. You never need a HashMap unless they forbid reusing the sorted order (or want original indices and you did not keep them).
Brute. Nested loops or a map on an already-sorted array. Time O(n²) or O(n) with an extra map. Space O(1) nested, or O(n) if you still allocate the map. The map is wasted space; the nested loops ignore the sort.
Optimal. Two ints L,R. Time O(n). Space O(1). If you sorted a copy to restore indices, Space O(n) for the copy of pairs.
int l = 0, r = a.length - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) { /* record; l++; r--; if distinct pairs */ }
else if (s < target) l++;
else r--;
}
Liar / neighbor. Sorted + rotated is binary search for the pivot, not two-pointer pair (Search in Rotated Sorted Array is in §5.A — different clue). Sorted + “pair with difference k” still two-pointer or two-pointer+set. Sorted + subarray sum = k with positives is window, not pair.
Amazon IE example: Search in Rotated Sorted Array is the liar sibling (LC 6461439; LC 8014509) — do not use this pair loop. Single element in sorted array, LC 6475219 R2, is XOR / mid-parity BS, not pair sum.
"merge intervals" → Sort + Greedy Standard CS
Why you think of this. Overlap is not visible until intervals are ordered by start. After that, one linear scan: if the next start is past the current end, emit a new interval; else extend the end. That is greedy — the merged end is the max end you have seen in the current cluster. A heap is unnecessary unless you also need “how many rooms” (overlap count).
Brute. Repeatedly pick an interval and scan the rest for overlap, mark merged. Time O(n²). Space O(n). Brute because sort makes overlap a local question against only the last emitted interval.
Optimal. Arrays.sort by start, List<int[]> output. Time O(n log n). Space O(n) for the answer (or O(1) extra if you write in place).
Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
List<int[]> out = new ArrayList<>();
for (int[] cur : a) {
if (out.isEmpty() || out.get(out.size() - 1)[1] < cur[0]) out.add(cur.clone());
else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
}
Liar / neighbor. Insert one interval into an already-merged list is a walk, not a full re-sort if they promised sorted. Meeting-room count is sort + heap of ends. Min arrows to burst balloons is sort + greedy end, same family, different IO.
Amazon IE example: Merge Intervals, GFG fresher R1 (with Burning Tree) — chapter 05. Min Arrows to Burst Balloons, Deepak R1 (snippet). Not UTA-default; not 10454435.
"meeting overlap" → Sort / Heap Standard CS
Why you think of this. A room (or platform) is freed when the earliest end ≤ the next start. Sort meetings by start. A min-heap of end times is the set of busy rooms; if the smallest end is ≤ start, reuse that room (poll), then offer the new end. The heap size is the answer (Meeting Rooms II / min platforms). Two arrays of starts and ends sorted separately also work: two pointers, +1 on start, −1 on end.
Brute. For each meeting, scan all others for overlap and color rooms. Time O(n²). Space O(n). Brute because you only need the earliest room to free, not a full conflict matrix.
Optimal. Sort O(n log n) + PriorityQueue<Integer> of ends. Time O(n log n). Space O(n). Two-pointer starts/ends: same time after two sorts, Space O(n) if you copy ends.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> ends = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!ends.isEmpty() && ends.peek() <= iv[0]) ends.poll();
ends.offer(iv[1]);
}
return ends.size();
Liar / neighbor. Merge intervals asks for the union segments, not the peak concurrency. Can-attend-all is “heap size == 1” or “no overlap after sort” — a boolean, not a count. Reschedule for free time (TUF) is a different IO on the same sort.
Amazon IE example: min platforms, Prabhash R1; GFG off-campus-10 their R3 — chapter 05. TUF Meeting Rooms II. Mentor extra-DSA in amazon-sde1-interview-prep.md is mentor, not first-hand 10454435.
"dependency/prerequisite" → Topological Sort Standard CS
Why you think of this. Directed edges “must do A before B.” A legal order is a topological order. Kahn: start with indegree 0, peel, reduce neighbors. The queue is the current set of unlocked tasks. DFS post-order also works if you detect a back edge.
Brute. Try all permutations and test the edge list. Time O(n! · E). Space O(n). Brute because most permutations are killed by a single leftover edge you could have peeled in linear time.
Optimal. List<List<Integer>> adj, int[] indeg, ArrayDeque<Integer>. Time O(V+E). Space O(V+E).
int[] indeg = new int[n];
for (int u = 0; u < n; u++) for (int v : adj.get(u)) indeg[v]++;
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
boolean cycle = order.size() < n;
Liar / neighbor. Undirected “connected” is not a prerequisite graph — DSU/DFS. Weighted “cheapest with at most K stops” is Dijkstra / BFS-on-stops, not plain Kahn. Delivery-stations + classes still Kahn, but do not stamp LC 210 on LC 6369243.
Amazon IE example: Course Schedule II, LC 210 linked on LC 6282609 only — chapter 05. Delivery stations / parcels + classes + topological sort, LC 6369243 R2. TUF topological sort / Kahn (modified; handle cycles).
"can finish courses/tasks?" → Directed Cycle / Topological Sort Standard CS
Why you think of this. You can finish iff the directed graph is a DAG — iff Kahn emits all n nodes, iff DFS never sees a gray (in-stack) back edge. The boolean is the cycle test; the order is a bonus they may also want.
Brute. For each node, DFS a path set and hope you do not revisit; restart without memo. Time exponential on dense DAGs. Space O(n). Brute because you re-explore the same suffix.
Optimal. Kahn: Time O(V+E), Space O(V+E), answer order.size()==n. DFS colors WHITE/GRAY/BLACK: same bounds; GRAY neighbor ⇒ cycle.
boolean canFinish(int n, int[][] pre) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : pre) { adj.get(e[1]).add(e[0]); indeg[e[0]]++; }
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 : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return seen == n;
}
Liar / neighbor. Undirected cycle is parent-pointer / DSU, not indegree. “Finish with time / parallelism” is DP on the DAG (longest path), not the boolean. Bipartite “enemies not same group” is 2-color, not course schedule.
Amazon IE example: same Course Schedule II family as above (LC 6282609; do not copy 210 onto 6369243). TUF Kahn modified to handle cycles.
"connected components" → DFS / BFS / DSU Standard CS
Why you think of this. An undirected (or “can reach both ways”) relation partitions nodes. DFS/BFS flood from an unseen node and increment the component count. DSU unions the given edges and counts roots — better when the input is an edge list and you never build adj.
Brute. Warshall on an n×n matrix, then cluster rows. Time O(n³). Space O(n²). Brute when they only gave m edges.
Optimal. Adj + boolean[] vis DFS/BFS: Time O(V+E), Space O(V+E). DSU: Time ~O(E α(V)), Space O(V). Grid islands: DFS in place, Time O(mn), Space O(mn) recursion worst (or BFS O(mn)).
void dfs(char[][] g, int i, int j) {
if (i<0||j<0||i>=g.length||j>=g[0].length||g[i][j]!='1') return;
g[i][j] = '0';
dfs(g, i+1, j); dfs(g, i-1, j); dfs(g, i, j+1); dfs(g, i, j-1);
}
Liar / neighbor. Strongly connected (directed) is Kosaraju/Tarjan, not this flood. Bipartite components still flood, but you 2-color. Number of islands is this card; rotten oranges is multi-source BFS distance, not a count of components.
Amazon IE example: Number of Islands, AUTA 2026 LC 8362604 R1 and Deepak R1. TUF Most Stones Removed (similar) is DSU on row/col. chapter 05 islands live inside grid cards.
"shortest path, unweighted graph" → BFS Standard CS
Why you think of this. Every edge costs 1. The first time BFS reaches a node is the minimum hop count — levels are distances. DFS can find a path, not the shortest. Dijkstra also works with weight 1 but the PQ is wasted.
Brute. DFS all paths, keep min length. Time exponential. Space O(V) recursion. Brute because you re-walk suffixes and because a longer path to a node is never useful later.
Optimal. ArrayDeque of nodes (or int[]{i,j,d} on a grid), boolean[] vis mark on enqueue. Time O(V+E). Space O(V).
Queue<Integer> q = new ArrayDeque<>();
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
q.offer(src);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
Liar / neighbor. Positive weights → Dijkstra. Negative weights → Bellman-Ford. “At most K stops” + prices is a different state (node, stops). Unweighted longest simple path is NP-hard / DP-on-DAG, not BFS.
Amazon IE example: Word Ladder, LC 7035289 AUTA R2; TUF Word Ladder II. Rotten Oranges (multi-source BFS minutes) — chapter 05. similar to Open the Lock, LC 7623949 — chapter 05. Minimum Knight Moves, LC 6629948 R2.
"explore all reachable nodes" → DFS / BFS Standard CS
Why you think of this. They want the set (or a yes/no “can I reach all”), not a shortest hop. Either search is correct. DFS is less code on a grid; BFS if they later add “in d steps.” Mark visited so you do not explode on cycles.
Brute. Recurse without a visited set. Time infinite on a cycle, or exponential on a DAG with many merges. Space O(V) stack (or unbounded if you cycle). That is why it is brute / wrong — you treat a graph like a tree.
Optimal. boolean[] vis or a Set. DFS or ArrayDeque BFS. Time O(V+E) for the reachable subgraph. Space O(V).
void dfs(int u, boolean[] vis, List<List<Integer>> adj) {
vis[u] = true;
for (int v : adj.get(u)) if (!vis[v]) dfs(v, vis, adj);
}
boolean allReachable(int n, List<List<Integer>> rooms) {
boolean[] vis = new boolean[n];
dfs(0, vis, rooms);
for (boolean b : vis) if (!b) return false;
return true;
}
Liar / neighbor. “Explore” + “shortest” → BFS only. Keys-and-rooms is this card. Detonate bombs is reachability on a directed geometric graph — still DFS/BFS, not DSU unless the relation is undirected.
Amazon IE example: Keys and Rooms, named, LC 6491881 R2. Number of Islands is components (count starts), not one flood from 0. Detonate the Maximum Bombs, LC 7724048 R1.
"cycle in undirected graph" → DFS parent / BFS parent / DSU Standard CS
Why you think of this. In an undirected graph, the edge back to your parent is not a cycle. A visited neighbor that is not the parent is a cycle. DSU: union each edge; if both ends already share a parent, that edge closes a cycle. Do not use directed 3-color without treating the parent — you will flag every edge twice.
Brute. Enumerate simple paths / use a stack set as if directed. Easy to mis-count the parent edge. Time exponential if you list cycles. Space O(V) for the path set. Brute because the first extra visited neighbor is enough for yes/no.
Optimal. DFS/BFS + parent: Time O(V+E), Space O(V). DSU on the edge list: Time ~O(E α(V)), Space O(V).
boolean dfs(int u, int parent, boolean[] vis, List<List<Integer>> adj) {
vis[u] = true;
for (int v : adj.get(u)) {
if (!vis[v]) { if (dfs(v, u, vis, adj)) return true; }
else if (v != parent) return true;
}
return false;
}
Liar / neighbor. Directed cycle ≠ parent test — a back edge to an ancestor on the recursion stack (gray). “Most stones” DSU is components, not a cycle question. Tree = connected + acyclic; if they already said “tree,” do not cycle-check unless they asked to validate.
Amazon IE example: omitted — §5.A / TUF / chapter 05 do not name a live “detect undirected cycle” title. TUF Most Stones (similar) is DSU components, not this yes/no.
"cycle in directed graph" → DFS colors / Kahn Standard CS
Why you think of this. A directed cycle is a back edge to a node still on the DFS stack (GRAY). BLACK is done and safe. Kahn’s leftover nodes with indegree > 0 after peeling are exactly the cycle participants (or nodes that depend on them). Parent-pointer from the undirected card is the liar here.
Brute. Walk every path with a set; restart. Time exponential. Space O(V). Brute because colors memoize “this node is not on a cycle from here.”
Optimal. int[] color 0/1/2 or Kahn seen < n. Time O(V+E). Space O(V+E).
boolean dfsCycle(int u, int[] col, List<List<Integer>> adj) {
col[u] = 1; // GRAY
for (int v : adj.get(u)) {
if (col[v] == 1) return true;
if (col[v] == 0 && dfsCycle(v, col, adj)) return true;
}
col[u] = 2;
return false;
}
Liar / neighbor. Undirected parent test will miss directed cycles that are not “not-parent.” Topo order when they also want the sequence — Kahn. Currency converter / evaluate division is a weighted graph, not a cycle-yes question (but a cycle of factors can mean inconsistency — only if they ask).
Amazon IE example: Course Schedule II family — chapter 05, LC 6282609. Delivery stations + topo, LC 6369243 (entities + Kahn; not an LC 210 stamp).
"tree" → DFS / BFS Standard CS
Why you think of this. A tree is connected and acyclic. From any node there is one path to any other. Recursion on left/right (binary) or on the adj list with a parent argument (n-ary / undirected tree). BFS is level order / width. You do not need a visited set on a binary tree unless they put extra edges (then it is a graph).
Brute. Convert to a graph and run a general algorithm that ignores the tree invariant (e.g. Dijkstra with all weights 1). Time O((n) log n) extra, Space O(n) for dist + PQ. Brute-ish: it works and hides that height / subtree sums are one DFS.
Optimal. Recursive DFS or ArrayDeque<TreeNode> BFS. Time O(n). Space O(h) recursion or O(w) queue. If they forbid a parent map, pass parent as an argument or return a distance upward — Distance K card.
void dfs(TreeNode n, TreeNode parent) {
if (n == null) return;
// visit n
if (n.left != parent) dfs(n.left, n);
if (n.right != parent) dfs(n.right, n);
}
Liar / neighbor. “Tree DP / diameter / path sum” is still DFS but the return value is the state, not “I walked.” Graph with cycles needs vis. BST search is O(h) compare, not a full walk, if they said BST.
Amazon IE example: Path Sum–like tree, Akash AUTA R1. All nodes distance K no parent map — LC 7406809 R2 and LC 7623949 Fluency-as-DSA — chapter 05. Diameter variation, LC 7280347. Uni-valued subtrees, LC 6461439.
"tree diameter" → Two BFS / DFS Standard CS
Why you think of this. On an unweighted tree, the longest path’s ends are leaves. BFS from any node to the farthest u, then BFS from u to the farthest v; dist(u,v) is the diameter. On a binary tree they usually want the same idea as one DFS: height(left)+height(right) through each node, track the max (edges or nodes — ask). Two BFS is the graph-tree form; one DFS heights is the Live Code binary-tree form.
Brute. For every pair of leaves, walk the path (or all-pairs BFS). Time O(n²). Space O(n). Brute because the two-farthest property makes n starts unnecessary.
Optimal. Two BFS: Time O(n), Space O(n). Binary-tree DFS: Time O(n), Space O(h).
int[] best = {0};
int height(TreeNode n) {
if (n == null) return 0;
int L = height(n.left), R = height(n.right);
best[0] = Math.max(best[0], L + R); // edges; +1/+2 if they want nodes
return 1 + Math.max(L, R);
}
Liar / neighbor. Diameter of a graph with cycles is not two BFS (counterexamples exist). Max path sum between two leaves is a different IO — do not clamp a negative child to zero the way the any-node path-sum problem does. Burning tree is multi-source time from a start node, not diameter (though both walk farthest).
Amazon IE example: Diameter of Binary Tree variation, LC 7280347 R1. Burning Tree, GFG fresher R1 (with Merge Intervals). Max path between two leaves is paste-only in chapter 05 until the research bible has a URL — do not invent an id.
"grid" → DFS / BFS / DP Standard CS
Why you think of this. A grid is a graph with degree ≤ 4 (or 8). Flood / islands / rot / knight = BFS or DFS on cells. Count of paths or max reward with only right/down (or similar DAG moves) = DP, because each cell has a fixed predecessor set and you would recompute DAG paths if you DFS without memo. First sentence in the room: “is movement a DAG, or can I revisit?”
Brute. Recurse every walk without memo or without visited. Time exponential (paths) or infinite (cycles). Space O(mn) stack. Brute because overlapping subproblems (DP) or because the first visit is enough (flood).
Optimal. Flood: in-place mark or boolean[][], Time O(mn), Space O(mn). Multi-source BFS: ArrayDeque<int[]>, same bounds. Path DP: int[][] or 1D roll, Time O(mn), Space O(n) if only left is needed.
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
Liar / neighbor. Longest increasing path allows four directions — that is memo DFS on a DAG of values, not unique-paths DP. Row-sorted 0/1 max-1s row is a staircase, not flood. Matrix rotate 90° is index arithmetic, not a grid search.
Amazon IE example: Number of Islands, LC 8362604. Rotten Oranges — chapter 05. Grid paths avoiding −1 then max reward, LC 6800853 (OA-as-R1 remap, our R2 analogue) — chapter 05. Unique Paths II companion — chapter 05. TUF Unique Paths II (similar; max points).
"number of ways" → DP Standard CS
Why you think of this. Ways add. If two routes reach the same state, you add their counts, you do not enumerate both trees. Define state so the last decision is local (last cell, last coin, last decode index). Mod 10^9+7 if they said so. DFS+memo is the same DP; un-memoized recursion is the brute they will reject at n=20+.
Brute. Recurse every path / every subset. Time O(2ⁿ) or worse. Space O(n) stack. Brute because the same suffix is counted many times.
Optimal. int[] or int[][] dp, or HashMap memo on a state key. Time polynomial in the state count (unique paths O(mn), knapsack O(nW), decode O(n)). Space the same or rolled to one dimension.
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
if (i >= 2 && okTwo(s, i - 2)) dp[i] += dp[i - 2];
}
Liar / neighbor. “Number of islands / components” is a count of floods, not path DP. “Ways” on a graph with cycles needs a DAG restriction or you infinite-loop. Return the combination (the actual subset) is backtracking or parent pointers, not only the integer count.
Amazon IE example: Unique Paths–like / Unique Paths II, LC 7035289 BR family and TUF 06/10. Decode Ways ii, TUF 02. Distinct Subsequences, TUF 16. Reconstruct coins from ways-DP, LC 6606011 R2 (they wanted the coins, not only the count).
"maximum/minimum path value" → DP Standard CS
Why you think of this. You want the best numeric score along a path with a restricted move set. Optimal substructure: the best way to a cell is a max/min over predecessors plus this cell. On a DAG (right/down, falling path, triangle) a bottom-up table is enough. On four-direction increasing-value, memoize DFS — you may not visit a cell from every neighbor.
Brute. Enumerate all legal paths, track best. Time exponential. Space O(path). Brute because overlapping prefixes are recomputed.
Optimal. int[][] dp or 1D roll. Time O(mn) for DAG grids. Space O(n) if only the previous row lives. Four-dir LIP: Time O(mn) with memo, Space O(mn).
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] == -1) { dp[i][j] = Integer.MIN_VALUE / 4; continue; }
int best = Integer.MIN_VALUE / 4;
if (i > 0) best = Math.max(best, dp[i - 1][j]);
if (j > 0) best = Math.max(best, dp[i][j - 1]);
if (i == 0 && j == 0) best = 0;
dp[i][j] = best + grid[i][j];
}
Liar / neighbor. Shortest hop on an unweighted grid is BFS, not min-value DP (unless every step costs the cell). Max path sum any node in a binary tree clamps negative children; leaf-to-leaf does not. Kadane is 1D path = subarray, not a 2D grid.
Amazon IE example: grid max reward after path-count, LC 6800853 — chapter 05. Falling Path Sum variation, LC 6461439 R2. matrix max-path right/diag, Prince Job 3057703. Longest increasing path in a matrix, GFG off-campus-2021-4 labeled BR — chapter 05; do not stamp LC 329.
"transactions buy/sell" → DP state machine Standard CS
Why you think of this. Each day you are in a small set of states (cash, hold, cooldown, sold-k). A transaction is a transition, not a “subarray max minus min” unless they said one buy and one sell with no cooldown. The invariant is: you never need the whole history, only the best way to reach each state yesterday.
Brute. Recurse day + holding + remaining sells. Time O(2ⁿ) without memo. Space O(n). Brute because days share the same (hold, k) suffix.
Optimal. A handful of int variables, or dp[i][k][hold]. Time O(n) for k=1 or unlimited, O(nk) for k capped. Space O(1) after rolling.
int hold = Integer.MIN_VALUE / 2, cash = 0;
for (int p : prices) {
int nh = Math.max(hold, cash - p);
int nc = Math.max(cash, hold + p);
hold = nh; cash = nc;
}
return cash;
Liar / neighbor. Trapping rain is stack / two-pointer water, not a stock state (igreaper asked both). Kadane on diffs is one-transaction max profit only. “Transactions” on a log of transfers is parsing + HashMap, not this DP.
Amazon IE example: DP on Stocks, igreaper R1 (OA-as-R1). Trapping Rainwater was the sibling in that same hour — see the Amazon-reported card below. Not UTA two-DSA default.
"strictly increasing after removing one" → Greedy Standard CS
Why you think of this. At most one violation. Scan once; at the first dip you must choose whether the previous value or the current value is the one that leaves the chain increasing (compare to a[i-2]). A second dip fails. That local choice is greedy — you do not need LIS DP, because k_remove = 1.
Brute. For each index, delete it and test if the rest is strictly increasing. Time O(n²). Space O(1). Brute because only the first (and maybe second) inversion matters.
Optimal. One pass, a dip counter, maybe mutate a copy or use two virtual values. Time O(n). Space O(1).
int dips = 0;
for (int i = 1; i < n; i++) {
if (a[i] <= a[i - 1]) {
dips++;
if (dips > 1) return false;
if (i >= 2 && a[i] <= a[i - 2]) a[i] = a[i - 1]; // drop current
}
}
return true;
Liar / neighbor. Longest increasing subsequence is patience / DP, not “remove one.” Remove k to make increasing is a different budget — often LIS leftover n−LIS. “Non-decreasing after one” allows equals — lock < vs ≤.
Amazon IE example: omitted — not a named title in bible §5.A, TUF questions-asked, or chapter 05.
"minimum operations" → Greedy / DP / BFS depending on state Standard CS
Why you think of this. “Min ops” is not one pattern. Ask: what is a state, and what is one move? If moves are ±1 / double / change a digit, states are integers or strings → BFS (each edge cost 1). If you can always take the locally best move and prove no regret, greedy. If ops combine with capacity (knapsack, reduce n with coins), DP. Say the state out loud before picking.
Brute. Recurse every move sequence. Time exponential in the depth. Space the recursion. Brute because first-reach of a state is enough when every op costs 1.
Optimal. BFS: ArrayDeque + boolean[] or Set, Time O(states · branching), Space O(states). DP: int[] dp, Time O(n · digits) for subtract-a-digit. Greedy: Time O(digits · steps) only if you have proven it.
int minOpsBfs(int n) {
Queue<Integer> q = new ArrayDeque<>();
boolean[] seen = new boolean[n + 1];
q.offer(n); seen[n] = true;
int ops = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int s = 0; s < sz; s++) {
int cur = q.poll();
if (cur == 0) return ops;
for (int x = cur; x > 0; x /= 10) {
int d = x % 10;
if (d > 0 && !seen[cur - d]) { seen[cur - d] = true; q.offer(cur - d); }
}
}
ops++;
}
return -1;
}
Liar / neighbor. “Minimum operations so that a binary predicate becomes true” with a monotonic budget (speed, capacity, days) is BS on answer, not BFS. Connect ropes is heap cost, not BFS. Word-ladder min transforms is BFS on words — see min changes.
Amazon IE example: min ops reduce n to 0 subtracting a digit of n, LC 6800853 — our R2 analogue (OA-as-R1) — chapter 05. Race Car, GFG sde-1-34 R1 (BFS on state). Open the Lock similar, LC 7623949.
"all combinations" → Backtracking Standard CS
Why you think of this. They want the list of lists, not a count. Each position is take / skip (subsets) or choose among remaining (permutations, combinations of size k). You mutate a path, recurse, then undo — that undo is the whole pattern. n ≤ 20 is the budget from §0.
Brute. Allocate 2ⁿ bitmasks and filter. Time O(2ⁿ · n). Space O(2ⁿ · n) for the answer. Same complexity class as backtracking; it is “brute” when you generate illegal paths and filter instead of pruning (used > target, leftover duplicates).
Optimal. Recursion + List<Integer> path + sort-and-skip for duplicates. Time O(2ⁿ · n) subsets, O(n! · n) perms. Space O(n) extra besides the answer.
void subsets(int[] a, int i, List<Integer> path, List<List<Integer>> ans) {
if (i == a.length) { ans.add(new ArrayList<>(path)); return; }
path.add(a[i]); subsets(a, i + 1, path, ans); path.remove(path.size() - 1);
subsets(a, i + 1, path, ans);
}
Liar / neighbor. “Number of combinations / ways” is DP. Combination sum that only needs yes/no is knapsack. Generate parentheses is backtracking with a balance prune, not subset-of-array. Validate sudoku is constraints, not “all boards” (Solver is backtracking; Validate is not).
Amazon IE example: Generate all subsets, LC linked, AUTA R1 LC 7406809. balanced parentheses combinations, older GFG remainder. Validate sudoku (not Solver), GFG sde-1-17 their R3.
"minimum number of changes" → DP / BFS / Greedy Standard CS
Why you think of this. A change is an edit of a structure: replace a char, flip a bit, change a word by one letter. If every change costs 1 and the state graph is unweighted → BFS (word ladder, open lock). If you align two strings → DP edit distance. If a local replace never hurts → greedy. Lock the definition of one change before you pick.
Brute. Try every edit sequence / every alignment. Time exponential or O(3ⁿ). Space the recursion. Brute because first reach of a word (BFS) or the optimal alignment table (DP) reuses work.
Optimal. Word graph BFS: Time O(N · L · 26), Space O(N · L). Edit DP: Time O(nm), Space O(min(n,m)). Greedy replace: Time O(n), Space O(1).
Set<String> dict = new HashSet<>(wordList);
Queue<String> q = new ArrayDeque<>();
q.offer(begin);
int dist = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int s = 0; s < sz; s++) {
String w = q.poll();
if (w.equals(end)) return dist;
char[] ch = w.toCharArray();
for (int i = 0; i < ch.length; i++) {
char old = ch[i];
for (char c = 'a'; c <= 'z'; c++) {
ch[i] = c;
String nxt = new String(ch);
if (dict.remove(nxt)) q.offer(nxt);
}
ch[i] = old;
}
}
dist++;
}
return 0;
Liar / neighbor. Longest Repeating Character Replacement is “at most K changes” inside a window — sliding window, not edit DP. Min ops on an integer (subtract digit) is the other card. Min changes to make a binary string alternating is greedy count, not BFS.
Amazon IE example: Word Ladder, LC 7035289; TUF Word Ladder II. similar to Open the Lock, LC 7623949. Longest Repeating Character Replacement variation (K changes as a budget) is the window liar — Prince LC 424.
"binary answer: possible or impossible" → Binary Search on Answer Standard CS
Why you think of this. The thing you return is a number T, and feasible(T) is monotonic: if T works, every easier T also works (or the opposite). You do not binary-search the array index; you search the value domain (speed, capacity, min-distance, max-load). n can be small while T’s range is 1e9 — that is the §0 last row.
Brute. Test T = 1,2,3,… or every possible threshold. Time O(RANGE · feasible). Space O(1). Brute because monotonicity lets you jump half the remaining range.
Optimal. lo, hi + boolean feasible(mid) that is usually one O(n) scan. Time O(n log RANGE). Space O(1) extra.
int lo = 1, hi = (int) 1e9, ans = hi;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(mid)) { ans = mid; hi = mid - 1; } // min feasible
else lo = mid + 1;
}
return ans;
Liar / neighbor. Binary search on a sorted array (find target / rotated) is not “on answer.” “Binary search solved using PQ” (unnamed, LC 7981646) is a different story — do not invent the title. Heap is the liar for Koko: you are not repeatedly extracting a pile.
Amazon IE example: Capacity to Ship Packages Within D Days, LC linked, AUTA R1 LC 6806195. Koko Eating Bananas–like, Naina UTA R2. Aggressive Cows, LC 7724048 R2. TUF Koko; Smallest Divisor; Minimum Days to Make M Bouquets.
"maximize minimum" → Binary Search on Answer Standard CS
Why you think of this. You want the largest D such that you can still place / assign / split so that the poorest bucket is ≥ D. feasible(D) = “can I place cows with gap ≥ D,” “can I assign power so every device gets ≥ D.” Larger D is harder — if D works, smaller D also works. Search D, not the index.
Brute. Sort candidate D values (all pairwise distances) and test each. Time O(n² · n) if you enumerate pairs. Space O(n²). Brute because the feasible border is one binary search on [min gap, max−min].
Optimal. Same lo, hi, feasible skeleton; on success you try larger min (ans = mid; lo = mid + 1). Time O(n log RANGE) after a sort if placement needs order. Space O(1) extra.
boolean feasible(int[] pos, int k, int minDist) {
int placed = 1, last = pos[0];
for (int i = 1; i < pos.length; i++) {
if (pos[i] - last >= minDist) { placed++; last = pos[i]; }
}
return placed >= k;
}
// if (feasible(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
Liar / neighbor. Minimize the maximum is the next card — the feasible inequality flips. Max-heap of current loads is a different “spread load” story, not always BS-on-answer. Do not invent an LC id for unnamed power-allocation wording beyond what the IE wrote.
Amazon IE example: Aggressive Cows, LC 7724048 R2. power allocation max-min (BS-on-answer), LC 7850431 R1 (snippet — title unnamed beyond that phrase). Heaters, LC 7035289 AUTA R1 (min radius so every house is covered — lock which extreme they want).
"minimum maximum" → Binary Search on Answer Standard CS
Why you think of this. You want the smallest capacity / largest-sum / load T such that a greedy pack still finishes (ship in D days, split array into m subarrays, assign pages). feasible(T) = “can I do it if no piece exceeds T.” Larger T is easier. This is the classic ship-packages / split-array shape.
Brute. Try every T from max(a[i]) to sum(a). Time O(sum · n). Space O(1). Brute at sum = n·1e9.
Optimal. lo = max element, hi = sum; on feasible, shrink hi. Time O(n log SUM). Space O(1).
boolean canShip(int[] w, int days, int cap) {
int d = 1, load = 0;
for (int x : w) {
if (load + x > cap) { d++; load = 0; }
load += x;
if (d > days) return false;
}
return true;
}
// if (feasible(mid)) { ans = mid; hi = mid - 1; } else lo = mid + 1;
Liar / neighbor. Maximize the minimum is the previous card. Painter / book-allocation is this card. “Minimum of the maximums in every window” is a deque, not BS-on-answer. Heap of server loads can also minimize max load online — say both if they stream assignments.
Amazon IE example: Capacity to Ship Packages Within D Days, LC 6806195. Split Array Largest Sum, LC 6630775 R2 (same post as Remove K Digits). TUF Smallest Divisor Given a Threshold; Minimum Days to Make M Bouquets.
"tree with repeated leaf logic" → Degree / Tree DP / Greedy Standard CS
Why you think of this. Leaves are degree 1 (or binary-tree nodes with no children). “Delete all leaves, repeat,” “collect coins at leaves,” “minimum height trees” are peeling layers — Kahn on an undirected tree: put degree-1 nodes in a queue, peel, the last remaining nodes are the center. Tree DP if each leaf reports a value upward (delete leaves with value X, uni-valued subtrees). Greedy if a local leaf delete never blocks a better later delete.
Brute. While the tree is non-empty, scan all nodes to find current leaves and delete. Time O(n²). Space O(n). Brute because you rescan; a queue of degree-1 already knows the next leaf layer.
Optimal. int[] deg + ArrayDeque of leaves, or one DFS that returns (height, deleted). Time O(n). Space O(n).
int[] deg = new int[n];
for (int u = 0; u < n; u++) deg[u] = adj.get(u).size();
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (deg[i] <= 1) q.offer(i);
int remain = n;
while (remain > 2) {
int sz = q.size();
remain -= sz;
for (int s = 0; s < sz; s++) {
int u = q.poll();
for (int v : adj.get(u)) if (--deg[v] == 1) q.offer(v);
}
}
Liar / neighbor. Ordinary tree DFS (path sum, LCA) is not “repeated leaf.” Delete-and-repeat on a graph with cycles is not this peel. Swati listed “similar to Delete Leaves with a Given Value” — similar-not-exact; do not stamp that title as asked.
Amazon IE example: delete leaf value X, older GFG remainder. Uni-valued subtrees, LC 6461439 R1 (tree DP: a subtree is uni-valued if both children are and match). Swati similar-not-exact Delete Leaves — not an asked exact title.
"everyone knows X, X knows nobody" → Elimination / graph matrix Standard CS
Why you think of this. Celebrity is a unique sink: column of 1s (everyone knows c) and a row of 0s (c knows nobody), ignoring the diagonal. Two-pointer elimination: if knows(a,b) then a is not the celebrity; else b is not. You discard one person per call, then verify the survivor in O(n). You do not need the full n² matrix if knows is an API.
Brute. For each candidate, scan the whole row and column. Time O(n²). Space O(1). Brute because one knows(a,b) already kills one of {a,b}.
Optimal. Two indices or a running candidate. Time O(n) calls to knows for elimination + O(n) verify. Space O(1).
int c = 0;
for (int i = 1; i < n; i++) if (knows(c, i)) c = i;
for (int i = 0; i < n; i++)
if (i != c && (knows(c, i) || !knows(i, c))) return -1;
return c;
Liar / neighbor. “Everyone can reach X” in a directed graph is not celebrity (no “X knows nobody”). Find the town judge is the same elimination idea with indegree/outdegree. Do not stamp LC 277 as an asked-id for Job 10454435.
Amazon IE example: Celebrity, GFG off-campus-10 (year-out remainder) — chapter 05. Paste AUTA BR variant is paste-only; no 2026 AUTA BR URL in the research bible.
"frequency from encoded string" → Parsing + HashMap Standard CS
Why you think of this. The map is the last step. The first step is a grammar: walk an index, parse a token (digit, dd#, run-length, (k) multiplier), then map.merge(letter, times). If you start with HashMap you will invent tokens. Confirm the grammar out loud — the AUTA sample was not fully specified.
Brute. Hard-code the sample string’s letters. Time O(1). Space O(1). It fails every other encoding. That is why it is brute — it is not a parser.
Optimal. Index i, HashMap<Character,Integer> for counts. Time O(n) if you do not expand huge (k); if they want the expanded string, time is proportional to the output length. Space O(Σ) for the map.
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;
}
Liar / neighbor. String compression wrap-at-9 is the inverse direction (encode, not decode) — Amazon §1.B. Regex-first is a trap. Do not invent an LC problem id for this sample.
Amazon IE example: encoded string frequency 1226#24#(2), LC 6800853 — mapped our R1 analogue (OA-as-R1), AUTA — chapter 05. Grammar assumed from the example; say that.
"k elements from range" → Heap / Selection Standard CS
Why you think of this. The universe is a range (or [k,n], or a stream), and they want K of them (smallest, largest, random, kth). If K ≪ size of range, a heap of size K or quickselect on a materialized window. If the range is implicit (all integers from L to R), you do not allocate R−L+1 unless they force it — generate candidates or binary-search the kth.
Brute. Materialize the whole range, sort, slice K. Time O(R log R). Space O(R). Brute when R is 1e9 or when you only needed K.
Optimal. PriorityQueue size K: Time O(N log K) if N items stream. Quickselect: average O(N), Space O(1). Implicit kth in a computed range: BS on value, Time O(log RANGE · cost).
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
for (int x = lo; x <= hi; x++) { // only if hi-lo is small
max.offer(x);
if (max.size() > k) max.poll();
}
// k smallest sit in a max-heap of size k; peek is the largest of those
Liar / neighbor. Top K frequent is “K of a multiset,” not “K from a numeric range.” Subarray of length K is a window. Do not guess an LC id for an unnamed “k from [k,n]” prompt.
Amazon IE example: LC 6800853 family includes a kth-from-[k,n] prompt — details unnamed, no numeric problem id (bible §5.B). Dynamic k-th largest is the online sibling — chapter 05, LC 7850431.
"circular array" → Modulo / duplicated array / House Robber II split Standard CS
Why you think of this. Index i neighbors (i±1+n)%n. Three legal encodings: (1) modulo in the hop, (2) concatenate the array to itself for a linear window that must not exceed length n, (3) House Robber II split — you cannot take both a[0] and a[n−1], so max(rob[0..n-2], rob[1..n-1]). Circular Kadane is “max subarray that may wrap”: total − min-subarray, and watch the all-negative case.
Brute. Rotate the array n times and run the linear algorithm. Time O(n · T_linear). Space O(n). Brute because the wrap is one extra case, not n copies.
Optimal. Robber II: two linear DPs, Time O(n), Space O(1). Circular next-greater: loop i = 0..2n-1, index i%n, Time O(n), Space O(n). Circular window of length k: deque + modulo or a 2n prefix, Time O(n), Space O(k).
int robLine(int[] a, int l, int r) {
int prev = 0, cur = 0;
for (int i = l; i <= r; i++) {
int next = Math.max(cur, prev + a[i]);
prev = cur; cur = next;
}
return cur;
}
int robCircular(int[] a) {
int n = a.length;
if (n == 1) return a[0];
return Math.max(robLine(a, 0, n - 2), robLine(a, 1, n - 1));
}
Liar / neighbor. Linear House Robber I has no split. Circular queue LLD is modulo on a buffer, not this DP. Duplicating the array for robber (run DP on 2n) double-counts and is the liar. Sliding-window on 2n without capping length n will accept a window that wraps more than once.
Amazon IE example: House Robber then House Robber II circular, named, LC 8029194 R1; Sachin R2 named LC 213 — chapter 05. circular Kadane, LC 8014509 R1 (with Search in Rotated).
Amazon-reported live clues (Cheat-Sheet §1.B only)
These rows are already in Cheat-Sheet.md §1.B / Answer-BIBLE §1–§2.
They are reported in other loops — not a Job 10454435 list.
Each card: why / brute / optimal / time / space / source.
No extra Amazon clues invented here.
Unnamed stays unnamed. Do not guess numeric LC ids when the IE did not name one.
| Clue they used | Think of | Bible / source |
|---|
| similar to sum of subarray minimums | monotonic stack + contribution | §1 A1 |
| row-sorted 0/1 matrix, row with max 1s | staircase O(m+n) or per-row BS | §1 A3 |
| Koko / ship packages / eat all in H hours | BS on answer | §1 A4 |
| equal-split tree / remove one edge | subtree sums, one DFS | §1 A4 |
| rotate matrix 90° | transpose + reverse rows | §1 A6 |
| next permutation similar | pivot from right + reverse suffix | §1 A6 |
| rotten oranges / minutes until all rot | multi-source BFS | §1 A7 |
| distance K, no parent map | undirected graph then BFS, or recursive no-map | §1 A7 |
| merge k sorted lists | min-heap of k heads | §1 A8 |
| word ladder (begin → end, dict) | BFS on words, 26-letter edges | §1 A10 |
| count beautiful splits (title named, no LC id) | prefix/z or equal-beauty split — clarify | §1 A10 |
| string compression, wrap count at 9 | RLE, split runs a12 → a9a3 | §1 A11 |
| beautiful nodes + adj matrix | graph on int[][], DFS/BFS | §1 A11 |
| connect ropes / sticks / garlands | min-heap, always merge two smallest | §1 B0 |
| students, enemies not same group | bipartite 2-color | §1 B0 |
| grid right/down, traps, max reward | DP paths (OA-as-R1 remap) | §1 B4 |
| min ops subtract a digit of n | BFS on integer states, or greedy | §1 B4 |
| LL → height-balanced BST | mid of array after LL→array, or slow/fast | §1 Deepak |
| first missing positive | cyclic sort in-place 1..n | §1 Deepak |
| median of stream | two heaps | §2 |
| top K frequent | HashMap + min-heap k | §2 |
| number of islands | DFS/BFS flood | §2 |
| currency converter | weighted DFS/BFS | §2 |
| clone graph | HashMap old→new + DFS/BFS | §2 |
| keys and rooms | DFS/BFS from 0 | §2 |
| delivery stations + classes + topo | entities + Kahn — not LC 210 stamp | §2 / §3 |
| max sum switching two sorted LLs | two-pointer on lists — not LC 962 | §2 |
| house robber then circular | DP, then max(rob[0..n-2], rob[1..n-1]) | §2 |
| trapping rain / stocks DP | stack / state DP | §2 |
| max rectangle of 1s | histogram + monotonic stack | §2 |
| longest subarray sum 0 | prefix + HashMap first-index | §2 |
| GetRandom O(1) | HashMap + ArrayList swap-delete | §2 |
| LRU | HashMap + DLL | §3 |
| LFU | HashMap + freq → DLL | §3 |
"similar to sum of subarray minimums" → monotonic stack + contribution IE-asked
Why you think of this. Every element is the minimum of a contiguous range. If you know the next-smaller on the left and on the right, the contribution is a[i] * leftDist * rightDist. That is two monotonic stacks, not a window max.
Brute. For every L,R take min of the segment. Time O(n²). Space O(1). Brute because each a[i]’s range of “I am the min” is computed from two nearest strict-smaller neighbors.
Optimal. ArrayDeque<Integer> indices, increasing stack, twice (or one pass with sentinels). Time O(n). Space O(n).
// next smaller right; mirror for left
Deque<Integer> st = new ArrayDeque<>();
int[] nsr = new int[n];
Arrays.fill(nsr, n);
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && a[st.peek()] > a[i]) nsr[st.pop()] = i;
st.push(i);
}
// ans += a[i] * (i - nsl[i]) * (nsr[i] - i); watch ties / long
Liar / neighbor. Next greater element is one stack and a different IO. Window minimum is a deque with expiry. Do not stamp a numeric LC id — the IE said “similar to.”
Source. Cheat-Sheet §1.B / Answer-BIBLE §1 A1. Akash AUTA R2 snippet, bible §5.A “similar to Sum of Subarray Minimums.” Other loops; not Job 10454435.
"row-sorted 0/1 matrix, row with max 1s" → staircase O(m+n) IE-asked
Why you think of this. Each row is sorted 0s then 1s. The first 1 only moves left as you go down (or you binary-search each row). Start at top-right; move left while you see 1, else move down. Never go right.
Brute. Count 1s in every row. Time O(mn). Space O(1). Brute because the sorted rows let you reuse the previous first-1 column.
Optimal. Two ints i, j. Time O(m+n). Space O(1). Per-row binary search: Time O(m log n).
int bestRow = -1, best = 0, j = n;
for (int i = 0; i < m; i++) {
while (j > 0 && mat[i][j - 1] == 1) j--;
int ones = n - j;
if (ones > best) { best = ones; bestRow = i; }
}
return bestRow;
Liar / neighbor. Unsorted 0/1 row is a linear count. Number of islands is flood, not staircase.
Source. Cheat-Sheet §1.B §1 A3. AUTA mail R2, interviewexperiences.in 2024-grad (opened). §5.A “max-1s row in row-sorted 0/1 matrix.”
"Koko / ship packages / eat all in H hours" → Binary Search on Answer IE-asked
Why you think of this. Speed or capacity T is monotonic: larger T finishes in fewer hours/days. feasible(T) is one O(n) pack. Not a heap of piles.
Brute. Try T = 1..max. Time O(max · n). Space O(1).
Optimal. lo, hi + feasible. Time O(n log RANGE). Space O(1).
boolean feasible(int[] piles, int h, int speed) {
long hours = 0;
for (int p : piles) hours += (p + (long) speed - 1) / speed;
return hours <= h;
}
Liar / neighbor. Heap “always eat the largest pile” is the wrong story for a fixed speed. Same skeleton as binary answer / min maximum.
Source. Cheat-Sheet §1 A4. Koko–like, Naina UTA R2. Capacity to Ship, LC 6806195 AUTA R1. TUF 07/09 Koko (that IE had no OA).
"equal-split tree / remove one edge" → subtree sums, one DFS IE-asked
Why you think of this. Removing one edge splits the tree into a subtree and the rest. If total sum is S, you need a subtree whose sum is S/2 (and S even). One DFS returns subtree sum and sets a flag.
Brute. For every edge, DFS both sides. Time O(n²). Space O(n).
Optimal. One DFS, Time O(n), Space O(h).
int total;
boolean ok = false;
int dfs(TreeNode n) {
if (n == null) return 0;
int s = n.val + dfs(n.left) + dfs(n.right);
if (n != root && s * 2 == total) ok = true;
return s;
}
Liar / neighbor. Equal partition of an array is knapsack, not tree. Max path sum is a different return value. GFG named this without a numeric id — do not invent one.
Source. Cheat-Sheet §1 A4. Naina UTA R2, same hour as Koko–like. Bible §5.A “equal-split tree (remove edge), GFG (no numeric id).”
"rotate matrix 90°" → transpose + reverse rows IE-asked
Why you think of this. Clockwise 90° is (i,j) → (j, n-1-i). In place: transpose (swap i<j) then reverse each row. Four-cell cycle also works. It is index arithmetic, not a grid DP.
Brute. Allocate n×n and copy. Time O(n²). Space O(n²). Correct but they usually want in-place.
Optimal. In-place two passes. Time O(n²). Space O(1).
void rotate(int[][] m) {
int n = m.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t;
}
for (int i = 0; i < n; i++)
for (int l = 0, r = n - 1; l < r; l++, r--) {
int t = m[i][l]; m[i][l] = m[i][r]; m[i][r] = t;
}
}
Liar / neighbor. Anticlockwise is transpose + reverse columns. Spiral print is a different IO.
Source. Cheat-Sheet §1 A6. Rotate Image; similar to Next Permutation, LC 6806195 AUTA R2.
"next permutation similar" → pivot from right + reverse suffix IE-asked
Why you think of this. The next lexicographic permutation is: find the rightmost ascent a[i] < a[i+1], swap a[i] with the rightmost successor, reverse the suffix. No extra array of all perms.
Brute. Generate all permutations, sort, pick next. Time O(n! · n). Space O(n!).
Optimal. One pass from the right + reverse. Time O(n). Space O(1).
void nextPermutation(int[] a) {
int n = a.length, i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
int j = n - 1;
while (a[j] <= a[i]) j--;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
for (int l = i + 1, r = n - 1; l < r; l++, r--) {
int t = a[l]; a[l] = a[r]; a[r] = t;
}
}
Liar / neighbor. Next greater element is a stack, not a suffix reverse. Next greater same digits (Prabhash) is this family. Do not stamp an LC id unless they name one — 6806195 said “similar.”
Source. Cheat-Sheet §1 A6. LC 6806195 R2 similar. Prabhash R1 mixed next-perm / next-greater-same-digits. chapter 05.
"rotten oranges / minutes until all rot" → multi-source BFS IE-asked
Why you think of this. Every initially rotten orange starts rotting neighbors at minute 0. The time until a fresh orange rots is the min hop from any rotten source — that is multi-source BFS, one queue, level = minutes. DFS cannot keep a global clock.
Brute. Simulate minute-by-minute by scanning the whole grid each minute. Time O(m²n²) worst. Space O(mn).
Optimal. ArrayDeque<int[]> of all 2s, count fresh. Time O(mn). Space O(mn).
Queue<int[]> q = new ArrayDeque<>();
int fresh = 0, minutes = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (g[i][j] == 2) q.offer(new int[]{i, j});
if (g[i][j] == 1) fresh++;
}
while (!q.isEmpty() && fresh > 0) {
int sz = q.size();
minutes++;
for (int s = 0; s < sz; s++) {
int[] c = q.poll();
for (int[] d : DIRS) {
int ni = c[0] + d[0], nj = c[1] + d[1];
if (ni<0||nj<0||ni>=m||nj>=n||g[ni][nj]!=1) continue;
g[ni][nj] = 2; fresh--; q.offer(new int[]{ni, nj});
}
}
}
return fresh == 0 ? minutes : -1;
Liar / neighbor. Number of islands is a count of floods, not minutes. Single-source BFS from one orange is wrong if several start rotten. OA-as-R1 on igreaper/GFG 2025 — their later “R3” can be this loop’s R2 analogue.
Source. Cheat-Sheet §1 A7. Bible §5.A Rotten Oranges mixed R2 (GFG 2025; igreaper; LC 6461439; 7406809 variation; 7563011). TUF 11. chapter 05.
"distance K, no parent map" → undirected graph then BFS, or recursive no-map IE-asked
Why you think of this. A binary tree plus “go up” is an undirected graph. If they forbid a stored Map parent, either build adj by passing parent as a DFS argument, then BFS from the target, or recurse and return distance-to-target so the other subtree can be collected at k − dist − 1.
Brute. Parent map + BFS is the usual solution — they may reject the map. All-pairs paths: Time O(n²), Space O(n).
Optimal. Adj list Map<TreeNode,List<TreeNode>> built without storing a parent map field, then BFS. Time O(n). Space O(n). Recursive no-map: Time O(n), Space O(h).
void build(TreeNode n, TreeNode p, Map<TreeNode, List<TreeNode>> adj) {
if (n == null) return;
adj.computeIfAbsent(n, k -> new ArrayList<>());
if (p != null) { adj.get(n).add(p); adj.get(p).add(n); }
build(n.left, n, adj);
build(n.right, n, adj);
}
// then ArrayDeque BFS from target, depth == k
Liar / neighbor. Distance between two nodes is a different IO (usually LCA). Intern LC 7643209 Fluency was an unnamed min-heap, not Distance K. If they paste a tree in a Fluency slot, write the tree first.
Source. Cheat-Sheet §1 A7. LC 7406809 AUTA R2; LC 7623949 R3 labeled GenAI Fluency. chapter 05.
"merge k sorted lists" → min-heap of k heads IE-asked
Why you think of this. Each list is already sorted. The next global min is the min of the current k heads. A heap of size k beats merging lists pairwise in a chain (still OK, just more pointer work).
Brute. Collect all values, sort, rebuild. Time O(N log N). Space O(N). Ignores that each list is sorted.
Optimal. PriorityQueue<ListNode> of heads. Time O(N log k). Space O(k).
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode h : lists) if (h != null) pq.offer(h);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
ListNode n = pq.poll();
tail.next = n; tail = n;
if (n.next != null) pq.offer(n.next);
}
return dummy.next;
Liar / neighbor. Top K frequent is a heap of scores, not list heads. Merge two lists is O(N) two-pointer, no heap.
Source. Cheat-Sheet §1 A8. Merge k sorted linked lists, LC 7563011 AUTA R2; Bhavya R1. chapter 05.
"word ladder (begin → end, dict)" → BFS on words IE-asked
Why you think of this. Each word is a node; an edge exists if they differ by one letter. Unweighted shortest transform is BFS. Generating 26·L neighbors and dict.remove is enough; you do not build the full graph.
Brute. DFS all ladders, keep min length. Time exponential. Space O(N) path.
Optimal. HashSet dict + ArrayDeque BFS. Time O(N · L · 26). Space O(N · L). Word Ladder II (all shortest) needs parents / level BFS — TUF asked II.
// Cheat-Sheet §4.18 — see also min-changes card
if (!dict.contains(end)) return 0;
Queue<String> q = new ArrayDeque<>();
q.offer(begin);
int dist = 1;
// level BFS; 26-letter edges; dict.remove on enqueue
Liar / neighbor. Edit distance between two strings with no dict is DP. Open the Lock is the same BFS on a 4-digit wheel.
Source. Cheat-Sheet §1 A10. Word Ladder, LC 7035289 AUTA R2. TUF 06 Word Ladder II. GFG sde-1-17 CAT→MEN family (their later live / BR-adj).
"count beautiful splits" → prefix / Z or equal-beauty split — clarify IE-asked
Why you think of this. The title was named; the numeric LC id was not. “Beautiful” usually means two or three pieces whose hashes / Z-boxes / equal sums match a definition they will paste. Do not implement a guessed LC 3253. Ask: how many cuts, what makes a piece beautiful, array or string.
Brute. Try every cut position, rescan pieces. Time O(n²) or O(n³). Space O(1). Fine after they lock n.
Optimal. Prefix hashes or Z-array so a piece query is O(1). Time often O(n) or O(n²) depending on the locked definition. Space O(n). Speak TC only after the definition.
// after they define beauty:
long[] pref = new long[n + 1];
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
// or Z-box: int[] z = zFunction(s);
int ans = 0;
for (int i = 1; i < n; i++) if (/* locked predicate on [0,i) vs [i,n) */) ans++;
Liar / neighbor. Do not stamp a numeric LC id. Equal-split tree is the other card. Palindrome splits are a different beauty.
Source. Cheat-Sheet §1 A10: “title named, no LC id.” Bible §5.A Word Ladder; Count Beautiful Splits, LC 7035289 AUTA R2. TUF 06 linked a problem URL — still do not invent a numeric id in the room unless they name it.
"string compression, wrap count at 9" → RLE split runs Standard CS
Why you think of this. Run-length encode, but a count above 9 wraps: a12 → a9a3. Walk runs with two indices; emit chunks of at most 9. Clarify count=1 written as a or a1, and wrap at 9 vs 10. This is the inverse of encoded-frequency parse.
Brute. Count a run, then emit one number (forgetting the wrap): a12. Time O(n). Space O(n). Wrong output, not a complexity fail.
Optimal. StringBuilder. Time O(n + output). Space O(output).
StringBuilder sb = new StringBuilder();
int i = 0, n = s.length();
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
int cnt = j - i;
while (cnt > 0) {
int chunk = Math.min(9, cnt);
sb.append(s.charAt(i));
if (chunk > 1) sb.append(chunk); // ASK: emit '1' or not
cnt -= chunk;
}
i = j;
}
Liar / neighbor. Encoded frequency 1226#24#(2) is decode + map, not this. Do not invent an IE title beyond Cheat-Sheet §1.B.
Source. Cheat-Sheet §1.B / Answer-BIBLE §1 A11. No extra §5.A title beyond that clue row — example omitted rather than fabricated.
"beautiful nodes + adj matrix" → graph on int[][], DFS/BFS Standard CS
Why you think of this. They gave an adjacency matrix, not an edge list. “Beautiful” is a predicate on a node or a component they will define (degree, value, reachable set). Build nothing fancy: int[][] g, then DFS/BFS with boolean[] vis. Ask the predicate before coloring nodes beautiful.
Brute. For each node, scan the whole matrix repeatedly. Time O(n³) if you restart. Space O(n).
Optimal. One or few floods. Time O(n²) to read the matrix (that is the input size) + O(n²) DFS. Space O(n).
void dfs(int u, int[][] g, boolean[] vis) {
vis[u] = true;
for (int v = 0; v < g.length; v++)
if (g[u][v] != 0 && !vis[v]) dfs(v, g, vis);
}
Liar / neighbor. Count beautiful splits is an array cut, not this graph. Do not invent the beauty predicate.
Source. Cheat-Sheet §1.B / Answer-BIBLE §1 A11. No extra §5.A title — example omitted rather than fabricated.
"connect ropes / sticks / garlands" → min-heap, always merge two smallest IE-asked
Why you think of this. Cost of a merge is the sum, and the new rope goes back into the set. Always merge the two current smallest — Huffman / greedy. A single sort is the liar because the merged length re-enters.
Brute. Try merge orders. Time factorial. Space O(n).
Optimal. PriorityQueue<Integer> (use long if they said overflow). Time O(n log n). Space O(n).
PriorityQueue<Integer> min = new PriorityQueue<>();
for (int x : ropes) min.offer(x);
int cost = 0;
while (min.size() > 1) {
int s = min.poll() + min.poll();
cost += s;
min.offer(s);
}
Liar / neighbor. Top K is “stop at K,” not merge until one. Sort-once then pair adjacent is wrong.
Source. Cheat-Sheet §1 B0. Connect Sticks, GFG 2025 (OA-as-R1 on that post) and LC 8362604 Combine Garlands AUTA HM. LC 7850431 also. chapter 05.
"students, enemies not same group" → bipartite 2-color IE-asked
Why you think of this. “Not same group” is an undirected edge that forbids the same color. The graph must be 2-colorable. BFS/DFS color with 0/1; a same-color edge fails. Not Kahn (that is directed prerequisites).
Brute. Assign each student to group A or B, test all enemy pairs. Time O(2ⁿ · E). Space O(n).
Optimal. int[] col + BFS per component. Time O(V+E). Space O(V+E).
boolean bipartite(List<List<Integer>> adj, int n) {
int[] col = new int[n];
Arrays.fill(col, -1);
for (int s = 0; s < n; s++) if (col[s] == -1) {
Queue<Integer> q = new ArrayDeque<>();
q.offer(s); col[s] = 0;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (col[v] == -1) { col[v] = col[u] ^ 1; q.offer(v); }
else if (col[v] == col[u]) return false;
}
}
}
return true;
}
Liar / neighbor. Course schedule is directed cycle. “Most stones” DSU is components, not 2-color.
Source. Cheat-Sheet §1 B0. bipartite students / enemies, LC 8362604 AUTA 2026 R2 (opened).
"grid right/down, traps, max reward" → DP paths IE-asked
Why you think of this. Moves are a DAG. Traps (−1) block a cell. First they may ask count of paths, then max reward on a surviving path. That is two DP tables or one pass that tracks both. OA-as-R1 remap: LC 6800853 their later live is this loop’s R2 analogue, still a live pattern if a third hour is a grid.
Brute. DFS every right/down walk. Time exponential. Space O(m+n).
Optimal. int[][] ways and int[][] reward. Time O(mn). Space O(mn) or rolled.
// sketch: skip traps; ways[i][j] += ways from up/left;
// reward[i][j] = grid[i][j] + max(reward from up/left among cells with ways>0)
Liar / neighbor. Four-direction increasing path is memo DFS, not this DAG DP. Unique Paths II is the count-only sibling.
Source. Cheat-Sheet §1 B4. LC 6800853. chapter 05. TUF Unique Paths II similar (max points).
"min ops subtract a digit of n" → BFS on integer states, or greedy IE-asked
Why you think of this. From n you go to n−d for each non-zero digit d of the current n. Digits change after each subtract. Sample 27 → 5. Shortest path on 0..n is BFS/DP. Greedy max-digit matches that sample — verify with DP if they doubt it.
Brute. Recurse without seen. Time exponential / infinite if you subtract 0. Space the recursion depth.
Optimal. BFS or int[] dp for n in Live Code range. Time O(n · digits). Space O(n). Do not dp[n] on a long.
// BFS on 0..n; full Java: chapter 05 reduce-by-digit
Queue<Integer> q = new ArrayDeque<>();
boolean[] seen = new boolean[n + 1];
q.offer(n); seen[n] = true;
int ops = 0;
// level loop: for each cur, enqueue cur-d for digits d of cur
Liar / neighbor. Subtracting only the original digits of n is wrong. BS-on-answer is the wrong family (no monotonic T).
Source. Cheat-Sheet §1 B4. LC 6800853 — our R2 analogue (OA-as-R1). chapter 05.
"LL → height-balanced BST" → mid of array after LL→array IE-asked
Why you think of this. A height-balanced BST from a sorted linked list is “middle becomes root.” Converting to an array makes mid O(1). In-place slow/fast also works: find mid, recurse left half / right half, cut the list.
Brute. Insert each node into a BST in list order. Time O(n log n) average, O(n²) if the list is sorted and you always insert as right child without balancing. Space O(n). Unbalanced risk — Cheat-Sheet §6 refuse.
Optimal. Array + mid recurse: Time O(n), Space O(n). Slow/fast: Time O(n log n) if you rescan, or O(n) with a moving pointer; Space O(log n) stack.
TreeNode build(int[] a, int l, int r) {
if (l > r) return null;
int m = l + (r - l) / 2;
return new TreeNode(a[m], build(a, l, m - 1), build(a, m + 1, r));
}
Liar / neighbor. Random BST inserts are not height-balanced. Sorted array → BST is the same mid trick without the LL walk.
Source. Cheat-Sheet §1 Deepak. Deepak LinkedIn R2 (snippet), bible §5.A.
"first missing positive" → cyclic sort in-place 1..n IE-asked
Why you think of this. The answer is in 1..n+1. Put value v in index v−1 when v is in 1..n. Then the first index i with a[i] != i+1 is the missing. You do not need a HashSet if they want O(1) extra space.
Brute. HashSet of positives, scan 1..n+1. Time O(n). Space O(n) — they may forbid the set.
Optimal. Cyclic swap. Time O(n). Space O(1).
int firstMissingPositive(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
while (a[i] >= 1 && a[i] <= n && a[a[i] - 1] != a[i]) {
int t = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = t;
}
}
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
Liar / neighbor. “Missing number 0..n with one hole” is XOR / sum, not cyclic sort. Prem R2 “cyclic sort similar” is this family (OA-as-R1 on that post).
Source. Cheat-Sheet §1 Deepak. Deepak R2. Prem “Cyclic sort similar to First Missing Positive.” Cheat-Sheet §4.16.
"median of stream" → two heaps IE-asked
Why you think of this. You need the middle as numbers arrive. A max-heap of the lower half and a min-heap of the upper half stay size-balanced; the median is a peek or the average of two peeks. One heap of all n is the liar for “get median” (you would need delete-middle).
Brute. Keep an ArrayList, sort on each query. Time O(n log n) per query. Space O(n).
Optimal. Two PriorityQueue. Offer/rebalance O(log n). Peek O(1). Space O(n).
PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> high = new PriorityQueue<>();
void add(int x) {
if (low.isEmpty() || x <= low.peek()) low.offer(x);
else high.offer(x);
if (low.size() > high.size() + 1) high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
}
double median() {
if (low.size() > high.size()) return low.peek();
return (low.peek() + high.peek()) / 2.0;
}
Liar / neighbor. Median of two sorted arrays is partition BS, not a stream. Dynamic kth is one heap of size k.
Source. Cheat-Sheet §2. Median of Data Stream, LC 8362604 AUTA R1. LC 6475219 Find Median from stream. Cheat-Sheet §4.6.
"top K frequent" → HashMap + min-heap k IE-asked
Why you think of this. Count first, then you only need K keys. Min-heap of size K on frequency. Bucket sort of freq is O(n) if you want to skip the heap.
Brute. Sort all unique by freq. Time O(n + u log u). Space O(u).
Optimal. HashMap + heap K. Time O(n + u log K). Space O(u + K).
// identical skeleton to top K
Liar / neighbor. Connect ropes is a different heap. Group anagrams is signature grouping, not top-K.
Source. Cheat-Sheet §2. Top K Frequent, LC 7406809 AUTA R1. TUF 12 live. chapter 05.
"number of islands" → DFS / BFS flood IE-asked
Why you think of this. Each unvisited land starts one component. Flood 4-dir and increment. DSU on flattened indices also works.
Brute. Union every pair of adjacent lands by rescanning. Time worse than one flood (up to O(m²n²)). Space O(mn).
Optimal. DFS/BFS. Time O(mn). Space O(mn) worst recursion (prefer BFS if they fear stack).
void dfs(char[][] g, int i, int j) {
if (i<0||j<0||i>=g.length||j>=g[0].length||g[i][j]!='1') return;
g[i][j] = '0';
dfs(g, i+1, j); dfs(g, i-1, j); dfs(g, i, j+1); dfs(g, i, j-1);
}
Liar / neighbor. Rotten oranges is minutes, not a count. Max area of island is the same flood with a size return.
Source. Cheat-Sheet §2. Number of Islands, LC 8362604 AUTA R1; Deepak R1. Cheat-Sheet §4.10.
"currency converter" → weighted DFS/BFS IE-asked
Why you think of this. Rates are directed weighted edges (multiply). Query A→B is a path product. DFS/BFS with a visited set; invert the edge for the reverse rate if they allow it. Evaluate Division is the named sibling (TUF 01 said similar).
Brute. Floyd-Warshall on currencies. Time O(n³). Space O(n²). Fine if n is tiny; overkill if they ask one query.
Optimal. Adj Map<String, List<pair>> + DFS. Time O(V+E) per query (or cache). Space O(V+E).
boolean dfs(String u, String dest, double prod, Set<String> vis,
Map<String, List<AbstractMap.SimpleEntry<String, Double>>> adj, double[] out) {
if (u.equals(dest)) { out[0] = prod; return true; }
vis.add(u);
for (var e : adj.getOrDefault(u, List.of()))
if (vis.add(e.getKey()) && dfs(e.getKey(), dest, prod * e.getValue(), vis, adj, out))
return true;
return false;
}
Liar / neighbor. Unweighted BFS gives hops, not the product. Dijkstra if they ask “best rate” with a min product and positive weights — lock the IO.
Source. Cheat-Sheet §2. Currency Converter, Shiwangi UTA R1 (opened). TUF 01 Evaluate Division (similar). Do not stamp an LC id unless they name it.
"clone graph" → HashMap old→new + DFS/BFS IE-asked
Why you think of this. You must copy nodes and edges without aliasing. The map old→new is the invariant: if a neighbor is already cloned, point at the clone; else create, map, recurse. Without the map you infinite-loop on a cycle.
Brute. Deep copy a spanning tree and miss back edges / cycles. Time O(V) incomplete. Space O(V).
Optimal. HashMap<Node,Node> + DFS or BFS. Time O(V+E). Space O(V).
Map<Node, Node> map = new HashMap<>();
Node clone(Node n) {
if (n == null) return null;
if (map.containsKey(n)) return map.get(n);
Node c = new Node(n.val);
map.put(n, c);
for (Node nb : n.neighbors) c.neighbors.add(clone(nb));
return c;
}
Liar / neighbor. Clone a tree has no cycle — still a map is safer if they sneak extra edges. Copy List with Random Pointer is the same map idea on a list.
Source. Cheat-Sheet §2. Clone Graph, LC 7280347 R2 (with Next Palindromic Number).
"keys and rooms" → DFS/BFS from 0 IE-asked
Why you think of this. Room 0 is unlocked. Keys inside a room are outgoing edges. You can visit all rooms iff the flood from 0 covers n. Same as explore reachable.
Brute. Recurse without visited — cycle if two rooms point at each other. Time unbounded. Space unbounded stack.
Optimal. boolean[] vis + stack/queue. Time O(n + keys). Space O(n).
boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] vis = new boolean[rooms.size()];
Deque<Integer> st = new ArrayDeque<>();
st.push(0); vis[0] = true;
while (!st.isEmpty()) {
int u = st.pop();
for (int v : rooms.get(u)) if (!vis[v]) { vis[v] = true; st.push(v); }
}
for (boolean b : vis) if (!b) return false;
return true;
}
Liar / neighbor. Course schedule is directed constraints, not “keys unlock.” Detonate bombs is reachability with a geometric edge rule.
Source. Cheat-Sheet §2. Keys and Rooms, named, LC 6491881 R2.
"delivery stations + classes + topo" → entities + Kahn IE-asked
Why you think of this. They want Java classes for stations / parcels / prerequisites, then a legal process order. The algorithm is still Kahn. Do not stamp LC 210 on LC 6369243 — that post did not link 210 (210 is only on LC 6282609).
Brute. Empty class boxes with no indegree loop. They will ask you to run an example. Time none until Kahn: then O(V+E), Space O(V+E).
Optimal. Entity classes + int[] indeg + queue. Time O(V+E). Space O(V+E).
// Kahn as in dependency; wrap nodes as Station / Parcel if they asked OOD
boolean cycle = order.size() < n;
Liar / neighbor. Course Schedule II on 6282609 is the titled sibling. Max-sum switching lists is the other problem on 6369243 — do not mix them.
Source. Cheat-Sheet §2 / §3. LC 6369243 R2. chapter 05 (remap note).
"max sum switching two sorted LLs" → two-pointer on lists IE-asked
Why you think of this. Two sorted lists share some values. You may switch only at a common node. Walk both, accumulate a segment sum between commons, then take max of the two segment sums at each intersection. Not LC 962 (interval list intersections).
Brute. Enumerate switch sequences. Time exponential. Space O(n+m) for copies.
Optimal. Two ListNode pointers. Time O(n+m). Space O(1).
// at each common value: ans += max(sumA, sumB); reset both segment sums
// after last node: ans += max(sumA, sumB)
// lock: commons must match by value; lists already sorted
Liar / neighbor. Do not stamp LC 962 or 210. Merge two lists is a different IO (one merged sequence, not max path).
Source. Cheat-Sheet §2. LC 6369243; TUF 05 GFG “Maximum Sum Linked List from two sorted linked lists.” chapter 05.
"house robber then circular" → DP + split IE-asked
Why you think of this. Linear robber is dp[i] = max(dp[i-1], dp[i-2]+a[i]). Circular: houses 0 and n−1 touch, so run the line on [0..n-2] and [1..n-1]. Same as circular.
Brute. Recurse take/skip with a “used first” flag. Time exponential without memo. Space O(n).
Optimal. Two O(n) / O(1) space linear DPs. Time O(n). Space O(1).
// Cheat-Sheet §4.17 — robCircular in the circular card
Liar / neighbor. House Robber I only. House Robber III is a tree (unnamed “similar” stays similar — do not stamp LC 337). Circular Kadane is wrap-subarray, not rob-adjacent.
Source. Cheat-Sheet §2. LC 8029194 R1 named I then II; Sachin R2 named LC 213. chapter 05.
"trapping rain / stocks DP" → stack / state DP IE-asked
Why you think of this. One IE hour asked both. Rain: water on i is min(maxLeft, maxRight) − height[i]; two arrays, two pointers, or a monotonic stack of bars. Stocks: state machine on the same day index — see buy/sell. They share “scan left-to-right keeping a running extreme,” not the same DS.
Brute. Rain: for each i scan left and right max. Time O(n²). Space O(1). Stocks: 2ⁿ recurse.
Optimal. Rain two-pointer or stack: Time O(n), Space O(1) or O(n). Stocks rolled ints: Time O(n), Space O(1).
int trap(int[] h) {
int l = 0, r = h.length - 1, lmax = 0, rmax = 0, ans = 0;
while (l < r) {
if (h[l] < h[r]) {
lmax = Math.max(lmax, h[l]);
ans += lmax - h[l];
l++;
} else {
rmax = Math.max(rmax, h[r]);
ans += rmax - h[r];
r--;
}
}
return ans;
}
Liar / neighbor. Histogram largest rectangle is the stack sibling used for maximal rectangle of 1s — next card. Kadane is max subarray, not water.
Source. Cheat-Sheet §2. Trapping Rainwater; DP on Stocks, igreaper R1 (OA-as-R1). Not UTA two-DSA default.
"max rectangle of 1s" → histogram + monotonic stack IE-asked
Why you think of this. Each row, treat consecutive 1s upward as a histogram bar height. Largest rectangle in that histogram is next-smaller left/right via a monotonic stack. Max over rows. Maximal Rectangle, not “max square” (square is DP 2×2).
Brute. Enumerate all sub-rectangles, test all-1s. Time O(m²n²) or worse. Space O(1).
Optimal. int[] height + stack of indices per row. Time O(mn). Space O(n).
int largestRectangle(int[] h) {
Deque<Integer> st = new ArrayDeque<>();
int ans = 0, n = h.length;
for (int i = 0; i <= n; i++) {
int cur = i == n ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] > cur) {
int mid = st.pop();
int left = st.isEmpty() ? -1 : st.peek();
ans = Math.max(ans, h[mid] * (i - left - 1));
}
st.push(i);
}
return ans;
}
Liar / neighbor. Maximal square is dp[i][j] = min(three) + 1. Window max deque is 1D sliding, not histogram.
Source. Cheat-Sheet §2. Maximum Rectangle all 1s, igreaper R2 (OA-as-R1 on that write-up) — chapter 05. Their R3 = our R2 analogue.
"longest subarray sum 0" → prefix + HashMap first-index IE-asked
Why you think of this. Sum 0 means two prefixes equal. Store the first index of each prefix (Cheat-Sheet §4.2). Length is i − first.get(prefix). Count of sum=k uses a count map instead.
Brute. All L,R. Time O(n²). Space O(1).
Optimal. HashMap<Long,Integer> prefix→first index; seed 0 → −1. Time O(n) average. Space O(n).
Map<Long, Integer> first = new HashMap<>();
first.put(0L, -1);
long sum = 0;
int ans = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
if (first.containsKey(sum)) ans = Math.max(ans, i - first.get(sum));
else first.put(sum, i);
}
Liar / neighbor. Count of subarrays with sum k updates the map every time (frequency). All-positive window cannot look for exact 0 unless zeros exist.
Source. Cheat-Sheet §2. longest subarray sum = 0, LC 7850431 R2 (snippet).
"GetRandom O(1)" → HashMap + ArrayList swap-delete IE-asked
Why you think of this. HashMap gives O(1) insert/remove/contains but not uniform random. ArrayList gives O(1) random index. Delete in O(1): swap the target with the last slot, pop, update the map index. That pair is the whole DS.
Brute. HashSet + walk to a random rank. Time O(n) getRandom. Space O(n). Or TreeMap — O(log n), not O(1).
Optimal. HashMap<Integer,Integer> val→index, ArrayList<Integer> vals. insert/remove/getRandom average O(1). Space O(n).
Map<Integer, Integer> idx = new HashMap<>();
List<Integer> vals = new ArrayList<>();
boolean insert(int x) {
if (idx.containsKey(x)) return false;
idx.put(x, vals.size());
vals.add(x);
return true;
}
boolean remove(int x) {
if (!idx.containsKey(x)) return false;
int i = idx.get(x), last = vals.get(vals.size() - 1);
vals.set(i, last); idx.put(last, i);
vals.remove(vals.size() - 1); idx.remove(x);
return true;
}
int getRandom() { return vals.get(ThreadLocalRandom.current().nextInt(vals.size())); }
Liar / neighbor. LRU is recency, not random. HashMap alone cannot getRandom in O(1) uniformly.
Source. Cheat-Sheet §2. GetRandom O(1), LC 6573582 R1; GetRandom Insert/Delete/Search O(1), Reddit 1lqy9uq R2.
"LRU" → HashMap + DLL IE-asked
Why you think of this. get/put must be O(1) and you must evict the least recently used. HashMap finds the node; a doubly linked list moves it to the front and evicts the tail. LinkedHashMap access-order works only if you know removeEldestEntry. Login Tracker (new_login / get_oldest_login) is the same shape and is unverified mentor-only — do not present it as a 10454435 question.
Brute. ArrayList of keys, scan for LRU. Time O(n) per op. Space O(capacity).
Optimal. HashMap<Integer,Node> + dummy head/tail. get/put O(1). Space O(capacity).
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;
}
Liar / neighbor. LFU evicts least frequent (next card). Min Stack is two stacks, not a cache. TUF 15 body said LFU while the title said LRU — lock which.
Source. Cheat-Sheet §3 / §4.21. LRU, Bhavya Interview 2 Hyd — chapter 05. Recurring NMF (Roundz R4/BR LRU). Not UTA default.
"LFU" → HashMap + freq → DLL IE-asked
Why you think of this. Evict the least frequent; ties break as LRU inside that freq. You need val map, freq map, and a map freq→DLL of keys at that freq, plus a running minFreq. One HashMap+single DLL is LRU, not LFU.
Brute. Scan all keys for min freq on each eviction. Time O(n) per put. Space O(capacity).
Optimal. HashMap + freq buckets of DLLs. get/put O(1). Space O(capacity).
// Node {k, v, f}; Map<Integer,Node> byKey;
// Map<Integer, LinkedHashSet<Integer>> byFreq; int minFreq;
// on get: leave old freq list, f++, enter new list; if old list empty && f-1==minFreq, minFreq++
// on put over cap: evict byFreq.get(minFreq).iterator().next()
Liar / neighbor. LRU is recency only. Reddit LFU is a different IE from Bhavya LRU. Do not mix Login Tracker into this.
Source. Cheat-Sheet §3. LFU Cache (slug) + extensible-cache LLD, Reddit 1idtlan R2 (opened). TUF 15 title/body mismatch (LRU title, LFU text).