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.
Complexity
Asked in the first two minutes, and again after every solution you write.
Basic
Q1
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.
Intermediate
Q2
What is amortised complexity?
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).
Intermediate
Q3
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
Recognising the pattern is most of the interview. Writing it is the easy part.
Intermediate
Q4
When do you use the two pointer technique?
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.
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};
}
Intermediate
Q5
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.
Advanced
Q6
How do you count subarrays with a given sum?
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.
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);
}
Intermediate
Q7
How do you detect a cycle in a linked list?
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.
Intermediate
Q8
When do you use BFS and when DFS?
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
Expect a follow-up on cost for every one of these.
Intermediate
Q9
What is a binary search tree, and what breaks it?
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.
Intermediate
Q10
What is a heap, and what is it for?
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.
Advanced
Q11
How would you find the top k frequent elements?
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).
Basic
Q12
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
The hardest round for most freshers, and the most learnable.
Advanced
Q13
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.
Advanced
Q14
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.
Intermediate
Q15
How do you write a correct recursion?
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.
Advanced
Q16
What is backtracking?
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
Reliably asked, and reliably answered badly on the follow-up.
Intermediate
Q17
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.
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.
Intermediate
Q18
Compare merge sort and quicksort.
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.
Intermediate
Q19
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.
Basic
Q20
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.
Advanced
Q21
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.
Intermediate
Q22
How do you reverse a linked list?
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.
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;
}
Intermediate
Q23
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".
Advanced
Q24
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.
If any answer above needed more than a paragraph, the structured lessons go deeper: DSA on JBattle Learn.