How to Approach a DSA Interview

Prev Next

Knowing every data structure and algorithm in this track doesn't automatically make you good in an interview — plenty of strong engineers freeze up because they treat the interview as a silent coding test instead of a conversation. What follows is a six-step framework that interviewers are, in practice, actively grading you on, whether or not they say so out loud.

The Six-Step Framework

Step	What to do	Why it matters
1	Clarify the problem and constraints out loud	Confirms you understood the question correctly before writing a single line, and surfaces edge cases (empty input? duplicates? negative numbers?) before they surprise you mid-code.
2	State a brute-force approach first, even if not optimal	Proves you can solve something immediately, gives you a correctness baseline to compare against, and often reveals the optimization naturally.
3	Identify which pattern it matches	Two pointers? Sliding window? DP? Graph traversal? Naming the pattern out loud shows you're recognizing structure, not guessing.
4	Code it while talking through your reasoning	Interviewers can't read your mind — narrating why you write each line is most of what's actually being evaluated.
5	Test with a small example by hand	Catches off-by-one errors and logic bugs before the interviewer has to point them out, which reads as far stronger than "looks right to me."
6	State final time/space complexity, unprompted	Shows complexity awareness is part of how you think about code, not an afterthought bolted on when asked.

Step 1: Clarify the Problem

Before touching a keyboard, restate the problem in your own words and ask about the shape of the input: can it be empty? How large can it get? Are there duplicates? Is the array sorted already? Is negative input possible? Each answer can change which pattern applies — a sorted-array clue often means two pointers or binary search are in play; an unsorted array with a "find pairs/triples" ask often means hashing.

Step 2: State the Brute Force

Say the obvious, unoptimized approach out loud even when you already see the better one — for example "the brute force here is checking every pair, which is O(n²); I think we can do better with a hash set." This costs seconds and buys you a fallback if the optimal approach stalls partway through.

Step 3: Identify the Pattern

This track exists specifically to build this recognition muscle. A few of the strongest signals:

Sorted array, looking for a pair/triple: two pointers.
Subarray/substring with a running condition (max sum, longest without repeat): sliding window.
"Count the ways" / "minimum cost" with overlapping subproblems: dynamic programming.
"Find all combinations/arrangements" with constraints to backtrack out of: backtracking.
Anything phrased in terms of nodes/edges/connections: BFS/DFS, or Dijkstra/MST if weights are involved.
"Make the locally best choice at each step": greedy — but confirm the greedy choice is actually provably optimal first.

Step 4-6: Code, Test, State Complexity

Narrate while coding rather than going silent — "I'll use a HashMap here to get O(1) lookups instead of scanning." After the code is down, pick a small example (3-5 elements is usually enough) and trace it by hand, catching bugs before the interviewer has to. Then state complexity unprompted: "this runs in O(n) time since we make one pass, and O(n) space for the hash map."

Worked Example: First Non-Repeating Character

Problem: given a string, return the first character that appears exactly once. Applying the framework:

1. Clarify: "Is the string guaranteed non-empty? Case-sensitive? Only one answer expected, or should I return -1/null if every character repeats?" Assume: non-empty, case-sensitive, return a sentinel if none found.

2. Brute force: "For each character, scan the rest of the string to check if it repeats anywhere else — O(n²), but correct."

3. Pattern: "This is a frequency-counting problem — a HashMap pattern, not two pointers or DP, since order matters but pairwise scanning doesn't."

public static char firstNonRepeating(String s) {
    Map<Character, Integer> counts = new LinkedHashMap<>();

    // Pass 1: count occurrences of every character
    for (char c : s.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0) + 1);
    }

    // Pass 2: walk the string again, return the first char with count == 1
    for (char c : s.toCharArray()) {
        if (counts.get(c) == 1) {
            return c;
        }
    }
    return '\0';              // sentinel: no non-repeating character found
}

5. Test by hand: on "swiss": pass 1 counts s=3, w=1, i=1. Pass 2 walks s(count 3, skip), w(count 1, return 'w'). Correct — 'w' is indeed the first character that appears exactly once.

6. Complexity, stated unprompted: Time complexity: O(n) — two linear passes over the string, each O(n), and O(n) dominates the constant factor of "2 passes." Space complexity: O(k) where k is the number of distinct characters (bounded by the alphabet size, so often treated as O(1) for fixed character sets, but O(n) worst case if every character is unique).

The point of walking through all six steps on something this simple: the framework isn't reserved for hard problems — applying it consistently, even on easy ones, is what makes it automatic when a problem actually is hard.

Next up: Best Practices & Common Patterns Recap ties every pattern from this entire track together in one condensed reference, and closes out the DSA in Java track.

Prev Next