Java toolkit for coding rounds

Java is a strong language for coding rounds: its collections include a deque, a priority queue, sorted maps and a map that can evict in least-recently-used order, and its types catch mistakes before a test does. What it does not catch are a handful of quiet traps: comparators that overflow, Integer objects compared with ==, int arithmetic that wraps around, and input read too slowly for a million numbers. This lesson tours the collections a coding round uses, reproduces each trap next to its fix, measures the input methods, and shows which Java versions a platform must run for the newer features. Every program here ran on JDK 27, the current release; nothing in it behaves differently on Java 21 or 25 except the compact source file, which needs 25.

The collections a coding round uses

A handful of classes cover almost every problem, and the run below uses each of them once. java CollectionsTour.java compiles a single file in memory and runs it, which JDK 11 introduced (JEP 330) and which is the quickest way to practise.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class CollectionsTour {
    public static void main(String[] args) {
        // ArrayDeque is the stack and the queue: push/pop at the front, offer/poll for first in, first out.
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        Deque<Integer> queue = new ArrayDeque<>(List.of(1, 2, 3));
        queue.offer(4);
        System.out.println("stack pops " + stack.pop() + ", queue polls " + queue.poll());

        // PriorityQueue gives the least element first; reverseOrder() turns it around.
        PriorityQueue<Integer> least = new PriorityQueue<>(List.of(40, 75, 62, 90));
        PriorityQueue<Integer> greatest = new PriorityQueue<>(Comparator.reverseOrder());
        greatest.addAll(List.of(40, 75, 62, 90));
        System.out.println("least " + least.poll() + ", greatest " + greatest.poll());

        // TreeMap answers "the nearest key below or above" in O(log n).
        TreeMap<Integer, String> slots = new TreeMap<>(Map.of(9, "standup", 11, "review", 14, "demo"));
        System.out.println("at or before 12: " + slots.floorKey(12) + ", at or after 12: " + slots.ceilingKey(12)
                + ", after 14: " + slots.higherKey(14));

        // merge() counts in one call; the map here is a TreeMap only so the printed order is fixed.
        Map<String, Integer> counts = new TreeMap<>();
        for (String w : "pear fig pear apple fig pear".split(" ")) counts.merge(w, 1, Integer::sum);
        System.out.println(counts);

        // Java 21's sequenced collections: getFirst, getLast and reversed on lists and deques.
        List<Integer> days = new ArrayList<>(List.of(3, 8, 12));
        System.out.println("first " + days.getFirst() + ", last " + days.getLast() + ", reversed " + days.reversed());

        // LinkedHashMap in access order with removeEldestEntry is a ready LRU cache.
        Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > 2;
            }
        };
        lru.put("a", 1);
        lru.put("b", 2);
        lru.get("a");
        lru.put("c", 3);
        System.out.println("LRU keeps " + lru.keySet());

        // getOrDefault and a plain HashMap for lookups whose order does not matter.
        Map<Character, Integer> seen = new HashMap<>();
        System.out.println("missing key: " + seen.getOrDefault('z', 0));
    }
}

"""Runs shell commands as you would type them in a terminal, and prints the session.

Each line of the script is one command. The session shows it after "$ ", then what it printed (standard output and
standard error together, as a terminal shows them), and, when the command fails, its exit status. The JDK's commands
come first on PATH, so `java` and `javac` are the JDK named in the lesson.
"""

import os
import subprocess

JDK_BIN = "/opt/homebrew/opt/openjdk/bin"


def run(script: str) -> None:
    env = dict(os.environ)
    env["PATH"] = os.pathsep.join([JDK_BIN, env.get("PATH", "")])
    for command in script.strip().splitlines():
        command = command.strip()
        if not command:
            continue
        print(f"$ {command}")
        result = subprocess.run(command, shell=True, env=env, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)
        print(result.stdout, end="")
        if result.returncode != 0:
            print(f"[exit status {result.returncode}]")

from session import run

# java <file>.java compiles the file in memory and runs it (the source launcher), one program per command.
run("""
java CollectionsTour.java
""")

$ java CollectionsTour.java
stack pops 3, queue polls 1
least 40, greatest 90
at or before 12: 11, at or after 12: 14, after 14: null
{apple=1, fig=2, pear=3}
first 3, last 12, reversed [12, 8, 3]
LRU keeps [a, c]
missing key: 0

• ArrayDeque serves as both stack and queue. Its Javadoc expects it to beat Stack for stack work and LinkedList for queue work, and the page of Stack points readers to Deque instead. push and pop work at the front, offer and poll give first-in, first-out order.
• PriorityQueue returns the least element first. Comparator.reverseOrder() makes it return the greatest.
• TreeMap keeps keys sorted, with a guaranteed O(log n) cost, and answers “the nearest key at or below 12” (floorKey) and “at or above” (ceilingKey) directly; higherKey(14) returns null because no key is above 14. Problems about bookings, intervals and “the closest smaller value” are short with it.
• merge(word, 1, Integer::sum) counts in one call on any map. The tour uses a TreeMap only so that the printed order is the same on every run; a HashMap makes no promise about its order.
• LinkedHashMap in access order with removeEldestEntry is a ready LRU cache: after get("a"), adding c evicted b, the least recently used key. Its documentation describes exactly this use.

Java 21 added sequenced collections (JEP 431), so lists and deques have getFirst, getLast and reversed. They replace list.get(list.size() - 1), but only where the platform runs Java 21 or later. The documented cost of each operation is listed in the DSA toolkit lesson.

Comparators that overflow

Sorting in descending order with (a, b) -> b - a works on small numbers and fails on large ones, because the subtraction is int arithmetic and can wrap around.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class ComparatorOverflow {
    public static void main(String[] args) {
        List<Integer> values = List.of(5, Integer.MIN_VALUE, 100, -3, Integer.MAX_VALUE);

        // b - a overflows when the values are far apart: MIN_VALUE - 5 wraps to a large positive number.
        List<Integer> bySubtraction = new ArrayList<>(values);
        bySubtraction.sort((a, b) -> b - a);
        System.out.println("b - a:            " + bySubtraction);

        // Integer.compare never overflows.
        List<Integer> byCompare = new ArrayList<>(values);
        byCompare.sort((a, b) -> Integer.compare(b, a));
        System.out.println("Integer.compare:  " + byCompare);

        List<Integer> byReverse = new ArrayList<>(values);
        byReverse.sort(Comparator.reverseOrder());
        System.out.println("reverseOrder():   " + byReverse);
    }
}

import java.util.HashMap;
import java.util.Map;

public class BoxedEquality {
    public static void main(String[] args) {
        // == on Integer objects compares references. Small values come from a shared cache, large ones may not.
        Integer a = 127, b = 127;
        Integer c = 128, d = 128;
        System.out.println("127 == 127: " + (a == b) + ", 128 == 128: " + (c == d) + ", 128 equals 128: " + c.equals(d));

        // The same trap hides in map lookups: get() returns an Integer.
        Map<String, Integer> votes = new HashMap<>();
        votes.put("asha", 500);
        votes.put("ravi", 500);
        System.out.println("tie by ==: " + (votes.get("asha") == votes.get("ravi"))
                + ", tie by equals: " + votes.get("asha").equals(votes.get("ravi"))
                + ", tie by intValue: " + (votes.get("asha").intValue() == votes.get("ravi").intValue()));
    }
}

public class IntOverflow {
    public static void main(String[] args) {
        // int arithmetic wraps around silently.
        int big = Integer.MAX_VALUE;
        System.out.println("MAX_VALUE + 1 = " + (big + 1));

        // n * n is computed in int before it is stored in the long.
        int n = 100_000;
        long wrong = n * n;
        long right = (long) n * n;
        System.out.println("n * n = " + wrong + ", (long) n * n = " + right);

        // Math.addExact and multiplyExact throw instead of wrapping.
        try {
            Math.multiplyExact(n, n);
        } catch (ArithmeticException e) {
            System.out.println("multiplyExact: " + e.getMessage());
        }

        // Integer division truncates towards zero; % keeps the sign of the left operand.
        System.out.println("-7 / 2 = " + (-7 / 2) + ", -7 % 3 = " + (-7 % 3) + ", 7 % -3 = " + (7 % -3));
        System.out.println("Math.floorDiv(-7, 2) = " + Math.floorDiv(-7, 2) + ", Math.floorMod(-7, 3) = " + Math.floorMod(-7, 3));

        // The one int that has no positive twin.
        int min = Integer.MIN_VALUE;
        System.out.println("MIN_VALUE / -1 = " + (min / -1) + ", Math.abs(MIN_VALUE) = " + Math.abs(min));

        // A shift uses only the lowest five bits of its distance for an int: 1 << 32 is 1 << 0.
        System.out.println("1 << 31 = " + (1 << 31) + ", 1 << 32 = " + (1 << 32) + ", 1L << 32 = " + (1L << 32));
    }
}

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.List;

public class RemoveWhileIterating {
    public static void main(String[] args) {
        List<Integer> scores = new ArrayList<>(List.of(12, 7, 30, 5, 18));
        try {
            for (Integer s : scores) {
                if (s < 10) scores.remove(s);
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("for-each and remove: ConcurrentModificationException");
        }

        List<Integer> kept = new ArrayList<>(List.of(12, 7, 30, 5, 18));
        kept.removeIf(s -> s < 10);
        System.out.println("removeIf: " + kept);

        // remove(int) removes by index, remove(Object) by value: remove(7) on this list means index 7.
        List<Integer> small = new ArrayList<>(List.of(3, 7, 9));
        small.remove(Integer.valueOf(7));
        System.out.println("remove(Integer.valueOf(7)): " + small);
    }
}

from session import run

run("""
java ComparatorOverflow.java
java BoxedEquality.java
java IntOverflow.java
java RemoveWhileIterating.java
""")

$ java ComparatorOverflow.java
b - a:            [-2147483648, 2147483647, 100, 5, -3]
Integer.compare:  [2147483647, 100, 5, -3, -2147483648]
reverseOrder():   [2147483647, 100, 5, -3, -2147483648]
$ java BoxedEquality.java
127 == 127: true, 128 == 128: false, 128 equals 128: true
tie by ==: false, tie by equals: true, tie by intValue: true
$ java IntOverflow.java
MAX_VALUE + 1 = -2147483648
n * n = 1410065408, (long) n * n = 10000000000
multiplyExact: integer overflow
-7 / 2 = -3, -7 % 3 = -1, 7 % -3 = 1
Math.floorDiv(-7, 2) = -4, Math.floorMod(-7, 3) = 2
MIN_VALUE / -1 = -2147483648, Math.abs(MIN_VALUE) = -2147483648
1 << 31 = -2147483648, 1 << 32 = 1, 1L << 32 = 4294967296
$ java RemoveWhileIterating.java
for-each and remove: ConcurrentModificationException
removeIf: [12, 30, 18]
remove(Integer.valueOf(7)): [3, 9]

The first program’s subtraction comparator put Integer.MIN_VALUE first in a descending sort: comparing it with 5, 5 - MIN_VALUE wraps to a negative number, so the comparator claimed that MIN_VALUE was the larger one. Integer.compare(b, a) compares without subtracting, and Comparator.reverseOrder() says what it means; both sorted correctly. Use one of them, or Comparator.comparingInt(...) and thenComparing(...) for records with several keys.

Integer objects and ==

Collections hold objects, so an int put into a list or a map is boxed into an Integer. == on two Integer values compares references, not numbers. The Java Language Specification guarantees that boxing a value from -128 to 127 always gives the same object, so 127 == 127 is true; outside that range two boxes may be different objects, and here 128 == 128 was false.

The map line shows where this bites in practice: two candidates with 500 votes each are not “tied” when the counts are compared with ==. Compare boxed values with equals, or unbox them first, as intValue() does. A test with small numbers passes either way, which is why the bug survives until a hidden test uses larger counts.

int arithmetic: overflow, division and shifts

An int holds 32 bits, from -2,147,483,648 to 2,147,483,647, and every operation on it keeps only those 32 bits. The third program shows the cases that decide answers:

• Integer.MAX_VALUE + 1 is Integer.MIN_VALUE, with no error.
• n * n with int n = 100_000 gives 1,410,065,408 even when stored in a long, because the multiplication happens in int first. Cast one operand, (long) n * n, to multiply in 64 bits. Math.multiplyExact and addExact throw ArithmeticException instead of wrapping, which is useful while you test.
• / truncates towards zero and % takes the sign of the dividend, so -7 / 2 is -3 and -7 % 3 is -1. For a remainder from 0 to m − 1, use Math.floorMod; Math.floorDiv rounds down like Python’s //.
• Integer.MIN_VALUE has no positive counterpart, so MIN_VALUE / -1 overflows back to MIN_VALUE, and the documentation of Math.abs warns that Math.abs(Integer.MIN_VALUE) is that same negative number.
• A shift of an int uses only the five lowest bits of its distance, so 1 << 32 is 1, not 0. Use 1L << k for masks of 32 bits or more.

Changing a list while you loop over it

The fourth program removes small scores inside a for-each loop. ArrayList’s iterator is fail-fast: once the list changes in a way the iterator did not make, its next step throws ConcurrentModificationException. removeIf does the same job safely in one call. The last line is a separate trap of List<Integer>: remove(7) removes the element at index 7, while remove(Integer.valueOf(7)) removes the value 7.

Fast input and output

A judge measures your whole program, input included. Scanner is convenient, but its documentation describes it as a scanner that parses with regular expressions, which costs time on every number. Reading lines with a BufferedReader and splitting them is several times faster:

import java.util.Scanner;

public class SumScanner {
    public static void main(String[] args) {
        long start = System.nanoTime();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long sum = 0;
        for (int i = 0; i < n; i++) sum += in.nextInt();
        System.out.println("Scanner: sum " + sum + ", " + (System.nanoTime() - start) / 1_000_000 + " ms");
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SumFast {
    public static void main(String[] args) throws IOException {
        long start = System.nanoTime();
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer("");
        int n = -1;
        long sum = 0;
        for (int read = 0; n < 0 || read < n; ) {
            while (!tokens.hasMoreTokens()) tokens = new StringTokenizer(in.readLine());
            int value = Integer.parseInt(tokens.nextToken());
            if (n < 0) n = value;
            else {
                sum += value;
                read++;
            }
        }
        System.out.println("BufferedReader + StringTokenizer: sum " + sum + ", " + (System.nanoTime() - start) / 1_000_000 + " ms");
    }
}

import random

# One million integers between -10^9 and 10^9, ten to a line, after their count: a typical large test input.
random.seed(1)
n = 1_000_000
values = [random.randint(-10**9, 10**9) for _ in range(n)]
with open("numbers.txt", "w") as f:
    f.write(f"{n}\n")
    for i in range(0, n, 10):
        f.write(" ".join(map(str, values[i : i + 10])) + "\n")
print(f"wrote {n} numbers, sum {sum(values)}")

from session import run

run("""
python3 make_numbers.py
java SumScanner.java < numbers.txt
java SumFast.java < numbers.txt
""")

$ python3 make_numbers.py
wrote 1000000 numbers, sum -230773644225
$ java SumScanner.java < numbers.txt
Scanner: sum -230773644225, 1297 ms
$ java SumFast.java < numbers.txt
BufferedReader + StringTokenizer: sum -230773644225, 226 ms

Both programs print the same sum; only the time differs. With a limit of a few seconds for Java (HackerRank’s environment page lists 4 seconds), the difference can decide whether a correct solution passes. The documentation of StringTokenizer calls it a legacy class whose use is discouraged in new code; it is still a common choice for contest input because it is fast, and line.split(" ") or StreamTokenizer are alternatives. For output, collect the lines in a StringBuilder and print once, or use a PrintWriter around System.out and flush it at the end, instead of one System.out.println per line.

Deep recursion: a thread with a bigger stack

A depth-first search on a path-shaped tree of a million nodes recurses a million levels deep, and the main thread’s stack holds far fewer frames.

public class DeepRecursion {
    static int depth = 0;

    static void dive() {
        depth++;
        dive();
    }

    // The length of a path of n nodes, walked recursively (a deep test case of a tree problem).
    static int[] next;

    static int length(int node) {
        return node == -1 ? 0 : 1 + length(next[node]);
    }

    public static void main(String[] args) throws InterruptedException {
        try {
            dive();
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError after about " + Math.round(depth / 1000.0) + " thousand calls");
        }

        int n = 1_000_000;
        next = new int[n];
        for (int i = 0; i < n; i++) next[i] = i + 1 < n ? i + 1 : -1;
        try {
            System.out.println("main thread: " + length(0));
        } catch (StackOverflowError e) {
            System.out.println("main thread: StackOverflowError");
        }

        // A thread of its own with a 512 MB stack runs the same recursion.
        int[] result = new int[1];
        Thread worker = new Thread(null, () -> result[0] = length(0), "deep", 512L * 1024 * 1024);
        worker.start();
        worker.join();
        System.out.println("thread with a 512 MB stack: " + result[0]);
    }
}

from session import run

run("""
java DeepRecursion.java
""")

$ java DeepRecursion.java
StackOverflowError after about 38 thousand calls
main thread: StackOverflowError
thread with a 512 MB stack: 1000000

The trivial function overflowed after some tens of thousands of calls, and the number changes from one run to the next, so never rely on an exact limit. Running the same recursion in a Thread created with a stack size of 512 MB reached a million levels. The documentation of that Thread constructor warns that the stack size is only a suggestion, which some platforms ignore, so the safe habit for very deep inputs is still an iterative version with an explicit ArrayDeque as the stack; the thread is the quick fix when a recursive solution is already written.

Java 21, Java 25 and what a judge runs

Java ships a feature release every six months, and every two years one of them is a long-term support release: Java 21 and Java 25 are, while JDK 27, the current release, is a feature release with six months of updates. Judges move slowly. HackerRank’s execution environment page lists OpenJDK 21.0.4 as the newest Java for its coding questions, so sequenced collections are available there and Java 25 features are not.

The feature most likely to catch you is the compact source file of JEP 512, final in Java 25: a file with a bare void main() and calls such as IO.println, without a class around them. It ran on JDK 27, and compiling the same file for the Java 21 language level failed:

void main() {
    var scores = java.util.List.of(72, 100, 9);
    IO.println("compact source file, Java " + Runtime.version().feature() + ": " + scores.getLast());
}

from session import run

# The same compact source file run on this JDK, then compiled for the Java 21 language level.
run("""
java Compact.java
javac --release 21 -d classes Compact.java
""")

$ java Compact.java
compact source file, Java 27: 9
$ javac --release 21 -d classes Compact.java
Compact.java:1: error: implicitly declared classes are not supported in -source 21
void main() {
^
  (use -source 25 or higher to enable implicitly declared classes)
1 error
[exit status 1]

JDK 21 had only a preview of the feature (JEP 445), switched off unless you ask for it, and the details changed before Java 25. Write a normal class with public static void main(String[] args) whenever you are not sure which Java a platform runs.

Practise: predict Java’s int arithmetic

Java does not run in this site’s browser runner, so the exercise turns the rules of this lesson into Python: write functions that return exactly what Java computes for int operands. The tests use the values that IntOverflow.java printed above, from 100000 * 100000 to 1 << 32.

def to_int(x):
    """The value a Java int holds after storing x: the low 32 bits, read as a signed number."""
    return x


def add(a, b):
    """Java's a + b on two ints."""
    return a + b


def mul(a, b):
    """Java's a * b on two ints."""
    return a * b


def div(a, b):
    """Java's a / b on two ints (b is not 0)."""
    return a // b


def rem(a, b):
    """Java's a % b on two ints (b is not 0)."""
    return a % b


def abs_int(a):
    """Java's Math.abs(a) on an int."""
    return abs(a)


def shift_left(a, n):
    """Java's a << n on an int a, for a distance n from 0 to 100."""
    return a << n

from java_int import abs_int, add, div, mul, rem, shift_left, to_int

MIN = -(2**31)
MAX = 2**31 - 1


def test_to_int_wraps():
    """2 ** 31 becomes MIN_VALUE, 2 ** 32 + 5 becomes 5, and MIN_VALUE - 1 becomes MAX_VALUE"""
    assert to_int(2**31) == MIN
    assert to_int(2**32 + 5) == 5
    assert to_int(MIN - 1) == MAX


def test_to_int_keeps_values_that_fit():
    """values from MIN_VALUE to MAX_VALUE stay as they are"""
    assert [to_int(v) for v in (MIN, -1, 0, 7, MAX)] == [MIN, -1, 0, 7, MAX]


def test_add_overflows():
    """MAX_VALUE + 1 is MIN_VALUE, as IntOverflow.java printed"""
    assert add(MAX, 1) == MIN
    assert add(-5, 3) == -2


def test_mul_overflows():
    """100000 * 100000 is 1410065408 in int arithmetic"""
    assert mul(100_000, 100_000) == 1410065408
    assert mul(-3, 4) == -12


def test_div_truncates_towards_zero():
    """-7 / 2 is -3 and 7 / -2 is -3"""
    assert div(-7, 2) == -3
    assert div(7, -2) == -3
    assert div(7, 2) == 3


def test_div_min_by_minus_one():
    """MIN_VALUE / -1 overflows back to MIN_VALUE"""
    assert div(MIN, -1) == MIN


def test_rem_keeps_the_sign_of_the_dividend():
    """-7 % 3 is -1 and 7 % -3 is 1"""
    assert rem(-7, 3) == -1
    assert rem(7, -3) == 1
    assert rem(7, 3) == 1


def test_rem_min_by_minus_one():
    """MIN_VALUE % -1 is 0"""
    assert rem(MIN, -1) == 0


def test_abs_of_min_value():
    """Math.abs(MIN_VALUE) is MIN_VALUE itself"""
    assert abs_int(MIN) == MIN
    assert abs_int(-5) == 5


def test_shift_left():
    """1 << 31 is MIN_VALUE, 1 << 32 is 1 and 3 << 33 is 6"""
    assert shift_left(1, 31) == MIN
    assert shift_left(1, 32) == 1
    assert shift_left(3, 33) == 6
    assert shift_left(1, 30) == 2**30

Interview questions

Fresher · Why can Integer a = 128, b = 128; a == b be false while a.equals(b) is true?

Integer is an object, and == on two objects asks whether they are the same object, not whether they hold the same number. Autoboxing calls Integer.valueOf, and the Java Language Specification requires that boxing the values from -128 to 127 always returns the same cached objects, so 127 == 127 is true. For 128 the boxes may be two different objects, and on a standard JDK they are, so == is false. equals compares the values and is true. The bug appears in real code when two counts come out of a map or a list, because get returns Integer: compare them with equals, or unbox them to int first, for example by assigning them to int variables.

Key takeaways

• Use ArrayDeque for stacks and queues, PriorityQueue with a comparator for heaps, TreeMap for nearest-key queries and LinkedHashMap in access order for an LRU cache.
• Never subtract in a comparator; use Integer.compare, Comparator.reverseOrder() or comparingInt.
• Compare boxed numbers with equals; == works only by luck below 128.
• Cast to long before multiplying, use floorMod for remainders, and remember that Math.abs(MIN_VALUE) is negative and 1 << 32 is 1.
• Read large input with a BufferedReader and print once from a StringBuilder.
• Check the platform’s Java version: sequenced collections need 21, compact source files need 25.