Java for Coding Interviews

Runtime boundaryPortable Java 17+ subset compiled with --release 17, -Xlint:all, and -Werror; the hosted fixture retains its Temurin 25 lane. No code executes in the browser.

ReviewedSeptember 6, 2026

Compatibility floorJava 17+

Fixture evidenceCanonical sources target Java 17; the common fixture is also compiled and executed on hosted Temurin 25.

Source notes

Java Language Specification 25Primitive/reference values, equality, numeric promotion, strings, arrays, generics, and language semantics.
Java SE 25 java.utilCollections Framework, comparators, maps, sets, deques, and priority queues.
Java SE 25 ArrayDequeStack/queue operations, null restrictions, and amortized operation guarantees.
Java SE 25 PriorityQueueHeap ordering, head semantics, comparator behavior, and operation costs.

Input and output conventions#

Function interview: Implement the requested method and minimal helper types. Return the value instead of building a console parser unless requested.
Online assessment: Use the platform's class, method, stdin, and stdout contract exactly; keep diagnostic output out of judged output.

Java interview sequence#

Read in order for a full review, or jump to the contract behind a syntax decision. This remains one guide - not eighteen new routes.

Quick reference#

The four retained cards are compact recall aids. Their full contracts live in the sequence below.

Arrays and listsjava

int[] nums = new int[n];
int[][] grid = new int[rows][cols];
Arrays.fill(nums, -1);
Arrays.sort(nums);

List<Integer> list = new ArrayList<>();
list.add(value);
int first = list.get(0);

Maps and setsjava

Map<Integer, Integer> frequency = new HashMap<>();
Set<Integer> seen = new HashSet<>();

frequency.put(value, frequency.getOrDefault(value, 0) + 1);
boolean present = seen.contains(value);
seen.add(value);

Stack and queuejava

Deque<Integer> stack = new ArrayDeque<>();
stack.push(value);
int top = stack.pop();

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(value);
Integer next = queue.poll();

Priority queuesjava

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue<int[]> byFirst =
    new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

Read the contract and write a method#

Module 1 of 18

Translate the prompt into accepted inputs, mutation policy, return shape, and platform-owned I/O before choosing syntax.

Objectives

Separate a function interview from an assessment program.
State null, empty, mutation, and numeric-width policies.
Return exactly what the caller requests.

PrerequisitesNone.

A bounded method contractjava

public class J01PositiveTotal {
    static long positiveTotal(int[] values) {
        long total = 0;
        for (int value : values) if (value > 0) total += value;
        return total;
    }
    public static void main(String[] args) {
        int[] input = {4, -2, 0, 7};
        assert positiveTotal(input) == 11;
        assert positiveTotal(new int[0]) == 0;
        assert java.util.Arrays.equals(input, new int[]{4, -2, 0, 7});
        System.out.println(positiveTotal(input));
    }
}

Expected: 11; the input is unchanged.

Worked trace

total advances 0 → 4 → 4 → 4 → 11; negative and zero values do not contribute.

MistakeAdding a Scanner and labels to a method-only prompt changes the contract.

RepairKeep parsing at the assessment boundary and the algorithm in a testable method.

Cost modelO(n) time and O(1) working storage; the returned scalar is separate.

BoundariesNon-null int array; empty is valid; long prevents the accumulation from overflowing int.

TakeawaySolve the caller's contract, not a remembered platform format.

Deeper note and related practice

Java passes every argument value by value. For an array, that copied value is a reference to the same array object.

Values, references and method calls#

Module 2 of 18

A reference variable stores a value that identifies an object; copying that value can create aliases, while reassigning a parameter changes only the local slot.

Objectives

Distinguish primitive values from reference values.
Predict shared mutation and local reassignment.
Use equals and identity questions deliberately.

PrerequisitesJ01.

Mutation versus local rebindingjava

public class J02ParameterValues {
    static void change(int[] alias, int scalar) {
        alias[0] = 9;
        alias = new int[]{5};
        scalar = 8;
        assert alias[0] == 5 && scalar == 8;
    }
    public static void main(String[] args) {
        int[] values = {2, 3}; int number = 3;
        change(values, number);
        assert values[0] == 9 && values[1] == 3 && number == 3;
        System.out.println(values[0] + " " + number);
    }
}

Expected: 9 3

Worked trace

The call copies the array reference and scalar. The element write reaches the shared array; both parameter reassignments remain local.

MistakeCalling Java pass-by-reference predicts that reassigning alias changes values in the caller.

RepairDraw caller and callee variables separately, with both reference values pointing to the same array object.

Cost modelReference/scalar assignment is O(1); object equality may inspect data.

BoundariesThe diagram is conceptual identity - not a physical address or JVM heap layout.

TakeawayArguments are copied values; copied reference values may still alias one object.

Copied references, shared mutation

Track caller and callee variables without inventing physical addresses.

JV01 · JV01-pass-values@2026-09-06

public class JV01PassValues {
static boolean trace;
static int[] callerData;
static int callerCount;
static void change(int[] items, int count) {
items[0] = 9;
if (trace) System.out.println("MUTATE|mainData=A|items=A|sameObject=" + (items == callerData) + "|A=" + java.util.Arrays.toString(callerData));
items = new int[]{7, 8};
if (trace) System.out.println("REBIND|mainData=A|items=B|sameObject=" + (items == callerData) + "|A=" + java.util.Arrays.toString(callerData) + "|B=" + java.util.Arrays.toString(items));
count = 99;
if (trace) System.out.println("SCALAR|mainCount=" + callerCount + "|changeCount=" + count + "|mainData=A|items=B|A=" + java.util.Arrays.toString(callerData) + "|B=" + java.util.Arrays.toString(items));
}
public static void main(String[] args) {
trace = args.length == 1 && args[0].equals("--trace");
if (trace) System.out.println("INITIAL|data=unbound|count=unbound");
int[] data = {1, 2};
callerData = data;
if (trace) System.out.println("BIND_DATA|data=A|A=" + java.util.Arrays.toString(data));
int count = 3;
callerCount = count;
if (trace) System.out.println("BIND_COUNT|data=A|count=" + count + "|A=" + java.util.Arrays.toString(data));
if (trace) System.out.println("CALL|mainData=A|items=A|sameObject=" + (data == callerData) + "|mainCount=" + count + "|changeCount=" + count + "|A=" + java.util.Arrays.toString(data));
change(data, count);
if (trace) {
System.out.println("RETURN|mainData=A|mainCount=" + count + "|BUnreachableFromShownLocals=true|A=" + java.util.Arrays.toString(data));
System.out.println("COMPLETE|mainData=A|mainCount=" + count + "|sameCallerBinding=" + (data == callerData) + "|A=" + java.util.Arrays.toString(data));
System.out.println("OUTPUT|output=" + data[0] + " " + count + "|mainData=A|mainCount=" + count + "|A=" + java.util.Arrays.toString(data));
} else {
System.out.println(data[0] + " " + count);
}
assert data[0] == 9 && data[1] == 2 && count == 3;
}
}

Step 1 of 10 · initialInitial state

Main is active; data and count are unbound.

Names and values

dataunbound

countunbound

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Shared array and local slots

Step 1: Initial state
Main is active; data and count are unbound.
data
unbound
count
unbound
Step 2: Bind data
data stores a reference to array A.
data
→ A
A
[1, 2]
Step 3: Bind count
count stores primitive value 3.
data
→ A
count
3
A
[1, 2]
Step 4: Call change
The call copies both argument values into callee parameter slots.
main.data
→ A
main.count
3
change.items
→ A
change.count
3
A
[1, 2]
Step 5: Mutate A
Both reference values still reach A, so the element write is caller-visible.
main.data
→ A
change.items
→ A
A
[9, 2]
Step 6: Rebind callee reference
Only change.items now refers to new array B.
main.data
→ A
change.items
→ B
A
[9, 2]
B
[7, 8]
Step 7: Reassign callee scalar
Changing change.count leaves main.count at 3.
main.count
3
change.count
99
main.data
→ A
change.items
→ B
A
[9, 2]
B
[7, 8]
Step 8: Return change
The callee frame leaves; B is unreachable from the shown locals.
main.data
→ A
main.count
3
B status
unreachable from shown locals
A
[9, 2]
Step 9: Complete call
Main resumes with its original variable bindings.
main.data
→ A
main.count
3
A
[9, 2]
Step 10: Observe caller
The shared mutation remains; local reassignments do not.
output
9 3
main.data
→ A
main.count
3
A
[9, 2]

Deeper note and related practice

Object mutation and variable reassignment are different operations even when they appear in one method.

Primitive values, wrappers and null#

Module 3 of 18

Generics use reference types, so collection operations can box primitives and produce nullable wrapper results.

Objectives

Recognize boxing and unboxing sites.
Avoid identity comparisons between wrappers.
Guard nullable results before unboxing.

PrerequisitesJ02.

Nullable wrapper boundaryjava

import java.util.*;
public class J03BoxingNull {
    static int count(Map<String, Integer> counts, String key) {
        Integer boxed = counts.get(key);
        return boxed == null ? 0 : boxed;
    }
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>(); counts.put("x", 2);
        assert count(counts, "x") == 2 && count(counts, "missing") == 0;
        assert Integer.valueOf(1000).equals(Integer.valueOf(1000));
        System.out.println(count(counts, "missing"));
    }
}

Expected: 0

Worked trace

get(missing) returns null; the guard selects zero before an unboxing conversion could fail.

MistakeAssigning map.get(key) directly to int can throw NullPointerException.

RepairKeep the result boxed until absence has been handled, or use an intentional default.

Cost modelExpected O(1) lookup under ordinary hashing assumptions; boxing may allocate or reuse an object and should not be identity-tested.

BoundariesA present key mapped to null is distinct from an absent key when the map permits null values.

TakeawayTreat wrapper nullability as part of the contract.

Deeper note and related practice

Some Integer instances are cached by specification, which is another reason == is not a value comparison.

Arrays, copies and rectangular grids#

Module 4 of 18

An array fixes its outer length, and a two-dimensional array is an array whose elements are row references.

Objectives

Separate shallow outer copies from copied rows.
Validate rectangular-grid assumptions.
Use half-open copy ranges.

PrerequisitesJ02.

Copy the intended leveljava

import java.util.*;
public class J04ArrayCopy {
    public static void main(String[] args) {
        int[][] grid = {{1, 2}, {3, 4}};
        int[][] shallow = grid.clone();
        int[][] independent = Arrays.stream(grid).map(int[]::clone).toArray(int[][]::new);
        grid[0][1] = 9;
        assert shallow[0][1] == 9 && independent[0][1] == 2;
        System.out.println(shallow[0][1] + " " + independent[0][1]);
    }
}

Expected: 9 2

Worked trace

The outer clone gets new row slots but copies both row references; the stream explicitly clones each row.

MistakeCalling grid.clone() a deep copy hides shared rows.

RepairClone each row when row mutation must be isolated.

Cost modelOuter clone is O(rows); copying every rectangular cell is O(rows×cols) and allocates the copied cells.

BoundariesRows may legally be null or different lengths unless the algorithm requires and validates a rectangle.

TakeawayName which array level a copy duplicates.

Deeper note and related practice

Arrays.copyOfRange uses [from,to); it pads only when the destination range extends past the source for supported overloads.

ArrayList operations, views and copies#

Module 5 of 18

ArrayList offers indexed access and amortized append, while subList is a backed range view rather than a copy.

Objectives

Distinguish view from copy.
Select remove-by-index or remove-by-value.
Account for shifted references.

PrerequisitesJ03, J04.

Range view and removal overloadsjava

import java.util.*;
public class J05ListViews {
    public static void main(String[] args) {
        List<Integer> base = new ArrayList<>(List.of(4, 8, 10));
        List<Integer> view = base.subList(1, 3);
        List<Integer> copy = new ArrayList<>(view);
        view.remove(0); copy.add(12);
        boolean removedValue = copy.remove(Integer.valueOf(8));
        int removedIndex = copy.remove(1);
        assert base.equals(List.of(4, 10)) && view.equals(List.of(10));
        assert removedValue && removedIndex == 12;
        System.out.println(base + " " + view + " " + copy);
    }
}

Expected: [4, 10] [10] [10]

Worked trace

Removing view index 0 removes base index 1. The copy changes independently; the two remove overloads choose value and position.

Mistakeremove(1) on List<Integer> removes index 1, not value 1.

RepairUse Integer.valueOf(value) for value removal and new ArrayList<>(view) for ownership.

Cost modelget is O(1), append amortized O(1), and middle/front removal O(n) due to shifts.

BoundariesStructural changes outside a live view can invalidate its later operations.

TakeawayA range view shares structure until you explicitly copy it.

ArrayList view versus copy

Follow backing-list edits and the two Integer removal overloads.

JV02 · JV02-view-copy@2026-09-06

import java.util.ArrayList;
import java.util.List;
public class JV02ViewCopy {
static boolean trace;
static void emit(String step, List<Integer> base, List<Integer> view, List<Integer> copy) {
if (trace) System.out.println(step + "|baseRef=B|viewRef=V|copyRef=C|viewRange=[1," + (1 + view.size()) + ")|viewBacksBase="
+ view.equals(base.subList(1, 1 + view.size())) + "|B=" + base + "|V=" + view + "|C=" + copy);
}
public static void main(String[] args) {
trace = args.length == 1 && args[0].equals("--trace");
List<Integer> base = new ArrayList<>(List.of(4, 9, 12));
if (trace) System.out.println("1|B=" + base);
List<Integer> view = base.subList(1, 3);
if (trace) System.out.println("2|baseRef=B|viewRef=V|viewRange=[1,3)|viewBacksBase=" + view.equals(base.subList(1, 3)) + "|B=" + base + "|V=" + view + "|baseDistinctView=" + (base != view));
List<Integer> copy = new ArrayList<>(view);
if (trace) System.out.println("3|baseRef=B|viewRef=V|copyRef=C|viewRange=[1,3)|viewBacksBase=" + view.equals(base.subList(1, 3)) + "|B=" + base + "|V=" + view + "|C=" + copy + "|distinct=" + (base != copy && view != copy));
view.set(0, 10);
emit("4", base, view, copy);
int removedIndex = view.remove(1);
emit("5|removedIndex=" + removedIndex, base, view, copy);
boolean removedValue = copy.remove(Integer.valueOf(9));
emit("6|removedValue=" + removedValue, base, view, copy);
if (trace) System.out.println("7|baseRef=B|viewRef=V|copyRef=C|viewRange=[1,2)|viewBacksBase=" + view.equals(base.subList(1, 2)) + "|output=" + base + " / " + view + " / " + copy + "|B=" + base + "|V=" + view + "|C=" + copy);
else System.out.println(base + " / " + view + " / " + copy);
assert base.equals(List.of(4, 10)) && view.equals(List.of(10));
assert copy.equals(List.of(12)) && removedIndex == 12 && removedValue;
}
}

Step 1 of 8 · initialInitial state

No example bindings exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

View, copy, and overloads

Step 1: Initial state
No example bindings exist yet.
bindings
Not available
Step 2: Create base
B is the resizable outer list owned by base.
base
→ B
B
[4, 9, 12]
Step 3: Create backed view
V denotes B positions [1,3); it has no independent element copy.
base
→ B
view
→ V
B
[4, 9, 12]
V
B[1,3) = [9, 12]
Step 4: Create outer copy
C owns separate outer storage initialized from V.
base
→ B
view
→ V
copy
→ C
B
[4, 9, 12]
V
B[1,3) = [9, 12]
C
[9, 12]
Step 5: Replace through view
Updating V index 0 replaces B index 1; C stays unchanged.
base
→ B
view
→ V
copy
→ C
B
[4, 10, 12]
V
B[1,3) = [10, 12]
C
[9, 12]
Step 6: Remove view index 1
remove(int) returns 12 and shortens B and V together.
base
→ B
view
→ V
copy
→ C
removedIndex
12
B
[4, 10]
V
B[1,2) = [10]
C
[9, 12]
Step 7: Remove value from copy
remove(Object) finds 9 in C and returns true; B and V do not change.
base
→ B
view
→ V
copy
→ C
removedValue
true
B
[4, 10]
V
B[1,2) = [10]
C
[12]
Step 8: Print independent owners
The backed view and independent copy now have different contents.
base
→ B
view
→ V
copy
→ C
output
[4, 10] / [10] / [12]
B
[4, 10]
V
B[1,2) = [10]
C
[12]

Deeper note and related practice

Choose a view only while shared structural ownership is intentional and short-lived.

Strings, builders and character assumptions#

Module 6 of 18

String is immutable and indexed in UTF-16 code units; StringBuilder makes repeated construction explicit.

Objectives

Use equals for content.
State ASCII, UTF-16, or code-point assumptions.
Avoid repeatedly copying a growing prefix.

PrerequisitesJ01.

Build one resultjava

public class J06StringBuilder {
    static String join(int[] values) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            if (i > 0) out.append(','); out.append(values[i]);
        }
        return out.toString();
    }
    public static void main(String[] args) {
        assert join(new int[]{10, -2, 7}).equals("10,-2,7");
        assert "😀".length() == 2;
        System.out.println(join(new int[]{10, -2, 7}));
    }
}

Expected: 10,-2,7

Worked trace

The builder grows through 10, 10,-2, then 10,-2,7; toString creates the returned String.

MistakecharAt counts UTF-16 units, not user-perceived characters.

RepairDeclare an ASCII/UTF-16 contract or iterate code points when the task requires them.

Cost modelConstruction is O(m) in produced UTF-16 units under ordinary amortized growth; the returned String is O(m) output.

BoundariesEmpty input returns the empty string; null input is outside this example contract.

TakeawayMake the unit of text processing explicit.

Deeper note and related practice

Do not claim a universal constant-time substring operation; its implementation is not the algorithm contract.

Keys, counts and ordered alternatives#

Module 7 of 18

HashMap and HashSet answer expected-time lookup questions; ordered alternatives change iteration and cost contracts.

Objectives

Keep equals and hashCode consistent.
Distinguish absent from present-null.
Choose HashMap, LinkedHashMap, or TreeMap intentionally.

PrerequisitesJ03.

Count without relying on iteration orderjava

import java.util.*;
public class J07HashContracts {
    public static void main(String[] args) {
        int[] values = {4, 1, 4}; Map<Integer, Integer> counts = new HashMap<>();
        for (int value : values) counts.merge(value, 1, Integer::sum);
        assert counts.get(4) == 2 && counts.getOrDefault(9, 0) == 0;
        assert !counts.containsKey(9);
        System.out.println(counts.get(4));
    }
}

Expected: 2

Worked trace

merge inserts 4→1, inserts 1→1, then replaces 4 with 2; no iteration order is used.

MistakeReturning the first HashMap entry assumes an order the API does not promise.

RepairPreserve input position separately, use LinkedHashMap for encounter order, or TreeMap for key order.

Cost modelExpected O(n) total under ordinary hashing assumptions and O(u) entries; no unconditional worst-case O(1) lookup claim.

BoundariesMutable keys can become unreachable if fields used by equals/hashCode change after insertion.

TakeawayPick both lookup behavior and iteration contract.

Deeper note and related practice

TreeMap gives logarithmic basic operations and comparator order; that is a different tradeoff from hashing.

Iteration, generics and lazy work#

Module 8 of 18

Enhanced-for, Iterator, and Stream expose different mutation and evaluation contracts.

Objectives

Remove through Iterator when structurally editing during traversal.
Recognize erased generic type boundaries.
Know when a lazy stream pipeline executes.

PrerequisitesJ03, J05.

Iterator removal and lazy streamjava

import java.util.*;
public class J08Iteration {
    public static void main(String[] args) {
        List<Integer> values = new ArrayList<>(List.of(1, 2, 3, 4));
        for (Iterator<Integer> it = values.iterator(); it.hasNext();) {
            if ((it.next() & 1) == 0) it.remove();
        }
        long count = values.stream().filter(v -> v > 1).count();
        assert values.equals(List.of(1, 3)) && count == 1;
        System.out.println(values);
    }
}

Expected: [1, 3]

Worked trace

Iterator visits each element and owns both structural removals; the stream filter runs only when count is requested.

MistakeRemoving from the list inside enhanced-for can invalidate the iterator.

RepairUse Iterator.remove, removeIf, or collect changes separately.

Cost modelTraversal is O(n); ArrayList iterator removals can shift a suffix and make repeated removals O(n²).

BoundariesStreams are single-use; toList returns an unmodifiable result in the supported baseline.

TakeawayChoose an iteration form whose mutation and evaluation rules match the task.

Deeper note and related practice

Generic type arguments are mostly erased; runtime casts can still fail where unchecked code crosses the boundary.

Stack and queue contracts#

Module 9 of 18

ArrayDeque supports both LIFO and FIFO end operations without the shifting cost of ArrayList front removal.

Objectives

Use one coherent stack or queue API.
Mark graph discoveries when enqueuing.
Handle empty results without unsafe unboxing.

PrerequisitesJ05.

Explicit empty policyjava

import java.util.*;
public class J09DequeContracts {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(10);
        queue.addLast(20);
        int first = queue.removeFirst();
        Integer second = queue.pollFirst();
        Integer empty = queue.peekFirst();
        assert first == 10 && second != null && second == 20 && empty == null;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        int top = stack.pop();
        int last = stack.pop();
        Integer after = stack.peek();
        assert top == 20 && last == 10 && after == null;
        System.out.println(first + " " + top);
    }
}

Expected: 10 20

Worked trace

The queue removes 10 then 20; the stack removes 20 then 10. These operations happen before validation, so the same 10 20 result is produced with assertions enabled or disabled.

Mistakeint next = queue.peek() throws when an empty queue returns null.

RepairKeep the nullable result as Integer until the empty case is handled, and never put an operation required for the demonstrated result only inside assert.

Cost modelArrayDeque end operations are amortized O(1); n ArrayList front removals shift n(n−1)/2 references in the simple model.

BoundariesArrayDeque rejects null elements; empty poll/peek return null, while remove/element throw.

TakeawayChoose the empty behavior and end convention deliberately.

Front-removal work model

Compare equal FIFO results with ArrayList reference shifts and ArrayDeque end operations.

JV03 · JV03-queue-work@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class JV03QueueWork {
record Summary(List<Integer> removed, long shifts) {}
static Summary drain(List<Integer> input, boolean trace) {
List<Integer> items = new ArrayList<>(input);
Deque<Integer> queue = new ArrayDeque<>(input);
long shifts = 0;
List<Integer> removed = new ArrayList<>();
if (trace) System.out.println("0|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|shifts=" + shifts);
while (!items.isEmpty()) {
long increment = items.size() - 1;
shifts += increment;
int left = items.remove(0);
int right = queue.removeFirst();
if (left != right) throw new AssertionError("FIFO mismatch");
removed.add(left);
if (trace) System.out.println("I|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|increment=" + increment + "|shifts=" + shifts);
}
if (trace) System.out.println("R|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|shifts=" + shifts);
return new Summary(List.copyOf(removed), shifts);
}
public static void main(String[] args) {
if (args.length > 0 && args[0].equals("--trace")) {
String preset = args.length == 1 ? "default" : args[1];
List<Integer> input = switch (preset) {
case "default" -> List.of(10, 20, 30, 40);
case "empty" -> List.of();
case "eight" -> List.of(1, 2, 3, 4, 5, 6, 7, 8);
default -> throw new IllegalArgumentException("unknown preset");
};
drain(input, true);
return;
}
Summary result = drain(List.of(10, 20, 30, 40), false);
assert result.removed().equals(List.of(10, 20, 30, 40)) && result.shifts() == 6;
Summary empty = drain(List.of(), false);
assert empty.removed().isEmpty() && empty.shifts() == 0;
Summary wide = drain(List.of(1, 2, 3, 4, 5, 6, 7, 8), false);
assert wide.shifts() == 28 && wide.removed().size() == 8;
System.out.println(result.removed() + " shifts=" + result.shifts());
}
}

Step 1 of 6 · initialInitial lanes

Both collections contain the same FIFO values; shifts are a logical reference-movement model.

ArrayList

010120230340

ArrayDeque

010120230340

removed

[]

shift model total

0

Speed

Read all steps

Four values

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[10, 20, 30, 40]
ArrayDeque
[10, 20, 30, 40]
removed
[]
shift model total
0
Step 2: Remove 10
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[20, 30, 40]
ArrayDeque
[20, 30, 40]
removed
[10]
shift model step / total
3 / 3
Step 3: Remove 20
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[30, 40]
ArrayDeque
[30, 40]
removed
[10, 20]
shift model step / total
2 / 5
Step 4: Remove 30
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[40]
ArrayDeque
[40]
removed
[10, 20, 30]
shift model step / total
1 / 6
Step 5: Remove 40
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[]
ArrayDeque
[]
removed
[10, 20, 30, 40]
shift model step / total
0 / 6
Step 6: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[10, 20, 30, 40]
shift model total
6

Empty

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[]
ArrayDeque
[]
removed
[]
shift model total
0
Step 2: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[]
shift model total
0

Eight-entry frontier

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[1, 2, 3, 4, 5, 6, 7, 8]
ArrayDeque
[1, 2, 3, 4, 5, 6, 7, 8]
removed
[]
shift model total
0
Step 2: Remove 1
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[2, 3, 4, 5, 6, 7, 8]
ArrayDeque
[2, 3, 4, 5, 6, 7, 8]
removed
[1]
shift model step / total
7 / 7
Step 3: Remove 2
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[3, 4, 5, 6, 7, 8]
ArrayDeque
[3, 4, 5, 6, 7, 8]
removed
[1, 2]
shift model step / total
6 / 13
Step 4: Remove 3
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[4, 5, 6, 7, 8]
ArrayDeque
[4, 5, 6, 7, 8]
removed
[1, 2, 3]
shift model step / total
5 / 18
Step 5: Remove 4
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[5, 6, 7, 8]
ArrayDeque
[5, 6, 7, 8]
removed
[1, 2, 3, 4]
shift model step / total
4 / 22
Step 6: Remove 5
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[6, 7, 8]
ArrayDeque
[6, 7, 8]
removed
[1, 2, 3, 4, 5]
shift model step / total
3 / 25
Step 7: Remove 6
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[7, 8]
ArrayDeque
[7, 8]
removed
[1, 2, 3, 4, 5, 6]
shift model step / total
2 / 27
Step 8: Remove 7
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[8]
ArrayDeque
[8]
removed
[1, 2, 3, 4, 5, 6, 7]
shift model step / total
1 / 28
Step 9: Remove 8
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[]
ArrayDeque
[]
removed
[1, 2, 3, 4, 5, 6, 7, 8]
shift model step / total
0 / 28
Step 10: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[1, 2, 3, 4, 5, 6, 7, 8]
shift model total
28

Deeper note and related practice

The shift model counts logical reference moves, not CPU instructions or elapsed time.

Comparators and stable object sorting#

Module 10 of 18

A comparator defines ordering; stable object sorting retains encounter order when that comparator returns zero.

Objectives

Avoid subtraction overflow.
Declare tie policy.
Distinguish copied from mutated lists.

PrerequisitesJ05, J07.

Stable copied orderingjava

import java.util.*;
public class J10StableSort {
    record Item(String id, int rank) {}
    public static void main(String[] args) {
        List<Item> source = new ArrayList<>(List.of(new Item("A",2), new Item("B",1), new Item("C",2)));
        List<Item> ordered = new ArrayList<>(source);
        ordered.sort(Comparator.comparingInt(Item::rank));
        assert source.get(0).id().equals("A");
        assert ordered.stream().map(Item::id).reduce("", String::concat).equals("BAC");
        System.out.println("BAC");
    }
}

Expected: BAC; A remains before C among equal ranks.

Worked trace

The copy starts A,B,C. Sorting by rank yields B,A,C; source retains A,B,C.

Mistake(a,b) -> a.rank-b.rank can overflow; an undeclared tie leaves PriorityQueue behavior arbitrary.

RepairUse comparingInt/Integer.compare and thenComparing when ties need deterministic order.

Cost modelObject-list sorting is O(n log n) comparisons; comparator key extraction may run many times and is not cached once per element.

BoundariesList.sort is stable and mutates the list; copying n references first costs O(n) time/storage.

TakeawayPut the complete order policy in the comparator.

Stable object sorting

Separate comparator policy, stable ties, copied input, and sorted output.

JV04 · JV04-sort-rule@2026-09-06

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class JV04SortRule {
record Item(String id, int priority) {}
static String labels(List<Item> items) {
StringBuilder out = new StringBuilder();
for (Item item : items) {
if (!out.isEmpty()) out.append(',');
out.append(item.id()).append(':').append(item.priority());
}
return out.toString();
}
public static void main(String[] args) {
boolean trace = args.length == 1 && args[0].equals("--trace");
Item a = new Item("A", 2), b = new Item("B", 1), c = new Item("C", 2);
List<Item> original = new ArrayList<>(List.of(a, b, c));
if (trace) System.out.println("CREATE|original=" + labels(original));
List<Item> ordered = new ArrayList<>(original);
if (trace) System.out.println("COPY|original=" + labels(original) + "|ordered=" + labels(ordered) + "|outerDistinct=" + (original != ordered) + "|sameItems=" + (original.get(0) == ordered.get(0) && original.get(1) == ordered.get(1) && original.get(2) == ordered.get(2)));
if (trace) System.out.println("CONCEPTUAL|original=" + labels(original) + "|ordered=" + labels(ordered) + "|keys=" + labels(List.of(a, b, c)));
Comparator<Item> order = Comparator.comparingInt(Item::priority);
if (trace) System.out.println("COMPARATOR|original=" + labels(original) + "|ordered=" + labels(ordered) + "|rule=ascending priority|BbeforeA=" + (order.compare(b, a) < 0));
ordered.sort(order);
if (trace) System.out.println("SORT_COPY|original=" + labels(original) + "|ordered=" + labels(ordered) + "|stableTie=" + (ordered.indexOf(a) < ordered.indexOf(c)) + "|sameItems=" + (ordered.containsAll(original) && original.containsAll(ordered)));
original.sort(order);
if (trace) System.out.println("SORT_ORIGINAL|original=" + labels(original) + "|ordered=" + labels(ordered) + "|outerDistinct=" + (original != ordered) + "|stableTie=" + (original.indexOf(a) < original.indexOf(c)));
String output = ordered.get(0).id() + ordered.get(1).id() + ordered.get(2).id();
if (trace) System.out.println("OUTPUT|original=" + labels(original) + "|ordered=" + labels(ordered) + "|output=" + output + "|sharedA=" + (ordered.get(1) == a) + "|stableTie=" + (ordered.indexOf(a) < ordered.indexOf(c)));
else System.out.println(output);
assert ordered.equals(List.of(b, a, c)) && original.equals(ordered);
assert ordered != original && ordered.get(1) == a;
Comparator<Integer> broken = (left, right) -> left - right;
assert broken.compare(Integer.MAX_VALUE, 0) > 0;
assert broken.compare(0, -1) > 0;
assert broken.compare(Integer.MAX_VALUE, -1) < 0;
assert Integer.compare(Integer.MAX_VALUE, -1) > 0;
}
}

Step 1 of 7 · initialCreate original

A precedes C among equal priorities.

original

A:2 · B:1 · C:2

Speed

Boundary check: The three subtraction comparisons in the executable harness contradict transitivity at extreme int values. Integer.compare does not overflow; sort need not reject every broken comparator.

Read all steps

Priority with stable ties

Step 1: Create original
A precedes C among equal priorities.
original
A:2 · B:1 · C:2
Step 2: Copy original
The new outer list stores the same item references.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
Step 3: Conceptual comparator focus
Priority badges aid the explanation; comparingInt may call the extractor repeatedly.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
keys
A→2 · B→1 · C→2
Step 4: Create comparator
The ordering rule exists; neither list has been sorted.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
rule
ascending priority
Step 5: Sort copied list
B moves first; stable sorting keeps A before C.
original
A:2 · B:1 · C:2
ordered
B:1 · A:2 · C:2
Step 6: Sort original list
Original now mutates to the same order but remains a distinct outer list.
original
B:1 · A:2 · C:2
ordered
B:1 · A:2 · C:2
Step 7: Print BAC
Both stable lists retain A before C among tied priorities.
original
B:1 · A:2 · C:2
ordered
B:1 · A:2 · C:2
output
BAC

Deeper note and related practice

Comparator consistency with equals is sometimes desirable but not automatically required; document deviations.

Priorities, ties and bounded selection#

Module 11 of 18

PriorityQueue exposes the least element under its comparator, not a sorted iterator or portable backing-array layout.

Objectives

Separate membership, head, and poll order.
Make tie policy explicit.
Define k=0 and k>n.

PrerequisitesJ10.

Priority and insertion sequencejava

import java.util.*;
public class J11PriorityTies {
    record Task(String id, int priority, long sequence) {}
    public static void main(String[] args) {
        PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::priority).thenComparingLong(Task::sequence));
        queue.offer(new Task("A",2,0)); queue.offer(new Task("B",1,1)); queue.offer(new Task("C",2,2));
        String order = queue.poll().id() + queue.poll().id() + queue.poll().id();
        assert order.equals("BAC") && queue.poll() == null;
        System.out.println(order);
    }
}

Expected: BAC

Worked trace

B becomes head by priority; A precedes C only because sequence is the declared secondary key.

MistakeDisplaying iteration order as sorted output or as a specified internal heap layout is false.

RepairPoll to obtain priority order; label any tree as a conceptual arrangement satisfying parent≤child.

Cost modeloffer/poll O(log n), peek O(1); heapify from a collection can be O(n), while repeated insertion is O(n log n).

BoundariesTies are arbitrary without a secondary comparator; null elements are rejected.

TakeawayA heap promises the next priority, not a fully sorted view.

PriorityQueue membership and head

Use a labeled conceptual heap arrangement without claiming the private backing layout.

JV05 · JV05-heap-ties@2026-09-06

import java.util.Comparator;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.PriorityQueue;
public class JV05HeapTies {
record Task(int priority, long sequence, String name) {}
static String tuple(Task task) {
return task == null ? "null" : "(" + task.priority() + "," + task.sequence() + "," + task.name() + ")";
}
static String heap(List<Task> conceptual) {
StringBuilder out = new StringBuilder("[");
for (int i = 0; i < conceptual.size(); i++) {
if (i > 0) out.append(", ");
out.append(tuple(conceptual.get(i)));
}
return out.append(']').toString();
}
static boolean heapInvariant(List<Task> conceptual, Comparator<Task> order) {
for (int child = 1; child < conceptual.size(); child++) {
if (order.compare(conceptual.get((child - 1) / 2), conceptual.get(child)) > 0) return false;
}
return true;
}
static String membership(PriorityQueue<Task> queue, Task a, Task b, Task c) {
StringBuilder out = new StringBuilder("[");
for (Task task : List.of(a, b, c)) if (queue.contains(task)) {
if (out.length() > 1) out.append(", ");
out.append(task.name());
}
return out.append(']').toString();
}
static boolean actualMembershipMatches(List<Task> conceptual, PriorityQueue<Task> queue) {
if (conceptual.size() != queue.size()) return false;
IdentityHashMap<Task, Integer> conceptualCounts = new IdentityHashMap<>();
IdentityHashMap<Task, Integer> actualCounts = new IdentityHashMap<>();
for (Task task : conceptual) conceptualCounts.merge(task, 1, Integer::sum);
for (Task task : queue) actualCounts.merge(task, 1, Integer::sum);
if (conceptualCounts.size() != actualCounts.size()) return false;
for (Task task : conceptualCounts.keySet()) {
if (!conceptualCounts.get(task).equals(actualCounts.get(task))) return false;
}
return true;
}
static void emit(boolean trace, String event, List<Task> conceptual, PriorityQueue<Task> queue,
Comparator<Task> order, Task a, Task b, Task c, String returned) {
if (!trace) return;
System.out.println(event + "|heap=" + heap(conceptual) + "|membership=" + membership(queue, a, b, c)
+ "|head=" + (queue.peek() == null ? "none" : queue.peek().name())
+ "|heapInvariant=" + heapInvariant(conceptual, order)
+ "|actualMembershipMatch=" + actualMembershipMatches(conceptual, queue) + returned);
}
public static void main(String[] args) {
boolean trace = args.length == 1 && args[0].equals("--trace");
Comparator<Task> order = Comparator.comparingInt(Task::priority).thenComparingLong(Task::sequence);
Task a = new Task(2, 0, "A"), b = new Task(1, 1, "B"), c = new Task(2, 2, "C");
PriorityQueue<Task> queue = new PriorityQueue<>(order);
emit(trace, "INIT", List.of(), queue, order, a, b, c, "");
queue.offer(a);
emit(trace, "OFFER_A", List.of(a), queue, order, a, b, c, "");
queue.offer(b);
emit(trace, "OFFER_B", List.of(b, a), queue, order, a, b, c, "");
queue.offer(c);
emit(trace, "OFFER_C", List.of(b, a, c), queue, order, a, b, c, "");
Task first = queue.remove();
emit(trace, "REMOVE_B", List.of(a, c), queue, order, a, b, c, "|returned=B");
Task second = queue.remove();
emit(trace, "REMOVE_A", List.of(c), queue, order, a, b, c, "|returned=B,A");
Task third = queue.remove();
emit(trace, "REMOVE_C", List.of(), queue, order, a, b, c, "|returned=B,A,C");
Task empty = queue.poll();
emit(trace, "POLL_EMPTY", List.of(), queue, order, a, b, c, "|empty=null");
String output = first.name() + second.name() + third.name();
if (trace) emit(true, "OUTPUT", List.of(), queue, order, a, b, c, "|output=" + output);
else System.out.println(output);
assert first == b && second == a && third == c && empty == null;
}
}

Step 1 of 9 · initialInitial queue

No task is present.

One heap, array view

empty

Same entries, parent/child view

empty

membership: []

Speed

Boundary check: One valid heap arrangement; Java PriorityQueue does not expose a guaranteed backing-array order. [B,C,A] is also a valid conceptual min-heap while not globally sorted.

Read all steps

Priorities and explicit ties

Step 1: Initial queue
No task is present.
heap array
[]
membership
[]
Step 2: Offer A
A is the only member and therefore the head.
heap array
[(2,0,A)]
membership
[A]
head
A
Step 3: Offer B
B has smaller priority and becomes head.
heap array
[(1,1,B), (2,0,A)]
membership
[A, B]
head
B
Step 4: Offer C
Sequence breaks the priority-2 tie between A and C.
heap array
[(1,1,B), (2,0,A), (2,2,C)]
membership
[A, B, C]
head
B
Step 5: Remove B
The comparator-minimum object leaves.
heap array
[(2,0,A), (2,2,C)]
membership
[A, C]
returned
B
Step 6: Remove A
A wins the explicit sequence tie.
heap array
[(2,2,C)]
membership
[C]
returned
B · A
Step 7: Remove C
The queue becomes empty.
heap array
[]
membership
[]
returned
B · A · C
Step 8: Poll empty
poll returns null rather than throwing.
heap array
[]
membership
[]
empty result
null
Step 9: Print BAC
The declared policy produces deterministic poll order.
heap array
[]
membership
[]
output
BAC

Deeper note and related practice

For top-k, state whether output must be sorted; sorting k retained values adds O(k log k).

Search results and duplicate boundaries#

Module 12 of 18

Half-open [left,right) invariants make lower and upper duplicate boundaries composable.

Objectives

Decode library insertion points.
Write lower and upper boundaries.
Handle duplicates, after-all, and empty input.

PrerequisitesJ04.

Both duplicate boundariesjava

public class J12Boundaries {
    static int boundary(int[] a, int target, boolean upper) {
        int left=0, right=a.length;
        while (left<right) { int middle=left+(right-left)/2;
            if (a[middle]<target || (upper && a[middle]==target)) left=middle+1; else right=middle;
        }
        return left;
    }
    public static void main(String[] args) {
        int[] a={1,3,3,7}; assert boundary(a,3,false)==1; assert boundary(a,3,true)==3;
        assert boundary(a,9,false)==4 && boundary(new int[0],3,false)==0;
        System.out.println(boundary(a,3,false)+" "+boundary(a,3,true));
    }
}

Expected: 1 3

Worked trace

Lower moves equal values rightward into the candidate region; upper moves them leftward out of it.

MistakeArrays.binarySearch may return any matching duplicate index, not the first or last.

RepairEncode the partition explicitly and return the insertion boundary.

Cost modelO(log(n+1)) comparisons and O(1) working storage on random-access arrays.

BoundariesEmpty returns 0; after-all returns n; use right-left arithmetic to avoid midpoint addition overflow.

TakeawaySearch for a boundary predicate, not merely an equal element.

Duplicate boundaries

Trace lower/upper insertion boundaries without revealing the result before the interval closes.

JV06 · JV06-boundaries@2026-09-06

Example

public class JV06Boundaries {
static int boundary(int[] values, int target, boolean upper, boolean trace) {
int left = 0, right = values.length;
if (trace) System.out.println("0|interval=[" + left + "," + right + ")");
while (left < right) {
int middle = left + (right - left) / 2;
int compared = values[middle];
if (values[middle] < target || (upper && values[middle] == target)) {
left = middle + 1;
} else {
right = middle;
}
if (trace) System.out.println("I|middle=" + middle + "|value=" + compared + "|interval=[" + left + "," + right + ")");
}
if (trace) System.out.println("R|result=" + left + "|interval=[" + left + "," + right + ")");
return left;
}
public static void main(String[] args) {
boolean trace = args.length > 0 && args[0].equals("--trace");
String preset = trace ? (args.length > 1 ? args[1] : "lower") : (args.length == 0 ? "lower" : args[0]);
int[] values = preset.equals("empty") ? new int[0] : new int[]{1, 3, 3, 7};
int target = preset.equals("after") ? 9 : 3;
boolean upper = preset.equals("upper");
int result = boundary(values, target, upper, trace);
int expected = switch (preset) {
case "lower" -> 1;
case "upper" -> 3;
case "after" -> 4;
case "empty" -> 0;
default -> throw new IllegalArgumentException("unknown preset");
};
assert result == expected;
if (!trace) System.out.println(result);
}
}

Step 1 of 5 · initialStart lower

The half-open candidate interval shrinks while the answer remains concealed.

values

01132337

candidate interval

[0,4)

result

hidden

Speed

Read all steps

lower 3

Step 1: Start lower
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,2)
result
hidden
Step 3: Compare index 1 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,1)
result
hidden
Step 4: Compare index 0 / value 1
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[1,1)
result
hidden
Step 5: Return lower
The empty half-open interval reveals boundary 1.
values
[1, 3, 3, 7]
candidate interval
[1,1)
result
1

upper 3

Step 1: Start upper
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,4)
result
hidden
Step 3: Compare index 3 / value 7
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,3)
result
hidden
Step 4: Return upper
The empty half-open interval reveals boundary 3.
values
[1, 3, 3, 7]
candidate interval
[3,3)
result
3

lower 9

Step 1: Start after
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,4)
result
hidden
Step 3: Compare index 3 / value 7
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[4,4)
result
hidden
Step 4: Return length
The empty half-open interval reveals boundary 4.
values
[1, 3, 3, 7]
candidate interval
[4,4)
result
4

empty

Step 1: Start empty
The half-open candidate interval shrinks while the answer remains concealed.
values
[]
candidate interval
[0,0)
result
hidden
Step 2: Return zero
The empty half-open interval reveals boundary 0.
values
[]
candidate interval
[0,0)
result
0

Deeper note and related practice

A negative library result encodes insertion point as -result-1; Integer.MIN_VALUE is not produced for valid array lengths.

Overflow, division and bit masks#

Module 13 of 18

Java integer arithmetic uses fixed widths; widening after overflow is too late, and / truncates toward zero.

Objectives

Promote operands before arithmetic.
Choose truncating or floor division.
Build masks without shifting in the wrong width.

PrerequisitesJ01.

Promote before the operationjava

public class J13NumericContracts {
    public static void main(String[] args) {
        int a=Integer.MAX_VALUE, b=1; long safe=(long)a+b;
        assert safe==2147483648L && -7/3==-2 && Math.floorDiv(-7,3)==-3;
        long bit40=1L<<40; assert bit40==1099511627776L;
        System.out.println(safe);
    }
}

Expected: 2147483648

Worked trace

Casting a first selects long addition; 1L selects a 64-bit shift before bit 40 is formed.

Mistakelong total = a+b still performs overflowing int addition first.

RepairWiden an operand before the operation and use exact arithmetic helpers when overflow must reject.

Cost modelFixed-width primitive arithmetic is O(1); BigInteger costs depend on operand size.

BoundariesMath.abs(Integer.MIN_VALUE) remains negative; shift distances are masked by the language.

TakeawayChoose width and rounding semantics before calculating.

Deeper note and related practice

Use floorDiv/floorMod only when mathematical floor behavior - not truncation toward zero - is the contract.

Waiting calls and return values#

Module 14 of 18

Each invocation owns locals while callers wait at a call site; a return value is then assigned into the resumed frame.

Objectives

Trace calls and returns separately.
Account for O(depth) frames.
Replace unbounded depth with an explicit stack.

PrerequisitesJ01, J02.

Triangular return chainjava

public class J14CallReturns {
    static int triangular(int n) {
        if (n==0) return 0;
        int subtotal=triangular(n-1);
        return n+subtotal;
    }
    public static void main(String[] args) {
        assert triangular(3)==6 && triangular(0)==0;
        System.out.println(triangular(3));
    }
}

Expected: 6

Worked trace

Calls create n=3,2,1,0 frames; returns produce 0, then locals receive 0,1,3 before returning 1,3,6.

MistakeMerging a callee return with assignment into the caller hides the suspended frame.

RepairDraw a return token, then a separate resumed-caller state.

Cost modelO(n) time and O(n) call frames for this recurrence.

BoundariesThis method requires n≥0; Java does not guarantee a portable safe recursion-depth number.

TakeawayEvery recursive call suspends one distinct local environment.

Recursive callers wait

Distinguish return tokens from assignment into suspended caller locals.

JV07 · JV07-call-stack@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.Deque;
public class JV07CallStack {
static boolean trace;
static final Deque<Integer> liveCalls = new ArrayDeque<>();
static void emit(String event) {
if (trace) System.out.println(event + "|stack=" + liveCalls + "|depth=" + liveCalls.size());
}
static long triangular(int n) {
liveCalls.addLast(n);
emit("CALL|n=" + n);
if (n == 0) {
liveCalls.removeLast();
emit("RETURN|n=0|value=0");
return 0L;
}
long subtotal = triangular(n - 1);
emit("ASSIGN|n=" + n + "|subtotal=" + subtotal);
long result = n + subtotal;
liveCalls.removeLast();
emit("RETURN|n=" + n + "|value=" + result);
return result;
}
public static void main(String[] args) {
trace = args.length > 0 && args[0].equals("--trace");
int n = trace ? (args.length > 1 ? Integer.parseInt(args[1]) : 3) : (args.length == 0 ? 3 : Integer.parseInt(args[0]));
if (n != 0 && n != 3) throw new IllegalArgumentException("preset must be 0 or 3");
liveCalls.clear();
long answer = triangular(n);
if (trace) {
emit("MAIN_ASSIGN|answer=" + answer);
emit("PRINT|output=" + answer);
} else {
System.out.println(answer);
}
assert answer == (n == 0 ? 0L : 6L);
}
}

Step 1 of 14 · initialInitial state

Ready to call triangular(3); answer is unbound.

Call stack · newest active frame first

call stackempty

Return token and shared state

answer: unbound

Speed

Read all steps

n = 3

Step 1: Initial state
Ready to call triangular(3); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F3
Create F3 with n=3 and an unbound subtotal.
F3
n=3 · subtotal=unbound
Step 3: Call F2
F3 waits while F2 starts.
F3
waiting at L3
F2
n=2 · subtotal=unbound
Step 4: Call F1
F3 and F2 wait while F1 starts.
F3
waiting
F2
waiting
F1
n=1 · subtotal=unbound
Step 5: Call F0
The next invocation reaches the base case.
F3
waiting at L3
F2
waiting at L3
F1
waiting at L3
F0
n=0
Step 6: Return 0
F0 produces a return token; F1 has not assigned it yet.
F3
waiting at L3
F2
waiting at L3
F1
waiting at L3
just returned
0
Step 7: Assign F1 subtotal
F1 consumes the token into subtotal.
F3
waiting at L3
F2
waiting at L3
F1
n=1 · subtotal=0
Step 8: Return 1
F1 computes 1+0 and returns a token to F2.
F3
waiting at L3
F2
waiting at L3
just returned
1
Step 9: Assign F2 subtotal
F2 consumes the token into subtotal.
F3
waiting at L3
F2
n=2 · subtotal=1
Step 10: Return 3
F2 computes 2+1 and returns a token to F3.
F3
waiting at L3
just returned
3
Step 11: Assign F3 subtotal
F3 consumes the token into subtotal.
F3
n=3 · subtotal=3
Step 12: Return 6
F3 computes 3+3; the call stack becomes empty.
call stack
empty
just returned
6
Step 13: Assign answer
The outer call consumes the final token.
call stack
empty
answer
6
Step 14: Print 6
The final output reads the assigned result after every callee has returned.
output
6
answer
6

n = 0

Step 1: Initial state
Ready to call triangular(0); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F0
Main waits while the boundary invocation runs.
main
waiting at L5
F0
n=0
Step 3: Return 0
The base frame emits a return token; main has not assigned it yet.
call stack
empty
just returned
0
Step 4: Assign answer
Main consumes the token into answer.
call stack
empty
answer
0
Step 5: Print 0
The output reads the assigned result.
output
0
answer
0

Deeper note and related practice

Tail-call elimination is not a Java language guarantee, so do not rely on it for unbounded traversal.

Backtracking copies and memo states#

Module 15 of 18

Backtracking mutates one working path and saves independent snapshots; memoization also needs a distinct uncomputed state.

Objectives

Follow choose/recurse/undo.
Copy at the save boundary.
Separate an uncomputed memo slot from a valid zero.

PrerequisitesJ14.

Save path snapshotsjava

import java.util.*;
public class J15Subsets {
    static void search(int[] a,int i,List<Integer> path,List<List<Integer>> out){
        if(i==a.length){out.add(new ArrayList<>(path));return;}
        search(a,i+1,path,out); path.add(a[i]); search(a,i+1,path,out); path.remove(path.size()-1);
    }
    static List<List<Integer>> subsets(int[] a){List<List<Integer>> out=new ArrayList<>();search(a,0,new ArrayList<>(),out);return out;}
    public static void main(String[] args){var out=subsets(new int[]{1,2});assert out.toString().equals("[[], [2], [1], [1, 2]]");System.out.println(out);}
}

Expected: [[], [2], [1], [1, 2]]

Uncomputed is not zerojava

import java.util.*;
public class J15MemoStates {
    static long best(int[] a,int i,Long[] memo){if(i>=a.length)return 0;if(memo[i]!=null)return memo[i];return memo[i]=Math.max(best(a,i+1,memo),a[i]+best(a,i+2,memo));}
    public static void main(String[] args){int[] a={-2,0,5};long answer=best(a,0,new Long[a.length]);assert answer==5;System.out.println(answer);}
}

Expected: 5

Worked trace

For [1,2], exclude-first saves [], [2], [1], [1,2]; after every child returns, undo restores the caller's path.

MistakeSaving path itself stores four references to the same mutable object.

RepairCreate new ArrayList<>(path) at each leaf and use nullable/visited state for memo entries.

Cost modelSubsets require Θ(n·2ⁿ) returned elements across copied answers and O(n) active path/frames.

BoundariesEmpty input returns one empty subset; output cost is not auxiliary workspace.

TakeawayShare the work buffer; copy only when ownership transfers to the result.

Backtracking restores shared state

Follow exclude, choose, recurse, undo, copied saves, outer return, and caller assignment.

JV08 · JV08-backtracking@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.List;
public class JV08Backtracking {
static boolean trace;
static final Deque<Integer> stack = new ArrayDeque<>();
static int savedId;
static List<Integer> trackedPath;
static List<List<Integer>> trackedAnswers;
static void emit(String event, List<Integer> path, List<List<Integer>> answers) {
if (trace) System.out.println(event + "|stack=" + stack + "|path=" + path + "|answers=" + answers
+ "|samePath=" + (path == trackedPath) + "|sameAnswers=" + (answers == trackedAnswers));
}
static List<List<Integer>> subsets(int[] values) {
List<List<Integer>> answers = new ArrayList<>();
List<Integer> path = new ArrayList<>();
trackedPath = path;
trackedAnswers = answers;
stack.clear();
savedId = 0;
emit("INIT|pathDistinctAnswers=" + (path != (Object) answers), path, answers);
search(values, 0, path, answers);
emit("AFTER_OUTER_CALL", path, answers);
emit("OUTER_RETURN|token=A", path, answers);
return answers;
}
static void search(int[] values, int index, List<Integer> path,
List<List<Integer>> answers) {
stack.addLast(index);
emit("CALL|index=" + index, path, answers);
if (index == values.length) {
List<Integer> snapshot = new ArrayList<>(path);
answers.add(snapshot);
emit("SAVE|id=A" + savedId++ + "|distinctFromPath=" + (snapshot != path), path, answers);
stack.removeLast();
emit("RETURN_LEAF|index=" + index, path, answers);
return;
}
search(values, index + 1, path, answers);
path.add(values[index]);
emit("CHOOSE|value=" + values[index], path, answers);
search(values, index + 1, path, answers);
path.remove(path.size() - 1);
emit("UNDO|value=" + values[index], path, answers);
stack.removeLast();
emit("RETURN_SEARCH|index=" + index, path, answers);
}
public static void main(String[] args) {
trace = args.length > 0 && args[0].equals("--trace");
boolean empty = trace ? args.length > 1 && args[1].equals("empty") : args.length == 1 && args[0].equals("empty");
int[] values = empty ? new int[0] : new int[]{1, 2};
List<List<Integer>> result = subsets(values);
if (trace) {
IdentityHashMap<List<Integer>, Boolean> identities = new IdentityHashMap<>();
for (List<Integer> answer : result) identities.put(answer, Boolean.TRUE);
System.out.println("MAIN_ASSIGN|resultSameAnswers=" + (result == trackedAnswers) + "|savedDistinct=" + (identities.size() == result.size()) + "|result=" + result);
System.out.println("PRINT|output=" + result);
} else {
System.out.println(result);
}
List<List<Integer>> expected = empty ? List.of(List.of())
: List.of(List.of(), List.of(2), List.of(1), List.of(1, 2));
assert result.equals(expected);
}
}

Step 1 of 29 · afterAfter outer initialization

P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.

Call stack · newest active frame first

search stack[]

Return token and shared state

path P: []
saved objects: []

Speed

Boundary check: Replacing L6 with answers.add(path) stores the same mutable path reference four times. Executing that change yields [[], [], [], []] after all undo steps.

Read all steps

values = [1, 2]

Step 1: After outer initialization
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[]
Step 2: Call search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[]
Step 3: Exclude 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[]
Step 4: Exclude 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2a:index=2]
path P
[]
saved objects
[]
Step 5: Save A0
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2a]
path P
[]
saved objects
[A0=[]]
Step 6: Return leaf F2a
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[A0=[]]
Step 7: Choose 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[2]
saved objects
[A0=[]]
Step 8: Include 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2b:index=2]
path P
[2]
saved objects
[A0=[]]
Step 9: Save A1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2b]
path P
[2]
saved objects
[A0=[],A1=[2]]
Step 10: Return leaf F2b
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[2]
saved objects
[A0=[],A1=[2]]
Step 11: Undo 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[A0=[],A1=[2]]
Step 12: Return search(1)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[],A1=[2]]
Step 13: Choose 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 14: Include 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 15: Exclude 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2c:index=2]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 16: Save A2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2c]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 17: Return leaf F2c
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 18: Choose 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 19: Include 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2d:index=2]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 20: Save A3
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2d]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 21: Return leaf F2d
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 22: Undo 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 23: Return search(1)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 24: Undo 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 25: Return search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 26: After search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 27: Return answers
The outer method returns answer-list reference A as a token; main has not assigned it yet.
search stack
no live search/outer frame
path P
not live
saved objects
token→A=[[],[2],[1],[1,2]]
Step 28: Assign result
Main consumes the returned reference into result.
search stack
main active
path P
not live
saved objects
main.result→A=[[],[2],[1],[1,2]]
Step 29: Final output
The output reads four independent saved lists after P was restored.
search stack
main active
path P
not live
saved objects
output [[], [2], [1], [1, 2]]

values = []

Step 1: After outer initialization
The outer frame holds shared path P and answer list A while main waits on L12.
outer frame
values→I=[] · path→P · answers→A
path P
[]
saved objects
[]
Step 2: Call search(0)
The empty input starts one leaf invocation with the same P and A references.
search stack
[F0:index=0]
path P
[]
saved objects
[]
Step 3: Save A0
A new empty ArrayList is stored, distinct from P.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[]]
Step 4: Return search(0)
The leaf returns with P equal to its own entry state.
search stack
[]
path P
[]
saved objects
[A0=[]]
Step 5: After outer call
The call statement completes; P is empty and A contains one independent list.
outer frame
ready to return
path P
[]
saved objects
[A0=[]]
Step 6: Return answers
The subsets frame leaves and returns reference A as a token.
search stack
no live search/outer frame
path P
not live
just returned
A=[[]]
Step 7: Assign main.result
Main consumes the returned reference into result.
main
active
path P
not live
saved objects
main.result→A=[[]]
Step 8: Print result
The final output is the one saved empty subset.
main
active
path P
not live
saved objects
output [[]]

Deeper note and related practice

A memo value of zero can be a legitimate optimum, so zero alone cannot always mean uncomputed.

Linked nodes and tree traversals#

Module 16 of 18

Minimal node types make identity and pointer changes visible; save the next reference before rewiring a list.

Objectives

Preserve node identity during reversal.
Choose recursive or iterative tree traversal by depth.
Handle null roots.

PrerequisitesJ02, J14.

Reverse existing nodesjava

public class J16ListReversal {
    static class Node {int value;Node next;Node(int value){this.value=value;}}
    static Node reverse(Node head){Node previous=null,current=head;while(current!=null){Node following=current.next;current.next=previous;previous=current;current=following;}return previous;}
    public static void main(String[] args){Node a=new Node(1),b=new Node(2),c=new Node(3);a.next=b;b.next=c;Node head=reverse(a);assert head==c&&c.next==b&&b.next==a&&a.next==null;System.out.println(head.value);}
}

Expected: 3

Iterative preorderjava

import java.util.*;
public class J16TreePreorder {static class Node{int v;Node l,r;Node(int v){this.v=v;}}static List<Integer> walk(Node root){List<Integer> out=new ArrayList<>();if(root==null)return out;Deque<Node>s=new ArrayDeque<>();s.push(root);while(!s.isEmpty()){Node n=s.pop();out.add(n.v);if(n.r!=null)s.push(n.r);if(n.l!=null)s.push(n.l);}return out;}public static void main(String[]args){Node r=new Node(1);r.l=new Node(2);r.r=new Node(3);assert walk(r).equals(List.of(1,2,3));System.out.println(walk(r));}}

Expected: [1, 2, 3]

Worked trace

List reversal moves one existing next edge at a time after preserving following; preorder pushes right before left so left is popped first.

MistakeOverwriting current.next before saving it loses the unreversed suffix.

RepairPreserve following, rewire current, then advance both pointers.

Cost modelBoth examples visit each node once; list reversal uses O(1) workspace, iterative tree traversal O(h) to O(n) pending nodes.

BoundariesNull input returns null/empty; the explicit stack avoids depending on call-stack depth.

TakeawayTrack node identities and pending references, not only printed values.

Deeper note and related practice

A traversal's peak memory follows the maximum pending frontier, not always tree height.

Graph and grid implementation choices#

Module 17 of 18

Dense integer nodes fit indexed adjacency lists and arrays; arbitrary keys often need maps and sets.

Objectives

Mark discovered on enqueue.
Validate graph/grid indices.
Distinguish graph size from pending frontier.

PrerequisitesJ04, J07, J09.

Unweighted distancesjava

import java.util.*;
public class J17BfsDistances {
    static int[] distances(List<List<Integer>> graph,int start){int[] d=new int[graph.size()];Arrays.fill(d,-1);Queue<Integer>q=new ArrayDeque<>();d[start]=0;q.offer(start);while(!q.isEmpty()){int node=q.poll();for(int next:graph.get(node))if(d[next]==-1){d[next]=d[node]+1;q.offer(next);}}return d;}
    public static void main(String[]args){var g=List.of(List.of(1,2),List.of(3),List.of(3),List.<Integer>of());int[]d=distances(g,0);assert Arrays.equals(d,new int[]{0,1,1,2});System.out.println(Arrays.toString(d));}
}

Expected: [0, 1, 1, 2]

Worked trace

Start 0 discovers 1 and 2 at distance 1; 1 discovers 3 at distance 2 before 2 can enqueue it again.

MistakeMarking seen only on dequeue permits duplicate pending entries.

RepairMark discovery at enqueue time and validate every neighbor index if input is untrusted.

Cost modelO(V+E) time and O(V) result/visited storage; queue peak equals the largest pending frontier.

BoundariesThe example requires a non-null graph, valid start, and neighbor indices in range.

TakeawayChoose representations from node identity and traversal operations.

Deeper note and related practice

For grids, rectangular arrays permit one column count; ragged arrays require per-row bounds.

Pattern handoffs and assessment IO#

Module 18 of 18

Templates are recall aids: select one by invariant, state its preconditions, then adapt it to the prompt and judge boundary.

Objectives

Select among the 15 retained Java templates.
Keep method and assessment I/O separate.
Carry ordering, mutation, width, and empty policies into adaptation.

PrerequisitesJ01–J17 as needed.

Thin assessment wrapperjava

import java.io.*;import java.util.*;
public class J18AssessmentIO {
    static long solve(int[] values){long total=0;for(int value:values)if(value>0)total+=value;return total;}
    public static void main(String[]args)throws Exception{Scanner in=new Scanner(new BufferedInputStream(System.in));if(!in.hasNextInt())return;int n=in.nextInt();if(n<0)throw new IllegalArgumentException("negative n");int[]a=new int[n];for(int i=0;i<n;i++)a[i]=in.nextInt();System.out.println(solve(a));}
}

Expected: For stdin `4 4 -2 0 7`, prints `11` and one newline.

Worked trace

The wrapper parses exactly n integers, calls a pure method, then emits only the requested answer.

MistakeCopying a template without its precondition can turn a linear idea into a wrong algorithm.

RepairName why the invariant applies, then adapt types, boundaries, and output policy.

Cost modelParsing plus the example method is O(n); template-specific costs remain attached to each disclosure.

BoundariesJudge input is trusted to contain n integers here; production parsing would need a different error contract.

TakeawayRecall structure, but re-derive correctness for the actual prompt.

Deeper note and related practice

The page never sends, stores, or executes entered code; fixtures verify checked-in canonical sources only.

Common interview templates#

These fifteen retained contracts are recall aids, not proprietary answers. Open one only after stating why its invariant and preconditions match.

Two PointersA sorted array and target sum let each comparison discard one endpoint. This contract returns indices or {-1,-1} and does not mutate input.

Use when: A sorted array and target sum let each comparison discard one endpoint. This contract returns indices or {-1,-1} and does not mutate input.

Typical complexity: O(n) time and O(1) working space.

Two Pointers templatejava

static int[] pairSum(int[] nums, long target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        long sum = (long) nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

Sliding WindowValues are nonnegative and you need the shortest nonempty contiguous range whose sum reaches target; target must be positive.

Use when: Values are nonnegative and you need the shortest nonempty contiguous range whose sum reaches target; target must be positive.

Typical complexity: O(n) time and O(1) working space because both boundaries only advance.

Sliding Window templatejava

static int minWindowAtLeast(int[] nums, long target) {
    if (target <= 0) throw new IllegalArgumentException("target must be positive");
    int left = 0;
    long windowSum = 0;
    int answer = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] < 0) throw new IllegalArgumentException("negative value");
        windowSum += nums[right];
        while (windowSum >= target) {
            answer = Math.min(answer, right - left + 1);
            windowSum -= nums[left++];
        }
    }
    return answer == Integer.MAX_VALUE ? 0 : answer;
}

Binary SearchA sorted array needs a lower or upper insertion boundary, including duplicates and absent targets.

Use when: A sorted array needs a lower or upper insertion boundary, including duplicates and absent targets.

Typical complexity: O(log(n+1)) comparisons and O(1) working space.

Binary Search templatejava

public class J12Boundaries {
    static int boundary(int[] a, int target, boolean upper) {
        int left=0, right=a.length;
        while (left<right) { int middle=left+(right-left)/2;
            if (a[middle]<target || (upper && a[middle]==target)) left=middle+1; else right=middle;
        }
        return left;
    }
    public static void main(String[] args) {
        int[] a={1,3,3,7}; assert boundary(a,3,false)==1; assert boundary(a,3,true)==3;
        assert boundary(a,9,false)==4 && boundary(new int[0],3,false)==0;
        System.out.println(boundary(a,3,false)+" "+boundary(a,3,true));
    }
}

BFSYou need levels or shortest unweighted distance.

Use when: You need levels or shortest unweighted distance.

Typical complexity: O(V + E) time and O(V) space.

BFS templatejava

static List<Integer> bfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] seen = new boolean[graph.size()];
    queue.offer(start);
    seen[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (!seen[neighbor]) {
                seen[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
    return order;
}

DFSYou need deterministic preorder reachability without relying on recursive call depth. Iterator frames preserve adjacency order.

Use when: You need deterministic preorder reachability without relying on recursive call depth. Iterator frames preserve adjacency order.

Typical complexity: O(V + E) time and O(V) visited/frame space.

DFS templatejava

static List<Integer> dfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] seen = new boolean[graph.size()];
    record Frame(int node, Iterator<Integer> edges) {}
    Deque<Frame> stack = new ArrayDeque<>();
    seen[start] = true;
    order.add(start);
    stack.push(new Frame(start, graph.get(start).iterator()));
    while (!stack.isEmpty()) {
        Frame frame = stack.peek();
        if (!frame.edges().hasNext()) { stack.pop(); continue; }
        int next = frame.edges().next();
        if (seen[next]) continue;
        seen[next] = true;
        order.add(next);
        stack.push(new Frame(next, graph.get(next).iterator()));
    }
    return order;
}

Tree DFSA tree answer depends on values returned from child subtrees.

Use when: A tree answer depends on values returned from child subtrees.

Typical complexity: O(n) time and O(h) call-stack space.

Tree DFS templatejava

static int treeDepth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = treeDepth(node.left);
    int rightDepth = treeDepth(node.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

Tree BFSYou need levels, nearest depth, or breadth-first order.

Use when: You need levels, nearest depth, or breadth-first order.

Typical complexity: O(n) time and O(w) queue space.

Tree BFS templatejava

static List<List<Integer>> treeLevels(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

BacktrackingYou must enumerate every subset while restoring one shared working path and saving independent results.

Use when: You must enumerate every subset while restoring one shared working path and saving independent results.

Typical complexity: Θ(n·2ⁿ) returned elements and O(n) active path/call space.

Backtracking templatejava

import java.util.*;
public class J15Subsets {
    static void search(int[] a,int i,List<Integer> path,List<List<Integer>> out){
        if(i==a.length){out.add(new ArrayList<>(path));return;}
        search(a,i+1,path,out); path.add(a[i]); search(a,i+1,path,out); path.remove(path.size()-1);
    }
    static List<List<Integer>> subsets(int[] a){List<List<Integer>> out=new ArrayList<>();search(a,0,new ArrayList<>(),out);return out;}
    public static void main(String[] args){var out=subsets(new int[]{1,2});assert out.toString().equals("[[], [2], [1], [1, 2]]");System.out.println(out);}
}

Heap / Top KReturn the largest k values in ascending order. k<0 rejects; k=0 returns empty; k>n returns every value.

Use when: Return the largest k values in ascending order. k<0 rejects; k=0 returns empty; k>n returns every value.

Typical complexity: O(n log(min(k,n))) time plus O(k log k) output sorting; O(min(k,n)) heap space.

Heap / Top K templatejava

static int[] largestK(int[] nums, int k) {
    if (k < 0) throw new IllegalArgumentException("negative k");
    int keep = Math.min(k, nums.length);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int value : nums) {
        heap.offer(value);
        if (heap.size() > keep) heap.poll();
    }
    int[] answer = new int[keep];
    for (int i = 0; i < keep; i++) answer[i] = heap.poll();
    return answer;
}

Prefix SumMany half-open range [left,right) sum queries can reuse one widened cumulative array.

Use when: Many half-open range [left,right) sum queries can reuse one widened cumulative array.

Typical complexity: O(n) preprocessing and O(1) per query, with O(n) stored prefix values.

Prefix Sum templatejava

static long[] prefixSums(int[] nums) {
    long[] prefix = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

static long rangeSum(long[] prefix, int left, int rightExclusive) {
    if (left < 0 || left > rightExclusive || rightExclusive >= prefix.length) {
        throw new IllegalArgumentException("invalid half-open range");
    }
    return prefix[rightExclusive] - prefix[left];
}

Monotonic StackYou need the next previous greater/smaller boundary.

Use when: You need the next previous greater/smaller boundary.

Typical complexity: O(n) time and O(n) space.

Monotonic Stack templatejava

static int[] nextGreater(int[] nums) {
    int[] answer = new int[nums.length];
    Arrays.fill(answer, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            answer[stack.pop()] = i;
        }
        stack.push(i);
    }
    return answer;
}

Union FindEdges merge components and connectivity queries repeat; node IDs must be in [0,n).

Use when: Edges merge components and connectivity queries repeat; node IDs must be in [0,n).

Typical complexity: O(n) initialization; inverse-Ackermann amortized find/union with path halving and rank; O(n) storage.

Union Find templatejava

static class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private int components;

    UnionFind(int n) {
        if (n < 0) throw new IllegalArgumentException("negative size");
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        components = n;
    }

    int find(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }

    boolean union(int first, int second) {
        int rootA = find(first);
        int rootB = find(second);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) {
            int swap = rootA;
            rootA = rootB;
            rootB = swap;
        }
        parent[rootB] = rootA;
        if (rank[rootA] == rank[rootB]) rank[rootA]++;
        components--;
        return true;
    }

    int components() { return components; }
}

Topological SortDirected dependencies must be processed after prerequisites; return null when a cycle makes an order impossible.

Use when: Directed dependencies must be processed after prerequisites; return null when a cycle makes an order impossible.

Typical complexity: O(V + E) time and O(V) result/indegree/queue space.

Topological Sort templatejava

static List<Integer> topologicalOrder(List<List<Integer>> graph) {
    int[] indegree = new int[graph.size()];
    for (List<Integer> neighbors : graph) {
        for (int neighbor : neighbors) indegree[neighbor]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int node = 0; node < indegree.length; node++) {
        if (indegree[node] == 0) queue.offer(node);
    }
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (--indegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return order.size() == graph.size() ? order : null;
}

1-D Dynamic ProgrammingReturn the maximum sum of nonadjacent values, allowing the empty selection. Use long state so int inputs cannot overflow the recurrence.

Use when: Return the maximum sum of nonadjacent values, allowing the empty selection. Use long state so int inputs cannot overflow the recurrence.

Typical complexity: O(n) time and O(1) working space.

1-D Dynamic Programming templatejava

static long bestTotal(int[] values) {
    long previousTwo = 0;
    long previousOne = 0;
    for (int value : values) {
        long current = Math.max(previousOne, previousTwo + value);
        previousTwo = previousOne;
        previousOne = current;
    }
    return previousOne;
}

Grid TraversalCount reachable passable 1-cells in a non-null rectangular grid from a valid start; blocked starts return zero.

Use when: Count reachable passable 1-cells in a non-null rectangular grid from a valid start; blocked starts return zero.

Typical complexity: O(rows × cols) time and visited/queue space in the worst case.

Grid Traversal templatejava

static int visitGrid(int[][] grid, int startRow, int startCol) {
    int rows = grid.length;
    if (rows == 0) return 0;
    int cols = grid[0].length;
    for (int[] row : grid) if (row.length != cols) throw new IllegalArgumentException("ragged grid");
    if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) throw new IllegalArgumentException("invalid start");
    if (grid[startRow][startCol] != 1) return 0;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] seen = new boolean[rows][cols];
    queue.offer(new int[]{startRow, startCol});
    seen[startRow][startCol] = true;
    int visited = 0;
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        visited++;
        for (int[] direction : directions) {
            int row = cell[0] + direction[0];
            int col = cell[1] + direction[1];
            if (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] == 1 && !seen[row][col]) {
                seen[row][col] = true;
                queue.offer(new int[]{row, col});
            }
        }
    }
    return visited;
}

Common interview mistakes#

Comparing strings with ==

== compares references. Use equals for String content.

Defaulting to legacy Stack

Prefer Deque with ArrayDeque for stack behavior.

Comparator subtraction

a - b can overflow and break ordering. Use Integer.compare.

Mixing length APIs

Arrays use length, strings use length(), and collections use size().

ArrayList.remove overloads

remove(int) uses an index; remove(Object) removes a matching value.

Ignoring integer overflow

Promote to long before addition or multiplication when the result can exceed int.

Forgetting String immutability

Use StringBuilder for repeated construction or mutation-like work.

Mutating during enhanced-for

Structural modification can throw ConcurrentModificationException. Use an iterator or collect changes separately.

Mixing queue APIs

offer/poll/peek and add/remove/element have different empty/capacity behavior. Choose intentionally.

Unsafe autounboxing

Unboxing a null wrapper throws NullPointerException; check nullable map/queue results.

Broken and corrected examples#

The three retained repair IDs name a concrete regression case.

Overflow-safe ordering

Failure: Subtraction can overflow and violate the comparator contract.

Regression case: Sort Integer.MIN_VALUE and Integer.MAX_VALUE and assert ascending order.

Brokenjava

items.sort((a, b) -> a.score - b.score);

Correctedjava

items.sort((a, b) -> Integer.compare(a.score, b.score));

Compare string content

Failure: The broken form compares object identities rather than String contents.

Regression case: Build two distinct String objects containing x and assert the comparison is true.

Brokenjava

boolean same = new String("x") == new String("x");

Correctedjava

boolean same = new String("x").equals(new String("x"));

Promote before arithmetic

Failure: The int addition can overflow before its result is widened to long.

Regression case: Add Integer.MAX_VALUE and one and assert the result equals 2147483648L.

Brokenjava

long total = first + second;

Correctedjava

long total = (long) first + second;

Debugging checklist#

Restate the invariant and trace the smallest failing input before editing the implementation.
Check primitive versus reference equality, nullable wrappers, and every equals/hashCode assumption used by maps or sets.
Promote operands to long before arithmetic that may overflow int; avoid subtraction comparators.
Verify array, String, and collection length APIs and the chosen closed or half-open interval convention.
Test empty, singleton, duplicate, overflow, Unicode, and deep traversal cases; choose an explicit stack when depth is unbounded.

Questions about the language#

These are reasonable discussion prompts, not claims about every interviewer or company.

Why == and equals answer different questions for references and how hashCode must agree with equals.
Why ArrayDeque is normally preferable to legacy Stack and which operations reject null.
How PriorityQueue chooses its head and how to build an overflow-safe comparator.
Where boxing, unboxing, generic collections, and nullable lookup results create runtime cost or risk.
When int is insufficient and why casting after an overflowing operation is too late.

Language transfer exercises#

The five existing checks remain concealed until you choose to open them. The later Java exercise backlog is intentionally not shipped here.

predict
Reference or value equality
Predict the results of new String("x") == new String("x") and the corresponding equals call.
Answer check
The reference comparison is false for the two distinct objects; equals is true because String defines content equality.
trace
Trace queue discovery
Trace an ArrayDeque BFS from A to neighbors B and C when both point to D. Mark visited at insertion time.
Answer check
D is offered once: mark it visited when B offers it so C cannot add a duplicate queue entry.
repair
Repair the comparator
Replace (a, b) -> a.score - b.score and explain the failure it avoids.
Answer check
Use Comparator.comparingInt or Integer.compare(a.score, b.score); subtraction can overflow and violate comparator ordering.
choose
Choose a collection
Choose ArrayList, HashSet, HashMap, ArrayDeque, TreeMap, or PriorityQueue for indexed access, membership, FIFO, ordered keys, and next priority.
Answer check
ArrayList, HashSet, ArrayDeque, TreeMap, and PriorityQueue respectively; HashMap is for key/value lookup without sorted-key requirements.
transfer
Unlabeled transfer
Maintain the next three tasks by smallest deadline, breaking ties by insertion order. State the queue element and comparator.
Answer check
Store a record/object with deadline and sequence; compare first with Long.compare on deadline, then Long.compare on sequence.

Reach this point to mark the lesson as read.

Runtime boundaryPortable Java 17+ subset compiled with --release 17, -Xlint:all, and -Werror; the hosted fixture retains its Temurin 25 lane. No code executes in the browser.

ReviewedSeptember 6, 2026

Compatibility floorJava 17+

Fixture evidenceCanonical sources target Java 17; the common fixture is also compiled and executed on hosted Temurin 25.

Source notes

Java Language Specification 25Primitive/reference values, equality, numeric promotion, strings, arrays, generics, and language semantics.
Java SE 25 java.utilCollections Framework, comparators, maps, sets, deques, and priority queues.
Java SE 25 ArrayDequeStack/queue operations, null restrictions, and amortized operation guarantees.
Java SE 25 PriorityQueueHeap ordering, head semantics, comparator behavior, and operation costs.

Input and output conventions#

Function interview: Implement the requested method and minimal helper types. Return the value instead of building a console parser unless requested.
Online assessment: Use the platform's class, method, stdin, and stdout contract exactly; keep diagnostic output out of judged output.

Java interview sequence#

Read in order for a full review, or jump to the contract behind a syntax decision. This remains one guide - not eighteen new routes.

Quick reference#

The four retained cards are compact recall aids. Their full contracts live in the sequence below.

Arrays and listsjava

int[] nums = new int[n];
int[][] grid = new int[rows][cols];
Arrays.fill(nums, -1);
Arrays.sort(nums);

List<Integer> list = new ArrayList<>();
list.add(value);
int first = list.get(0);

Maps and setsjava

Map<Integer, Integer> frequency = new HashMap<>();
Set<Integer> seen = new HashSet<>();

frequency.put(value, frequency.getOrDefault(value, 0) + 1);
boolean present = seen.contains(value);
seen.add(value);

Stack and queuejava

Deque<Integer> stack = new ArrayDeque<>();
stack.push(value);
int top = stack.pop();

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(value);
Integer next = queue.poll();

Priority queuesjava

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue<int[]> byFirst =
    new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

Read the contract and write a method#

Module 1 of 18

Translate the prompt into accepted inputs, mutation policy, return shape, and platform-owned I/O before choosing syntax.

Objectives

Separate a function interview from an assessment program.
State null, empty, mutation, and numeric-width policies.
Return exactly what the caller requests.

PrerequisitesNone.

A bounded method contractjava

public class J01PositiveTotal {
    static long positiveTotal(int[] values) {
        long total = 0;
        for (int value : values) if (value > 0) total += value;
        return total;
    }
    public static void main(String[] args) {
        int[] input = {4, -2, 0, 7};
        assert positiveTotal(input) == 11;
        assert positiveTotal(new int[0]) == 0;
        assert java.util.Arrays.equals(input, new int[]{4, -2, 0, 7});
        System.out.println(positiveTotal(input));
    }
}

Expected: 11; the input is unchanged.

Worked trace

total advances 0 → 4 → 4 → 4 → 11; negative and zero values do not contribute.

MistakeAdding a Scanner and labels to a method-only prompt changes the contract.

RepairKeep parsing at the assessment boundary and the algorithm in a testable method.

Cost modelO(n) time and O(1) working storage; the returned scalar is separate.

BoundariesNon-null int array; empty is valid; long prevents the accumulation from overflowing int.

TakeawaySolve the caller's contract, not a remembered platform format.

Deeper note and related practice

Java passes every argument value by value. For an array, that copied value is a reference to the same array object.

Values, references and method calls#

Module 2 of 18

A reference variable stores a value that identifies an object; copying that value can create aliases, while reassigning a parameter changes only the local slot.

Objectives

Distinguish primitive values from reference values.
Predict shared mutation and local reassignment.
Use equals and identity questions deliberately.

PrerequisitesJ01.

Mutation versus local rebindingjava

public class J02ParameterValues {
    static void change(int[] alias, int scalar) {
        alias[0] = 9;
        alias = new int[]{5};
        scalar = 8;
        assert alias[0] == 5 && scalar == 8;
    }
    public static void main(String[] args) {
        int[] values = {2, 3}; int number = 3;
        change(values, number);
        assert values[0] == 9 && values[1] == 3 && number == 3;
        System.out.println(values[0] + " " + number);
    }
}

Expected: 9 3

Worked trace

The call copies the array reference and scalar. The element write reaches the shared array; both parameter reassignments remain local.

MistakeCalling Java pass-by-reference predicts that reassigning alias changes values in the caller.

RepairDraw caller and callee variables separately, with both reference values pointing to the same array object.

Cost modelReference/scalar assignment is O(1); object equality may inspect data.

BoundariesThe diagram is conceptual identity - not a physical address or JVM heap layout.

TakeawayArguments are copied values; copied reference values may still alias one object.

Copied references, shared mutation

Track caller and callee variables without inventing physical addresses.

JV01 · JV01-pass-values@2026-09-06

public class JV01PassValues {
static boolean trace;
static int[] callerData;
static int callerCount;
static void change(int[] items, int count) {
items[0] = 9;
if (trace) System.out.println("MUTATE|mainData=A|items=A|sameObject=" + (items == callerData) + "|A=" + java.util.Arrays.toString(callerData));
items = new int[]{7, 8};
if (trace) System.out.println("REBIND|mainData=A|items=B|sameObject=" + (items == callerData) + "|A=" + java.util.Arrays.toString(callerData) + "|B=" + java.util.Arrays.toString(items));
count = 99;
if (trace) System.out.println("SCALAR|mainCount=" + callerCount + "|changeCount=" + count + "|mainData=A|items=B|A=" + java.util.Arrays.toString(callerData) + "|B=" + java.util.Arrays.toString(items));
}
public static void main(String[] args) {
trace = args.length == 1 && args[0].equals("--trace");
if (trace) System.out.println("INITIAL|data=unbound|count=unbound");
int[] data = {1, 2};
callerData = data;
if (trace) System.out.println("BIND_DATA|data=A|A=" + java.util.Arrays.toString(data));
int count = 3;
callerCount = count;
if (trace) System.out.println("BIND_COUNT|data=A|count=" + count + "|A=" + java.util.Arrays.toString(data));
if (trace) System.out.println("CALL|mainData=A|items=A|sameObject=" + (data == callerData) + "|mainCount=" + count + "|changeCount=" + count + "|A=" + java.util.Arrays.toString(data));
change(data, count);
if (trace) {
System.out.println("RETURN|mainData=A|mainCount=" + count + "|BUnreachableFromShownLocals=true|A=" + java.util.Arrays.toString(data));
System.out.println("COMPLETE|mainData=A|mainCount=" + count + "|sameCallerBinding=" + (data == callerData) + "|A=" + java.util.Arrays.toString(data));
System.out.println("OUTPUT|output=" + data[0] + " " + count + "|mainData=A|mainCount=" + count + "|A=" + java.util.Arrays.toString(data));
} else {
System.out.println(data[0] + " " + count);
}
assert data[0] == 9 && data[1] == 2 && count == 3;
}
}

Step 1 of 10 · initialInitial state

Main is active; data and count are unbound.

Names and values

dataunbound

countunbound

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Shared array and local slots

Step 1: Initial state
Main is active; data and count are unbound.
data
unbound
count
unbound
Step 2: Bind data
data stores a reference to array A.
data
→ A
A
[1, 2]
Step 3: Bind count
count stores primitive value 3.
data
→ A
count
3
A
[1, 2]
Step 4: Call change
The call copies both argument values into callee parameter slots.
main.data
→ A
main.count
3
change.items
→ A
change.count
3
A
[1, 2]
Step 5: Mutate A
Both reference values still reach A, so the element write is caller-visible.
main.data
→ A
change.items
→ A
A
[9, 2]
Step 6: Rebind callee reference
Only change.items now refers to new array B.
main.data
→ A
change.items
→ B
A
[9, 2]
B
[7, 8]
Step 7: Reassign callee scalar
Changing change.count leaves main.count at 3.
main.count
3
change.count
99
main.data
→ A
change.items
→ B
A
[9, 2]
B
[7, 8]
Step 8: Return change
The callee frame leaves; B is unreachable from the shown locals.
main.data
→ A
main.count
3
B status
unreachable from shown locals
A
[9, 2]
Step 9: Complete call
Main resumes with its original variable bindings.
main.data
→ A
main.count
3
A
[9, 2]
Step 10: Observe caller
The shared mutation remains; local reassignments do not.
output
9 3
main.data
→ A
main.count
3
A
[9, 2]

Deeper note and related practice

Object mutation and variable reassignment are different operations even when they appear in one method.

Primitive values, wrappers and null#

Module 3 of 18

Generics use reference types, so collection operations can box primitives and produce nullable wrapper results.

Objectives

Recognize boxing and unboxing sites.
Avoid identity comparisons between wrappers.
Guard nullable results before unboxing.

PrerequisitesJ02.

Nullable wrapper boundaryjava

import java.util.*;
public class J03BoxingNull {
    static int count(Map<String, Integer> counts, String key) {
        Integer boxed = counts.get(key);
        return boxed == null ? 0 : boxed;
    }
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>(); counts.put("x", 2);
        assert count(counts, "x") == 2 && count(counts, "missing") == 0;
        assert Integer.valueOf(1000).equals(Integer.valueOf(1000));
        System.out.println(count(counts, "missing"));
    }
}

Expected: 0

Worked trace

get(missing) returns null; the guard selects zero before an unboxing conversion could fail.

MistakeAssigning map.get(key) directly to int can throw NullPointerException.

RepairKeep the result boxed until absence has been handled, or use an intentional default.

Cost modelExpected O(1) lookup under ordinary hashing assumptions; boxing may allocate or reuse an object and should not be identity-tested.

BoundariesA present key mapped to null is distinct from an absent key when the map permits null values.

TakeawayTreat wrapper nullability as part of the contract.

Deeper note and related practice

Some Integer instances are cached by specification, which is another reason == is not a value comparison.

Arrays, copies and rectangular grids#

Module 4 of 18

An array fixes its outer length, and a two-dimensional array is an array whose elements are row references.

Objectives

Separate shallow outer copies from copied rows.
Validate rectangular-grid assumptions.
Use half-open copy ranges.

PrerequisitesJ02.

Copy the intended leveljava

import java.util.*;
public class J04ArrayCopy {
    public static void main(String[] args) {
        int[][] grid = {{1, 2}, {3, 4}};
        int[][] shallow = grid.clone();
        int[][] independent = Arrays.stream(grid).map(int[]::clone).toArray(int[][]::new);
        grid[0][1] = 9;
        assert shallow[0][1] == 9 && independent[0][1] == 2;
        System.out.println(shallow[0][1] + " " + independent[0][1]);
    }
}

Expected: 9 2

Worked trace

The outer clone gets new row slots but copies both row references; the stream explicitly clones each row.

MistakeCalling grid.clone() a deep copy hides shared rows.

RepairClone each row when row mutation must be isolated.

Cost modelOuter clone is O(rows); copying every rectangular cell is O(rows×cols) and allocates the copied cells.

BoundariesRows may legally be null or different lengths unless the algorithm requires and validates a rectangle.

TakeawayName which array level a copy duplicates.

Deeper note and related practice

Arrays.copyOfRange uses [from,to); it pads only when the destination range extends past the source for supported overloads.

ArrayList operations, views and copies#

Module 5 of 18

ArrayList offers indexed access and amortized append, while subList is a backed range view rather than a copy.

Objectives

Distinguish view from copy.
Select remove-by-index or remove-by-value.
Account for shifted references.

PrerequisitesJ03, J04.

Range view and removal overloadsjava

import java.util.*;
public class J05ListViews {
    public static void main(String[] args) {
        List<Integer> base = new ArrayList<>(List.of(4, 8, 10));
        List<Integer> view = base.subList(1, 3);
        List<Integer> copy = new ArrayList<>(view);
        view.remove(0); copy.add(12);
        boolean removedValue = copy.remove(Integer.valueOf(8));
        int removedIndex = copy.remove(1);
        assert base.equals(List.of(4, 10)) && view.equals(List.of(10));
        assert removedValue && removedIndex == 12;
        System.out.println(base + " " + view + " " + copy);
    }
}

Expected: [4, 10] [10] [10]

Worked trace

Removing view index 0 removes base index 1. The copy changes independently; the two remove overloads choose value and position.

Mistakeremove(1) on List<Integer> removes index 1, not value 1.

RepairUse Integer.valueOf(value) for value removal and new ArrayList<>(view) for ownership.

Cost modelget is O(1), append amortized O(1), and middle/front removal O(n) due to shifts.

BoundariesStructural changes outside a live view can invalidate its later operations.

TakeawayA range view shares structure until you explicitly copy it.

ArrayList view versus copy

Follow backing-list edits and the two Integer removal overloads.

JV02 · JV02-view-copy@2026-09-06

import java.util.ArrayList;
import java.util.List;
public class JV02ViewCopy {
static boolean trace;
static void emit(String step, List<Integer> base, List<Integer> view, List<Integer> copy) {
if (trace) System.out.println(step + "|baseRef=B|viewRef=V|copyRef=C|viewRange=[1," + (1 + view.size()) + ")|viewBacksBase="
+ view.equals(base.subList(1, 1 + view.size())) + "|B=" + base + "|V=" + view + "|C=" + copy);
}
public static void main(String[] args) {
trace = args.length == 1 && args[0].equals("--trace");
List<Integer> base = new ArrayList<>(List.of(4, 9, 12));
if (trace) System.out.println("1|B=" + base);
List<Integer> view = base.subList(1, 3);
if (trace) System.out.println("2|baseRef=B|viewRef=V|viewRange=[1,3)|viewBacksBase=" + view.equals(base.subList(1, 3)) + "|B=" + base + "|V=" + view + "|baseDistinctView=" + (base != view));
List<Integer> copy = new ArrayList<>(view);
if (trace) System.out.println("3|baseRef=B|viewRef=V|copyRef=C|viewRange=[1,3)|viewBacksBase=" + view.equals(base.subList(1, 3)) + "|B=" + base + "|V=" + view + "|C=" + copy + "|distinct=" + (base != copy && view != copy));
view.set(0, 10);
emit("4", base, view, copy);
int removedIndex = view.remove(1);
emit("5|removedIndex=" + removedIndex, base, view, copy);
boolean removedValue = copy.remove(Integer.valueOf(9));
emit("6|removedValue=" + removedValue, base, view, copy);
if (trace) System.out.println("7|baseRef=B|viewRef=V|copyRef=C|viewRange=[1,2)|viewBacksBase=" + view.equals(base.subList(1, 2)) + "|output=" + base + " / " + view + " / " + copy + "|B=" + base + "|V=" + view + "|C=" + copy);
else System.out.println(base + " / " + view + " / " + copy);
assert base.equals(List.of(4, 10)) && view.equals(List.of(10));
assert copy.equals(List.of(12)) && removedIndex == 12 && removedValue;
}
}

Step 1 of 8 · initialInitial state

No example bindings exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

View, copy, and overloads

Step 1: Initial state
No example bindings exist yet.
bindings
Not available
Step 2: Create base
B is the resizable outer list owned by base.
base
→ B
B
[4, 9, 12]
Step 3: Create backed view
V denotes B positions [1,3); it has no independent element copy.
base
→ B
view
→ V
B
[4, 9, 12]
V
B[1,3) = [9, 12]
Step 4: Create outer copy
C owns separate outer storage initialized from V.
base
→ B
view
→ V
copy
→ C
B
[4, 9, 12]
V
B[1,3) = [9, 12]
C
[9, 12]
Step 5: Replace through view
Updating V index 0 replaces B index 1; C stays unchanged.
base
→ B
view
→ V
copy
→ C
B
[4, 10, 12]
V
B[1,3) = [10, 12]
C
[9, 12]
Step 6: Remove view index 1
remove(int) returns 12 and shortens B and V together.
base
→ B
view
→ V
copy
→ C
removedIndex
12
B
[4, 10]
V
B[1,2) = [10]
C
[9, 12]
Step 7: Remove value from copy
remove(Object) finds 9 in C and returns true; B and V do not change.
base
→ B
view
→ V
copy
→ C
removedValue
true
B
[4, 10]
V
B[1,2) = [10]
C
[12]
Step 8: Print independent owners
The backed view and independent copy now have different contents.
base
→ B
view
→ V
copy
→ C
output
[4, 10] / [10] / [12]
B
[4, 10]
V
B[1,2) = [10]
C
[12]

Deeper note and related practice

Choose a view only while shared structural ownership is intentional and short-lived.

Strings, builders and character assumptions#

Module 6 of 18

String is immutable and indexed in UTF-16 code units; StringBuilder makes repeated construction explicit.

Objectives

Use equals for content.
State ASCII, UTF-16, or code-point assumptions.
Avoid repeatedly copying a growing prefix.

PrerequisitesJ01.

Build one resultjava

public class J06StringBuilder {
    static String join(int[] values) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            if (i > 0) out.append(','); out.append(values[i]);
        }
        return out.toString();
    }
    public static void main(String[] args) {
        assert join(new int[]{10, -2, 7}).equals("10,-2,7");
        assert "😀".length() == 2;
        System.out.println(join(new int[]{10, -2, 7}));
    }
}

Expected: 10,-2,7

Worked trace

The builder grows through 10, 10,-2, then 10,-2,7; toString creates the returned String.

MistakecharAt counts UTF-16 units, not user-perceived characters.

RepairDeclare an ASCII/UTF-16 contract or iterate code points when the task requires them.

Cost modelConstruction is O(m) in produced UTF-16 units under ordinary amortized growth; the returned String is O(m) output.

BoundariesEmpty input returns the empty string; null input is outside this example contract.

TakeawayMake the unit of text processing explicit.

Deeper note and related practice

Do not claim a universal constant-time substring operation; its implementation is not the algorithm contract.

Keys, counts and ordered alternatives#

Module 7 of 18

HashMap and HashSet answer expected-time lookup questions; ordered alternatives change iteration and cost contracts.

Objectives

Keep equals and hashCode consistent.
Distinguish absent from present-null.
Choose HashMap, LinkedHashMap, or TreeMap intentionally.

PrerequisitesJ03.

Count without relying on iteration orderjava

import java.util.*;
public class J07HashContracts {
    public static void main(String[] args) {
        int[] values = {4, 1, 4}; Map<Integer, Integer> counts = new HashMap<>();
        for (int value : values) counts.merge(value, 1, Integer::sum);
        assert counts.get(4) == 2 && counts.getOrDefault(9, 0) == 0;
        assert !counts.containsKey(9);
        System.out.println(counts.get(4));
    }
}

Expected: 2

Worked trace

merge inserts 4→1, inserts 1→1, then replaces 4 with 2; no iteration order is used.

MistakeReturning the first HashMap entry assumes an order the API does not promise.

RepairPreserve input position separately, use LinkedHashMap for encounter order, or TreeMap for key order.

Cost modelExpected O(n) total under ordinary hashing assumptions and O(u) entries; no unconditional worst-case O(1) lookup claim.

BoundariesMutable keys can become unreachable if fields used by equals/hashCode change after insertion.

TakeawayPick both lookup behavior and iteration contract.

Deeper note and related practice

TreeMap gives logarithmic basic operations and comparator order; that is a different tradeoff from hashing.

Iteration, generics and lazy work#

Module 8 of 18

Enhanced-for, Iterator, and Stream expose different mutation and evaluation contracts.

Objectives

Remove through Iterator when structurally editing during traversal.
Recognize erased generic type boundaries.
Know when a lazy stream pipeline executes.

PrerequisitesJ03, J05.

Iterator removal and lazy streamjava

import java.util.*;
public class J08Iteration {
    public static void main(String[] args) {
        List<Integer> values = new ArrayList<>(List.of(1, 2, 3, 4));
        for (Iterator<Integer> it = values.iterator(); it.hasNext();) {
            if ((it.next() & 1) == 0) it.remove();
        }
        long count = values.stream().filter(v -> v > 1).count();
        assert values.equals(List.of(1, 3)) && count == 1;
        System.out.println(values);
    }
}

Expected: [1, 3]

Worked trace

Iterator visits each element and owns both structural removals; the stream filter runs only when count is requested.

MistakeRemoving from the list inside enhanced-for can invalidate the iterator.

RepairUse Iterator.remove, removeIf, or collect changes separately.

Cost modelTraversal is O(n); ArrayList iterator removals can shift a suffix and make repeated removals O(n²).

BoundariesStreams are single-use; toList returns an unmodifiable result in the supported baseline.

TakeawayChoose an iteration form whose mutation and evaluation rules match the task.

Deeper note and related practice

Generic type arguments are mostly erased; runtime casts can still fail where unchecked code crosses the boundary.

Stack and queue contracts#

Module 9 of 18

ArrayDeque supports both LIFO and FIFO end operations without the shifting cost of ArrayList front removal.

Objectives

Use one coherent stack or queue API.
Mark graph discoveries when enqueuing.
Handle empty results without unsafe unboxing.

PrerequisitesJ05.

Explicit empty policyjava

import java.util.*;
public class J09DequeContracts {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(10);
        queue.addLast(20);
        int first = queue.removeFirst();
        Integer second = queue.pollFirst();
        Integer empty = queue.peekFirst();
        assert first == 10 && second != null && second == 20 && empty == null;

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        int top = stack.pop();
        int last = stack.pop();
        Integer after = stack.peek();
        assert top == 20 && last == 10 && after == null;
        System.out.println(first + " " + top);
    }
}

Expected: 10 20

Worked trace

The queue removes 10 then 20; the stack removes 20 then 10. These operations happen before validation, so the same 10 20 result is produced with assertions enabled or disabled.

Mistakeint next = queue.peek() throws when an empty queue returns null.

RepairKeep the nullable result as Integer until the empty case is handled, and never put an operation required for the demonstrated result only inside assert.

Cost modelArrayDeque end operations are amortized O(1); n ArrayList front removals shift n(n−1)/2 references in the simple model.

BoundariesArrayDeque rejects null elements; empty poll/peek return null, while remove/element throw.

TakeawayChoose the empty behavior and end convention deliberately.

Front-removal work model

Compare equal FIFO results with ArrayList reference shifts and ArrayDeque end operations.

JV03 · JV03-queue-work@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class JV03QueueWork {
record Summary(List<Integer> removed, long shifts) {}
static Summary drain(List<Integer> input, boolean trace) {
List<Integer> items = new ArrayList<>(input);
Deque<Integer> queue = new ArrayDeque<>(input);
long shifts = 0;
List<Integer> removed = new ArrayList<>();
if (trace) System.out.println("0|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|shifts=" + shifts);
while (!items.isEmpty()) {
long increment = items.size() - 1;
shifts += increment;
int left = items.remove(0);
int right = queue.removeFirst();
if (left != right) throw new AssertionError("FIFO mismatch");
removed.add(left);
if (trace) System.out.println("I|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|increment=" + increment + "|shifts=" + shifts);
}
if (trace) System.out.println("R|remaining=" + items + "|queue=" + queue + "|removed=" + removed + "|shifts=" + shifts);
return new Summary(List.copyOf(removed), shifts);
}
public static void main(String[] args) {
if (args.length > 0 && args[0].equals("--trace")) {
String preset = args.length == 1 ? "default" : args[1];
List<Integer> input = switch (preset) {
case "default" -> List.of(10, 20, 30, 40);
case "empty" -> List.of();
case "eight" -> List.of(1, 2, 3, 4, 5, 6, 7, 8);
default -> throw new IllegalArgumentException("unknown preset");
};
drain(input, true);
return;
}
Summary result = drain(List.of(10, 20, 30, 40), false);
assert result.removed().equals(List.of(10, 20, 30, 40)) && result.shifts() == 6;
Summary empty = drain(List.of(), false);
assert empty.removed().isEmpty() && empty.shifts() == 0;
Summary wide = drain(List.of(1, 2, 3, 4, 5, 6, 7, 8), false);
assert wide.shifts() == 28 && wide.removed().size() == 8;
System.out.println(result.removed() + " shifts=" + result.shifts());
}
}

Step 1 of 6 · initialInitial lanes

Both collections contain the same FIFO values; shifts are a logical reference-movement model.

ArrayList

010120230340

ArrayDeque

010120230340

removed

[]

shift model total

0

Speed

Read all steps

Four values

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[10, 20, 30, 40]
ArrayDeque
[10, 20, 30, 40]
removed
[]
shift model total
0
Step 2: Remove 10
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[20, 30, 40]
ArrayDeque
[20, 30, 40]
removed
[10]
shift model step / total
3 / 3
Step 3: Remove 20
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[30, 40]
ArrayDeque
[30, 40]
removed
[10, 20]
shift model step / total
2 / 5
Step 4: Remove 30
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[40]
ArrayDeque
[40]
removed
[10, 20, 30]
shift model step / total
1 / 6
Step 5: Remove 40
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[]
ArrayDeque
[]
removed
[10, 20, 30, 40]
shift model step / total
0 / 6
Step 6: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[10, 20, 30, 40]
shift model total
6

Empty

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[]
ArrayDeque
[]
removed
[]
shift model total
0
Step 2: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[]
shift model total
0

Eight-entry frontier

Step 1: Initial lanes
Both collections contain the same FIFO values; shifts are a logical reference-movement model.
ArrayList
[1, 2, 3, 4, 5, 6, 7, 8]
ArrayDeque
[1, 2, 3, 4, 5, 6, 7, 8]
removed
[]
shift model total
0
Step 2: Remove 1
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[2, 3, 4, 5, 6, 7, 8]
ArrayDeque
[2, 3, 4, 5, 6, 7, 8]
removed
[1]
shift model step / total
7 / 7
Step 3: Remove 2
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[3, 4, 5, 6, 7, 8]
ArrayDeque
[3, 4, 5, 6, 7, 8]
removed
[1, 2]
shift model step / total
6 / 13
Step 4: Remove 3
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[4, 5, 6, 7, 8]
ArrayDeque
[4, 5, 6, 7, 8]
removed
[1, 2, 3]
shift model step / total
5 / 18
Step 5: Remove 4
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[5, 6, 7, 8]
ArrayDeque
[5, 6, 7, 8]
removed
[1, 2, 3, 4]
shift model step / total
4 / 22
Step 6: Remove 5
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[6, 7, 8]
ArrayDeque
[6, 7, 8]
removed
[1, 2, 3, 4, 5]
shift model step / total
3 / 25
Step 7: Remove 6
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[7, 8]
ArrayDeque
[7, 8]
removed
[1, 2, 3, 4, 5, 6]
shift model step / total
2 / 27
Step 8: Remove 7
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[8]
ArrayDeque
[8]
removed
[1, 2, 3, 4, 5, 6, 7]
shift model step / total
1 / 28
Step 9: Remove 8
Both lanes return the same value; only the ArrayList lane shifts its remaining references.
ArrayList
[]
ArrayDeque
[]
removed
[1, 2, 3, 4, 5, 6, 7, 8]
shift model step / total
0 / 28
Step 10: Return summary
Both lanes produced the same FIFO order. The shift total is a collection-operation model, not elapsed time, CPU instructions, bytes, or the final snapshot copy.
ArrayList
[]
ArrayDeque
[]
removed
[1, 2, 3, 4, 5, 6, 7, 8]
shift model total
28

Deeper note and related practice

The shift model counts logical reference moves, not CPU instructions or elapsed time.

Comparators and stable object sorting#

Module 10 of 18

A comparator defines ordering; stable object sorting retains encounter order when that comparator returns zero.

Objectives

Avoid subtraction overflow.
Declare tie policy.
Distinguish copied from mutated lists.

PrerequisitesJ05, J07.

Stable copied orderingjava

import java.util.*;
public class J10StableSort {
    record Item(String id, int rank) {}
    public static void main(String[] args) {
        List<Item> source = new ArrayList<>(List.of(new Item("A",2), new Item("B",1), new Item("C",2)));
        List<Item> ordered = new ArrayList<>(source);
        ordered.sort(Comparator.comparingInt(Item::rank));
        assert source.get(0).id().equals("A");
        assert ordered.stream().map(Item::id).reduce("", String::concat).equals("BAC");
        System.out.println("BAC");
    }
}

Expected: BAC; A remains before C among equal ranks.

Worked trace

The copy starts A,B,C. Sorting by rank yields B,A,C; source retains A,B,C.

Mistake(a,b) -> a.rank-b.rank can overflow; an undeclared tie leaves PriorityQueue behavior arbitrary.

RepairUse comparingInt/Integer.compare and thenComparing when ties need deterministic order.

Cost modelObject-list sorting is O(n log n) comparisons; comparator key extraction may run many times and is not cached once per element.

BoundariesList.sort is stable and mutates the list; copying n references first costs O(n) time/storage.

TakeawayPut the complete order policy in the comparator.

Stable object sorting

Separate comparator policy, stable ties, copied input, and sorted output.

JV04 · JV04-sort-rule@2026-09-06

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class JV04SortRule {
record Item(String id, int priority) {}
static String labels(List<Item> items) {
StringBuilder out = new StringBuilder();
for (Item item : items) {
if (!out.isEmpty()) out.append(',');
out.append(item.id()).append(':').append(item.priority());
}
return out.toString();
}
public static void main(String[] args) {
boolean trace = args.length == 1 && args[0].equals("--trace");
Item a = new Item("A", 2), b = new Item("B", 1), c = new Item("C", 2);
List<Item> original = new ArrayList<>(List.of(a, b, c));
if (trace) System.out.println("CREATE|original=" + labels(original));
List<Item> ordered = new ArrayList<>(original);
if (trace) System.out.println("COPY|original=" + labels(original) + "|ordered=" + labels(ordered) + "|outerDistinct=" + (original != ordered) + "|sameItems=" + (original.get(0) == ordered.get(0) && original.get(1) == ordered.get(1) && original.get(2) == ordered.get(2)));
if (trace) System.out.println("CONCEPTUAL|original=" + labels(original) + "|ordered=" + labels(ordered) + "|keys=" + labels(List.of(a, b, c)));
Comparator<Item> order = Comparator.comparingInt(Item::priority);
if (trace) System.out.println("COMPARATOR|original=" + labels(original) + "|ordered=" + labels(ordered) + "|rule=ascending priority|BbeforeA=" + (order.compare(b, a) < 0));
ordered.sort(order);
if (trace) System.out.println("SORT_COPY|original=" + labels(original) + "|ordered=" + labels(ordered) + "|stableTie=" + (ordered.indexOf(a) < ordered.indexOf(c)) + "|sameItems=" + (ordered.containsAll(original) && original.containsAll(ordered)));
original.sort(order);
if (trace) System.out.println("SORT_ORIGINAL|original=" + labels(original) + "|ordered=" + labels(ordered) + "|outerDistinct=" + (original != ordered) + "|stableTie=" + (original.indexOf(a) < original.indexOf(c)));
String output = ordered.get(0).id() + ordered.get(1).id() + ordered.get(2).id();
if (trace) System.out.println("OUTPUT|original=" + labels(original) + "|ordered=" + labels(ordered) + "|output=" + output + "|sharedA=" + (ordered.get(1) == a) + "|stableTie=" + (ordered.indexOf(a) < ordered.indexOf(c)));
else System.out.println(output);
assert ordered.equals(List.of(b, a, c)) && original.equals(ordered);
assert ordered != original && ordered.get(1) == a;
Comparator<Integer> broken = (left, right) -> left - right;
assert broken.compare(Integer.MAX_VALUE, 0) > 0;
assert broken.compare(0, -1) > 0;
assert broken.compare(Integer.MAX_VALUE, -1) < 0;
assert Integer.compare(Integer.MAX_VALUE, -1) > 0;
}
}

Step 1 of 7 · initialCreate original

A precedes C among equal priorities.

original

A:2 · B:1 · C:2

Speed

Read all steps

Priority with stable ties

Step 1: Create original
A precedes C among equal priorities.
original
A:2 · B:1 · C:2
Step 2: Copy original
The new outer list stores the same item references.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
Step 3: Conceptual comparator focus
Priority badges aid the explanation; comparingInt may call the extractor repeatedly.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
keys
A→2 · B→1 · C→2
Step 4: Create comparator
The ordering rule exists; neither list has been sorted.
original
A:2 · B:1 · C:2
ordered
A:2 · B:1 · C:2
rule
ascending priority
Step 5: Sort copied list
B moves first; stable sorting keeps A before C.
original
A:2 · B:1 · C:2
ordered
B:1 · A:2 · C:2
Step 6: Sort original list
Original now mutates to the same order but remains a distinct outer list.
original
B:1 · A:2 · C:2
ordered
B:1 · A:2 · C:2
Step 7: Print BAC
Both stable lists retain A before C among tied priorities.
original
B:1 · A:2 · C:2
ordered
B:1 · A:2 · C:2
output
BAC

Deeper note and related practice

Comparator consistency with equals is sometimes desirable but not automatically required; document deviations.

Priorities, ties and bounded selection#

Module 11 of 18

PriorityQueue exposes the least element under its comparator, not a sorted iterator or portable backing-array layout.

Objectives

Separate membership, head, and poll order.
Make tie policy explicit.
Define k=0 and k>n.

PrerequisitesJ10.

Priority and insertion sequencejava

import java.util.*;
public class J11PriorityTies {
    record Task(String id, int priority, long sequence) {}
    public static void main(String[] args) {
        PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::priority).thenComparingLong(Task::sequence));
        queue.offer(new Task("A",2,0)); queue.offer(new Task("B",1,1)); queue.offer(new Task("C",2,2));
        String order = queue.poll().id() + queue.poll().id() + queue.poll().id();
        assert order.equals("BAC") && queue.poll() == null;
        System.out.println(order);
    }
}

Expected: BAC

Worked trace

B becomes head by priority; A precedes C only because sequence is the declared secondary key.

MistakeDisplaying iteration order as sorted output or as a specified internal heap layout is false.

RepairPoll to obtain priority order; label any tree as a conceptual arrangement satisfying parent≤child.

Cost modeloffer/poll O(log n), peek O(1); heapify from a collection can be O(n), while repeated insertion is O(n log n).

BoundariesTies are arbitrary without a secondary comparator; null elements are rejected.

TakeawayA heap promises the next priority, not a fully sorted view.

PriorityQueue membership and head

Use a labeled conceptual heap arrangement without claiming the private backing layout.

JV05 · JV05-heap-ties@2026-09-06

import java.util.Comparator;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.PriorityQueue;
public class JV05HeapTies {
record Task(int priority, long sequence, String name) {}
static String tuple(Task task) {
return task == null ? "null" : "(" + task.priority() + "," + task.sequence() + "," + task.name() + ")";
}
static String heap(List<Task> conceptual) {
StringBuilder out = new StringBuilder("[");
for (int i = 0; i < conceptual.size(); i++) {
if (i > 0) out.append(", ");
out.append(tuple(conceptual.get(i)));
}
return out.append(']').toString();
}
static boolean heapInvariant(List<Task> conceptual, Comparator<Task> order) {
for (int child = 1; child < conceptual.size(); child++) {
if (order.compare(conceptual.get((child - 1) / 2), conceptual.get(child)) > 0) return false;
}
return true;
}
static String membership(PriorityQueue<Task> queue, Task a, Task b, Task c) {
StringBuilder out = new StringBuilder("[");
for (Task task : List.of(a, b, c)) if (queue.contains(task)) {
if (out.length() > 1) out.append(", ");
out.append(task.name());
}
return out.append(']').toString();
}
static boolean actualMembershipMatches(List<Task> conceptual, PriorityQueue<Task> queue) {
if (conceptual.size() != queue.size()) return false;
IdentityHashMap<Task, Integer> conceptualCounts = new IdentityHashMap<>();
IdentityHashMap<Task, Integer> actualCounts = new IdentityHashMap<>();
for (Task task : conceptual) conceptualCounts.merge(task, 1, Integer::sum);
for (Task task : queue) actualCounts.merge(task, 1, Integer::sum);
if (conceptualCounts.size() != actualCounts.size()) return false;
for (Task task : conceptualCounts.keySet()) {
if (!conceptualCounts.get(task).equals(actualCounts.get(task))) return false;
}
return true;
}
static void emit(boolean trace, String event, List<Task> conceptual, PriorityQueue<Task> queue,
Comparator<Task> order, Task a, Task b, Task c, String returned) {
if (!trace) return;
System.out.println(event + "|heap=" + heap(conceptual) + "|membership=" + membership(queue, a, b, c)
+ "|head=" + (queue.peek() == null ? "none" : queue.peek().name())
+ "|heapInvariant=" + heapInvariant(conceptual, order)
+ "|actualMembershipMatch=" + actualMembershipMatches(conceptual, queue) + returned);
}
public static void main(String[] args) {
boolean trace = args.length == 1 && args[0].equals("--trace");
Comparator<Task> order = Comparator.comparingInt(Task::priority).thenComparingLong(Task::sequence);
Task a = new Task(2, 0, "A"), b = new Task(1, 1, "B"), c = new Task(2, 2, "C");
PriorityQueue<Task> queue = new PriorityQueue<>(order);
emit(trace, "INIT", List.of(), queue, order, a, b, c, "");
queue.offer(a);
emit(trace, "OFFER_A", List.of(a), queue, order, a, b, c, "");
queue.offer(b);
emit(trace, "OFFER_B", List.of(b, a), queue, order, a, b, c, "");
queue.offer(c);
emit(trace, "OFFER_C", List.of(b, a, c), queue, order, a, b, c, "");
Task first = queue.remove();
emit(trace, "REMOVE_B", List.of(a, c), queue, order, a, b, c, "|returned=B");
Task second = queue.remove();
emit(trace, "REMOVE_A", List.of(c), queue, order, a, b, c, "|returned=B,A");
Task third = queue.remove();
emit(trace, "REMOVE_C", List.of(), queue, order, a, b, c, "|returned=B,A,C");
Task empty = queue.poll();
emit(trace, "POLL_EMPTY", List.of(), queue, order, a, b, c, "|empty=null");
String output = first.name() + second.name() + third.name();
if (trace) emit(true, "OUTPUT", List.of(), queue, order, a, b, c, "|output=" + output);
else System.out.println(output);
assert first == b && second == a && third == c && empty == null;
}
}

Step 1 of 9 · initialInitial queue

No task is present.

One heap, array view

empty

Same entries, parent/child view

empty

membership: []

Speed

Boundary check: One valid heap arrangement; Java PriorityQueue does not expose a guaranteed backing-array order. [B,C,A] is also a valid conceptual min-heap while not globally sorted.

Read all steps

Priorities and explicit ties

Step 1: Initial queue
No task is present.
heap array
[]
membership
[]
Step 2: Offer A
A is the only member and therefore the head.
heap array
[(2,0,A)]
membership
[A]
head
A
Step 3: Offer B
B has smaller priority and becomes head.
heap array
[(1,1,B), (2,0,A)]
membership
[A, B]
head
B
Step 4: Offer C
Sequence breaks the priority-2 tie between A and C.
heap array
[(1,1,B), (2,0,A), (2,2,C)]
membership
[A, B, C]
head
B
Step 5: Remove B
The comparator-minimum object leaves.
heap array
[(2,0,A), (2,2,C)]
membership
[A, C]
returned
B
Step 6: Remove A
A wins the explicit sequence tie.
heap array
[(2,2,C)]
membership
[C]
returned
B · A
Step 7: Remove C
The queue becomes empty.
heap array
[]
membership
[]
returned
B · A · C
Step 8: Poll empty
poll returns null rather than throwing.
heap array
[]
membership
[]
empty result
null
Step 9: Print BAC
The declared policy produces deterministic poll order.
heap array
[]
membership
[]
output
BAC

Deeper note and related practice

For top-k, state whether output must be sorted; sorting k retained values adds O(k log k).

Search results and duplicate boundaries#

Module 12 of 18

Half-open [left,right) invariants make lower and upper duplicate boundaries composable.

Objectives

Decode library insertion points.
Write lower and upper boundaries.
Handle duplicates, after-all, and empty input.

PrerequisitesJ04.

Both duplicate boundariesjava

public class J12Boundaries {
    static int boundary(int[] a, int target, boolean upper) {
        int left=0, right=a.length;
        while (left<right) { int middle=left+(right-left)/2;
            if (a[middle]<target || (upper && a[middle]==target)) left=middle+1; else right=middle;
        }
        return left;
    }
    public static void main(String[] args) {
        int[] a={1,3,3,7}; assert boundary(a,3,false)==1; assert boundary(a,3,true)==3;
        assert boundary(a,9,false)==4 && boundary(new int[0],3,false)==0;
        System.out.println(boundary(a,3,false)+" "+boundary(a,3,true));
    }
}

Expected: 1 3

Worked trace

Lower moves equal values rightward into the candidate region; upper moves them leftward out of it.

MistakeArrays.binarySearch may return any matching duplicate index, not the first or last.

RepairEncode the partition explicitly and return the insertion boundary.

Cost modelO(log(n+1)) comparisons and O(1) working storage on random-access arrays.

BoundariesEmpty returns 0; after-all returns n; use right-left arithmetic to avoid midpoint addition overflow.

TakeawaySearch for a boundary predicate, not merely an equal element.

Duplicate boundaries

Trace lower/upper insertion boundaries without revealing the result before the interval closes.

JV06 · JV06-boundaries@2026-09-06

Example

public class JV06Boundaries {
static int boundary(int[] values, int target, boolean upper, boolean trace) {
int left = 0, right = values.length;
if (trace) System.out.println("0|interval=[" + left + "," + right + ")");
while (left < right) {
int middle = left + (right - left) / 2;
int compared = values[middle];
if (values[middle] < target || (upper && values[middle] == target)) {
left = middle + 1;
} else {
right = middle;
}
if (trace) System.out.println("I|middle=" + middle + "|value=" + compared + "|interval=[" + left + "," + right + ")");
}
if (trace) System.out.println("R|result=" + left + "|interval=[" + left + "," + right + ")");
return left;
}
public static void main(String[] args) {
boolean trace = args.length > 0 && args[0].equals("--trace");
String preset = trace ? (args.length > 1 ? args[1] : "lower") : (args.length == 0 ? "lower" : args[0]);
int[] values = preset.equals("empty") ? new int[0] : new int[]{1, 3, 3, 7};
int target = preset.equals("after") ? 9 : 3;
boolean upper = preset.equals("upper");
int result = boundary(values, target, upper, trace);
int expected = switch (preset) {
case "lower" -> 1;
case "upper" -> 3;
case "after" -> 4;
case "empty" -> 0;
default -> throw new IllegalArgumentException("unknown preset");
};
assert result == expected;
if (!trace) System.out.println(result);
}
}

Step 1 of 5 · initialStart lower

The half-open candidate interval shrinks while the answer remains concealed.

values

01132337

candidate interval

[0,4)

result

hidden

Speed

Read all steps

lower 3

Step 1: Start lower
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,2)
result
hidden
Step 3: Compare index 1 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,1)
result
hidden
Step 4: Compare index 0 / value 1
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[1,1)
result
hidden
Step 5: Return lower
The empty half-open interval reveals boundary 1.
values
[1, 3, 3, 7]
candidate interval
[1,1)
result
1

upper 3

Step 1: Start upper
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,4)
result
hidden
Step 3: Compare index 3 / value 7
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,3)
result
hidden
Step 4: Return upper
The empty half-open interval reveals boundary 3.
values
[1, 3, 3, 7]
candidate interval
[3,3)
result
3

lower 9

Step 1: Start after
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[0,4)
result
hidden
Step 2: Compare index 2 / value 3
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[3,4)
result
hidden
Step 3: Compare index 3 / value 7
The half-open candidate interval shrinks while the answer remains concealed.
values
[1, 3, 3, 7]
candidate interval
[4,4)
result
hidden
Step 4: Return length
The empty half-open interval reveals boundary 4.
values
[1, 3, 3, 7]
candidate interval
[4,4)
result
4

empty

Step 1: Start empty
The half-open candidate interval shrinks while the answer remains concealed.
values
[]
candidate interval
[0,0)
result
hidden
Step 2: Return zero
The empty half-open interval reveals boundary 0.
values
[]
candidate interval
[0,0)
result
0

Deeper note and related practice

A negative library result encodes insertion point as -result-1; Integer.MIN_VALUE is not produced for valid array lengths.

Overflow, division and bit masks#

Module 13 of 18

Java integer arithmetic uses fixed widths; widening after overflow is too late, and / truncates toward zero.

Objectives

Promote operands before arithmetic.
Choose truncating or floor division.
Build masks without shifting in the wrong width.

PrerequisitesJ01.

Promote before the operationjava

public class J13NumericContracts {
    public static void main(String[] args) {
        int a=Integer.MAX_VALUE, b=1; long safe=(long)a+b;
        assert safe==2147483648L && -7/3==-2 && Math.floorDiv(-7,3)==-3;
        long bit40=1L<<40; assert bit40==1099511627776L;
        System.out.println(safe);
    }
}

Expected: 2147483648

Worked trace

Casting a first selects long addition; 1L selects a 64-bit shift before bit 40 is formed.

Mistakelong total = a+b still performs overflowing int addition first.

RepairWiden an operand before the operation and use exact arithmetic helpers when overflow must reject.

Cost modelFixed-width primitive arithmetic is O(1); BigInteger costs depend on operand size.

BoundariesMath.abs(Integer.MIN_VALUE) remains negative; shift distances are masked by the language.

TakeawayChoose width and rounding semantics before calculating.

Deeper note and related practice

Use floorDiv/floorMod only when mathematical floor behavior - not truncation toward zero - is the contract.

Waiting calls and return values#

Module 14 of 18

Each invocation owns locals while callers wait at a call site; a return value is then assigned into the resumed frame.

Objectives

Trace calls and returns separately.
Account for O(depth) frames.
Replace unbounded depth with an explicit stack.

PrerequisitesJ01, J02.

Triangular return chainjava

public class J14CallReturns {
    static int triangular(int n) {
        if (n==0) return 0;
        int subtotal=triangular(n-1);
        return n+subtotal;
    }
    public static void main(String[] args) {
        assert triangular(3)==6 && triangular(0)==0;
        System.out.println(triangular(3));
    }
}

Expected: 6

Worked trace

Calls create n=3,2,1,0 frames; returns produce 0, then locals receive 0,1,3 before returning 1,3,6.

MistakeMerging a callee return with assignment into the caller hides the suspended frame.

RepairDraw a return token, then a separate resumed-caller state.

Cost modelO(n) time and O(n) call frames for this recurrence.

BoundariesThis method requires n≥0; Java does not guarantee a portable safe recursion-depth number.

TakeawayEvery recursive call suspends one distinct local environment.

Recursive callers wait

Distinguish return tokens from assignment into suspended caller locals.

JV07 · JV07-call-stack@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.Deque;
public class JV07CallStack {
static boolean trace;
static final Deque<Integer> liveCalls = new ArrayDeque<>();
static void emit(String event) {
if (trace) System.out.println(event + "|stack=" + liveCalls + "|depth=" + liveCalls.size());
}
static long triangular(int n) {
liveCalls.addLast(n);
emit("CALL|n=" + n);
if (n == 0) {
liveCalls.removeLast();
emit("RETURN|n=0|value=0");
return 0L;
}
long subtotal = triangular(n - 1);
emit("ASSIGN|n=" + n + "|subtotal=" + subtotal);
long result = n + subtotal;
liveCalls.removeLast();
emit("RETURN|n=" + n + "|value=" + result);
return result;
}
public static void main(String[] args) {
trace = args.length > 0 && args[0].equals("--trace");
int n = trace ? (args.length > 1 ? Integer.parseInt(args[1]) : 3) : (args.length == 0 ? 3 : Integer.parseInt(args[0]));
if (n != 0 && n != 3) throw new IllegalArgumentException("preset must be 0 or 3");
liveCalls.clear();
long answer = triangular(n);
if (trace) {
emit("MAIN_ASSIGN|answer=" + answer);
emit("PRINT|output=" + answer);
} else {
System.out.println(answer);
}
assert answer == (n == 0 ? 0L : 6L);
}
}

Step 1 of 14 · initialInitial state

Ready to call triangular(3); answer is unbound.

Call stack · newest active frame first

call stackempty

Return token and shared state

answer: unbound

Speed

Read all steps

n = 3

Step 1: Initial state
Ready to call triangular(3); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F3
Create F3 with n=3 and an unbound subtotal.
F3
n=3 · subtotal=unbound
Step 3: Call F2
F3 waits while F2 starts.
F3
waiting at L3
F2
n=2 · subtotal=unbound
Step 4: Call F1
F3 and F2 wait while F1 starts.
F3
waiting
F2
waiting
F1
n=1 · subtotal=unbound
Step 5: Call F0
The next invocation reaches the base case.
F3
waiting at L3
F2
waiting at L3
F1
waiting at L3
F0
n=0
Step 6: Return 0
F0 produces a return token; F1 has not assigned it yet.
F3
waiting at L3
F2
waiting at L3
F1
waiting at L3
just returned
0
Step 7: Assign F1 subtotal
F1 consumes the token into subtotal.
F3
waiting at L3
F2
waiting at L3
F1
n=1 · subtotal=0
Step 8: Return 1
F1 computes 1+0 and returns a token to F2.
F3
waiting at L3
F2
waiting at L3
just returned
1
Step 9: Assign F2 subtotal
F2 consumes the token into subtotal.
F3
waiting at L3
F2
n=2 · subtotal=1
Step 10: Return 3
F2 computes 2+1 and returns a token to F3.
F3
waiting at L3
just returned
3
Step 11: Assign F3 subtotal
F3 consumes the token into subtotal.
F3
n=3 · subtotal=3
Step 12: Return 6
F3 computes 3+3; the call stack becomes empty.
call stack
empty
just returned
6
Step 13: Assign answer
The outer call consumes the final token.
call stack
empty
answer
6
Step 14: Print 6
The final output reads the assigned result after every callee has returned.
output
6
answer
6

n = 0

Step 1: Initial state
Ready to call triangular(0); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F0
Main waits while the boundary invocation runs.
main
waiting at L5
F0
n=0
Step 3: Return 0
The base frame emits a return token; main has not assigned it yet.
call stack
empty
just returned
0
Step 4: Assign answer
Main consumes the token into answer.
call stack
empty
answer
0
Step 5: Print 0
The output reads the assigned result.
output
0
answer
0

Deeper note and related practice

Tail-call elimination is not a Java language guarantee, so do not rely on it for unbounded traversal.

Backtracking copies and memo states#

Module 15 of 18

Backtracking mutates one working path and saves independent snapshots; memoization also needs a distinct uncomputed state.

Objectives

Follow choose/recurse/undo.
Copy at the save boundary.
Separate an uncomputed memo slot from a valid zero.

PrerequisitesJ14.

Save path snapshotsjava

import java.util.*;
public class J15Subsets {
    static void search(int[] a,int i,List<Integer> path,List<List<Integer>> out){
        if(i==a.length){out.add(new ArrayList<>(path));return;}
        search(a,i+1,path,out); path.add(a[i]); search(a,i+1,path,out); path.remove(path.size()-1);
    }
    static List<List<Integer>> subsets(int[] a){List<List<Integer>> out=new ArrayList<>();search(a,0,new ArrayList<>(),out);return out;}
    public static void main(String[] args){var out=subsets(new int[]{1,2});assert out.toString().equals("[[], [2], [1], [1, 2]]");System.out.println(out);}
}

Expected: [[], [2], [1], [1, 2]]

Uncomputed is not zerojava

import java.util.*;
public class J15MemoStates {
    static long best(int[] a,int i,Long[] memo){if(i>=a.length)return 0;if(memo[i]!=null)return memo[i];return memo[i]=Math.max(best(a,i+1,memo),a[i]+best(a,i+2,memo));}
    public static void main(String[] args){int[] a={-2,0,5};long answer=best(a,0,new Long[a.length]);assert answer==5;System.out.println(answer);}
}

Expected: 5

Worked trace

For [1,2], exclude-first saves [], [2], [1], [1,2]; after every child returns, undo restores the caller's path.

MistakeSaving path itself stores four references to the same mutable object.

RepairCreate new ArrayList<>(path) at each leaf and use nullable/visited state for memo entries.

Cost modelSubsets require Θ(n·2ⁿ) returned elements across copied answers and O(n) active path/frames.

BoundariesEmpty input returns one empty subset; output cost is not auxiliary workspace.

TakeawayShare the work buffer; copy only when ownership transfers to the result.

Backtracking restores shared state

Follow exclude, choose, recurse, undo, copied saves, outer return, and caller assignment.

JV08 · JV08-backtracking@2026-09-06

Example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.List;
public class JV08Backtracking {
static boolean trace;
static final Deque<Integer> stack = new ArrayDeque<>();
static int savedId;
static List<Integer> trackedPath;
static List<List<Integer>> trackedAnswers;
static void emit(String event, List<Integer> path, List<List<Integer>> answers) {
if (trace) System.out.println(event + "|stack=" + stack + "|path=" + path + "|answers=" + answers
+ "|samePath=" + (path == trackedPath) + "|sameAnswers=" + (answers == trackedAnswers));
}
static List<List<Integer>> subsets(int[] values) {
List<List<Integer>> answers = new ArrayList<>();
List<Integer> path = new ArrayList<>();
trackedPath = path;
trackedAnswers = answers;
stack.clear();
savedId = 0;
emit("INIT|pathDistinctAnswers=" + (path != (Object) answers), path, answers);
search(values, 0, path, answers);
emit("AFTER_OUTER_CALL", path, answers);
emit("OUTER_RETURN|token=A", path, answers);
return answers;
}
static void search(int[] values, int index, List<Integer> path,
List<List<Integer>> answers) {
stack.addLast(index);
emit("CALL|index=" + index, path, answers);
if (index == values.length) {
List<Integer> snapshot = new ArrayList<>(path);
answers.add(snapshot);
emit("SAVE|id=A" + savedId++ + "|distinctFromPath=" + (snapshot != path), path, answers);
stack.removeLast();
emit("RETURN_LEAF|index=" + index, path, answers);
return;
}
search(values, index + 1, path, answers);
path.add(values[index]);
emit("CHOOSE|value=" + values[index], path, answers);
search(values, index + 1, path, answers);
path.remove(path.size() - 1);
emit("UNDO|value=" + values[index], path, answers);
stack.removeLast();
emit("RETURN_SEARCH|index=" + index, path, answers);
}
public static void main(String[] args) {
trace = args.length > 0 && args[0].equals("--trace");
boolean empty = trace ? args.length > 1 && args[1].equals("empty") : args.length == 1 && args[0].equals("empty");
int[] values = empty ? new int[0] : new int[]{1, 2};
List<List<Integer>> result = subsets(values);
if (trace) {
IdentityHashMap<List<Integer>, Boolean> identities = new IdentityHashMap<>();
for (List<Integer> answer : result) identities.put(answer, Boolean.TRUE);
System.out.println("MAIN_ASSIGN|resultSameAnswers=" + (result == trackedAnswers) + "|savedDistinct=" + (identities.size() == result.size()) + "|result=" + result);
System.out.println("PRINT|output=" + result);
} else {
System.out.println(result);
}
List<List<Integer>> expected = empty ? List.of(List.of())
: List.of(List.of(), List.of(2), List.of(1), List.of(1, 2));
assert result.equals(expected);
}
}

Step 1 of 29 · afterAfter outer initialization

P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.

Call stack · newest active frame first

search stack[]

Return token and shared state

path P: []
saved objects: []

Speed

Boundary check: Replacing L6 with answers.add(path) stores the same mutable path reference four times. Executing that change yields [[], [], [], []] after all undo steps.

Read all steps

values = [1, 2]

Step 1: After outer initialization
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[]
Step 2: Call search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[]
Step 3: Exclude 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[]
Step 4: Exclude 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2a:index=2]
path P
[]
saved objects
[]
Step 5: Save A0
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2a]
path P
[]
saved objects
[A0=[]]
Step 6: Return leaf F2a
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[A0=[]]
Step 7: Choose 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[2]
saved objects
[A0=[]]
Step 8: Include 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2b:index=2]
path P
[2]
saved objects
[A0=[]]
Step 9: Save A1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1 waiting,F2b]
path P
[2]
saved objects
[A0=[],A1=[2]]
Step 10: Return leaf F2b
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[2]
saved objects
[A0=[],A1=[2]]
Step 11: Undo 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1:index=1]
path P
[]
saved objects
[A0=[],A1=[2]]
Step 12: Return search(1)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[],A1=[2]]
Step 13: Choose 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 14: Include 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 15: Exclude 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2c:index=2]
path P
[1]
saved objects
[A0=[],A1=[2]]
Step 16: Save A2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2c]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 17: Return leaf F2c
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 18: Choose 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 19: Include 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2d:index=2]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1]]
Step 20: Save A3
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b waiting,F2d]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 21: Return leaf F2d
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1,2]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 22: Undo 2
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0 waiting,F1b:index=1]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 23: Return search(1)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[1]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 24: Undo 1
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 25: Return search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 26: After search(0)
P is one shared working list; every A-labelled saved value is a distinct ArrayList copy.
search stack
[]
path P
[]
saved objects
[A0=[],A1=[2],A2=[1],A3=[1,2]]
Step 27: Return answers
The outer method returns answer-list reference A as a token; main has not assigned it yet.
search stack
no live search/outer frame
path P
not live
saved objects
token→A=[[],[2],[1],[1,2]]
Step 28: Assign result
Main consumes the returned reference into result.
search stack
main active
path P
not live
saved objects
main.result→A=[[],[2],[1],[1,2]]
Step 29: Final output
The output reads four independent saved lists after P was restored.
search stack
main active
path P
not live
saved objects
output [[], [2], [1], [1, 2]]

values = []

Step 1: After outer initialization
The outer frame holds shared path P and answer list A while main waits on L12.
outer frame
values→I=[] · path→P · answers→A
path P
[]
saved objects
[]
Step 2: Call search(0)
The empty input starts one leaf invocation with the same P and A references.
search stack
[F0:index=0]
path P
[]
saved objects
[]
Step 3: Save A0
A new empty ArrayList is stored, distinct from P.
search stack
[F0:index=0]
path P
[]
saved objects
[A0=[]]
Step 4: Return search(0)
The leaf returns with P equal to its own entry state.
search stack
[]
path P
[]
saved objects
[A0=[]]
Step 5: After outer call
The call statement completes; P is empty and A contains one independent list.
outer frame
ready to return
path P
[]
saved objects
[A0=[]]
Step 6: Return answers
The subsets frame leaves and returns reference A as a token.
search stack
no live search/outer frame
path P
not live
just returned
A=[[]]
Step 7: Assign main.result
Main consumes the returned reference into result.
main
active
path P
not live
saved objects
main.result→A=[[]]
Step 8: Print result
The final output is the one saved empty subset.
main
active
path P
not live
saved objects
output [[]]

Deeper note and related practice

A memo value of zero can be a legitimate optimum, so zero alone cannot always mean uncomputed.

Linked nodes and tree traversals#

Module 16 of 18

Minimal node types make identity and pointer changes visible; save the next reference before rewiring a list.

Objectives

Preserve node identity during reversal.
Choose recursive or iterative tree traversal by depth.
Handle null roots.

PrerequisitesJ02, J14.

Reverse existing nodesjava

public class J16ListReversal {
    static class Node {int value;Node next;Node(int value){this.value=value;}}
    static Node reverse(Node head){Node previous=null,current=head;while(current!=null){Node following=current.next;current.next=previous;previous=current;current=following;}return previous;}
    public static void main(String[] args){Node a=new Node(1),b=new Node(2),c=new Node(3);a.next=b;b.next=c;Node head=reverse(a);assert head==c&&c.next==b&&b.next==a&&a.next==null;System.out.println(head.value);}
}

Expected: 3

Iterative preorderjava

import java.util.*;
public class J16TreePreorder {static class Node{int v;Node l,r;Node(int v){this.v=v;}}static List<Integer> walk(Node root){List<Integer> out=new ArrayList<>();if(root==null)return out;Deque<Node>s=new ArrayDeque<>();s.push(root);while(!s.isEmpty()){Node n=s.pop();out.add(n.v);if(n.r!=null)s.push(n.r);if(n.l!=null)s.push(n.l);}return out;}public static void main(String[]args){Node r=new Node(1);r.l=new Node(2);r.r=new Node(3);assert walk(r).equals(List.of(1,2,3));System.out.println(walk(r));}}

Expected: [1, 2, 3]

Worked trace

List reversal moves one existing next edge at a time after preserving following; preorder pushes right before left so left is popped first.

MistakeOverwriting current.next before saving it loses the unreversed suffix.

RepairPreserve following, rewire current, then advance both pointers.

Cost modelBoth examples visit each node once; list reversal uses O(1) workspace, iterative tree traversal O(h) to O(n) pending nodes.

BoundariesNull input returns null/empty; the explicit stack avoids depending on call-stack depth.

TakeawayTrack node identities and pending references, not only printed values.

Deeper note and related practice

A traversal's peak memory follows the maximum pending frontier, not always tree height.

Graph and grid implementation choices#

Module 17 of 18

Dense integer nodes fit indexed adjacency lists and arrays; arbitrary keys often need maps and sets.

Objectives

Mark discovered on enqueue.
Validate graph/grid indices.
Distinguish graph size from pending frontier.

PrerequisitesJ04, J07, J09.

Unweighted distancesjava

import java.util.*;
public class J17BfsDistances {
    static int[] distances(List<List<Integer>> graph,int start){int[] d=new int[graph.size()];Arrays.fill(d,-1);Queue<Integer>q=new ArrayDeque<>();d[start]=0;q.offer(start);while(!q.isEmpty()){int node=q.poll();for(int next:graph.get(node))if(d[next]==-1){d[next]=d[node]+1;q.offer(next);}}return d;}
    public static void main(String[]args){var g=List.of(List.of(1,2),List.of(3),List.of(3),List.<Integer>of());int[]d=distances(g,0);assert Arrays.equals(d,new int[]{0,1,1,2});System.out.println(Arrays.toString(d));}
}

Expected: [0, 1, 1, 2]

Worked trace

Start 0 discovers 1 and 2 at distance 1; 1 discovers 3 at distance 2 before 2 can enqueue it again.

MistakeMarking seen only on dequeue permits duplicate pending entries.

RepairMark discovery at enqueue time and validate every neighbor index if input is untrusted.

Cost modelO(V+E) time and O(V) result/visited storage; queue peak equals the largest pending frontier.

BoundariesThe example requires a non-null graph, valid start, and neighbor indices in range.

TakeawayChoose representations from node identity and traversal operations.

Deeper note and related practice

For grids, rectangular arrays permit one column count; ragged arrays require per-row bounds.

Pattern handoffs and assessment IO#

Module 18 of 18

Templates are recall aids: select one by invariant, state its preconditions, then adapt it to the prompt and judge boundary.

Objectives

Select among the 15 retained Java templates.
Keep method and assessment I/O separate.
Carry ordering, mutation, width, and empty policies into adaptation.

PrerequisitesJ01–J17 as needed.

Thin assessment wrapperjava

import java.io.*;import java.util.*;
public class J18AssessmentIO {
    static long solve(int[] values){long total=0;for(int value:values)if(value>0)total+=value;return total;}
    public static void main(String[]args)throws Exception{Scanner in=new Scanner(new BufferedInputStream(System.in));if(!in.hasNextInt())return;int n=in.nextInt();if(n<0)throw new IllegalArgumentException("negative n");int[]a=new int[n];for(int i=0;i<n;i++)a[i]=in.nextInt();System.out.println(solve(a));}
}

Expected: For stdin `4 4 -2 0 7`, prints `11` and one newline.

Worked trace

The wrapper parses exactly n integers, calls a pure method, then emits only the requested answer.

MistakeCopying a template without its precondition can turn a linear idea into a wrong algorithm.

RepairName why the invariant applies, then adapt types, boundaries, and output policy.

Cost modelParsing plus the example method is O(n); template-specific costs remain attached to each disclosure.

BoundariesJudge input is trusted to contain n integers here; production parsing would need a different error contract.

TakeawayRecall structure, but re-derive correctness for the actual prompt.

Deeper note and related practice

The page never sends, stores, or executes entered code; fixtures verify checked-in canonical sources only.

Common interview templates#

These fifteen retained contracts are recall aids, not proprietary answers. Open one only after stating why its invariant and preconditions match.

Two PointersA sorted array and target sum let each comparison discard one endpoint. This contract returns indices or {-1,-1} and does not mutate input.

Use when: A sorted array and target sum let each comparison discard one endpoint. This contract returns indices or {-1,-1} and does not mutate input.

Typical complexity: O(n) time and O(1) working space.

Two Pointers templatejava

static int[] pairSum(int[] nums, long target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        long sum = (long) nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

Sliding WindowValues are nonnegative and you need the shortest nonempty contiguous range whose sum reaches target; target must be positive.

Use when: Values are nonnegative and you need the shortest nonempty contiguous range whose sum reaches target; target must be positive.

Typical complexity: O(n) time and O(1) working space because both boundaries only advance.

Sliding Window templatejava

static int minWindowAtLeast(int[] nums, long target) {
    if (target <= 0) throw new IllegalArgumentException("target must be positive");
    int left = 0;
    long windowSum = 0;
    int answer = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] < 0) throw new IllegalArgumentException("negative value");
        windowSum += nums[right];
        while (windowSum >= target) {
            answer = Math.min(answer, right - left + 1);
            windowSum -= nums[left++];
        }
    }
    return answer == Integer.MAX_VALUE ? 0 : answer;
}

Binary SearchA sorted array needs a lower or upper insertion boundary, including duplicates and absent targets.

Use when: A sorted array needs a lower or upper insertion boundary, including duplicates and absent targets.

Typical complexity: O(log(n+1)) comparisons and O(1) working space.

Binary Search templatejava

public class J12Boundaries {
    static int boundary(int[] a, int target, boolean upper) {
        int left=0, right=a.length;
        while (left<right) { int middle=left+(right-left)/2;
            if (a[middle]<target || (upper && a[middle]==target)) left=middle+1; else right=middle;
        }
        return left;
    }
    public static void main(String[] args) {
        int[] a={1,3,3,7}; assert boundary(a,3,false)==1; assert boundary(a,3,true)==3;
        assert boundary(a,9,false)==4 && boundary(new int[0],3,false)==0;
        System.out.println(boundary(a,3,false)+" "+boundary(a,3,true));
    }
}

BFSYou need levels or shortest unweighted distance.

Use when: You need levels or shortest unweighted distance.

Typical complexity: O(V + E) time and O(V) space.

BFS templatejava

static List<Integer> bfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] seen = new boolean[graph.size()];
    queue.offer(start);
    seen[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (!seen[neighbor]) {
                seen[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
    return order;
}

DFSYou need deterministic preorder reachability without relying on recursive call depth. Iterator frames preserve adjacency order.

Use when: You need deterministic preorder reachability without relying on recursive call depth. Iterator frames preserve adjacency order.

Typical complexity: O(V + E) time and O(V) visited/frame space.

DFS templatejava

static List<Integer> dfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] seen = new boolean[graph.size()];
    record Frame(int node, Iterator<Integer> edges) {}
    Deque<Frame> stack = new ArrayDeque<>();
    seen[start] = true;
    order.add(start);
    stack.push(new Frame(start, graph.get(start).iterator()));
    while (!stack.isEmpty()) {
        Frame frame = stack.peek();
        if (!frame.edges().hasNext()) { stack.pop(); continue; }
        int next = frame.edges().next();
        if (seen[next]) continue;
        seen[next] = true;
        order.add(next);
        stack.push(new Frame(next, graph.get(next).iterator()));
    }
    return order;
}

Tree DFSA tree answer depends on values returned from child subtrees.

Use when: A tree answer depends on values returned from child subtrees.

Typical complexity: O(n) time and O(h) call-stack space.

Tree DFS templatejava

static int treeDepth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = treeDepth(node.left);
    int rightDepth = treeDepth(node.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

Tree BFSYou need levels, nearest depth, or breadth-first order.

Use when: You need levels, nearest depth, or breadth-first order.

Typical complexity: O(n) time and O(w) queue space.

Tree BFS templatejava

static List<List<Integer>> treeLevels(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

BacktrackingYou must enumerate every subset while restoring one shared working path and saving independent results.

Use when: You must enumerate every subset while restoring one shared working path and saving independent results.

Typical complexity: Θ(n·2ⁿ) returned elements and O(n) active path/call space.

Backtracking templatejava

import java.util.*;
public class J15Subsets {
    static void search(int[] a,int i,List<Integer> path,List<List<Integer>> out){
        if(i==a.length){out.add(new ArrayList<>(path));return;}
        search(a,i+1,path,out); path.add(a[i]); search(a,i+1,path,out); path.remove(path.size()-1);
    }
    static List<List<Integer>> subsets(int[] a){List<List<Integer>> out=new ArrayList<>();search(a,0,new ArrayList<>(),out);return out;}
    public static void main(String[] args){var out=subsets(new int[]{1,2});assert out.toString().equals("[[], [2], [1], [1, 2]]");System.out.println(out);}
}

Heap / Top KReturn the largest k values in ascending order. k<0 rejects; k=0 returns empty; k>n returns every value.

Use when: Return the largest k values in ascending order. k<0 rejects; k=0 returns empty; k>n returns every value.

Typical complexity: O(n log(min(k,n))) time plus O(k log k) output sorting; O(min(k,n)) heap space.

Heap / Top K templatejava

static int[] largestK(int[] nums, int k) {
    if (k < 0) throw new IllegalArgumentException("negative k");
    int keep = Math.min(k, nums.length);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int value : nums) {
        heap.offer(value);
        if (heap.size() > keep) heap.poll();
    }
    int[] answer = new int[keep];
    for (int i = 0; i < keep; i++) answer[i] = heap.poll();
    return answer;
}

Prefix SumMany half-open range [left,right) sum queries can reuse one widened cumulative array.

Use when: Many half-open range [left,right) sum queries can reuse one widened cumulative array.

Typical complexity: O(n) preprocessing and O(1) per query, with O(n) stored prefix values.

Prefix Sum templatejava

static long[] prefixSums(int[] nums) {
    long[] prefix = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

static long rangeSum(long[] prefix, int left, int rightExclusive) {
    if (left < 0 || left > rightExclusive || rightExclusive >= prefix.length) {
        throw new IllegalArgumentException("invalid half-open range");
    }
    return prefix[rightExclusive] - prefix[left];
}

Monotonic StackYou need the next previous greater/smaller boundary.

Use when: You need the next previous greater/smaller boundary.

Typical complexity: O(n) time and O(n) space.

Monotonic Stack templatejava

static int[] nextGreater(int[] nums) {
    int[] answer = new int[nums.length];
    Arrays.fill(answer, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            answer[stack.pop()] = i;
        }
        stack.push(i);
    }
    return answer;
}

Union FindEdges merge components and connectivity queries repeat; node IDs must be in [0,n).

Use when: Edges merge components and connectivity queries repeat; node IDs must be in [0,n).

Typical complexity: O(n) initialization; inverse-Ackermann amortized find/union with path halving and rank; O(n) storage.

Union Find templatejava

static class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private int components;

    UnionFind(int n) {
        if (n < 0) throw new IllegalArgumentException("negative size");
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        components = n;
    }

    int find(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }

    boolean union(int first, int second) {
        int rootA = find(first);
        int rootB = find(second);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) {
            int swap = rootA;
            rootA = rootB;
            rootB = swap;
        }
        parent[rootB] = rootA;
        if (rank[rootA] == rank[rootB]) rank[rootA]++;
        components--;
        return true;
    }

    int components() { return components; }
}

Topological SortDirected dependencies must be processed after prerequisites; return null when a cycle makes an order impossible.

Use when: Directed dependencies must be processed after prerequisites; return null when a cycle makes an order impossible.

Typical complexity: O(V + E) time and O(V) result/indegree/queue space.

Topological Sort templatejava

static List<Integer> topologicalOrder(List<List<Integer>> graph) {
    int[] indegree = new int[graph.size()];
    for (List<Integer> neighbors : graph) {
        for (int neighbor : neighbors) indegree[neighbor]++;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int node = 0; node < indegree.length; node++) {
        if (indegree[node] == 0) queue.offer(node);
    }
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (--indegree[neighbor] == 0) queue.offer(neighbor);
        }
    }
    return order.size() == graph.size() ? order : null;
}

1-D Dynamic ProgrammingReturn the maximum sum of nonadjacent values, allowing the empty selection. Use long state so int inputs cannot overflow the recurrence.

Use when: Return the maximum sum of nonadjacent values, allowing the empty selection. Use long state so int inputs cannot overflow the recurrence.

Typical complexity: O(n) time and O(1) working space.

1-D Dynamic Programming templatejava

static long bestTotal(int[] values) {
    long previousTwo = 0;
    long previousOne = 0;
    for (int value : values) {
        long current = Math.max(previousOne, previousTwo + value);
        previousTwo = previousOne;
        previousOne = current;
    }
    return previousOne;
}

Grid TraversalCount reachable passable 1-cells in a non-null rectangular grid from a valid start; blocked starts return zero.

Use when: Count reachable passable 1-cells in a non-null rectangular grid from a valid start; blocked starts return zero.

Typical complexity: O(rows × cols) time and visited/queue space in the worst case.

Grid Traversal templatejava

static int visitGrid(int[][] grid, int startRow, int startCol) {
    int rows = grid.length;
    if (rows == 0) return 0;
    int cols = grid[0].length;
    for (int[] row : grid) if (row.length != cols) throw new IllegalArgumentException("ragged grid");
    if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) throw new IllegalArgumentException("invalid start");
    if (grid[startRow][startCol] != 1) return 0;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] seen = new boolean[rows][cols];
    queue.offer(new int[]{startRow, startCol});
    seen[startRow][startCol] = true;
    int visited = 0;
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        visited++;
        for (int[] direction : directions) {
            int row = cell[0] + direction[0];
            int col = cell[1] + direction[1];
            if (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] == 1 && !seen[row][col]) {
                seen[row][col] = true;
                queue.offer(new int[]{row, col});
            }
        }
    }
    return visited;
}

Common interview mistakes#

Comparing strings with ==

== compares references. Use equals for String content.

Defaulting to legacy Stack

Prefer Deque with ArrayDeque for stack behavior.

Comparator subtraction

a - b can overflow and break ordering. Use Integer.compare.

Mixing length APIs

Arrays use length, strings use length(), and collections use size().

ArrayList.remove overloads

remove(int) uses an index; remove(Object) removes a matching value.

Ignoring integer overflow

Promote to long before addition or multiplication when the result can exceed int.

Forgetting String immutability

Use StringBuilder for repeated construction or mutation-like work.

Mutating during enhanced-for

Structural modification can throw ConcurrentModificationException. Use an iterator or collect changes separately.

Mixing queue APIs

offer/poll/peek and add/remove/element have different empty/capacity behavior. Choose intentionally.

Unsafe autounboxing

Unboxing a null wrapper throws NullPointerException; check nullable map/queue results.

Broken and corrected examples#

The three retained repair IDs name a concrete regression case.

Overflow-safe ordering

Failure: Subtraction can overflow and violate the comparator contract.

Regression case: Sort Integer.MIN_VALUE and Integer.MAX_VALUE and assert ascending order.

Brokenjava

items.sort((a, b) -> a.score - b.score);

Correctedjava

items.sort((a, b) -> Integer.compare(a.score, b.score));

Compare string content

Failure: The broken form compares object identities rather than String contents.

Regression case: Build two distinct String objects containing x and assert the comparison is true.

Brokenjava

boolean same = new String("x") == new String("x");

Correctedjava

boolean same = new String("x").equals(new String("x"));

Promote before arithmetic

Failure: The int addition can overflow before its result is widened to long.

Regression case: Add Integer.MAX_VALUE and one and assert the result equals 2147483648L.

Brokenjava

long total = first + second;

Correctedjava

long total = (long) first + second;

Debugging checklist#

Restate the invariant and trace the smallest failing input before editing the implementation.
Check primitive versus reference equality, nullable wrappers, and every equals/hashCode assumption used by maps or sets.
Promote operands to long before arithmetic that may overflow int; avoid subtraction comparators.
Verify array, String, and collection length APIs and the chosen closed or half-open interval convention.
Test empty, singleton, duplicate, overflow, Unicode, and deep traversal cases; choose an explicit stack when depth is unbounded.

Questions about the language#

These are reasonable discussion prompts, not claims about every interviewer or company.

Why == and equals answer different questions for references and how hashCode must agree with equals.
Why ArrayDeque is normally preferable to legacy Stack and which operations reject null.
How PriorityQueue chooses its head and how to build an overflow-safe comparator.
Where boxing, unboxing, generic collections, and nullable lookup results create runtime cost or risk.
When int is insufficient and why casting after an overflowing operation is too late.

Language transfer exercises#

The five existing checks remain concealed until you choose to open them. The later Java exercise backlog is intentionally not shipped here.

predict
Reference or value equality
Predict the results of new String("x") == new String("x") and the corresponding equals call.
Answer check
The reference comparison is false for the two distinct objects; equals is true because String defines content equality.
trace
Trace queue discovery
Trace an ArrayDeque BFS from A to neighbors B and C when both point to D. Mark visited at insertion time.
Answer check
D is offered once: mark it visited when B offers it so C cannot add a duplicate queue entry.
repair
Repair the comparator
Replace (a, b) -> a.score - b.score and explain the failure it avoids.
Answer check
Use Comparator.comparingInt or Integer.compare(a.score, b.score); subtraction can overflow and violate comparator ordering.
choose
Choose a collection
Choose ArrayList, HashSet, HashMap, ArrayDeque, TreeMap, or PriorityQueue for indexed access, membership, FIFO, ordered keys, and next priority.
Answer check
ArrayList, HashSet, ArrayDeque, TreeMap, and PriorityQueue respectively; HashMap is for key/value lookup without sorted-key requirements.
transfer
Unlabeled transfer
Maintain the next three tasks by smallest deadline, breaking ties by insertion order. State the queue element and comparator.
Answer check
Store a record/object with deadline and sequence; compare first with Long.compare on deadline, then Long.compare on sequence.

Reach this point to mark the lesson as read.

Input and output conventions#

Java interview sequence#

Quick reference#

Read the contract and write a method#

Values, references and method calls#

Names and values

Objects

Shared array and local slots

Primitive values, wrappers and null#

Arrays, copies and rectangular grids#

ArrayList operations, views and copies#

Names and values

Objects

View, copy, and overloads

Strings, builders and character assumptions#

Keys, counts and ordered alternatives#

Iteration, generics and lazy work#

Stack and queue contracts#

ArrayList

ArrayDeque

removed

shift model total

Four values

Empty

Eight-entry frontier

Comparators and stable object sorting#

original

Priority with stable ties

Priorities, ties and bounded selection#

One heap, array view

Same entries, parent/child view

Priorities and explicit ties

Search results and duplicate boundaries#

values

candidate interval

result

lower 3

upper 3

lower 9

empty

Overflow, division and bit masks#

Waiting calls and return values#

Call stack · newest active frame first

Return token and shared state

n = 3

n = 0

Backtracking copies and memo states#

Call stack · newest active frame first

Return token and shared state

values = [1, 2]

values = []

Linked nodes and tree traversals#

Graph and grid implementation choices#

Pattern handoffs and assessment IO#

Common interview templates#

Common interview mistakes#

Comparing strings with ==

Defaulting to legacy Stack

Comparator subtraction

Mixing length APIs

ArrayList.remove overloads

Ignoring integer overflow

Forgetting String immutability

Mutating during enhanced-for

Mixing queue APIs

Unsafe autounboxing

Broken and corrected examples#

Overflow-safe ordering

Compare string content

Promote before arithmetic

Debugging checklist#

Questions about the language#

Language transfer exercises#

Reference or value equality

Trace queue discovery

Repair the comparator

Choose a collection

Unlabeled transfer

Finish this lesson

Input and output conventions#