Free Handbook · Every example compiled & verified

Data Structures & Algorithms

Stacks, queues, linked lists, trees, heaps and graphs built by hand in Java, then the java.util classes that replace them, plus searching, sorting and DP.

0 / 142 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Pick a structure from its Big-O cost table instead of defaulting to ArrayList for everything
Build a generic Stack, Queue, LinkedList, BinarySearchTree and MinHeap by hand, then swap in ArrayDeque, TreeMap and PriorityQueue
Use HashMap and HashSet correctly, including the equals/hashCode contract for your own key types
Traverse a graph with BFS and DFS, and binary-search a sorted array without the classic off-by-one and overflow bugs
Sort with Comparator chains and turn an exponential recursion into linear dynamic programming

The cost table: why the structure matters more than the code

A data structure is a decision about which operations are cheap. ArrayList.get(i) is instant; ArrayList.contains(x) checks every element. HashSet.contains(x) is instant but the set has no order. Picking the structure is usually the whole performance story: the same loop over the wrong structure can be a thousand times slower, and no amount of clever code inside the loop fixes that.

The notation is Big-O: how the work grows as the input size n grows. O(1) means "the same cost no matter how big", O(log n) means "one more step each time n doubles", O(n) means "proportional to n", O(n log n) is what good sorting costs, O(n²) is a loop inside a loop.

Learn this table before the code. Every interview question about "why is this slow" is answered by one row of it.
Structure (java.util)	Get by index / key	Search	Insert	Remove
array / `ArrayList`	O(1)	O(n)	O(1) amortised at end, O(n) in middle	O(1) at end, O(n) in middle
`LinkedList`	O(n)	O(n)	O(1) at either end	O(1) at either end
`ArrayDeque` (stack / queue)	ends only	O(n)	O(1) at either end	O(1) at either end
`HashMap` / `HashSet`	O(1) average	O(1) average by key	O(1) average	O(1) average
`TreeMap` / `TreeSet` (red-black tree)	O(log n)	O(log n)	O(log n)	O(log n)
`PriorityQueue` (binary heap)	O(1) peek at min	O(n)	O(log n)	O(log n) poll
Graph (adjacency list)	-	O(V + E) with BFS / DFS	O(1) add edge	O(degree) remove edge

javaMain.java

public class Main {
    public static void main(String[] args) {
        int n = 1_000_000;
        int[] sorted = new int[n];
        for (int i = 0; i < n; i++) sorted[i] = i * 2;
        int target = 1_999_998;

        int linearSteps = 0;
        for (int x : sorted) {
            linearSteps++;
            if (x == target) break;
        }

        int binarySteps = 0, lo = 0, hi = n - 1;
        while (lo <= hi) {
            binarySteps++;
            int mid = (lo + hi) >>> 1;
            if (sorted[mid] == target) break;
            if (sorted[mid] < target) lo = mid + 1; else hi = mid - 1;
        }
        System.out.println("linear search steps: " + linearSteps);
        System.out.println("binary search steps: " + binarySteps);
    }
}

Outputcompiled & run with real Java

linear search steps: 1000000
binary search steps: 20

O(n) versus O(log n) on a million sorted items: one checks every element, the other halves the range each step. 2 to the 20th is about a million, so 20 steps.

Your turn

Change n to 2,000,000 and predict both numbers before running it. The linear count doubles; the binary count goes up by exactly one.

How this module works

Each lesson builds the structure by hand so you see where the cost comes from, then shows the java.util class you would actually use at work. In an interview you may be asked to build either one, so learn both.

Arrays and ArrayList

A Java array has a fixed length chosen at creation: new int[5] is five ints, forever. ArrayList<E> wraps an array and grows it for you: when the backing array is full, it allocates a new one about 1.5 times bigger and copies everything across. Copying is O(n), but it happens so rarely that adding at the end is O(1) amortised (averaged over many adds).

Inserting or removing in the middle is different: every element after that position has to shift one slot. That is O(n) every time, which is why list.remove(0) in a loop is a classic performance bug.

javaMain.java

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

public class Main {
    public static void main(String[] args) {
        int[] fixed = new int[3];
        fixed[0] = 7;
        System.out.println("array length " + fixed.length + ", last " + fixed[2]);

        List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 40));
        nums.add(50);           // O(1) amortised, at the end
        nums.add(0, 5);         // O(n): every element shifts right
        System.out.println(nums);

        nums.remove(1);                     // removes INDEX 1 (the 10)
        nums.remove(Integer.valueOf(40));   // removes the VALUE 40
        System.out.println(nums + " size " + nums.size());
    }
}

Outputcompiled & run with real Java

array length 3, last 0
[5, 10, 20, 30, 40, 50]
[5, 20, 30, 50] size 4

Unused array slots hold the default value (0 for int, null for objects). remove(int) removes by position; remove(Object) removes by value. With a List<Integer> that difference bites.

Your turn

Call nums.remove(20) on the final list and read the exception. Then fix it to remove the value 20.

remove(int) vs remove(Object)

On a List<Integer>, list.remove(1) picks the remove(int index) overload because 1 is already an int and needs no boxing. To remove the value, box it: list.remove(Integer.valueOf(1)). This is a real interview trick question.

HashMap and HashSet

A HashMap turns a key into a bucket number with key.hashCode(), then uses equals to find the exact key inside that bucket. That is why lookups are O(1) on average: no scanning, just jump to the bucket. HashSet is a HashMap with only keys.

Two practical rules. First, iteration order of a HashMap is not something to rely on: when you need sorted keys use TreeMap, when you need insertion order use LinkedHashMap. Second, a class used as a key must override both equals and hashCode consistently. A record does that for you.

javaMain.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String text = "the cat and the hat and the bat";
        Map<String, Integer> counts = new TreeMap<>();   // sorted keys for printing
        for (String word : text.split(" ")) {
            counts.merge(word, 1, Integer::sum);
        }
        System.out.println(counts);

        Set<String> seen = new HashSet<>();
        List<String> dupes = new ArrayList<>();
        for (String word : text.split(" ")) {
            if (!seen.add(word)) dupes.add(word);   // add returns false if already present
        }
        System.out.println("duplicates in order: " + dupes);
        System.out.println("the -> " + counts.getOrDefault("the", 0) + ", dog -> " + counts.getOrDefault("dog", 0));
    }
}

Outputcompiled & run with real Java

{and=2, bat=1, cat=1, hat=1, the=3}
duplicates in order: [the, and, the]
the -> 3, dog -> 0

merge(key, 1, Integer::sum) is the idiomatic counter: insert 1, or add 1 to what is there. Set.add returning false is a free "have I seen this?" check.

Your turn

Swap TreeMap for LinkedHashMap and predict the new print order.

javaMain.java

import java.util.*;

public class Main {
    static class PointNoHash {
        final int x, y;
        PointNoHash(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof PointNoHash p && p.x == x && p.y == y;
        }
        // hashCode NOT overridden: equal objects land in different buckets
    }

    record Point(int x, int y) {}   // records generate equals AND hashCode

    public static void main(String[] args) {
        Set<PointNoHash> broken = new HashSet<>();
        broken.add(new PointNoHash(1, 2));
        System.out.println("broken contains (1,2)? " + broken.contains(new PointNoHash(1, 2)));

        Set<Point> fixed = new HashSet<>();
        fixed.add(new Point(1, 2));
        System.out.println("record contains (1,2)? " + fixed.contains(new Point(1, 2)));
    }
}

Outputcompiled & run with real Java

broken contains (1,2)? false
record contains (1,2)? true

Override equals without hashCode and the set looks in the wrong bucket, so an equal key is "missing". This is the most asked HashMap question in Java interviews.

Stack: last in, first out

A stack adds and removes at the same end: push on top, pop from the top. Undo history, the call stack, matching brackets and depth-first search are all stacks. Built by hand, it is an array plus a size counter, growing the array when full.

javaMain.java

import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
    static class Stack<T> {
        private Object[] items = new Object[2];
        private int size = 0;

        void push(T value) {
            if (size == items.length) items = Arrays.copyOf(items, size * 2);
            items[size++] = value;
        }

        @SuppressWarnings("unchecked")
        T pop() {
            if (size == 0) throw new NoSuchElementException("empty stack");
            T top = (T) items[--size];
            items[size] = null;   // let the GC reclaim it
            return top;
        }

        boolean isEmpty() { return size == 0; }
    }

    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        for (String w : new String[] {"a", "b", "c", "d"}) s.push(w);
        StringBuilder out = new StringBuilder();
        while (!s.isEmpty()) out.append(s.pop());
        System.out.println(out);
    }
}

Outputcompiled & run with real Java

dcba

Generic arrays cannot be created in Java (new T[2] does not compile, because of type erasure), so the stack stores Object[] and casts on the way out. ArrayList does exactly the same internally.

In real code, use ArrayDeque as a stack. The old java.util.Stack class extends Vector, synchronises every call, and is kept only for backwards compatibility.

javaMain.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class Main {
    static boolean balanced(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
            }
        }
        return stack.isEmpty();
    }

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

Outputcompiled & run with real Java

([]{}) -> true
([)] -> false
(( -> false
a(b)c -> true

Your turn

Make balanced return the index of the first bad character instead of false, or -1 when the string is balanced.

Visualizebalanced("([)]") step by stepStep 1 / 7

1for (char c : s.toCharArray()) {
2    if (c == '(' || c == '[' || c == '{') stack.push(c);
3    else if (pairs.containsKey(c)) {
4        if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
5    }
6}
7return stack.isEmpty();

Line 1

First character is (.

Variables now

`c`	`'('`
`stack`	`[]`

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	First character is `(`.	`c = '('` `stack = []`
2	2	An opener, so push it.	`stack = [(]`
3	1	Next character is `[`.	`c = '['`
4	2	Another opener, pushed on top.	`stack = [[, (]`
5	1	Next character is `)`.	`c = ')'`
6	3	A closer: look up its partner, `(`.
7	4	Pop gives `[`, which is not `(`: the brackets cross, so return false.	`stack = [(]`

Queue and Deque: first in, first out

A queue adds at the back and removes from the front: print jobs, request buffers, breadth-first search. Built on a plain array, removing from the front would shift everything (O(n)). The trick is a circular buffer: keep a head index and wrap around with %, so both ends are O(1).

javaMain.java

public class Main {
    static class RingQueue {
        private final int[] items;
        private int head = 0, size = 0;

        RingQueue(int capacity) { items = new int[capacity]; }

        boolean offer(int value) {
            if (size == items.length) return false;          // full
            items[(head + size) % items.length] = value;
            size++;
            return true;
        }

        int poll() {
            int value = items[head];
            head = (head + 1) % items.length;
            size--;
            return value;
        }
    }

    public static void main(String[] args) {
        RingQueue q = new RingQueue(3);
        q.offer(1); q.offer(2); q.offer(3);
        System.out.println("offer 4 when full: " + q.offer(4));
        System.out.println("poll " + q.poll() + ", poll " + q.poll());
        q.offer(4); q.offer(5);                               // wraps around to slots 0 and 1
        StringBuilder rest = new StringBuilder();
        while (q.size > 0) rest.append(q.poll()).append(' ');
        System.out.println("rest: " + rest.toString().trim());
    }
}

Outputcompiled & run with real Java

offer 4 when full: false
poll 1, poll 2
rest: 3 4 5

The array never shifts. head moves forward and wraps with % capacity; new items go at (head + size) % capacity.

In real code, ArrayDeque is that ring buffer, growable, and usable from both ends. Use the Queue methods offer/poll/peek (which return false/null when empty) rather than add/remove/element (which throw).

javaMain.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> jobs = new ArrayDeque<>();
        jobs.offer("print report");
        jobs.offer("send email");
        jobs.offer("resize image");
        System.out.println("next: " + jobs.poll() + ", then: " + jobs.peek());

        Deque<Integer> window = new ArrayDeque<>();
        for (int x = 1; x <= 5; x++) {
            window.offerLast(x);
            if (window.size() > 3) window.pollFirst();   // keep the last 3 only
        }
        System.out.println("last three: " + window);
        System.out.println("poll on empty: " + new ArrayDeque<String>().poll());
    }
}

Outputcompiled & run with real Java

next: print report, then: send email
last three: [3, 4, 5]
poll on empty: null

A linked list built by hand

A linked list is a chain of nodes, each holding a value and a reference to the next node. Adding at the head is O(1) (no shifting), but reaching element i means walking i links (O(n)). Interviewers love it because every operation is pointer juggling.

javaMain.java

public class Main {
    static class Node<T> {
        T value;
        Node<T> next;
        Node(T value, Node<T> next) { this.value = value; this.next = next; }
    }

    static <T> Node<T> reverse(Node<T> head) {
        Node<T> prev = null, cur = head;
        while (cur != null) {
            Node<T> next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

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

    public static void main(String[] args) {
        Node<Integer> head = new Node<>(1, new Node<>(2, new Node<>(3, null)));
        System.out.println(show(head));
        head = reverse(head);
        System.out.println(show(head));
    }
}

Outputcompiled & run with real Java

1 -> 2 -> 3
3 -> 2 -> 1

Your turn

Write middle(head) using two pointers: slow moves one node per step, fast moves two. When fast reaches the end, slow is in the middle.

Visualizereverse(1 -> 2 -> 3)Step 1 / 9

1Node<T> prev = null, cur = head;
2while (cur != null) {
3    Node<T> next = cur.next;
4    cur.next = prev;
5    prev = cur;
6    cur = next;
7}
8return prev;

Line 1

Start: nothing reversed yet.

Variables now

`prev`	`null`
`cur`	`1`

All 9 steps as a table

Step	Line	What happened	Variables now
1	1	Start: nothing reversed yet.	`prev = null` `cur = 1`
2	3	Remember where the rest of the list is before breaking the link.	`next = 2`
3	4	Point node 1 backwards, at null.	`1.next = null`
4	6	Advance both pointers.	`prev = 1` `cur = 2`
5	4	Second pass: node 2 now points at 1.	`next = 3` `2.next = 1`
6	6	Advance.	`prev = 2` `cur = 3`
7	4	Third pass: node 3 points at 2.	`next = null` `3.next = 2`
8	6	Advance; cur is null so the loop ends.	`prev = 3` `cur = null`
9	8	prev is the new head: 3 -> 2 -> 1.

java.util.LinkedList in real code

java.util.LinkedList exists and is doubly linked, but it is rarely the right choice: every node is a separate object scattered in memory, so iterating it is much slower than an ArrayList in practice, and ArrayDeque beats it as a queue. Build linked lists for interviews; reach for ArrayList or ArrayDeque at work.

Recursion and the call stack

A recursive method calls itself on a smaller input until it hits a base case it can answer directly. Each call gets its own frame on the thread's call stack holding its parameters and locals. Forget the base case, or recurse too deep, and the JVM throws StackOverflowError (the default stack fits roughly ten thousand frames of a small method).

javaMain.java

public class Main {
    static long factorial(int n) {
        if (n <= 1) return 1;          // base case
        return n * factorial(n - 1);   // smaller problem
    }

    static int sumDigits(int n) {
        if (n < 10) return n;
        return n % 10 + sumDigits(n / 10);
    }

    static void countdown(int n, String indent) {
        if (n == 0) { System.out.println(indent + "liftoff"); return; }
        System.out.println(indent + "enter " + n);
        countdown(n - 1, indent + "  ");
        System.out.println(indent + "leave " + n);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5) + ", 20! = " + factorial(20));
        System.out.println("sumDigits(9045) = " + sumDigits(9045));
        countdown(2, "");
    }
}

Outputcompiled & run with real Java

5! = 120, 20! = 2432902008176640000
sumDigits(9045) = 18
enter 2
  enter 1
    liftoff
  leave 1
leave 2

The indented countdown shows the call stack: every "enter" is a frame pushed, every "leave" is that frame popped, in reverse order. 20! is the largest factorial that fits in a long.

Visualizefactorial(3)Step 1 / 6

1static long factorial(int n) {
2    if (n <= 1) return 1;
3    return n * factorial(n - 1);
4}

Line 2

factorial(3): n is not 1, so it cannot answer yet.

Variables now

n 3

All 6 steps as a table

Step	Line	What happened	Variables now
1	2	factorial(3): n is not 1, so it cannot answer yet.	`n = 3`
2	3	Pauses and calls factorial(2). Frame for n=3 waits on the stack.	`stack = f(3)`
3	3	factorial(2) also pauses and calls factorial(1).	`n = 2` `stack = f(3), f(2)`
4	2	factorial(1) hits the base case and returns 1.	`n = 1` `stack = f(3), f(2), f(1)`
5	3	Back in f(2): 2 * 1 = 2, returns 2.	`stack = f(3), f(2)`
6	3	Back in f(3): 3 * 2 = 6, returns 6.	`stack = f(3)`

Binary search tree, then TreeMap

A binary search tree keeps every node's left subtree smaller and right subtree larger. Searching walks one path from the root, so it costs the tree's height: O(log n) when balanced, O(n) if you insert sorted data and the tree degenerates into a line. An in-order walk (left, node, right) visits keys in sorted order.

javaMain.java

public class Main {
    static class BST<T extends Comparable<T>> {
        private class Node {
            T key; Node left, right;
            Node(T key) { this.key = key; }
        }
        private Node root;

        void insert(T key) { root = insert(root, key); }
        private Node insert(Node n, T key) {
            if (n == null) return new Node(key);
            int c = key.compareTo(n.key);
            if (c < 0) n.left = insert(n.left, key);
            else if (c > 0) n.right = insert(n.right, key);
            return n;                                   // equal keys are ignored
        }

        boolean contains(T key) {
            Node n = root;
            while (n != null) {
                int c = key.compareTo(n.key);
                if (c == 0) return true;
                n = c < 0 ? n.left : n.right;
            }
            return false;
        }

        void inOrder(Node n, StringBuilder out) {
            if (n == null) return;
            inOrder(n.left, out); out.append(n.key).append(' '); inOrder(n.right, out);
        }
        String sorted() { StringBuilder sb = new StringBuilder(); inOrder(root, sb); return sb.toString().trim(); }
    }

    public static void main(String[] args) {
        BST<Integer> t = new BST<>();
        for (int k : new int[] {50, 30, 70, 20, 40, 60, 80, 30}) t.insert(k);
        System.out.println("in-order: " + t.sorted());
        System.out.println("contains 60? " + t.contains(60) + ", contains 65? " + t.contains(65));
    }
}

Outputcompiled & run with real Java

in-order: 20 30 40 50 60 70 80
contains 60? true, contains 65? false

T extends Comparable<T> is a bounded generic: the tree accepts any type that knows how to compare itself, so compareTo is available.

Your turn

Add height(). Insert 1..7 in order and compare the height with inserting 4, 2, 6, 1, 3, 5, 7.

The standard library's TreeMap and TreeSet are self-balancing (red-black) trees, so they stay O(log n) whatever the insert order, and they add range queries a hash map cannot answer.

javaMain.java

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> grades = new TreeMap<>();
        grades.put(90, "A"); grades.put(80, "B"); grades.put(70, "C"); grades.put(0, "F");

        for (int score : new int[] {95, 83, 70, 42}) {
            System.out.println(score + " -> " + grades.floorEntry(score).getValue());
        }
        System.out.println("first " + grades.firstKey() + ", last " + grades.lastKey());
        System.out.println("scores from 70 to 90: " + grades.subMap(70, true, 90, true).keySet());
    }
}

Outputcompiled & run with real Java

95 -> A
83 -> B
70 -> C
42 -> F
first 0, last 90
scores from 70 to 90: [70, 80, 90]

floorEntry(x) = the greatest key less than or equal to x. Grade bands, price tiers and time-window lookups are all one floorEntry call.

Heap and PriorityQueue

A binary min-heap is a complete binary tree stored in an array, where every parent is smaller than its children. The smallest element is always at index 0. For index i, the children are at 2i+1 and 2i+2 and the parent at (i-1)/2. Adding sifts the new item up; removing the minimum moves the last item to the root and sifts it down. Both are O(log n).

javaMain.java

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

public class Main {
    static class MinHeap {
        private final List<Integer> a = new ArrayList<>();

        void add(int x) {
            a.add(x);
            int i = a.size() - 1;
            while (i > 0 && a.get((i - 1) / 2) > a.get(i)) {      // sift up
                swap(i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }

        int poll() {
            int min = a.get(0);
            int last = a.remove(a.size() - 1);
            if (!a.isEmpty()) {
                a.set(0, last);
                int i = 0;
                while (true) {                                     // sift down
                    int l = 2 * i + 1, r = l + 1, small = i;
                    if (l < a.size() && a.get(l) < a.get(small)) small = l;
                    if (r < a.size() && a.get(r) < a.get(small)) small = r;
                    if (small == i) break;
                    swap(i, small);
                    i = small;
                }
            }
            return min;
        }

        boolean isEmpty() { return a.isEmpty(); }
        private void swap(int i, int j) { int t = a.get(i); a.set(i, a.get(j)); a.set(j, t); }
    }

    public static void main(String[] args) {
        MinHeap h = new MinHeap();
        for (int x : new int[] {42, 7, 19, 3, 25, 11}) h.add(x);
        StringBuilder out = new StringBuilder();
        while (!h.isEmpty()) out.append(h.poll()).append(' ');
        System.out.println(out.toString().trim());
    }
}

Outputcompiled & run with real Java

3 7 11 19 25 42

Polling every element out of a heap returns them sorted: that is heapsort, O(n log n).

PriorityQueue is that heap. It is a min-heap by natural order; pass a Comparator for anything else. Note that printing a PriorityQueue shows the internal array order, not sorted order; only poll() gives sorted output.

javaMain.java

import java.util.*;

public class Main {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed());
        tasks.add(new Task("write tests", 2));
        tasks.add(new Task("fix prod bug", 9));
        tasks.add(new Task("update docs", 1));
        while (!tasks.isEmpty()) System.out.println(tasks.poll().name());

        // top-3 largest with a size-3 MIN heap: O(n log k)
        int[] nums = {5, 1, 9, 3, 7, 8, 2};
        PriorityQueue<Integer> top = new PriorityQueue<>();
        for (int x : nums) {
            top.offer(x);
            if (top.size() > 3) top.poll();    // drop the smallest
        }
        List<Integer> result = new ArrayList<>(top);
        Collections.sort(result, Collections.reverseOrder());
        System.out.println("top 3: " + result);
    }
}

Outputcompiled & run with real Java

fix prod bug
write tests
update docs
top 3: [9, 8, 7]

Your turn

Use the same size-k heap idea to print the 2 most frequent words in a sentence (count with a map first, then keep a heap of map entries).

Graphs: BFS and DFS

A graph is nodes plus edges. The usual representation is an adjacency list: Map<String, List<String>> from each node to its neighbours. Breadth-first search uses a queue and explores in rings of distance, so the first time it reaches a node is along a shortest path (in edges). Depth-first search uses recursion (or a stack) and goes as deep as possible before backing up. Both are O(V + E), and both need a visited set or they loop forever on a cycle.

javaMain.java

import java.util.*;

public class Main {
    static Map<String, List<String>> graph = new LinkedHashMap<>();

    static void edge(String a, String b) {
        graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }

    static Map<String, Integer> bfs(String start) {
        Map<String, Integer> dist = new LinkedHashMap<>();
        Deque<String> queue = new ArrayDeque<>();
        dist.put(start, 0);
        queue.offer(start);
        while (!queue.isEmpty()) {
            String node = queue.poll();
            for (String next : graph.get(node)) {
                if (!dist.containsKey(next)) {           // dist doubles as "visited"
                    dist.put(next, dist.get(node) + 1);
                    queue.offer(next);
                }
            }
        }
        return dist;
    }

    static void dfs(String node, Set<String> visited, List<String> order) {
        if (!visited.add(node)) return;
        order.add(node);
        for (String next : graph.get(node)) dfs(next, visited, order);
    }

    public static void main(String[] args) {
        edge("A", "B"); edge("A", "C"); edge("B", "D"); edge("C", "D"); edge("D", "E");
        System.out.println("BFS distances: " + bfs("A"));
        List<String> order = new ArrayList<>();
        dfs("A", new HashSet<>(), order);
        System.out.println("DFS order: " + order);
    }
}

Outputcompiled & run with real Java

BFS distances: {A=0, B=1, C=1, D=2, E=3}
DFS order: [A, B, D, C, E]

LinkedHashMap keeps insertion order so the output is deterministic. DFS from A goes A, B, D, then from D tries C (unvisited) before E.

Your turn

Record each node's parent during BFS and print the actual shortest path from A to E.

Visualizebfs("A") on A-B, A-C, B-D, C-D, D-EStep 1 / 8

1while (!queue.isEmpty()) {
2    String node = queue.poll();
3    for (String next : graph.get(node)) {
4        if (!dist.containsKey(next)) {
5            dist.put(next, dist.get(node) + 1);
6            queue.offer(next);
7        }
8    }
9}

Line 2

Poll A (distance 0).

Variables now

`queue`	`[]`
`node`	`A`

All 8 steps as a table

Step	Line	What happened	Variables now
1	2	Poll A (distance 0).	`queue = []` `node = A`
2	5	B and C are new: distance 1, both queued.	`queue = [B, C]` `dist = A=0 B=1 C=1`
3	2	Poll B. Its neighbours are A (seen) and D (new).	`queue = [C]` `node = B`
4	5	D gets distance 2.	`queue = [C, D]` `dist = A=0 B=1 C=1 D=2`
5	2	Poll C. A and D are both already seen, nothing added.	`queue = [D]` `node = C`
6	2	Poll D. E is new.	`queue = []` `node = D`
7	5	E gets distance 3.	`queue = [E]` `dist = ... D=2 E=3`
8	2	Poll E: its only neighbour D is seen. Queue empty, loop ends.	`queue = []` `node = E`

Binary search without the bugs

Binary search finds a value in a sorted array by comparing with the middle and discarding half each step: O(log n). It is short, and it is famously easy to get wrong. The three bugs to avoid: using lo < hi when the loop needs lo <= hi, forgetting the +1/-1 so the loop never shrinks, and computing (lo + hi) / 2, which overflows int when both are above about 1.07 billion. Use lo + (hi - lo) / 2 or (lo + hi) >>> 1.

javaMain.java

import java.util.Arrays;

public class Main {
    static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    // first index whose value is >= target (the "lower bound")
    static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] a = {2, 5, 5, 5, 9, 14, 21};
        System.out.println("search 14 -> " + search(a, 14) + ", search 6 -> " + search(a, 6));
        System.out.println("lowerBound 5 -> " + lowerBound(a, 5) + ", lowerBound 6 -> " + lowerBound(a, 6));
        System.out.println("Arrays.binarySearch 21 -> " + Arrays.binarySearch(a, 21));
        System.out.println("Arrays.binarySearch 6 -> " + Arrays.binarySearch(a, 6));
    }
}

Outputcompiled & run with real Java

search 14 -> 5, search 6 -> -1
lowerBound 5 -> 1, lowerBound 6 -> 4
Arrays.binarySearch 21 -> 6
Arrays.binarySearch 6 -> -5

When the key is missing, Arrays.binarySearch returns -(insertionPoint) - 1: 6 would go at index 4, so it returns -5. The lower-bound variant is the one that answers "first time at or after X" questions.

Binary search on the answer

The same loop works on things that are not arrays: "the smallest capacity that ships all packages in D days", "the lowest speed that finishes in time". If a yes/no check is monotonic (false, false, true, true), binary-search the boundary.

Sorting: by hand, then Comparator

Insertion sort (O(n²), fast on tiny or nearly sorted input) and merge sort (O(n log n), stable, divide and conquer) are the two worth writing by hand. Arrays.sort on primitives uses a dual-pivot quicksort; Arrays.sort on objects and List.sort use TimSort, a stable merge-sort hybrid. Stable means equal elements keep their original order, which is what lets you sort by one key and then another.

javaMain.java

import java.util.Arrays;

public class Main {
    static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], 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 mid = a.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
        int[] out = new int[a.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) out[k++] = left[i] <= right[j] ? left[i++] : right[j++];
        while (i < left.length) out[k++] = left[i++];
        while (j < right.length) out[k++] = right[j++];
        return out;
    }

    public static void main(String[] args) {
        int[] a = {29, 3, 17, 8, 3, 41};
        insertionSort(a);
        System.out.println("insertion: " + Arrays.toString(a));
        System.out.println("merge:     " + Arrays.toString(mergeSort(new int[] {29, 3, 17, 8, 3, 41})));
    }
}

Outputcompiled & run with real Java

insertion: [3, 3, 8, 17, 29, 41]
merge:     [3, 3, 8, 17, 29, 41]

left[i] <= right[j] (not <) is what makes merge sort stable: on a tie it takes from the left half first.

javaMain.java

import java.util.*;

public class Main {
    record Employee(String name, String dept, int salary) {}

    public static void main(String[] args) {
        List<Employee> staff = new ArrayList<>(List.of(
            new Employee("Maya", "Eng", 120),
            new Employee("Ravi", "Ops", 90),
            new Employee("Lena", "Eng", 150),
            new Employee("Omar", "Ops", 90),
            new Employee("Iris", "Eng", 120)));

        staff.sort(Comparator.comparing(Employee::dept)
                .thenComparing(Employee::salary, Comparator.reverseOrder())
                .thenComparing(Employee::name));
        staff.forEach(e -> System.out.println(e.dept() + " " + e.salary() + " " + e.name()));
    }
}

Outputcompiled & run with real Java

Eng 150 Lena
Eng 120 Iris
Eng 120 Maya
Ops 90 Omar
Ops 90 Ravi

Department ascending, then salary descending, then name as the tie-breaker. A comparator chain replaces a hand-written compareTo full of if-statements.

Your turn

Sort by salary descending only and check that Maya still comes before Iris (the original order), proving List.sort is stable.

Never write a comparator as a - b

(a, b) -> a - b overflows for large values of opposite sign and silently sorts wrong. Use Integer.compare(a, b) or Comparator.comparingInt.

Dynamic programming

Dynamic programming is recursion that remembers. If a recursive solution solves the same sub-problem many times, store each answer the first time (memoisation, top-down) or fill a table from the smallest case upward (tabulation, bottom-up). Naive Fibonacci makes about 2ⁿ calls; either DP version makes n.

javaMain.java

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

public class Main {
    static long calls = 0;

    static long fibNaive(int n) {
        calls++;
        return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
    }

    static Map<Integer, Long> memo = new HashMap<>();
    static long fibMemo(int n) {
        if (n < 2) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long result = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, result);
        return result;
    }

    static long fibTable(int n) {
        long prev = 0, cur = 1;
        for (int i = 2; i <= n; i++) { long next = prev + cur; prev = cur; cur = next; }
        return n == 0 ? 0 : cur;
    }

    public static void main(String[] args) {
        System.out.println("naive fib(30) = " + fibNaive(30) + " in " + calls + " calls");
        System.out.println("memo  fib(90) = " + fibMemo(90));
        System.out.println("table fib(90) = " + fibTable(90));
    }
}

Outputcompiled & run with real Java

naive fib(30) = 832040 in 2692537 calls
memo  fib(90) = 2880067194370816120
table fib(90) = 2880067194370816120

Naive fib(90) would take longer than a lifetime. Memoised, it is 90 map lookups. The table version keeps only the last two values, so it is O(n) time and O(1) memory.

The classic DP interview problem after Fibonacci is coin change: the fewest coins that make an amount. best[a] is the answer for amount a, built from smaller amounts.

javaMain.java

import java.util.Arrays;

public class Main {
    static int minCoins(int[] coins, int amount) {
        int[] best = new int[amount + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && best[a - c] != Integer.MAX_VALUE) {
                    best[a] = Math.min(best[a], best[a - c] + 1);
                }
            }
        }
        return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];
    }

    public static void main(String[] args) {
        System.out.println("coins {1,5,10,25} for 63: " + minCoins(new int[] {1, 5, 10, 25}, 63));
        System.out.println("coins {1,3,4} for 6: " + minCoins(new int[] {1, 3, 4}, 6));
        System.out.println("coins {5,10} for 3: " + minCoins(new int[] {5, 10}, 3));
    }
}

Outputcompiled & run with real Java

coins {1,5,10,25} for 63: 6
coins {1,3,4} for 6: 2
coins {5,10} for 3: -1

For {1, 3, 4} and 6, greedy "take the biggest coin" gives 4+1+1 (3 coins); DP finds 3+3 (2 coins). That gap is why greedy fails and DP is needed.

Your turn

Change it to count the number of ways to make the amount instead of the fewest coins. (Loop over coins in the outer loop so each combination is counted once.)

Cheat sheet: which structure, which algorithm

You need to…	Use	Cost
Keep items in order, read by index	`ArrayList`	O(1) get, O(1) amortised add
Look up by key / check "seen it?"	`HashMap` / `HashSet`	O(1) average
Keys in sorted order, floor/ceiling, ranges	`TreeMap` / `TreeSet`	O(log n)
Keys in insertion order	`LinkedHashMap`	O(1) average
Stack (undo, brackets, DFS)	`ArrayDeque` push/pop	O(1)
Queue (BFS, buffers)	`ArrayDeque` offer/poll	O(1)
Always take the smallest / largest next	`PriorityQueue`	O(log n) add/poll
Top k of n items	size-k `PriorityQueue`	O(n log k)
Find in sorted data	`Arrays.binarySearch` / `Collections.binarySearch`	O(log n)
Sort objects by several fields	`list.sort(Comparator.comparing(..).thenComparing(..))`	O(n log n), stable
Shortest path, unweighted	BFS with a queue	O(V + E)
Explore everything reachable / detect cycles	DFS (recursion or stack)	O(V + E)
Overlapping sub-problems	DP: memo map or table array	usually O(n) or O(n·m)

Big-O: How an algorithm's work grows with input size n, ignoring constants: O(1), O(log n), O(n), O(n log n), O(n²).
Amortised O(1): Usually O(1), occasionally O(n) (an ArrayList resize), averaging to O(1) per operation over many operations.
Hash collision: Two different keys landing in the same HashMap bucket; resolved by a list (or, past 8 entries, a tree) inside the bucket.
Stable sort: A sort that keeps equal elements in their original order. List.sort and Arrays.sort on objects are stable.
Binary heap: A complete binary tree in an array where each parent is smaller (min-heap) than its children. Backs PriorityQueue.
Adjacency list: A graph stored as a map from each node to the list of its neighbours.
BFS / DFS: Breadth-first search (queue, level by level, finds shortest unweighted paths) and depth-first search (stack or recursion, goes deep first).
Memoisation: Caching the result of a function call by its arguments so each sub-problem is solved once.
Base case: The input a recursive method answers directly without recursing. Missing it causes StackOverflowError.

Quick check

You need to check millions of times whether a username is already taken. Which structure?

HashSet.contains is O(1) on average. ArrayList.contains and LinkedList.contains scan every element (O(n)), and a heap only gives fast access to its minimum.

Quick check

Why is (lo + hi) / 2 a bug in a Java binary search over a huge array?

Two indices above about 1.07 billion sum past 2³¹ - 1 and overflow to a negative number. lo + (hi - lo) / 2 or (lo + hi) >>> 1 avoid it.

← Module 12Java + Tools Module 14 →Problem Solving

Frequently asked questions

Should I use java.util.Stack or ArrayDeque for a stack in Java?

ArrayDeque. java.util.Stack extends Vector, synchronises every method and is kept for backwards compatibility; the Deque interface's push, pop and peek on an ArrayDeque are faster and are what the JDK documentation itself recommends.

Is HashMap iteration order guaranteed in Java?

No. HashMap makes no ordering promise and the order can change when the map resizes. Use LinkedHashMap for insertion order or TreeMap for sorted keys whenever the order is printed, compared or tested.

Do I need to implement data structures by hand for Java interviews?

Often, yes: linked-list reversal, a stack-based bracket check, BFS on a grid and a hand-written binary search are common coding-round tasks. In production code you use java.util, so learn both the hand-built version and the library class that replaces it.

Finish the Java handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.