Choosing a Data Structure and Interview Strategy

This page summarizes the course: how to recognize which data structure a problem needs, what each structure costs in Java, and a routine for working through a problem in an interview.

From problem clues to data structures

Operation costs

h is the tree height (log n when balanced, n in the worst case), and L is the word length.

A routine for each problem

1. Restate the problem and ask about the input. How large can it be? Is it sorted? Can it be empty? Are there duplicates or negative numbers? Could the numbers overflow int?
2. Work through an example by hand. Write down one normal case and one edge case.
3. Describe the brute-force solution and its complexity. It proves you understand the problem, and it gives you something correct to fall back on.
4. Find what's slow in the brute force. Is it a repeated search (use a hash table)? A repeated sum (use prefix sums)? Repeatedly finding the minimum or maximum (use a heap)? Work that sorted input would avoid (sort first)?
5. Write the optimal solution. Start with the signature: choose the parameter and return types (int[], String), and return OptionalInt when there might be no answer.
6. Test it by tracing your example and the edge case through the code.
7. State the time and space complexity, and what you'd change if memory were tight.

Worked example

Given an int[], return the length of the longest run of consecutive values, in any order. [100, 4, 200, 1, 3, 2] → 4 (the run 1, 2, 3, 4).

• Questions. Can there be duplicates? (Yes, they don't extend a run.) Can the array be empty? (Yes, then the answer is 0.)
• Brute force. Sort, then scan for the longest run of +1 steps: O(n log n) time. Or, for each value, count upward with a linear search for the next value: O(n²).
• What's slow? The linear search. A HashSet makes each check O(1).
• Optimal idea. Only start counting at values that begin a run, meaning x - 1 is not in the set. Then each value is visited at most twice in total.

import java.util.HashSet;
import java.util.Set;

public class Main {
    static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        int best = 0;
        for (int x : set) {
            if (!set.contains(x - 1)) {
                // x starts a run: count upward
                int length = 1;
                while (set.contains(x + length)) {
                    length++;
                }
                best = Math.max(best, length);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}) + " "
                + longestConsecutive(new int[]{}) + " "
                + longestConsecutive(new int[]{1, 2, 2, 3}));
    }
}

4 0 3

• Complexity. O(n) time: the inner while only runs from the start of a run, so every value is counted once in total. O(n) space for the set. The HashSet iteration order is unspecified, but the result does not depend on it. The expression x - 1 wraps around at Integer.MIN_VALUE (see the next section), so the problem's value range must exclude that case.

Java mistakes that cost time

int overflow. int arithmetic wraps silently: Integer.MAX_VALUE + 1 is Integer.MIN_VALUE. Math.addExact, Math.multiplyExact, and Math.subtractExact throw ArithmeticException instead. Accumulate sums and products in long. Math.abs(Integer.MIN_VALUE) is still negative.

public class Main {
    public static void main(String[] args) {
        int big = Integer.MAX_VALUE;
        System.out.println(big + 1);
        long sum = (long) big + 1;
        System.out.println(sum);
        try {
            Math.addExact(big, 1);
        } catch (ArithmeticException e) {
            System.out.println("addExact throws: " + e.getMessage());
        }
    }
}

-2147483648
2147483648
addExact throws: integer overflow

Comparators written as subtraction. (a, b) -> a - b overflows for values far apart and gives the wrong order. Use Integer.compare(a, b) or Comparator.comparingInt.

public class Main {
    public static void main(String[] args) {
        int a = Integer.MAX_VALUE;
        int b = -1;
        System.out.println(a - b);                 // wraps: negative, so "a < b"
        System.out.println(Integer.compare(a, b)); // 1, so "a > b"
    }
}

-2147483648
1

Boxed Integer comparison. == on two Integer objects compares references. Use equals, or unbox with intValue(). Arrays used as HashMap keys also compare by identity, so convert them to a List<Integer> or a String first.

null instead of "empty". ArrayDeque.poll() and peek() return null on an empty deque, and unboxing that null into an int throws NullPointerException. ArrayDeque rejects null elements. OptionalInt makes the "no answer" case explicit in a return type.

Pointers in linked lists and trees. Nodes hold references that can be null. Check for null before reading node.next or node.left, and use a dummy head node to avoid special cases when the head can change. See Linked Lists in Java.

Graph nodes as objects. Number the vertices and store neighbors as indices in a List<List<Integer>>. See Graphs in Java.

Using ArrayList.remove(0) as a queue. It shifts every later element, so it is O(n) per call. Use ArrayDeque.poll.

Assuming PriorityQueue is a max-heap. It is a min-heap. Pass Comparator.reverseOrder() for a max-heap. Its iteration order and toString are not sorted, so print values by polling.

Depending on HashMap order. Iteration order is unspecified. Sort the results, use TreeMap or LinkedHashMap, or walk the original input and use the map only for lookups.

Removing while iterating. Calling list.remove(x) inside a for-each loop throws ConcurrentModificationException. Use an Iterator and it.remove(), or removeIf.

Deep recursion. Recursion as deep as the input can throw StackOverflowError, because the call stack is limited by the thread stack size. Use an explicit ArrayDeque as a stack when the depth can reach n.

Strings in loops. String is immutable, so s += c in a loop copies the string each time and is O(n²) overall. Use StringBuilder.