Practice

Java exercises

Make a change, predict what it will do, and compare the result.

1
Java Basics
Start with a class and main method.
Adapt the lesson example. Change one value or element, predict the result, and explain why it changes.
Review lesson →Open compiler
Show starting example
Java
```
class Main {
  public static void main(String[] args) {
    System.out.println("Hello Programonic");
  }
}
```

Java conditions, arrays, and loops

Count values that satisfy a boundary condition.

Add score 0 and score 100.

Reveal answer and reasoning

The count becomes 3 because only 100 adds another passing score.

Review lesson →Open compiler

Show starting example

Java

class Main {
    public static void main(String[] args) {
        int[] scores = {49, 50, 80};
        int passed = 0;
        for (int score : scores) {
            if (score >= 50) passed++;
        }
        System.out.println(passed);
        if (passed != 2) throw new AssertionError("count");
    }
}

Java methods and exception handling

Separate conversion errors from valid numeric values.

Predict showNumber('-3').

Reveal answer and reasoning

It prints -6 because -3 is valid integer syntax.

Review lesson →Open compiler

Show starting example

Java

class Main {
    static void showNumber(String text) {
        try {
            int value = Integer.parseInt(text);
            System.out.println(value * 2);
        } catch (NumberFormatException error) {
            System.out.println("Invalid integer");
        }
    }
    public static void main(String[] args) {
        showNumber("12");
        showNumber("abc");
    }
}

Java recursion and bounded factorial

Use a base case and validate the representable range.

What happens for factorial(21)?

Reveal answer and reasoning

It throws IllegalArgumentException before attempting the multiplication.

Review lesson →Open compiler

Show starting example

Java

class Main {
    static long factorial(int n) {
        if (n < 0 || n > 20) throw new IllegalArgumentException("use 0 through 20");
        if (n == 0) return 1;
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(factorial(4));
        if (factorial(0) != 1) throw new AssertionError("base");
    }
}

Java variables, types, and casting

Declare typed variables and understand integer division, overflow, and conversions.

What does 10 / 4 print, and what does 10 / 4.0 print?

Reveal answer and reasoning

10 / 4 prints 2 (integer division) and 10 / 4.0 prints 2.5.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    int count = 7;
    long big = 3_000_000_000L;
    double ratio = count / 2;
    double exact = count / 2.0;
    int overflow = Integer.MAX_VALUE + 1;
    char letter = 'A';
    letter += 2;
    boolean flag = count > 5 && big > count;

    System.out.println(ratio + " " + exact);
    System.out.println(overflow);
    System.out.println(letter + " " + (int) letter);
    System.out.println(flag);
    System.out.println((int) 3.99 + " " + Math.round(3.99));
  }
}

Java arrays and strings

Work with fixed-size arrays, common String methods, and the difference between == and equals.

What does "a,b,,".split(",").length return?

Reveal answer and reasoning

2, because split removes trailing empty strings, leaving just a and b.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    int[] scores = {82, 91, 76};
    int sum = 0;
    for (int score : scores) {
      sum += score;
    }
    System.out.println(scores.length + " scores, total " + sum);

    String text = "Programonic";
    System.out.println(text.length() + " " + text.substring(0, 7) + " " + text.indexOf('m'));

    String[] parts = "a,b,,c".split(",");
    System.out.println(parts.length + " " + String.join("-", parts));

    String first = new String("hi");
    String second = "hi";
    System.out.println((first == second) + " " + first.equals(second));

    System.out.println(new StringBuilder(text).reverse());
  }
}

Java method overloading, varargs, and pass by value

Declare several methods with the same name and see what a method can and cannot change.

What does sum() with no arguments return?

Reveal answer and reasoning

0, because the varargs array is empty and the loop adds nothing.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static int sum(int a, int b) {
    return a + b;
  }

  static double sum(double a, double b) {
    return a + b;
  }

  static int sum(int... values) {
    int total = 0;
    for (int v : values) {
      total += v;
    }
    return total;
  }

  static void bump(int x) {
    x++;
  }

  static void bumpAll(int[] values) {
    for (int i = 0; i < values.length; i++) {
      values[i]++;
    }
  }

  public static void main(String[] args) {
    System.out.println(sum(2, 3));
    System.out.println(sum(2.5, 3.0));
    System.out.println(sum(1, 2, 3, 4, 5));

    int n = 10;
    bump(n);
    int[] data = {1, 2, 3};
    bumpAll(data);
    System.out.println(n + " " + data[0] + data[1] + data[2]);
  }
}

Java constructors and encapsulation

Initialize private fields and validate changes through methods.

Call second.increment() twice.

Reveal answer and reasoning

The output becomes 3 and 12.

Review lesson →Open compiler

Show starting example

Java

class Counter {
    private int value;
    Counter(int start) {
        if (start < 0) throw new IllegalArgumentException("negative start");
        value = start;
    }
    void increment() { value++; }
    int getValue() { return value; }
}
class Main {
    public static void main(String[] args) {
        Counter first = new Counter(2);
        Counter second = new Counter(10);
        first.increment();
        System.out.println(first.getValue());
        System.out.println(second.getValue());
    }
}

Java inheritance and method overriding

Use a superclass reference to call subclass behavior.

Add Bird extends Animal with speak returning chirp.

Reveal answer and reasoning

Adding new Bird() to the array makes the loop print chirp as another line.

Review lesson →Open compiler

Show starting example

Java

class Animal {
    String speak() { return "sound"; }
}
class Dog extends Animal {
    @Override String speak() { return "woof"; }
}
class Cat extends Animal {
    @Override String speak() { return "meow"; }
}
class Main {
    public static void main(String[] args) {
        Animal[] animals = {new Dog(), new Cat()};
        for (Animal animal : animals) {
            System.out.println(animal.speak());
        }
    }
}

Java interfaces and composition

Depend on a contract and inject a collaborating object.

Implement a formatter that adds parentheses.

Reveal answer and reasoning

Return '(' + text + ')' as a string expression. Inject it to produce (Ready).

Review lesson →Open compiler

Show starting example

Java

interface Formatter {
    String format(String text);
}
class BracketFormatter implements Formatter {
    public String format(String text) { return "[" + text + "]"; }
}
class Report {
    private final Formatter formatter;
    Report(Formatter formatter) { this.formatter = formatter; }
    String render() { return formatter.format("Ready"); }
}
class Main {
    public static void main(String[] args) {
        Report report = new Report(new BracketFormatter());
        System.out.println(report.render());
    }
}

Java abstract classes and enums

Define a shared base with an abstract method, and a fixed set of constants with fields.

Add a Triangle shape.

Reveal answer and reasoning

Create a class Triangle extends Shape with base and height fields and area() returning 0.5 * base * height; no existing code changes.

Review lesson →Open compiler

Show starting example

Java

import java.util.Locale;

class Main {
  static abstract class Shape {
    abstract double area();

    String describe() {
      return getClass().getSimpleName() + " area " + String.format(Locale.ROOT, "%.2f", area());
    }
  }

  static class Circle extends Shape {
    private final double radius;

    Circle(double radius) {
      this.radius = radius;
    }

    double area() {
      return Math.PI * radius * radius;
    }
  }

  static class Rect extends Shape {
    private final double width;
    private final double height;

    Rect(double width, double height) {
      this.width = width;
      this.height = height;
    }

    double area() {
      return width * height;
    }
  }

  enum Level {
    LOW(1), MEDIUM(5), HIGH(10);

    private final int weight;

    Level(int weight) {
      this.weight = weight;
    }

    int weight() {
      return weight;
    }
  }

  public static void main(String[] args) {
    Shape[] shapes = {new Circle(1.5), new Rect(2, 3.5)};
    for (Shape shape : shapes) {
      System.out.println(shape.describe());
    }
    for (Level level : Level.values()) {
      System.out.println(level + " " + level.weight());
    }
  }
}

Java generics and bounded types

Write one class and one method that work for many types while the compiler checks them.

Why not use a List of Object and cast?

Reveal answer and reasoning

Casts can fail at run time with a ClassCastException, while generics let the compiler catch the mistake before the program runs.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static class Box<T> {
    private final T value;

    Box(T value) {
      this.value = value;
    }

    T get() {
      return value;
    }
  }

  static <T extends Comparable<T>> T largest(List<T> items) {
    T best = items.get(0);
    for (T item : items) {
      if (item.compareTo(best) > 0) {
        best = item;
      }
    }
    return best;
  }

  public static void main(String[] args) {
    Box<String> name = new Box<>("Ada");
    Box<Integer> age = new Box<>(36);
    String upper = name.get().toUpperCase();
    int next = age.get() + 1;
    System.out.println(upper + " " + next);

    System.out.println(largest(Arrays.asList(3, 9, 4)));
    System.out.println(largest(Arrays.asList("pear", "apple", "zebra", "mango")));
  }
}

Java equals, hashCode, and toString

Define when two objects are equal so that they work correctly in sets and maps.

What would the set size be without the hashCode override?

Reveal answer and reasoning

Probably 3, because a and b would usually have different identity hash codes and land in different buckets, so both would be kept.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static class Point {
    private final int x;
    private final int y;

    Point(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public boolean equals(Object other) {
      if (this == other) {
        return true;
      }
      if (!(other instanceof Point)) {
        return false;
      }
      Point p = (Point) other;
      return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x, y);
    }

    @Override
    public String toString() {
      return "(" + x + "," + y + ")";
    }
  }

  public static void main(String[] args) {
    Point a = new Point(1, 2);
    Point b = new Point(1, 2);
    System.out.println((a == b) + " " + a.equals(b));

    Set<Point> seen = new HashSet<>();
    seen.add(a);
    seen.add(b);
    seen.add(new Point(3, 4));
    System.out.println(seen.size() + " " + seen.contains(new Point(3, 4)));
    System.out.println(a + " " + (a.hashCode() == b.hashCode()));
  }
}

Java ArrayList and generics

Use a resizable, type-checked sequence.

Call values.remove(Integer.valueOf(99)).

Reveal answer and reasoning

It returns false and leaves the list unchanged because 99 is absent.

Review lesson →Open compiler

Show starting example

Java

import java.util.ArrayList;
import java.util.Arrays;
class Main {
    public static void main(String[] args) {
        ArrayList<Integer> values = new ArrayList<>(Arrays.asList(10, 20, 30));
        values.remove(1);
        values.add(40);
        values.remove(Integer.valueOf(10));
        System.out.println(values);
        if (values.size() != 2) throw new AssertionError("size");
    }
}

Java binary search and interval bounds

Implement logarithmic search on an ascending array.

Search for 1 in [2,4,6,8,10].

Reveal answer and reasoning

The interval moves left until empty and returns -1.

Review lesson →Open compiler

Show starting example

Java

class Main {
    static int search(int[] values, int target) {
        int low = 0, high = values.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (values[mid] == target) return mid;
            if (values[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(search(new int[]{2, 4, 6, 8, 10}, 8));
        System.out.println(search(new int[]{}, 8));
        if (search(new int[]{2, 4}, 3) != -1) throw new AssertionError("missing");
    }
}

Java stacks and balanced brackets

Use a stack to check that brackets are properly nested.

What happens for the input "{[}]"?

Reveal answer and reasoning

It returns false: when } arrives the top of the stack is [, which is not its match.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static boolean balanced(String text) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : text.toCharArray()) {
      if (ch == '(' || ch == '[' || ch == '{') {
        stack.push(ch);
      } else if (ch == ')' || ch == ']' || ch == '}') {
        if (stack.isEmpty()) {
          return false;
        }
        char open = stack.pop();
        if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) {
          return false;
        }
      }
    }
    return stack.isEmpty();
  }

  public static void main(String[] args) {
    String[] tests = {"(a[b]{c})", "(]", "((", ")(", ""};
    for (String test : tests) {
      System.out.println("'" + test + "' -> " + balanced(test));
    }
  }
}

Java ArrayDeque as a queue

Choose queue operations with explicit empty-queue behavior.

Use peek before the first poll. Does it remove build?

Reveal answer and reasoning

No. peek reads the head without removal, so the following poll still returns build.

Review lesson →Open compiler

Show starting example

Java

import java.util.ArrayDeque;
import java.util.Queue;
class Main {
    public static void main(String[] args) {
        Queue<String> jobs = new ArrayDeque<>();
        jobs.offer("build");
        jobs.offer("test");
        System.out.println(jobs.poll());
        System.out.println(jobs.poll());
        System.out.println(jobs.poll());
    }
}

Java maps, sets, and duplicate counting

Track counts and distinct values with separate collection roles.

Add another blue token.

Reveal answer and reasoning

The map becomes {blue=2, red=2}; the distinct count remains 2.

Review lesson →Open compiler

Show starting example

Java

import java.util.Map;
import java.util.TreeMap;
import java.util.Set;
import java.util.TreeSet;
class Main {
    public static void main(String[] args) {
        Map<String, Integer> counts = new TreeMap<>();
        Set<String> unique = new TreeSet<>();
        for (String word : new String[]{"red", "blue", "red"}) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
            unique.add(word);
        }
        System.out.println(counts);
        System.out.println(unique.size());
    }
}

Java singly linked lists

Build a list of nodes by hand, insert at the front and the back, and reverse it.

How would you add a tail reference to make addLast O(1)?

Reveal answer and reasoning

Keep a Node tail field; addLast sets tail.next = node and tail = node, with a special case for an empty list.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static class Node {
    int value;
    Node next;

    Node(int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }

  static Node head = null;

  static void addFirst(int value) {
    head = new Node(value, head);
  }

  static void addLast(int value) {
    Node node = new Node(value, null);
    if (head == null) {
      head = node;
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }

  static void reverse() {
    Node previous = null;
    Node current = head;
    while (current != null) {
      Node next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    head = previous;
  }

  static String show() {
    StringBuilder sb = new StringBuilder();
    for (Node n = head; n != null; n = n.next) {
      sb.append(n.value).append(n.next == null ? "" : " -> ");
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    addFirst(2);
    addFirst(1);
    addLast(3);
    addLast(4);
    System.out.println(show());
    reverse();
    System.out.println(show());
  }
}

Java binary search trees

Insert values into a tree that keeps smaller values on the left, and traverse it in sorted order.

In which order does a pre-order traversal visit the first tree?

Reveal answer and reasoning

50, 30, 20, 40, 70, 60, 80: the node first, then the left subtree, then the right subtree.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
      this.value = value;
    }
  }

  static Node insert(Node root, int value) {
    if (root == null) {
      return new Node(value);
    }
    if (value < root.value) {
      root.left = insert(root.left, value);
    } else if (value > root.value) {
      root.right = insert(root.right, value);
    }
    return root;
  }

  static boolean contains(Node root, int value) {
    while (root != null) {
      if (value == root.value) {
        return true;
      }
      root = value < root.value ? root.left : root.right;
    }
    return false;
  }

  static void inOrder(Node root, List<Integer> out) {
    if (root == null) {
      return;
    }
    inOrder(root.left, out);
    out.add(root.value);
    inOrder(root.right, out);
  }

  static int height(Node root) {
    return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));
  }

  public static void main(String[] args) {
    Node root = null;
    for (int v : new int[] {50, 30, 70, 20, 40, 60, 80, 40}) {
      root = insert(root, v);
    }
    List<Integer> sorted = new ArrayList<>();
    inOrder(root, sorted);
    System.out.println(sorted);
    System.out.println(contains(root, 60) + " " + contains(root, 65));
    System.out.println("height " + height(root));

    Node chain = null;
    for (int v = 1; v <= 7; v++) {
      chain = insert(chain, v);
    }
    System.out.println("height of the chain " + height(chain));
  }
}

Java sorting: insertion sort, merge sort, and comparators

Implement two sorts by hand and sort objects with a Comparator.

Which sort would you use for 10 nearly sorted items, and which for a million random items?

Reveal answer and reasoning

Insertion sort for the small nearly sorted list, because it is close to linear there. Merge sort (or the library's TimSort) for the million items.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
      int key = a[i];
      int j = i - 1;
      while (j >= 0 && a[j] > key) {
        a[j + 1] = a[j];
        j--;
      }
      a[j + 1] = key;
    }
  }

  static int[] mergeSort(int[] a) {
    if (a.length <= 1) {
      return a;
    }
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, a.length / 2));
    int[] right = mergeSort(Arrays.copyOfRange(a, a.length / 2, a.length));
    int[] merged = new int[a.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
      merged[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    while (i < left.length) {
      merged[k++] = left[i++];
    }
    while (j < right.length) {
      merged[k++] = right[j++];
    }
    return merged;
  }

  public static void main(String[] args) {
    int[] data = {5, 2, 9, 1, 5, 6};
    int[] copy = data.clone();
    insertionSort(copy);
    System.out.println(Arrays.toString(copy));
    System.out.println(Arrays.toString(mergeSort(data)));

    List<String> words = new ArrayList<>(List.of("pear", "fig", "apple", "kiwi", "plum"));
    words.sort(Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));
    System.out.println(words);
  }
}

Java priority queues and heaps

Always remove the smallest (or largest) item, and find the k largest values.

What does poll() return when the queue is empty?

Reveal answer and reasoning

null. Unlike remove(), which throws NoSuchElementException, poll returns null for an empty queue.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int v : new int[] {5, 1, 8, 3, 9, 2}) {
      minHeap.offer(v);
    }
    StringBuilder order = new StringBuilder();
    while (!minHeap.isEmpty()) {
      order.append(minHeap.poll()).append(' ');
    }
    System.out.println(order.toString().trim());

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    maxHeap.addAll(List.of(5, 1, 8, 3));
    System.out.println("largest " + maxHeap.peek());

    int k = 3;
    PriorityQueue<Integer> top = new PriorityQueue<>();
    for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) {
      top.offer(v);
      if (top.size() > k) {
        top.poll();
      }
    }
    List<Integer> result = new ArrayList<>(top);
    Collections.sort(result, Collections.reverseOrder());
    System.out.println("top " + k + ": " + result);
  }
}

Java: counting operations to see growth rates

Count loop iterations instead of timing them to compare linear, quadratic, and logarithmic growth.

Predict the three counts for n = 64.

Reveal answer and reasoning

linear = 64, quadratic = 4096, and log = 6, because 64 halves six times to reach 1.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static long[] count(int n) {
    long linear = 0, quadratic = 0, logarithmic = 0;
    for (int i = 0; i < n; i++) {
      linear++;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        quadratic++;
      }
    }
    for (int k = n; k > 1; k /= 2) {
      logarithmic++;
    }
    return new long[] {linear, quadratic, logarithmic};
  }

  public static void main(String[] args) {
    for (int n : new int[] {8, 16, 32}) {
      long[] c = count(n);
      System.out.println("n=" + n + " linear=" + c[0] + " quadratic=" + c[1] + " log=" + c[2]);
    }
  }
}

Java: amortized cost of a growing array

Show that doubling a backing array makes append cost O(1) on average even though some appends copy everything.

How many copies are needed for 32 appends?

Reveal answer and reasoning

31 copies (1 + 2 + 4 + 8 + 16), which is again less than the number of appends.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static class IntList {
    private int[] data = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int value) {
      if (size == data.length) {
        int[] bigger = new int[data.length * 2];
        for (int i = 0; i < size; i++) {
          bigger[i] = data[i];
          copies++;
        }
        data = bigger;
      }
      data[size++] = value;
    }
  }

  public static void main(String[] args) {
    IntList list = new IntList();
    for (int i = 1; i <= 16; i++) {
      list.add(i);
    }
    System.out.println("appends=16 copies=" + list.copies);
    System.out.println("copies per append=" + (double) list.copies / 16);
  }
}

Java: a hash join and why it beats a nested loop

Join two collections by building a hash table on one side and probing it with the other.

What changes if department 3 is added to the table?

Reveal answer and reasoning

Di would also be printed as 'Di -> ...' and all four employees would join.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static class Employee {
    final String name;
    final int deptId;

    Employee(String name, int deptId) {
      this.name = name;
      this.deptId = deptId;
    }
  }

  public static void main(String[] args) {
    Map<Integer, String> departments = new HashMap<>();
    departments.put(1, "Eng");
    departments.put(2, "Ops");

    List<Employee> staff = List.of(
        new Employee("Ada", 1), new Employee("Bo", 2),
        new Employee("Cy", 1), new Employee("Di", 3));

    int probes = 0;
    for (Employee e : staff) {
      probes++;
      String title = departments.get(e.deptId);
      if (title != null) {
        System.out.println(e.name + " -> " + title);
      }
    }
    System.out.println("probes=" + probes + " nested-loop comparisons=" + staff.size() * departments.size());
  }
}

Java: an ordered index with TreeMap

Use a sorted map the way a database uses an ordered index to answer range and nearest-key queries.

Which keys does byAge.headMap(30) contain?

Reveal answer and reasoning

It holds the keys strictly below 30: {24=Ada, 29=Bo}.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    TreeMap<Integer, String> byAge = new TreeMap<>();
    byAge.put(31, "Cy");
    byAge.put(24, "Ada");
    byAge.put(45, "Di");
    byAge.put(29, "Bo");

    System.out.println(byAge.firstKey() + " " + byAge.lastKey());
    System.out.println(byAge.subMap(25, true, 40, true));
    System.out.println(byAge.floorKey(30) + " " + byAge.ceilingKey(30));
  }
}

Java: simulating round-robin CPU scheduling

Rotate jobs through a ready queue with a fixed time slice and record when each one finishes.

How many slices does the schedule use?

Reveal answer and reasoning

Seven slices: A uses 3, B uses 2, and C uses 2.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    String[] names = {"A", "B", "C"};
    int[] remaining = {5, 3, 4};
    int quantum = 2;
    Deque<Integer> ready = new ArrayDeque<>(List.of(0, 1, 2));
    int clock = 0;
    while (!ready.isEmpty()) {
      int p = ready.pollFirst();
      int run = Math.min(quantum, remaining[p]);
      clock += run;
      remaining[p] -= run;
      System.out.println("t=" + clock + " ran " + names[p] + " for " + run);
      if (remaining[p] > 0) {
        ready.addLast(p);
      } else {
        System.out.println(names[p] + " finished at " + clock);
      }
    }
  }
}

Java: mutual exclusion with synchronized

Protect a shared counter from lost updates when two threads increment it.

What is a lock-free alternative for this counter?

Reveal answer and reasoning

Use java.util.concurrent.atomic.AtomicInteger and call incrementAndGet(); it makes the update atomic without a synchronized block.

Review lesson →Open compiler

Show starting example

Java

class Main {
  private static int counter = 0;
  private static final Object lock = new Object();

  static void work() {
    for (int i = 0; i < 100000; i++) {
      synchronized (lock) {
        counter++;
      }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread a = new Thread(Main::work);
    Thread b = new Thread(Main::work);
    a.start();
    b.start();
    a.join();
    b.join();
    System.out.println("counter=" + counter);
  }
}

Java: a TCP echo server on the loopback interface

Open a server socket on an ephemeral port and connect to it with a client socket in the same program.

How would the server handle several clients one after another?

Reveal answer and reasoning

Wrap accept and the read/reply code in a loop, or hand each accepted socket to a new thread or an executor.

Review lesson →Open compiler

Show starting example

Java

import java.io.*;
import java.net.*;

class Main {
  public static void main(String[] args) throws Exception {
    try (ServerSocket server = new ServerSocket(0, 1, InetAddress.getLoopbackAddress())) {
      int port = server.getLocalPort();
      Thread serverThread = new Thread(() -> {
        try (Socket client = server.accept();
             BufferedReader in = new BufferedReader(new InputStreamReader(client.getInputStream()));
             PrintWriter out = new PrintWriter(client.getOutputStream(), true)) {
          String line = in.readLine();
          out.println("echo: " + line);
        } catch (IOException e) {
          System.out.println("server error: " + e.getMessage());
        }
      });
      serverThread.start();

      try (Socket socket = new Socket(InetAddress.getLoopbackAddress(), port);
           PrintWriter out = new PrintWriter(socket.getOutputStream(), true);
           BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()))) {
        out.println("hello");
        System.out.println(in.readLine());
      }
      serverThread.join();
    }
  }
}

Java: IPv4 addresses, masks, and CIDR blocks

Compute the network address, broadcast address, and host count of a subnet with bitwise operations.

What are the network address and host count for 10.1.2.200/24?

Reveal answer and reasoning

The network address is 10.1.2.0, the broadcast address is 10.1.2.255, and there are 254 usable hosts.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static int toInt(String ip) {
    int value = 0;
    for (String part : ip.split("\\.")) {
      value = (value << 8) | Integer.parseInt(part);
    }
    return value;
  }

  static String toText(int value) {
    return ((value >>> 24) & 255) + "." + ((value >>> 16) & 255) + "."
        + ((value >>> 8) & 255) + "." + (value & 255);
  }

  public static void main(String[] args) {
    int ip = toInt("192.168.10.77");
    int prefix = 26;
    int mask = prefix == 0 ? 0 : -1 << (32 - prefix);
    int network = ip & mask;
    int broadcast = network | ~mask;
    System.out.println("network   " + toText(network));
    System.out.println("broadcast " + toText(broadcast));
    System.out.println("hosts     " + ((1L << (32 - prefix)) - 2));
  }
}

Java: testing a method with a tiny test runner

Check normal cases, boundaries, and error cases, and report which ones pass.

Add a boundary test for clamp(10, 0, 10).

Reveal answer and reasoning

check("at upper bound", 10, clamp(10, 0, 10)); the value is already equal to the maximum, so it is returned unchanged.

Review lesson →Open compiler

Show starting example

Java

class Main {
  static int clamp(int value, int low, int high) {
    if (low > high) {
      throw new IllegalArgumentException("low > high");
    }
    return Math.max(low, Math.min(high, value));
  }

  static int passed = 0;
  static int failed = 0;

  static void check(String name, int expected, int actual) {
    if (expected == actual) {
      passed++;
      System.out.println("PASS " + name);
    } else {
      failed++;
      System.out.println("FAIL " + name + ": expected " + expected + " but was " + actual);
    }
  }

  public static void main(String[] args) {
    check("inside range", 5, clamp(5, 0, 10));
    check("below range", 0, clamp(-3, 0, 10));
    check("above range", 10, clamp(99, 0, 10));
    try {
      clamp(1, 5, 2);
      failed++;
      System.out.println("FAIL bad bounds: no exception");
    } catch (IllegalArgumentException e) {
      passed++;
      System.out.println("PASS bad bounds throws: " + e.getMessage());
    }
    System.out.println(passed + " passed, " + failed + " failed");
  }
}

Java: strategy and observer with interfaces and lambdas

Swap behavior behind an interface and notify listeners without coupling the sender to them.

Add a Discount that takes a fixed 15 off.

Reveal answer and reasoning

Discount fifteenOff = price -> price - 15; with 100.0 it returns 85.0, and no existing code changes.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;
import java.util.function.*;

class Main {
  interface Discount {
    double apply(double price);
  }

  static class EventBus {
    private final List<Consumer<String>> listeners = new ArrayList<>();

    void subscribe(Consumer<String> listener) {
      listeners.add(listener);
    }

    void publish(String event) {
      for (Consumer<String> listener : listeners) {
        listener.accept(event);
      }
    }
  }

  public static void main(String[] args) {
    Discount none = price -> price;
    Discount tenPercent = price -> price * 0.9;
    Discount[] plans = {none, tenPercent};
    for (int i = 0; i < plans.length; i++) {
      System.out.println("plan " + i + ": " + plans[i].apply(100.0));
    }

    EventBus bus = new EventBus();
    List<String> log = new ArrayList<>();
    bus.subscribe(log::add);
    bus.subscribe(event -> System.out.println("got " + event));
    bus.publish("order_placed");
    System.out.println(log);
  }
}

Java: SHA-256 hashing for integrity

Compute a SHA-256 digest with MessageDigest and see that a tiny change produces a completely different value.

How can you check a downloaded file against a published digest?

Reveal answer and reasoning

Hash the file's bytes with the same algorithm and compare the hex result with the published value; they must match exactly.

Review lesson →Open compiler

Show starting example

Java

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;

class Main {
  static String hex(byte[] bytes) {
    StringBuilder sb = new StringBuilder();
    for (byte b : bytes) {
      sb.append(String.format("%02x", b));
    }
    return sb.toString();
  }

  public static void main(String[] args) throws Exception {
    MessageDigest sha = MessageDigest.getInstance("SHA-256");
    String a = hex(sha.digest("abc".getBytes(StandardCharsets.UTF_8)));
    String b = hex(sha.digest("abd".getBytes(StandardCharsets.UTF_8)));
    System.out.println(a);
    System.out.println(b);
    System.out.println(MessageDigest.isEqual(a.getBytes(StandardCharsets.UTF_8), a.getBytes(StandardCharsets.UTF_8)));
  }
}

Java: storing passwords with a salt and PBKDF2

Derive a password hash with a random salt and many iterations, then verify a login attempt.

Why is a different salt needed for every user?

Reveal answer and reasoning

With a shared salt, two users with the same password would have the same hash and one cracked guess would reveal both. A unique salt forces each hash to be attacked separately.

Review lesson →Open compiler

Show starting example

Java

import java.security.MessageDigest;
import java.security.SecureRandom;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.PBEKeySpec;

class Main {
  static byte[] derive(char[] password, byte[] salt) throws Exception {
    PBEKeySpec spec = new PBEKeySpec(password, salt, 600_000, 256);
    return SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256").generateSecret(spec).getEncoded();
  }

  public static void main(String[] args) throws Exception {
    byte[] salt = new byte[16];
    new SecureRandom().nextBytes(salt);
    byte[] stored = derive("correct horse".toCharArray(), salt);

    byte[] good = derive("correct horse".toCharArray(), salt);
    byte[] bad = derive("wrong guess".toCharArray(), salt);
    System.out.println("hash length: " + stored.length + " bytes");
    System.out.println("right password: " + MessageDigest.isEqual(stored, good));
    System.out.println("wrong password: " + MessageDigest.isEqual(stored, bad));
  }
}

Java: splitting work across a thread pool

Divide a sum into chunks, run them on an ExecutorService, and combine the Future results.

What happens if the pool has one thread?

Reveal answer and reasoning

The tasks run one after another and the answer is identical, so there is no speed-up but no change in correctness.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;
import java.util.concurrent.*;

class Main {
  public static void main(String[] args) throws Exception {
    ExecutorService pool = Executors.newFixedThreadPool(4);
    List<Future<Long>> parts = new ArrayList<>();
    for (int start = 1; start <= 1000; start += 250) {
      final int from = start;
      parts.add(pool.submit(() -> {
        long sum = 0;
        for (int n = from; n < from + 250; n++) {
          sum += (long) n * n;
        }
        return sum;
      }));
    }
    long total = 0;
    for (Future<Long> part : parts) {
      total += part.get();
    }
    pool.shutdown();
    System.out.println("sum of squares 1..1000 = " + total);
  }
}

Java: parallel streams and CompletableFuture

Count items with a parallel stream and combine two asynchronous results.

How would you run the two futures on your own executor?

Reveal answer and reasoning

Pass the executor as a second argument: CompletableFuture.supplyAsync(() -> 40, executor).

Review lesson →Open compiler

Show starting example

Java

import java.util.concurrent.*;
import java.util.stream.*;

class Main {
  public static void main(String[] args) throws Exception {
    long evens = LongStream.rangeClosed(1, 1_000_000).parallel().filter(n -> n % 2 == 0).count();
    System.out.println("evens: " + evens);

    CompletableFuture<Integer> price = CompletableFuture.supplyAsync(() -> 40);
    CompletableFuture<Integer> tax = CompletableFuture.supplyAsync(() -> 2);
    int total = price.thenCombine(tax, Integer::sum).get();
    System.out.println("total: " + total);
  }
}

Java: breadth-first search for a shortest path

Search a grid with a queue to find the fewest moves from the start to the goal around walls.

What does dist[2][3] stay as if the goal is walled in?

Reveal answer and reasoning

It stays -1 because the goal is never reached, which also tells you no path exists.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    String[] grid = {
      "S.#.",
      "..#.",
      "...G",
    };
    int rows = grid.length, cols = grid[0].length();
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) {
      Arrays.fill(row, -1);
    }
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[] {0, 0});
    dist[0][0] = 0;
    int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
      int[] cell = queue.poll();
      for (int[] move : moves) {
        int r = cell[0] + move[0], c = cell[1] + move[1];
        if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r].charAt(c) != '#' && dist[r][c] < 0) {
          dist[r][c] = dist[cell[0]][cell[1]] + 1;
          queue.add(new int[] {r, c});
        }
      }
    }
    System.out.println("shortest path to G: " + dist[2][3]);
  }
}

Java: game-tree search with minimax (negamax)

Search every move in a take-away game to find which positions are winning for the player to move.

Which move should a player make with 6 sticks?

Reveal answer and reasoning

Take 2, leaving 4 sticks, which is a lost position for the opponent.

Review lesson →Open compiler

Show starting example

Java

class Main {
  // Value for the player to move: +1 means a forced win, -1 means a forced loss.
  static int negamax(int sticks) {
    if (sticks == 0) {
      return -1;
    }
    int best = -1;
    for (int take = 1; take <= Math.min(3, sticks); take++) {
      best = Math.max(best, -negamax(sticks - take));
    }
    return best;
  }

  public static void main(String[] args) {
    for (int n = 1; n <= 8; n++) {
      System.out.println("sticks " + n + ": " + (negamax(n) == 1 ? "win" : "lose"));
    }
  }
}

Java: propositional entailment by model checking

Enumerate every truth assignment to decide whether a knowledge base entails a query.

What happens if you remove the fact p from the knowledge base?

Reveal answer and reasoning

More models satisfy the KB, including ones where R is false, so R is no longer entailed.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    boolean entailsR = true;
    boolean entailsNotR = true;
    int models = 0;
    for (int bits = 0; bits < 8; bits++) {
      boolean p = (bits & 1) != 0;
      boolean q = (bits & 2) != 0;
      boolean r = (bits & 4) != 0;
      boolean kb = (!p || q) && (!q || r) && p;
      if (kb) {
        models++;
        if (!r) {
          entailsR = false;
        }
        if (r) {
          entailsNotR = false;
        }
      }
    }
    System.out.println("models of KB: " + models);
    System.out.println("KB entails R: " + entailsR);
    System.out.println("KB entails not R: " + entailsNotR);
  }
}

Java: forward chaining with if-then rules

Repeatedly apply rules whose conditions are known until no new facts can be derived.

What is derived if cold is removed from the starting facts?

Reveal answer and reasoning

Only wet is derived, because ice needs both wet and cold.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static class Rule {
    final List<String> body;
    final String head;

    Rule(List<String> body, String head) {
      this.body = body;
      this.head = head;
    }
  }

  public static void main(String[] args) {
    List<Rule> rules = List.of(
        new Rule(List.of("rain"), "wet"),
        new Rule(List.of("wet", "cold"), "ice"),
        new Rule(List.of("ice"), "slippery"),
        new Rule(List.of("slippery"), "careful"));
    Set<String> known = new LinkedHashSet<>(List.of("rain", "cold"));

    boolean changed = true;
    while (changed) {
      changed = false;
      for (Rule rule : rules) {
        if (known.containsAll(rule.body) && known.add(rule.head)) {
          System.out.println("derived " + rule.head);
          changed = true;
        }
      }
    }
    System.out.println(known);
  }
}

Java: linear regression with gradient descent

Fit a straight line to data by repeatedly stepping the weights against the gradient of the squared error.

What would the weights become if the data were y = 3x?

Reveal answer and reasoning

w would approach 3 and b would approach 0.

Review lesson →Open compiler

Show starting example

Java

import java.util.Locale;

class Main {
  public static void main(String[] args) {
    double[] x = {1, 2, 3, 4};
    double[] y = {3, 5, 7, 9};
    double w = 0, b = 0, rate = 0.05;
    for (int epoch = 0; epoch < 2000; epoch++) {
      double gw = 0, gb = 0;
      for (int i = 0; i < x.length; i++) {
        double error = w * x[i] + b - y[i];
        gw += 2 * error * x[i] / x.length;
        gb += 2 * error / x.length;
      }
      w -= rate * gw;
      b -= rate * gb;
    }
    System.out.printf(Locale.ROOT, "w=%.2f b=%.2f%n", w, b);
    System.out.printf(Locale.ROOT, "prediction for x=5: %.2f%n", w * 5 + b);
  }
}

Java: k-nearest-neighbors classification

Classify a point by letting its k closest training points vote.

Which class wins for (6,5) with k = 3?

Reveal answer and reasoning

B wins: the nearest points are (6,6), (7,6), and (6,7), all labelled B.

Review lesson →Open compiler

Show starting example

Java

import java.util.*;

class Main {
  static double[][] points = {{1, 1}, {1, 2}, {2, 1}, {6, 6}, {7, 6}, {6, 7}};
  static String[] labels = {"A", "A", "A", "B", "B", "B"};

  static double dist(double[] a, double[] b) {
    return Math.hypot(a[0] - b[0], a[1] - b[1]);
  }

  static Map<String, Integer> classify(double[] query, int k) {
    Integer[] order = {0, 1, 2, 3, 4, 5};
    Arrays.sort(order, Comparator.comparingDouble(i -> dist(points[i], query)));
    Map<String, Integer> votes = new TreeMap<>();
    for (int i = 0; i < k; i++) {
      votes.merge(labels[order[i]], 1, Integer::sum);
    }
    return votes;
  }

  public static void main(String[] args) {
    System.out.println("near (5,5): " + classify(new double[] {5, 5}, 3));
    System.out.println("near (2,2): " + classify(new double[] {2, 2}, 3));
    System.out.println("near (3,3) with k=5: " + classify(new double[] {3, 3}, 5));
  }
}

Java: training a perceptron to learn AND

Update the weights of a single neuron with the perceptron rule until it classifies all four inputs correctly.

What would happen if you trained on XOR targets {0, 1, 1, 0}?

Reveal answer and reasoning

The perceptron would never classify all four correctly, because no single line separates the XOR classes.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    int[][] inputs = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
    int[] targets = {0, 0, 0, 1};
    double w1 = 0, w2 = 0, bias = 0, rate = 0.1;

    for (int epoch = 0; epoch < 50; epoch++) {
      for (int i = 0; i < inputs.length; i++) {
        double sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
        int output = sum > 0 ? 1 : 0;
        int error = targets[i] - output;
        w1 += rate * error * inputs[i][0];
        w2 += rate * error * inputs[i][1];
        bias += rate * error;
      }
    }

    for (int[] in : inputs) {
      double sum = w1 * in[0] + w2 * in[1] + bias;
      System.out.println(in[0] + " AND " + in[1] + " = " + (sum > 0 ? 1 : 0));
    }
  }
}

Java: a two-layer network that computes XOR

Combine two hidden neurons so that a network solves the problem a single perceptron cannot.

Why are two hidden neurons needed?

Reveal answer and reasoning

One neuron can draw only one line. Two hidden neurons give two features, OR and AND, and the output combines them with a third line.

Review lesson →Open compiler

Show starting example

Java

import java.util.Locale;

class Main {
  static double sigmoid(double z) {
    return 1.0 / (1.0 + Math.exp(-z));
  }

  public static void main(String[] args) {
    int[][] inputs = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
    for (int[] in : inputs) {
      double or = sigmoid(20 * in[0] + 20 * in[1] - 10);
      double and = sigmoid(20 * in[0] + 20 * in[1] - 30);
      double out = sigmoid(20 * or - 20 * and - 10);
      System.out.printf(Locale.ROOT, "%d XOR %d = %.3f%n", in[0], in[1], out);
    }
  }
}

Java: filtering an image with a convolution kernel

Slide a 3×3 averaging kernel over a small grayscale image to smooth it.

What is out[2][2]?

Reveal answer and reasoning

All nine pixels under that window are 80, so the average is 80.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    int[][] image = {
      {10, 10, 10, 10, 10},
      {10, 10, 10, 10, 10},
      {10, 10, 80, 80, 80},
      {10, 10, 80, 80, 80},
      {10, 10, 80, 80, 80},
    };
    int size = image.length - 2;
    int[][] out = new int[size][size];
    for (int r = 0; r < size; r++) {
      for (int c = 0; c < size; c++) {
        int sum = 0;
        for (int kr = 0; kr < 3; kr++) {
          for (int kc = 0; kc < 3; kc++) {
            sum += image[r + kr][c + kc];
          }
        }
        out[r][c] = sum / 9;
      }
    }
    for (int[] row : out) {
      System.out.println(row[0] + " " + row[1] + " " + row[2]);
    }
  }
}

Java: finding edges with the Sobel operator

Estimate the horizontal intensity change at each pixel and mark strong edges.

Which direction of edge does the transposed kernel detect?

Reveal answer and reasoning

The transposed kernel measures vertical change, so it responds to horizontal edges.

Review lesson →Open compiler

Show starting example

Java

class Main {
  public static void main(String[] args) {
    int[][] image = {
      {0, 0, 100, 100, 100},
      {0, 0, 100, 100, 100},
      {0, 0, 100, 100, 100},
      {0, 0, 100, 100, 100},
      {0, 0, 100, 100, 100},
    };
    int[][] gx = {{-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1}};
    for (int r = 1; r < 4; r++) {
      StringBuilder row = new StringBuilder();
      for (int c = 1; c < 4; c++) {
        int sum = 0;
        for (int kr = 0; kr < 3; kr++) {
          for (int kc = 0; kc < 3; kc++) {
            sum += image[r - 1 + kr][c - 1 + kc] * gx[kr][kc];
          }
        }
        row.append(Math.abs(sum) > 200 ? '#' : '.');
      }
      System.out.println(row);
    }
  }
}

Java Basics

Java conditions, arrays, and loops

Java methods and exception handling

Java recursion and bounded factorial

Java variables, types, and casting

Java arrays and strings

Java method overloading, varargs, and pass by value

Java constructors and encapsulation

Java inheritance and method overriding

Java interfaces and composition

Java abstract classes and enums

Java generics and bounded types

Java equals, hashCode, and toString

Java ArrayList and generics

Java binary search and interval bounds

Java stacks and balanced brackets

Java ArrayDeque as a queue

Java maps, sets, and duplicate counting

Java singly linked lists

Java binary search trees

Java sorting: insertion sort, merge sort, and comparators

Java priority queues and heaps

Java: counting operations to see growth rates

Java: amortized cost of a growing array

Java: a hash join and why it beats a nested loop

Java: an ordered index with TreeMap

Java: simulating round-robin CPU scheduling

Java: mutual exclusion with synchronized

Java: a TCP echo server on the loopback interface

Java: IPv4 addresses, masks, and CIDR blocks

Java: testing a method with a tiny test runner

Java: strategy and observer with interfaces and lambdas

Java: SHA-256 hashing for integrity

Java: storing passwords with a salt and PBKDF2

Java: splitting work across a thread pool

Java: parallel streams and CompletableFuture

Java: breadth-first search for a shortest path

Java: game-tree search with minimax (negamax)

Java: propositional entailment by model checking

Java: forward chaining with if-then rules

Java: linear regression with gradient descent

Java: k-nearest-neighbors classification

Java: training a perceptron to learn AND

Java: a two-layer network that computes XOR

Java: filtering an image with a convolution kernel

Java: finding edges with the Sobel operator