50 DSA Interview Questions and Answers (2026)

DSA is the single biggest filter in technical interviews, regardless of company size or which language the role uses. The same core data structures and algorithmic patterns show up everywhere: at startups, mid-size product companies, and FAANG alike.

The candidates who do well aren't the ones who've memorized 500 individual LeetCode problems. They're the ones who recognize patterns: "this is a sliding window problem," "this needs two pointers," "this is a graph problem in disguise." Roughly 80 to 90 percent of interview problems map onto a handful of recurring patterns once you learn to see them.

These 50 questions cover both layers: the conceptual fundamentals every candidate should know cold, and the pattern-driven coding problems that make up the bulk of real interviews, each with working code and stated time/space complexity. If you're also preparing for object-oriented design rounds, our OOP interview questions guide covers the four pillars, SOLID principles, and design patterns.

Fundamental questions test whether you understand trade-offs before writing code. Interviewers use these to assess whether you think about WHY you reach for a particular data structure, not just whether you can use one.

A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. The choice of data structure directly determines how fast your operations run and how much memory your program uses.

The classic interview framing: the same logical problem (storing a collection of items) can be solved with an array, a linked list, a hash map, or a tree, but each choice has dramatically different performance characteristics for insertion, deletion, and lookup. Picking the wrong structure for the access pattern your problem actually needs is one of the most common reasons candidates get a working solution that's too slow.

Why interviewers ask this first: it tests whether you think about trade-offs before writing code, rather than defaulting to the same structure (usually an array or a hash map) for every problem regardless of fit.

Linear data structures arrange elements sequentially, where each element connects to its previous and next neighbor in a single line. Arrays, linked lists, stacks, and queues are all linear. You can traverse the entire structure in one pass, start to end.

Non-linear data structures organize elements hierarchically or as a network, where an element can connect to multiple other elements in non-sequential ways. Trees and graphs are non-linear. There is no single "start to end" traversal order; you choose a traversal strategy (BFS, DFS, in-order, etc.) based on what you need.

This distinction matters because the algorithms you reach for differ completely. Linear structures favor simple iteration. Non-linear structures require explicit traversal algorithms (recursion, BFS queues, DFS stacks) since there's no single natural order to visit every element.

Big-O notation describes how an algorithm's running time or space requirement grows as the input size grows, in the worst case. It abstracts away machine-specific constants and focuses on the growth rate, which is what actually matters as input scales from 10 elements to 10 million.

Common complexity classes, from best to worst: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2^n) exponential, O(n!) factorial.

Interviewers care because a "correct" solution that's O(n²) when an O(n log n) or O(n) solution exists is usually considered an incomplete answer at any company that takes the technical round seriously. They are testing whether you can reason about scalability, not just produce output that matches expected test cases.

Time complexity measures how the running time of an algorithm grows relative to input size. Space complexity measures how the memory usage grows relative to input size, including any extra data structures the algorithm allocates (not counting the input itself, which is usually excluded from the count).

A very common interview follow-up: "can you do this in O(1) space?" For the reverse example, yes, by reversing in place with two pointers swapping elements:

This time/space trade-off question comes up constantly: many problems can trade extra memory (a hash map, a visited set) for faster time, or vice versa, and naming that trade-off explicitly is a strong signal in interviews.

An abstract data type defines the behavior and operations a structure supports, without specifying how those operations are implemented. A data structure is the concrete implementation that fulfills that contract.

The classic example: a Stack is an ADT. It defines push, pop, and peek operations with LIFO (last-in-first-out) behavior. You can implement that Stack ADT using an array or a linked list, two completely different concrete data structures fulfilling the same abstract contract.

Both classes satisfy the same Stack ADT contract with different underlying implementations and different trade-offs (array-backed stacks have better cache locality; linked-list-backed stacks avoid resizing costs).

Arrays win when you need fast random access by index and the size is roughly known upfront. Linked lists win when you need frequent insertions/deletions at the beginning or in the middle, and don't need fast random access.

A common follow-up: "why are arrays generally faster in practice for most real-world code, even when Big-O analysis suggests linked lists should be competitive?" The answer is cache locality. Array elements sit in contiguous memory, so the CPU can prefetch them efficiently. Linked list nodes are scattered across memory (pointer chasing), causing cache misses that Big-O notation doesn't capture at all.

Amortized complexity describes the average performance of an operation over a sequence of operations, even when some individual operations are much more expensive than others. It's the answer to "but doesn't resizing make array append slow sometimes?"

The classic example is dynamic array append (Python's list.append(), Java's ArrayList.add()). Most appends are O(1): there's room, you just place the new element. But occasionally, the array is full and must be resized, which means allocating a new larger array and copying every existing element, an O(n) operation.

Because the array typically doubles in size when it resizes, expensive resize operations become exponentially rarer as the array grows. When you average the total cost of n appends across all n operations, it works out to O(1) per operation on average, even though some individual operations are O(n). This is what "amortized O(1)" means, and it's worth being able to explain the doubling-strategy reasoning, not just cite the term.

Hash maps provide average O(1) lookup, insertion, and deletion by key, compared to O(n) for searching an unsorted array or O(log n) for a sorted array with binary search. Use a hash map whenever you need fast lookups by some key value rather than by position/index.

The catch interviewers want you to name: hash map performance assumes a good hash function with minimal collisions. In the worst case (many keys hashing to the same bucket), operations degrade to O(n). Hash maps also use more memory per element than arrays (storing the hash table structure itself), and they don't preserve insertion order by default in many languages (though Python's dict and JavaScript's Map do preserve insertion order as of recent language versions, which is itself a common trivia question).

Array and string problems are the bread and butter of coding interviews. These eight questions cover the most commonly asked problems and the patterns (hash map lookups, prefix/suffix, sliding window, two pointers) that solve the majority of array-based interview problems.

This is the single most commonly asked coding interview question across every company tier. The pattern: hash map for O(1) complement lookups.

Time: O(n). Space: O(n).

The brute-force O(n²) approach checks every pair with nested loops. The hash map approach is the expected "optimized" answer: as you iterate, you check whether the complement of the current number has already been seen, which turns the nested-loop search into a single pass with O(1) lookups.

Time: O(n). Space: O(1).

The key insight (Kadane's algorithm): at each position, decide whether extending the current subarray (current_sum + num) is better than starting fresh from the current element alone (num). If current_sum ever goes negative, starting fresh is always at least as good, so the running sum effectively "resets" itself through the max() comparison without needing an explicit reset condition.

Time: O(n). Space: O(1) extra (excluding the output array itself).

The pattern: prefix and suffix products. The first pass computes, for each index, the product of all elements to its LEFT. The second pass multiplies in the product of all elements to its RIGHT. Combined, each position ends up with the product of everything except itself, without ever dividing.

Time: O(n log n), dominated by the sort. Space: O(n) for the result.

The pattern: sort first, then a single linear pass. Sorting by start time guarantees that any interval that could possibly overlap with the current merged interval will be checked immediately next, since intervals further along in the sorted order start even later.

Time: O(n). Space: O(min(n, charset size)).

The pattern: sliding window. Expand the window by moving right forward. When a repeat is found, shrink the window from the left until the repeat is removed, then continue expanding. This avoids re-checking substrings from scratch, which is what makes the brute force O(n³) approach collapse down to O(n).

Time: O(n). Space: O(1) for fixed alphabet size (or O(k) for k distinct characters).

The pattern: frequency counting with a hash map. An alternative O(n log n) solution sorts both strings and compares them directly, which is simpler to write but asymptotically slower, worth mentioning to show you know the optimized approach exists.

Time: O(n). Space: O(1).

The pattern: two pointers, one tracking where the next non-zero element should be placed (insert_pos), one scanning through the array. This is a common variant of the broader "partition in place" pattern, the same underlying idea used in the Dutch national flag problem and certain quicksort partition steps.

Time: O(n). Space: O(1).

The pattern: reverse-based rotation. Reversing the entire array, then reversing each of the two resulting segments separately, produces the rotated result without any extra array allocation. It's a favorite "do you know a clever trick beyond the obvious approach" follow-up after a candidate first proposes the simpler O(n) extra-space solution.

Linked list problems test pointer manipulation skills, and stack/queue problems test whether you understand LIFO and FIFO behavior. The fast/slow pointer pattern introduced here shows up across multiple seemingly unrelated problems.

Time: O(n). Space: O(1).

This is one of the most fundamental linked list questions and a building block for many more complex linked list problems (reverse in groups of k, reverse a sublist, palindrome checks). The key insight: you need to save next before overwriting current.next, otherwise you lose your way forward through the list.

Time: O(n). Space: O(1).

The pattern: fast and slow pointers (also called the tortoise and hare algorithm). The slow pointer moves one step at a time, the fast pointer moves two steps. If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle. If there's no cycle, the fast pointer reaches the end (None) first.

This is a top-tier interview pattern specifically because it solves the problem in O(1) space, compared to the more obvious O(n) space solution using a hash set to track visited nodes. Naming both approaches and explaining why the pointer trick wins on space is a strong answer.

Time: O(n + m). Space: O(1) extra (reusing existing nodes).

The dummy node pattern shown here (a placeholder head node that gets discarded at the end via dummy.next) is a common technique that simplifies linked list code by avoiding special-case handling for the very first node.

Time: O(n). Space: O(n) for the stack in the worst case.

The pattern: stack-based matching. Every opening bracket gets pushed. Every closing bracket must match the most recently pushed opening bracket (LIFO order), which is exactly the behavior a stack provides natively. This pattern generalizes to any "matching pairs in nested order" problem.

Time: O(1) for both get and put. Space: O(capacity).

This is a frequently asked "design" question testing whether you know to combine a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering to track recency), or know that your language's standard library already provides this combination (Python's OrderedDict). Many interviewers expect you to implement the doubly linked list + hash map combination manually, so be ready to explain (or implement) that version if asked to go deeper.

Time: O(1) amortized for both operations. Space: O(n).

This question tests understanding of how LIFO and FIFO behaviors relate. Moving every element from stack1 to stack2 reverses their order once, which converts the LIFO behavior of a single stack into the FIFO behavior a queue needs. The amortized analysis (Q7) applies directly here: most dequeues are O(1) because stack2 already has elements ready, with the occasional O(n) transfer when stack2 empties out.

Time: O(n). Space: O(1).

This reuses the same fast/slow pointer pattern from cycle detection (Q18). The fast pointer moves twice as fast as the slow pointer, so by the time the fast pointer reaches the end, the slow pointer has covered exactly half the distance. This is a strong example of how learning one pattern (fast/slow pointers) unlocks multiple seemingly unrelated problems.

Tree and graph problems test recursive thinking and traversal strategy selection. Recognizing that a 2D grid problem is secretly a graph connectivity problem (Q28) or that a dependency problem is secretly cycle detection (Q29) is the kind of pattern recognition that separates strong candidates.

In-order visits left subtree, then the node, then right subtree. For a BST, in-order visits nodes in sorted ascending order.

Pre-order visits the node first, then left subtree, then right subtree. Useful for creating a copy of a tree.

Post-order visits left subtree, then right subtree, then the node. Useful for deleting a tree safely (children before parent).

All three run in O(n) time and O(h) space for the recursion stack, where h is the tree height (O(log n) for a balanced tree, O(n) for a completely skewed tree, which is itself a common follow-up about worst-case space).

Breadth-First Search (BFS) explores all neighbors of a node before moving to the next level, using a queue. It explores level by level, outward from the starting point.

Depth-First Search (DFS) explores as far as possible down one branch before backtracking, using a stack (or recursion, which uses the call stack implicitly).

Use BFS when you need the shortest path in an unweighted graph, or level-by-level processing (binary tree level order traversal, finding the minimum number of steps to reach a target).

Use DFS when you need to explore all possible paths, detect cycles, solve connectivity problems, or when the problem is naturally recursive (tree traversals, backtracking problems).

Time: O(n). Space: O(h) for the recursion stack.

The common mistake candidates make: checking only that <code>root.left.val < root.val < root.right.val</code> at each node locally, without tracking the valid RANGE inherited from ancestors. A node deep in the left subtree must be less than EVERY ancestor it's a left descendant of, not just its immediate parent. The recursive range-passing approach shown here handles this correctly.

Time: O(n). Space: O(h).

The pattern: post-order recursion that "bubbles up" findings. Each recursive call returns either None (neither target found), one of the target nodes (found exactly one), or the LCA itself (both targets found in different branches below). The genuinely clever part: if a node's left and right recursive calls both return non-None, that node IS the LCA.

Time: O(rows cols). Space: O(rows cols) worst case for the recursion stack.

This is the canonical "grid as implicit graph" problem. Each cell is a node, and adjacency is implicit (up/down/left/right neighbors) rather than an explicit adjacency list. Recognizing that a 2D grid traversal problem is secretly a graph connectivity problem is a key pattern-recognition skill this question specifically tests.

Time: O(V + E). Space: O(V + E) for the graph plus O(V) for the recursion stack.

This is the classic real-world application of topological sort and cycle detection in a directed graph: if course A requires course B, and course B (eventually) requires course A, the schedule is impossible because of the circular dependency. The visiting set (currently in the recursion path) versus visited set (fully processed, confirmed cycle-free) distinction is the key technique for detecting cycles in directed graphs specifically.

Time: O(n). Space: O(h).

This looks trivial, and it largely is, but it's frequently asked as a warm-up question to establish baseline recursive thinking. The recursive structure here (base case: empty tree has depth 0; recursive case: 1 plus the deeper of the two child subtrees) is the template that nearly every tree depth/height/balance problem builds on.

Time: O(n). Space: O(h).

Three base cases to get right: both null (match), exactly one null (no match), and value mismatch (no match). Many candidates forget the "exactly one is null" case and write code that crashes with a null pointer exception, which is itself a useful thing to watch for during an interview.

Adjacency lists are the default choice for most real-world graphs, which tend to be sparse (relatively few edges compared to V² possible edges). Adjacency matrices make sense when the graph is dense or when O(1) edge-existence checks matter more than memory efficiency.

This is the highest-leverage section of the entire guide. Learning these 8 patterns covers the vast majority of coding interview problems. Each entry describes the pattern, names the signals that indicate when to use it, and points back to the concrete problem earlier in this guide that demonstrates it.

Use two indices that move through a structure based on specific conditions, typically reducing an O(n²) brute-force approach to O(n).

Signals: sorted arrays, finding pairs that satisfy a condition, palindrome checks, or removing duplicates in place.

This is distinct from the hash-map Two Sum (Q9), which works on unsorted arrays. When the array is already sorted, two pointers achieves the same O(n) time with O(1) space instead of O(n) space, which is a common "can you do it without extra space" follow-up.

Maintain a "window" (a contiguous range defined by two pointers) over an array or string, expanding or shrinking it based on problem conditions, rather than recomputing from scratch for every possible subarray.

Signals: contiguous subarrays/substrings, problems mentioning "consecutive elements," finding the longest/shortest substring or subarray satisfying a condition.

Already demonstrated in Q13 (Longest Substring Without Repeating Characters). The pattern avoids the brute-force approach of checking every possible window from scratch (typically O(n²) or O(n³)), instead reusing work as the window slides, getting down to O(n).

Use two pointers moving at different speeds through a structure (usually a linked list), commonly one step versus two steps per iteration.

Signals: cycle detection, finding the middle element, detecting palindromic structure in a linked list.

Already demonstrated in Q18 (cycle detection) and Q23 (finding the middle). The key insight that unifies both use cases: the speed difference between the two pointers creates a predictable mathematical relationship (the fast pointer covers exactly twice the distance) that you can exploit without needing extra memory to track positions explicitly.

Explore all possible solutions by making a choice, recursing into the consequences of that choice, and undoing the choice (backtracking) if it doesn't lead anywhere, to try the next option.

Signals: "generate all combinations/permutations," "find all possible ways to," constraint satisfaction problems (N-Queens, Sudoku), or exhaustive search where you need every valid solution.

Time: O(2^n) for subsets specifically. Space: O(n) for the recursion depth.

The append-recurse-pop sequence is the universal backtracking template. The pop() after the recursive call is what makes it backtracking rather than just plain recursion: it explicitly undoes the choice before trying the next option in the loop.

Beyond standard binary search (Q3), several common variants come up specifically because they require adapting the basic template rather than applying it directly. Search in a rotated sorted array:

Time: O(log n). The key insight: at each midpoint, one half of the array is guaranteed to be properly sorted (even though the whole array isn't). Determine which half is sorted, then decide whether the target could lie in that sorted half or must be in the other half.

The unifying signal across all binary search variants: any time you can eliminate half the remaining search space based on a comparison, binary search (or a variant of it) is probably the right tool, even when the input isn't obviously "search for X in a sorted array."

Produce a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge from A to B, A comes before B in the ordering.

Signals: dependency ordering, task scheduling, build systems, course prerequisites (already shown in Q29), or any problem describing a DAG ordering constraint.

Time: O(V + E). Space: O(V + E).

This uses Kahn's algorithm (BFS-based): start with nodes that have no incoming edges (in-degree 0), process them, decrement the in-degree of their neighbors, and add any neighbor that reaches in-degree 0 to the queue. If the final result doesn't include every node, a cycle exists.

A monotonic stack maintains elements in either strictly increasing or strictly decreasing order, popping elements that violate the monotonic property before pushing a new element.

Signals: "next greater element," "daily temperatures," problems asking for the nearest element satisfying a comparison in a specific direction.

Time: O(n). Space: O(n).

The naive brute force is O(n²): for each element, scan forward until you find something bigger. The monotonic stack gets this down to O(n) because each element is pushed and popped at most once.

Union-Find efficiently tracks which elements belong to which connected group (set) and supports two operations: union (merge two groups) and find (determine which group an element belongs to), both close to O(1) with path compression.

Signals: counting connected components, detecting cycles in an undirected graph, problems about grouping/merging entities based on relationships (friend circles, network connectivity).

Time: nearly O(1) amortized per operation with path compression. Space: O(n).

Union-Find is often the cleanest solution for "are these two things connected" problems, frequently outperforming repeated BFS/DFS when you need to answer many connectivity queries interspersed with updates to the graph structure over time.

Dynamic programming is where mid-level and senior candidates get separated. The key is recognizing when a problem has optimal substructure and overlapping subproblems, then deciding between top-down (memoization) and bottom-up (tabulation) approaches.

Dynamic Programming (DP) solves complex problems by breaking them into smaller overlapping subproblems, solving each subproblem once, and storing (memoizing) the result to avoid redundant recomputation.

Two conditions signal a DP problem: optimal substructure (the optimal solution can be built from optimal solutions to its subproblems) and overlapping subproblems (the same subproblems get solved repeatedly in a naive recursive approach).

Signals in a problem statement: "find the maximum/minimum," "count the number of ways," or "is it possible to," combined with a sense that smaller versions of the same problem feed into the answer for larger versions.

Time: O(n). Space: O(1).

This is structurally identical to Fibonacci (Q41): the number of ways to reach step n equals the ways to reach step n-1 plus the ways to reach step n-2. Recognizing "this is secretly Fibonacci" is itself a useful pattern-matching skill.

Time: O(amount * len(coins)). Space: O(amount).

The DP array dp[i] stores the minimum coins needed to make amount i. For each amount, try every coin denomination that fits, and take the best result from "1 coin plus however many coins were needed for the remainder." This bottom-up (tabulation) style fills the array from smaller amounts up to the target.

Time: O(m n). Space: O(m n).

This is the canonical 2D DP problem. dp[i][j] represents the LCS length considering the first i characters of text1 and the first j characters of text2. If the characters match, extend by 1. If they don't, take the best achievable by dropping one character from either string. This same 2D DP table structure underlies many string-comparison problems (edit distance, longest common substring).

Time: O(n capacity). Space: O(n capacity).

For each item, you choose to either include it (and gain its value while using up its weight) or exclude it (keeping the previous best for the same capacity). This is the foundational pattern behind a huge family of "subset selection with a constraint" problems.

Time: O(n). Space: O(1).

At each house, you decide: skip it (carry forward the best result so far, prev1) or rob it (take its value plus the best result from two houses back, prev2 + num, since you can't rob adjacent houses). This is a simpler relative of Knapsack (Q45) with an implicit "adjacency" constraint instead of a weight constraint.

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. This works for some problems (like coin change with standard US denominations: 1, 5, 10, 25) but fails for others where local optimality doesn't guarantee global optimality.

The classic counter-example: Coin Change (Q43) with coins [1, 3, 4] and target 6. A greedy approach takes the largest coin first: 4, leaving 2, then two 1-coins, for a total of 3 coins (4+1+1). But the optimal answer is 2 coins (3+3).

Greedy is faster (usually O(n) or O(n log n)) and simpler when it works, but it only works when the problem has the "greedy choice property," where a locally optimal choice never prevents reaching the globally optimal solution. DP is the safer, more broadly correct tool when you're not certain that property holds, at the cost of higher time/space complexity. Being able to identify specifically WHY greedy fails on a counter-example is what separates a strong answer here.

This final category covers sorting algorithm trade-offs, advanced binary search variants, and the meta-question about what mistakes to avoid during the interview itself.

Most languages' built-in sort functions use a hybrid approach (Python's Timsort, a hybrid of merge sort and insertion sort). "Stable" matters when you need to preserve the relative order of equal elements, which comes up in multi-key sorting.

A common follow-up: "why does quicksort have a worst case of O(n²) despite being fast in practice?" Answer: a poor pivot choice (always picking the first or last element on an already-sorted array) degenerates into O(n²). Randomized pivot selection or median-of-three pivot selection mitigates this in practice.

Building on Q37, two other binary search variants come up consistently. Finding the first/last occurrence in a sorted array with duplicates:

Binary search on the answer space (rather than searching an actual array): used for problems like "find the minimum capacity needed" or "find the square root," where you binary search over a RANGE OF POSSIBLE ANSWERS, checking at each midpoint whether that candidate answer satisfies the problem's constraints.

Recognizing when a problem is "secretly" a binary search on the answer space, rather than a search through an explicit array, is a more advanced pattern-recognition skill that separates strong mid-level candidates.