DSA Interview Questions in Java (Patterns, Not Problems) — Freshers to Senior

DSA rounds don't test whether you've memorised 300 LeetCode problems — they test whether you can recognise the pattern and reason about complexity out loud. The senior skill is mapping a new problem to a known technique in 60 seconds: "this is a sliding window", "this is top-K, use a heap", "this smells like DP". This is a practical DSA interview guide built around patterns, not problems: the decision framework, a pattern-to-signal cheat-sheet, complexity you must know cold, and worked solutions for the templates that unlock dozens of variations.

Complexity — the language of every answer

Q1. What Big-O must you know instantly?

Always state both time and space, and mention the time–space tradeoff — most optimisations (like using a HashMap) spend O(n) memory to cut time from O(n²) to O(n).

The pattern cheat-sheet — recognise the signal

Template solutions worth memorising

Q2. Two Sum — the HashMap tradeoff (the archetype).

// Brute force O(n²); HashMap turns it into O(n) time, O(n) space
int[] twoSum(int[] a, int t) {
    Map<Integer,Integer> seen = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        if (seen.containsKey(t - a[i]))
            return new int[]{ seen.get(t - a[i]), i };
        seen.put(a[i], i);
    }
    return new int[0];
}

State the brute force first ("check every pair, O(n²)"), then the insight ("I can remember what I've seen — trade space for time"). That narration is what's being scored.

Q3. Sliding window — longest substring without repeating characters.

int longest(String s) {
    Set<Character> win = new HashSet<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        while (win.contains(s.charAt(r))) win.remove(s.charAt(l++)); // shrink
        win.add(s.charAt(r));
        best = Math.max(best, r - l + 1);
    }
    return best; // O(n) — each char enters/leaves the window once
}

Q4. Fast & slow pointers — detect a linked-list cycle.

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) return true; // they meet inside a cycle
    }
    return false; // O(n) time, O(1) space — Floyd's algorithm
}

Q5. Top-K frequent — the heap pattern.

// Count, then keep a MIN-heap of size k -> O(n log k), not O(n log n)
Map<Integer,Long> freq = Arrays.stream(nums).boxed()
    .collect(Collectors.groupingBy(x->x, Collectors.counting()));
PriorityQueue<Integer> heap =
    new PriorityQueue<>(Comparator.comparingLong(freq::get));
for (int n : freq.keySet()) {
    heap.offer(n);
    if (heap.size() > k) heap.poll(); // drop the least frequent
}

The "size-k heap" trick — keep only k elements instead of sorting everything — is a reusable senior optimisation. Note the Streams groupingBy for the frequency map.

Recursion, DP & the memoisation question

Q6. Memoisation vs tabulation — and why it matters.

// Naive Fibonacci: O(2ⁿ) — recomputes the same subproblems
// Top-down memoisation: cache results -> O(n)
long fib(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

Memoisation (top-down) caches recursion; tabulation (bottom-up) fills a table iteratively and avoids stack-overflow risk on deep inputs. Spot DP when you see overlapping subproblems + optimal substructure. Mention you can often reduce space (Fibonacci needs only the last two values → O(1) space).

Q7. When does recursion risk StackOverflowError?

Java doesn't do tail-call optimisation, so every recursive call adds a stack frame. Deep recursion (e.g. a 100k-node list or unbalanced tree) can overflow — convert to iteration with an explicit stack, or use bottom-up DP. Always ask the interviewer about input size to decide.

Trees & graphs

Q8. BFS vs DFS — when each?

BFS (queue) explores level by level — use for shortest path in an unweighted graph and level-order traversal. DFS (stack/recursion) goes deep — use for connectivity, cycle detection, topological sort, and backtracking. Both are O(V+E). For weighted shortest paths use Dijkstra (a heap-based BFS).

Q9. BST operations and the balance caveat.

Search/insert/delete in a balanced BST are O(log n); but an unbalanced BST (inserting sorted data) degrades to O(n) — a linked list. Self-balancing trees (Red-Black, used by TreeMap) guarantee O(log n). In-order traversal of a BST yields sorted order — a common "how would you...?" answer.

Sorting

Q10. Compare the sorts an interviewer will ask about.

Stability = equal elements keep their relative order (matters for multi-key sorts). Java's Arrays.sort uses dual-pivot quicksort for primitives and a stable Timsort for objects — a good detail to drop.

The framework — how to attack any coding problem

1. Clarify — inputs, ranges, duplicates, empty/null, sorted? Never start coding blind.
2. Examples — walk one by hand; find an edge case (empty, single element, all same).
3. Brute force — state it and its Big-O. It shows you can solve it at all.
4. Optimise — match to a pattern from the cheat-sheet; state the new complexity.
5. Code — clean, named variables, talk as you type.
6. Test — dry-run your example + the edge case; fix bugs before they ask.

Go deeper by topic

• Core Java interview questions — language mechanics
• Collections interview questions — the data structures behind these patterns
• Streams interview questions — concise grouping/counting for DSA
• DSA in Java roadmap — the full learning path

The single biggest change in my DSA prep was switching from "how many problems have I done?" to "how many patterns can I recognise instantly?" There are maybe a dozen — two pointers, sliding window, fast/slow, heap top-K, backtracking, DP, BFS/DFS, union-find, monotonic stack, prefix sum — and almost every interview question is one of them wearing a costume. So I'd read a new problem and force myself to name the pattern before writing a line, then reach for the template I already knew. Pair that with always stating the brute force and its Big-O first, and narrating the optimisation, and you turn an intimidating blank editor into a checklist you've run a hundred times. Learn the patterns, not the problems — that's how you walk into a coding round and stay calm when they hand you something you've never seen. You've got this.

Related

• The full DSA in Java roadmap
• The full Java course (Zero to Pro)
• Collections interview questions

← Spring Boot interview questions · Core Java interview questions →