A DSA round is not a memory test. The interviewer wants to hear you name the pattern, justify the data structure, and state the complexity before you write anything. These are the questions that come up, answered in that order — because that order is what is being graded.
What is Big O notation, and what does it actually measure?
It describes how the work grows as the input grows, ignoring constants and lower-order terms — so an O(n) algorithm is one whose cost roughly doubles when the input doubles. It is a statement about growth, not speed: an O(n²) algorithm can beat an O(n log n) one on small inputs, which is why libraries switch to insertion sort below a threshold.
The follow-upThen: what about best, average and worst case? Quicksort is O(n log n) on average and O(n²) in the worst case — knowing where the worst case comes from (a bad pivot) is the real question.
The average cost per operation across a long sequence, when individual operations vary. Appending to a dynamic array is usually O(1) but occasionally O(n) for a resize; because capacity doubles, those resizes get rarer, and n appends cost O(n) in total — so each is amortised O(1).
How do you decide between an array, a hash map and a tree?
By the access pattern. Need index access and cache-friendly scanning — array. Need membership or counting with no ordering — hash map, O(1) average. Need sorted order, ranges, or "the nearest key below x" — a balanced tree, at O(log n). Naming the trade you are accepting matters more than the choice.
Patterns that solve most questions
5 questions
Recognising the pattern is most of the interview. Writing it is the easy part.
When the array is sorted, or sorting it does not break the question, and you are looking for a pair, a triple, or an in-place partition. Order lets each comparison rule out many candidates at once, which turns a nested loop into one pass: O(n) time and O(1) space.
Java
int[] twoSumSorted(int[] a, int target) {
int left = 0, right = a.length - 1;
while (left < right) {
int sum = a[left] + a[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++; // need a bigger sum
else right--; // need a smaller sum
}
return new int[]{-1, -1};
}
What is the sliding window technique, and why is it O(n)?
Consecutive windows overlap almost entirely, so instead of recomputing each one you update the previous answer — add the entering element, drop the leaving one. In the variable-size version you expand the right edge and shrink the left while the window is invalid; it is O(n) because the left pointer only moves forward, so across the whole run it advances at most n times in total.
The follow-upThen: when does it fail? With negative numbers and a sum condition, because shrinking the window can increase the sum. That is when you switch to prefix sums with a hash map.
Prefix sums plus a hash map. A subarray sums to k exactly when prefix[j] - prefix[i] = k, so while scanning you ask how many earlier prefixes equalled current - k. O(n) time, O(n) space, and it handles negative numbers, which a sliding window cannot.
Java
Map<Integer,Integer> seen = new HashMap<>();
seen.put(0, 1); // the empty prefix - forgetting this is the classic bug
int running = 0, count = 0;
for (int v : a) {
running += v;
count += seen.getOrDefault(running - k, 0);
seen.merge(running, 1, Integer::sum);
}
Floyd's algorithm: a slow pointer moving one node at a time and a fast one moving two. If there is a cycle they must eventually meet inside it; if the fast pointer reaches null there is none. O(n) time, O(1) space — the point of the question is the space, since a hash set of visited nodes also works but costs O(n).
The follow-upThen: find where the cycle starts. Reset one pointer to the head and advance both one step at a time; they meet at the cycle's entry.
BFS explores level by level with a queue, so it finds the shortest path in an unweighted graph — that is the deciding factor. DFS goes deep with a stack or recursion, and suits cycle detection, topological sort, connected components and anything about paths or backtracking. Both are O(V + E).
Data structures
4 questions
Expect a follow-up on cost for every one of these.
A tree where every left descendant is smaller than the node and every right one is larger, giving O(log n) search, insert and delete. What breaks it is insertion order: inserting sorted data produces a chain, and every operation degrades to O(n). Self-balancing variants — AVL, red-black — restructure on insert to keep the height logarithmic.
A complete binary tree where every parent is smaller (min-heap) or larger (max-heap) than its children, stored in a plain array. It gives O(1) access to the extreme element and O(log n) insert and remove. It is the answer whenever a question involves "top k", a priority queue, or a running median.
Count with a hash map in O(n), then keep a min-heap of size k while scanning the counts — O(n log k), better than sorting everything at O(n log n) when k is small. If the counts are bounded, bucket sort by frequency does it in O(n).
What is the difference between a stack and a queue, and where does each appear?
A stack is last-in-first-out; a queue is first-in-first-out. Stacks appear in expression parsing, undo, DFS, and the monotonic-stack pattern behind "next greater element". Queues appear in BFS, scheduling, and sliding-window maximum via a deque.
Recursion and dynamic programming
4 questions
The hardest round for most freshers, and the most learnable.
What makes a problem a dynamic programming problem?
Two properties together: overlapping subproblems — the same smaller problem is solved repeatedly — and optimal substructure — the best answer is built from the best answers to those subproblems. If subproblems never repeat, it is plain divide and conquer, not DP.
What is the difference between memoisation and tabulation?
Memoisation is top-down: write the recursion, cache each result. It is easier to derive and only computes the states you actually reach, at the cost of recursion depth. Tabulation is bottom-up: fill a table in order, no recursion, and it often allows dropping to O(1) space by keeping only the last row.
The follow-upA good answer says how to move between them: get it right with memoisation, then convert to tabulation if the stack depth or constant factor matters.
Name the base case first and check it terminates. Then assume the recursive call already works for a smaller input and write the one step that uses it — trying to trace the whole call tree in your head is what makes recursion feel hard. State the recurrence out loud before writing code; interviewers score that.
Depth-first search over choices, where you undo a choice after exploring it and abandon a branch as soon as it cannot lead to a valid answer. Subsets, permutations, N-Queens and Sudoku are all the same skeleton: choose, recurse, un-choose. The pruning is what makes it fast enough to matter.
Sorting, searching and strings
8 questions
Reliably asked, and reliably answered badly on the follow-up.
How does binary search work, and where does it go wrong?
On a sorted array, compare the middle element and discard half the range each step: O(log n). It goes wrong in three places — computing the midpoint as (lo + hi) / 2 can overflow (use lo + (hi - lo) / 2), the loop condition < versus <= decides whether the last element is ever examined, and forgetting to move a bound produces an infinite loop.
Java
int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // overflow-safe
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
The follow-upThen: binary search on the answer. When a problem asks for the minimum value that satisfies a monotonic condition, you binary search the answer space rather than an array — that is the version interviews actually test.
Merge sort is O(n log n) always, stable, and needs O(n) extra space — which is why it is used for linked lists and external sorting. Quicksort is O(n log n) on average with O(log n) stack space and much better constants, but degrades to O(n²) on a bad pivot. Library sorts usually combine them: quicksort with a guard that switches to heapsort, or a stable merge sort for objects.
What does it mean for a sort to be stable, and when does it matter?
Equal elements keep their original relative order. It matters whenever you sort more than once to get a multi-level ordering — sort by name, then by score, and stability is what preserves the name order within each score. Without it, the first sort is lost.
How would you check whether two strings are anagrams?
Count characters in one pass, incrementing for the first string and decrementing for the second, then confirm every count ended at zero. O(n), against O(n log n) for sorting both. State your alphabet assumption — a fixed int[26] is only valid for lowercase ASCII; anything else needs a map.
How do you find the longest palindromic substring?
Expand around each of the 2n-1 centres — n single characters and n-1 gaps — keeping the longest match. O(n²) time, O(1) space. Forgetting the even-length centres is the standard bug: it finds "aba" and never "abba". Manacher's algorithm gets to O(n) and is worth naming.
Iteratively with three pointers — previous, current, next — relinking one node per step: O(n) time, O(1) space. The recursive version is shorter and costs O(n) stack. Interviewers ask because it is the smallest problem where losing a pointer loses the whole list.
Java
Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next; // save before overwriting
head.next = prev;
prev = head;
head = next;
}
return prev;
}
How would you find the middle of a linked list in one pass?
Two pointers again: advance one by one node and the other by two. When the fast pointer reaches the end, the slow one is at the middle. The same slow/fast idea answers cycle detection and "the kth node from the end".
What is a trie, and when is it the right structure?
A tree keyed by character, where a path from the root spells a prefix. Lookup is O(length of the key), independent of how many words are stored, and it makes prefix queries — autocomplete, dictionary matching — natural in a way a hash map cannot. The cost is memory: a node per character per branch.
Learn it properly firstIf any answer needed more than a paragraph, the structured lessons go deeper.
Most candidates know the material and still stumble when asked out loud. Take a DSA mock interview where the interviewer follows up on what you actually say.