How to Approach a DSA Coding Interview
The mindset and time-budget playbook for 45-minute LeetCode-style coding interviews. Covers what interviewers grade, the brute-force-first rule, pattern-recognition reflexes across data structures and algorithms, recovery patterns when stuck, and traps on dynamic programming and graph problems.
What This Page Is (and Isn't)
This page is the pre-game for a 45-minute DSA coding interview: how to think before you write a single line of code. The companion page, How to Design at DSA, covers the execution — concrete templates for two pointers, sliding window, binary search, BFS/DFS, monotonic stack, heap, backtracking, and DP.
Strong engineers fail DSA interviews not because they lack algorithmic knowledge — they have solved hundreds of problems — but because they make the wrong moves at the meta level: they jump to the optimal solution without explaining the brute force, code silently for 20 minutes, skip edge cases until the interviewer flags them, or forget to state time and space complexity. These are the differences between a weak hire and a strong hire signal.
Read this page to understand the signals interviewers grade, the traps that catch experienced candidates, and the recovery patterns when you're stuck on a hard problem at minute 25. Then read the design page for the mechanical pattern templates.
The asymmetric truth: in 45 minutes, the interviewer cannot test your full algorithmic depth. They sample your problem decomposition, communication, and code quality. A candidate who solves an O(n log n) approach but explains every decision crisply outperforms a candidate who silently arrives at O(n) but cannot articulate why the optimization works.
The Six Signals DSA Interviewers Score
Every FAANG, Microsoft, Stripe, and unicorn coding rubric is some variation of these six signals. Memorize them — they tell you what to optimize at every moment of the interview:
- Problem decomposition — do you restate the problem, identify constraints, and ask clarifying questions before coding? Or do you start typing on the first reading?
- Brute-force-then-optimize — do you propose an O(n^2) baseline first, state its complexity, and only then optimize? Jumping straight to the optimal hides reasoning and reads as memorization.
- Pattern recognition — within 2-3 minutes of seeing the problem, do you map it to a known family (sliding window, two pointers, binary search on answer, BFS, DP, heap, etc.)?
- Clean code — meaningful variable names, helper functions for repeated logic, no dead code, no commented-out attempts. The code reads like you wrote it for a teammate, not for yourself.
- Complexity analysis — both time AND space, stated unprompted, with the dominant cost identified (e.g., "O(n log n) sort dominates O(n) scan").
- Edge cases and testing — empty input, single element, all-equal elements, negative numbers, integer overflow, cycle in graph, duplicates. Surfaced before the interviewer asks.
Mid-level (L4 / E4) candidates miss signals 1, 5, and 6. Senior (L5 / E5) candidates lose on 2 and 4 — they know the optimal answer but skip the brute-force conversation. Staff (L6 / E6) candidates win on 3 and on naming non-obvious tradeoffs (e.g., "I could also solve this with a segment tree but the constant factor isn't worth it for n < 10^4").
Why DSA Interviews Are Communication Tests in Disguise
The biggest misconception about coding interviews: that they test your ability to produce correct code. They don't — at least not primarily. They test your ability to reason out loud about code in a constrained, ambiguous, time-pressured setting. Two candidates can produce the identical final solution and receive opposite hire/no-hire signals based purely on how they communicated the journey.
This matters because it inverts how you should practice. Solving a problem alone in 30 minutes with autocomplete and no narration is not training for the interview format — it's training for a different skill. The interview format is: hand-coded (no autocomplete), voiced (you explain every step), one-shot (no time to refactor), under observation (someone is grading reasoning), and optimized (interviewers expect you to identify and apply the best-fit pattern within minutes).
Three skills compound: (1) pattern matching — recognizing within 2-3 minutes which family of problem this is (sliding window? DP? graph traversal?); (2) structured narration — saying out loud what you're doing, why, and what you'd do differently; (3) complexity literacy — stating both time and space complexity, identifying the dominant cost, and connecting the cost to a real-world constraint ("at n=10^5, an O(n^2) solution runs ~10 billion operations, which is over a minute — we need O(n log n) or better").
The candidates who fail tend to be strong on raw problem-solving and weak on communication — they arrive at correct solutions silently, then can't explain why. The candidates who succeed are not necessarily the strongest at algorithms — they are the ones who treat the interview as a conversation about an algorithm, not a one-person coding session. The shift in framing is small but rewires what you practice.
The 8 Mindset Rules for DSA Coding Interviews
Rule 1 — Restate the problem in your own words before doing anything
After the interviewer states the problem, restate it: 'So we have an array of integers, possibly negative, and we want the longest contiguous subarray whose sum equals K — is that right?' This catches misreadings and signals you're not pattern-matching on a memorized title.
Rule 2 — Ask 3-5 clarifying questions before coding
Standard battery: input size (n < 10^3, 10^5, 10^7? — this rules in or out O(n^2)), value range (negatives? overflow risk?), duplicates allowed?, sorted or unsorted?, return value (index, value, count, all of them?), what should I return on empty input?. Each question takes 5 seconds and prevents minutes of wrong code.
Rule 3 — Always state the brute force first, even if you know the optimal
Say 'The brute force is O(n^2): try every pair of indices and check the sum. Space O(1). Now let me see if we can do better.' This earns the decomposition signal AND gives you a fallback if you can't find the optimal in time. Skipping brute force is a senior-level red flag — it reads as memorized.
Rule 4 — Explain the approach BEFORE coding, not while coding
After arriving at an approach, walk through it on a small example out loud BEFORE writing code. 'For input [1, -1, 2, 3], we'd build prefix sums [1, 0, 2, 5], then for each j check if prefix[j] - K exists in our hashmap...' This catches bugs before they're written and lets the interviewer course-correct early.
Rule 5 — Narrate the code as you write it
Coding silently for 15 minutes is the second-most-common interview-failing mistake. Narrate: 'I'll use a hashmap to store prefix_sum → first_index. Iterate through the array, compute running sum, check if sum - k is in the map...' The interviewer scores reasoning, not just the final code.
Rule 6 — Walk through your code on a test case before saying 'done'
After writing the code, trace through it manually with a small input. This catches off-by-one errors, wrong initial values, and missing edge cases. It also signals discipline — strong candidates always test their code before claiming it works. Saying 'I'm done' without tracing is a junior signal.
Rule 7 — Surface edge cases unprompted
Before tracing, list the edge cases: empty input, single element, all-equal, very large input, negative numbers, integer overflow. Then trace through 1-2 of them. Catching your own edge cases beats having the interviewer point them out.
Rule 8 — State final complexity unprompted
After tracing, say: 'Time: O(n), single pass. Space: O(n) for the hashmap. The hashmap dominates space; if memory is tight we could use a sliding-window approach but that requires non-negative inputs.' Stating BOTH time and space, plus the alternative tradeoff, is the L5+ signal.
The 45-Minute DSA Interview Time Budget
Pattern Recognition Reflexes — Signal-to-Pattern Mapping
Sorted array OR 'find pair / triplet' → Two Pointers
Sorted input + look for pair summing to target = two pointers from both ends, O(n) after the O(n log n) sort. 3Sum, Container With Most Water, Trapping Rain Water. If sort is too expensive, fall back to hashmap (O(n) time, O(n) space).
Contiguous subarray / substring problems → Sliding Window
Keywords: 'longest substring with X', 'shortest subarray summing to Y', 'maximum sum of size k window'. Variable-size window when the constraint is 'longest/shortest valid window'; fixed-size when k is given. Almost always O(n) time, O(k) or O(charset) space.
'Find target' OR 'minimum feasible X' → Binary Search
Sorted array + find target = textbook binary search. The non-obvious one: 'minimize the maximum X' or 'find the smallest k such that we can complete in time T' = binary search on the answer space, not the array. Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum. O(n log(max_answer)).
Tree → DFS recursion (or BFS for level-order)
DFS for: subtree properties, path sum, tree diameter, LCA, balanced check. BFS for: level-order traversal, shortest depth, level-aware aggregation. Recursion is cleaner; iterative DFS with stack is needed only when recursion depth could blow the stack (n > 10^4).
'Shortest path' in unweighted graph → BFS
BFS from source guarantees shortest path in unweighted graphs (each edge counted once). For weighted with non-negative weights, switch to Dijkstra (priority queue, O((V+E) log V)). For negative weights, Bellman-Ford (O(VE)). For all-pairs, Floyd-Warshall (O(V^3)).
'All combinations / permutations / subsets' → Backtracking
Build candidates incrementally; recurse; undo. Permutations, Combinations, Subsets, N-Queens, Word Search, Sudoku. Time is typically O(branching^depth × cost_per_node) — exponential, so only viable for small n (< ~20).
'Maximum subarray sum' → Kadane's Algorithm
Track running sum; reset to 0 when negative. O(n) time, O(1) space. The variant 'max subarray with at most k elements deleted' becomes a small DP. Maximum Product Subarray needs two states (max and min) because of negative numbers flipping signs.
'Count ways' OR 'min cost' OR 'longest X' on a structure → DP
Overlapping subproblems + optimal substructure = DP. Define dp[i] meaning explicitly. Coin Change, LCS, Edit Distance, 0/1 Knapsack, House Robber, Longest Increasing Subsequence. Start with memoized recursion; optimize to tabulation only if needed.
'Top K' OR 'kth element' OR 'running median' → Heap
Top K largest = min-heap of size K (O(n log K)). Top K smallest = max-heap of size K. Running median = two heaps (max-heap of lower half, min-heap of upper half). Median of Two Sorted Arrays is binary search, NOT heap — this trips up many candidates.
'Next greater element' OR 'rectangle in histogram' → Monotonic Stack
Maintain a stack where elements are monotonically increasing (or decreasing). On each new element, pop violators and process. Daily Temperatures, Largest Rectangle in Histogram, Trapping Rain Water (alternative to two pointers). O(n) amortized.
'Connected components' OR 'check cycle in undirected' → Union-Find
Initialize parent[i] = i. Union(a, b) merges sets; Find(a) returns root with path compression. Number of Provinces, Redundant Connection, Accounts Merge. Near-O(α(n)) amortized per op (effectively constant).
'Prefix matching / autocomplete / dictionary' → Trie
Insert each word character-by-character into a tree; each node has up to 26 children (ASCII a-z) and an isEnd flag. Word Search II, Implement Trie, Replace Words, Longest Word in Dictionary. O(L) per insert/search where L = word length.
The Single Most Expensive Mistake — Coding Before Confirming the Approach
The highest-leverage failure mode: arriving at an approach in your head and immediately coding it, without explaining it to the interviewer first.
Example: the interviewer says 'find the longest substring with at most K distinct characters.' You silently decide on sliding window with a hashmap. You start typing. At minute 20, the interviewer asks 'wait, why are you decrementing left there?' — you realize you confused this problem with 'exactly K distinct.' Now you're 20 minutes in with broken code, low confidence, and 25 minutes left.
Cost: 10-15 minutes of recovery, plus the perception that you couldn't articulate your reasoning.
Fix: after identifying the pattern, take 60-90 seconds to walk through the approach on a small input out loud. 'For "eceba" with K=2, expand right to e-c-e (2 distinct, valid), then add b (3 distinct, invalid), shrink left to drop e until distinct count is 2 again...' The interviewer will catch your misunderstanding before you write a single line. The cost of this 60-second check is tiny; the cost of skipping it is the whole interview.
Recovery Patterns When You're Stuck on a Hard Problem
When you can't find the optimal approach in 5 minutes
Commit to coding the brute force. A working O(n^2) solution beats no solution. Say: 'I want to make sure I have a working solution; let me code the O(n^2) approach first, then we can optimize together.' This earns partial credit AND often unlocks the optimization (the brute-force code's redundancy reveals the pattern).
When you've been silent for 60 seconds
Break the silence with structured thinking out loud. 'Let me think about the structure here. The input is X, the output is Y. The key insight I'm looking for is...' Silence reads as panic; structured reasoning under pressure reads as senior.
When the interviewer gives you a hint
Take it gracefully. Say 'Ah, that helps — so I should be thinking about [restated insight]. Let me reconsider...' Refusing or ignoring hints is a major negative signal. Hints are gift-wrapped credit; use them and move forward.
When your code has a bug you can't find by reading
Don't keep re-reading — trace through with a tiny input by hand, writing values on the whiteboard. 95% of bugs found this way. Say 'Let me trace through with arr=[1,2,3], k=2 to verify the loop bounds.'
When you realize at minute 30 your approach is wrong
Acknowledge cleanly: 'Stepping back — I think this approach has a flaw because [reason]. Let me reconsider — I think the right approach is [pattern], because [reasoning].' Self-correction is a positive senior signal; pretending the bug isn't there is a strong negative.
When time's running out and the code isn't finished
Don't try to finish frantically — finish the algorithm in pseudocode and articulate complexity. 'I have the core loop — for the cleanup, I'd handle the edge case where the input is empty by returning 0 immediately. Time complexity is O(n), space O(n) for the hashmap. If we had more time I'd add tests for [edge case 1, 2, 3].' Explicit prioritization beats incomplete code with no narrative.
The Per-Problem Decision Loop You Run On Every Problem
Anatomy of a Strong DSA Solution — What Interviewers Want to See
from typing import List
from collections import defaultdict
def longest_substring_k_distinct(s: str, k: int) -> int:
"""
Longest substring with at most k distinct characters (LC 340).
Approach: variable-size sliding window with a frequency map.
Expand right; shrink left when distinct count exceeds k.
Time: O(n) — each character enters and exits the window once.
Space: O(k) — the frequency map holds at most k+1 keys before shrinking.
"""
# Edge cases stated explicitly — surfaced before the interviewer asks
if not s or k == 0:
return 0
if k >= len(s):
return len(s)
freq: dict[str, int] = defaultdict(int)
left = 0
best = 0
for right, ch in enumerate(s):
freq[ch] += 1
# Shrink: invariant is len(freq) <= k after this loop
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
# Window [left, right] is valid; update answer
best = max(best, right - left + 1)
return best
# Trace: s = "eceba", k = 2
# right=0 'e' -> freq={e:1}, window="e", best=1
# right=1 'c' -> freq={e:1,c:1}, window="ec", best=2
# right=2 'e' -> freq={e:2,c:1}, window="ece", best=3
# right=3 'b' -> freq={e:2,c:1,b:1}, len=3 > 2 -> shrink
# left=0 'e' freq={e:1,c:1,b:1} -> still 3 distinct
# left=1 'c' freq={e:1,b:1} -> 2 distinct, exit shrink
# window="eb", best=3
# right=4 'a' -> freq={e:1,b:1,a:1}, len=3 > 2 -> shrink
# left=2 'e' freq={b:1,a:1} -> 2 distinct, exit shrink
# window="ba", best=3
# Final answer: 3 ("ece")
What Separates L4 / L5 / L6 in DSA Interviews
The interviewer's grading rubric varies by level even on the same problem.
L4 / Mid (E4) — solves the problem with help; arrives at a correct O(n log n) or O(n) solution; states one of time/space complexity; identifies one edge case unprompted.
L5 / Senior (E5) — solves independently within time; states brute force first, then optimizes; states both time and space; identifies 3+ edge cases; handles 1-2 follow-up questions ("what if input is streaming?", "what if memory is constrained?"). Code is clean enough that a teammate could read it.
L6 / Staff (E6) — same as L5 PLUS connects the problem to a broader pattern family ("this is a variant of binary search on the answer space, similar to Capacity to Ship Packages"); discusses non-obvious tradeoffs (segment tree vs Fenwick tree vs sqrt decomposition); proposes a generalization or a real-world application; handles open-ended follow-ups ("how would this extend to a distributed system?").
The pattern: progression isn't about solving harder problems — it's about depth of reasoning on the same problem. A staff candidate solving Two Sum should still discuss the hashmap-vs-sort tradeoff and articulate when each wins; a mid candidate solves Two Sum with a hashmap and moves on.
Anti-Patterns That Lose Points (and the Senior Fix)
| Anti-pattern | Why it costs points | Senior fix |
|---|---|---|
| Coding within 60 seconds of seeing the problem | Signals you skip clarification and risk solving the wrong problem | Take 5 minutes for clarification and approach before any code is written |
| Jumping to the optimal solution without mentioning brute force | Reads as memorized; loses the decomposition signal | State brute force with complexity, then say 'now let's optimize' |
| Coding silently for > 60 seconds | Interviewer cannot grade what they cannot hear | Narrate every decision: 'I'll use a hashmap because we need O(1) lookup of seen values' |
| Using single-letter variable names (a, b, x) outside loop counters | Reads as junior; obscures intent in 30+ line solutions | Use meaningful names: prefix_sum, last_seen, char_count, monotonic_stack |
| Forgetting to state space complexity | Half-answered complexity is a near-guaranteed downgrade at L5+ | Always state both: 'O(n) time, O(k) space because the hashmap holds at most k+1 keys' |
| Saying 'I'm done' without tracing through a test case | Junior signal — strong candidates always verify before claiming completion | Trace through a small input AND an edge case (empty, single, duplicates) before stating completion |
| Refusing or ignoring an interviewer hint | Reads as defensive or pattern-matching | Take the hint gracefully: 'That helps — so I should be thinking about a monotonic stack here. Let me reconsider...' |
| Memorized solutions for canonical problems (Two Sum, Reverse Linked List) | Falls apart on variants; interviewers deliberately ask twists | Re-derive from first principles even on familiar problems; state the pattern explicitly |
| Adding code comments instead of explaining out loud | Comments are for the reader after; the interviewer wants live reasoning | Talk through the reasoning; comments reserved for non-obvious invariants in the final code |
| Defending a wrong approach when the interviewer pushes back | Reads as inflexible; loses the reflection signal | 'Fair point — let me reconsider' followed by structured re-analysis |
How to Practice (and What to Practice)
The wrong practice: grinding 500 LeetCode problems shallowly. The right practice: solving 100-150 problems deeply, organized by pattern, with a 45-minute timer and out-loud narration as if an interviewer is in the room.
What to drill specifically:
- Pattern recognition under time pressure: pick a random LeetCode medium and aim to identify the pattern within 2-3 minutes. If you can't, that's the pattern to study next. Track which patterns you miss most often.
- Brute-force-first habit: even on problems you've seen before, force yourself to articulate the brute force out loud before coding the optimal. The habit atrophies fast if not maintained.
- Complexity stating reflex: after every solved problem, state time and space complexity unprompted. Identify the dominant cost. This is a 30-second exercise that compounds.
- Edge case checklist: empty input, single element, all-equal, sorted vs reverse-sorted, very large input, integer overflow, negative numbers, cycle in graph, duplicates. Memorize the list; surface 3-5 relevant ones for any problem.
- Mock interviews with peers: at least 5-10 mocks with someone playing interviewer, on a real whiteboard or shared editor with no autocomplete. This is the only way to drill the narration habit.
What NOT to over-practice: memorizing canonical problem solutions verbatim. Interviewers know the canonical problems and ask deliberate variants. A candidate who has memorized 'Two Sum' will fail on 'Two Sum where the array is sorted but with duplicates and we want all pairs' — because they didn't internalize why the hashmap approach works.
Coverage targets by pattern (rough): Arrays / Strings (40 problems), Two Pointers (15), Sliding Window (15), Binary Search (15), Trees (20), Graphs (20), DP (25), Backtracking (10), Heap (10), Stack / Monotonic Stack (10), Trie (5), Union-Find (5), Bit Manipulation (5). Total ~200 problems organized by pattern beats 500 random problems.