Java Coding Test Prep: DSA Patterns That Actually Show Up

Almost every coding round ends with "what's the time and space complexity?". Answer it before the interviewer asks — it signals you think about cost, not just correctness.

Big-O of the operations you will actually use:

Operation	Cost
array[i], ArrayList.get(i)	O(1)
ArrayList.add(x) (append)	O(1) amortized
ArrayList.add(0, x) / remove(0)	O(n) — shifts everything
HashMap.get/put/containsKey	O(1) average, O(n) worst case
TreeMap.get/put	O(log n)
Collections.sort / Arrays.sort(objects)	O(n log n)
String.concat in a loop	O(n²) — use StringBuilder
list.contains(x)	O(n) — a common hidden killer

The classic hidden O(n²):

// BAD — contains() is O(n), so this loop is O(n * m)
for (String s : listA) {
    if (listB.contains(s)) result.add(s);
}

// GOOD — build a Set once, then O(1) lookups => O(n + m)
Set<String> seen = new HashSet<>(listB);
for (String s : listA) {
    if (seen.contains(s)) result.add(s);
}

Rules of thumb for interviews:

• n ≤ 10⁴ → O(n²) usually passes. n ≥ 10⁵ → you need O(n log n) or better.
• Nested loops are not automatically O(n²) — check whether the inner loop's total work across all iterations is bounded (that is exactly why sliding window is O(n)).
• Recursion costs stack space: state the O(depth) space, not just the time.
• Say "average case O(1), worst case O(n)" for HashMap. Interviewers notice when you know the difference.

Most coding tests open with an array or string problem. The algorithm is rarely the hard part — the Java API is.

Strings are immutable. Every + in a loop allocates a new String:

// O(n²) — allocates a new String on every iteration
String out = "";
for (String part : parts) out += part;

// O(n) — the only acceptable answer in an interview
StringBuilder sb = new StringBuilder();
for (String part : parts) sb.append(part);
String out = sb.toString();

Conversions you must be able to write from memory:

char[] chars = s.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);          // canonical anagram key

int digit = c - '0';                        // char -> int, no parsing
boolean isLetter = Character.isLetterOrDigit(c);
char lower = Character.toLowerCase(c);

int n = Integer.parseInt("42");
String s = String.valueOf(42);
String[] words = sentence.trim().split("\\s+");   // split on any whitespace run

Equality: == compares references for objects. "a" == "a" may be true because of the string pool, and that accidental true is exactly how people ship the bug. Always use .equals().

Array vs List cheatsheet:

int[] a = new int[n];                       // .length, defaults to 0
Arrays.fill(a, -1);
int[] copy = Arrays.copyOf(a, a.length);
Arrays.sort(a);                             // dual-pivot quicksort, O(n log n)

List<Integer> list = new ArrayList<>();     // .size(), autoboxing applies
list.sort(Comparator.naturalOrder());

Watch out: Arrays.asList(intArray) on an int[] gives you a List<int[]> of size 1, not a list of ints. Use Arrays.stream(a).boxed().toList().

If a problem mentions duplicates, frequency, pairs that sum to, anagrams, or first/last occurrence, the answer almost always involves a HashMap or HashSet. This single pattern covers a large share of screening questions.

Frequency counting:

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);      // idiomatic; beats getOrDefault + put
}

Complement lookup (Two Sum) — one pass, O(n):

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] { j, i };
        seen.put(nums[i], i);                        // put AFTER checking
    }
    return new int[0];
}

Putting before checking is the bug interviewers watch for — it lets an element pair with itself.

Grouping (anagrams):

Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
    char[] c = w.toCharArray();
    Arrays.sort(c);
    groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w);
}
return new ArrayList<>(groups.values());

computeIfAbsent is the multi-map idiom. Knowing it saves you four lines and reads as fluent Java.

Deduplication while preserving order: LinkedHashSet. Sorted keys: TreeMap. Picking the right map type unprompted is a strong signal.

These two patterns turn O(n²) brute force into O(n) and come up constantly.

Two pointers — converging (works on a sorted array):

int lo = 0, hi = nums.length - 1;
while (lo < hi) {
    int sum = nums[lo] + nums[hi];
    if (sum == target) return new int[] { lo, hi };
    if (sum < target) lo++;               // need a bigger value
    else hi--;                            // need a smaller value
}

Same skeleton solves palindrome checks, reversing in place, and merging two sorted arrays.

Sliding window — longest substring without repeating characters:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int best = 0, start = 0;
    for (int end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        Integer prev = lastSeen.get(c);
        if (prev != null && prev >= start) {
            start = prev + 1;             // shrink window past the duplicate
        }
        lastSeen.put(c, end);
        best = Math.max(best, end - start + 1);
    }
    return best;
}

Each index enters and leaves the window at most once, so it is O(n) despite the nested feel.

How to recognise the pattern:

• "Longest / shortest / count of subarrays satisfying X" → sliding window.
• "Sorted input" or "in-place with O(1) extra space" → two pointers.
• "At most K distinct" → window plus a frequency map.

Say it out loud in the interview: "I'll expand the right edge and shrink the left while the window is invalid." Naming the invariant is what separates a memorised solution from an understood one.

Recursion template — base case first, then recurse, then combine:

int fib(int n, Map<Integer, Integer> memo) {
    if (n <= 1) return n;                        // base case
    Integer cached = memo.get(n);
    if (cached != null) return cached;
    int result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.put(n, result);                         // memoise: O(2^n) -> O(n)
    return result;
}

Backtracking template — choose, explore, un-choose:

void permute(List<Integer> nums, List<Integer> current,
             boolean[] used, List<List<Integer>> out) {
    if (current.size() == nums.size()) {
        out.add(new ArrayList<>(current));       // COPY — current keeps mutating
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums.get(i));                // choose
        permute(nums, current, used, out);       // explore
        current.remove(current.size() - 1);      // un-choose
        used[i] = false;
    }
}

Forgetting the defensive copy on out.add is the single most common backtracking bug — you end up with a list of empty lists.

Habits that earn points in a timed test:

1. Handle edge cases first. null, empty input, single element, all-duplicates. Write the guard clauses before the algorithm.
2. Name things. left/right/windowStart beats i/j/k when you have to explain your code.
3. Talk through one example by hand before writing. It catches off-by-one errors for free.
4. Prefer clarity over cleverness. A readable O(n) loop scores higher than an unreadable stream chain.
5. Test out loud at the end — walk your own code through the sample input. Interviewers weight this heavily.