Data Structures & Algorithms interview questions and answers

DSA interview questions organised by tested pattern: arrays, hashing, rotated arrays, dynamic programming, graphs, heaps and sliding windows, so you learn transferable coding-round techniques instead of memorising puzzles.

57 published across 16 topics.

Data Structures & AlgorithmsA 26-minute read on how the topic fits together, before the questions.Data structures and algorithms fundamentals54 short answers on one page, for revising rather than studying.

Arrays & Strings

4 questions

In-place manipulation, prefix sums, and the string-scanning problems that open most coding rounds.

mediumCoding

Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?

Uniform sampling needs a gapless array you can index, so a deletion cannot leave a hole and cannot shift the tail. You overwrite the hole with the last element and shrink by one, which costs a fixed amount of work but silently moves another member, so the map from value to index must be corrected for the element that moved and not only for the one removed.

6 minmid, senior

mediumCoding

Find the largest sum obtainable from a contiguous run of elements in an array.

Walk the array once, keeping the best sum ending at the current element - that element alone, or that element added to the best run ending before it. The maximum of those is the answer, and the familiar version that resets the running sum to zero is wrong when every element is negative.

4 minentry, mid, senior

mediumCoding

For every index, give me the product of all the other elements - and you cannot use division.

Two passes over the array do it: a left-to-right pass writes the product of everything before each index into the output, then a right-to-left pass multiplies in a running product of everything after it. Linear time, no working array beyond the output, and it is unbothered by zeros.

3 minentry, mid, senior

mediumCoding

Rotate an array k positions to the right, in place.

Rotate array by k in place by normalising k modulo n, reversing the whole array, then reversing the first k and remaining n-k elements. It is O(n) time, O(1) extra space, and avoids the cyclic-replacement pitfalls unless write count matters. Use this ARRAYS answer to show the decision, trade-off, and evidence rather than a memorised definition.

4 minentry, mid, senior

All 4 in Arrays & Strings

Hashing & Maps

4 questions

Trading memory for time with hash maps and sets, plus the collision and ordering caveats interviewers probe.

mediumCoding

You have thirty minutes to write a hash table from scratch. What do you get to skip, and what will the interviewer not let you skip?

Use separate chaining and skip iterators, shrinking, thread safety and null keys, saying so aloud. You cannot skip a non-negative bucket index, an equality check after the hash matches, overwriting an existing key, unlinking the head of a chain, or a resize that rehashes every entry against the new capacity.

5 minentry, mid

mediumCodingConcept

Count the subarrays whose elements sum to k, where the values may be negative.

Subarray Sum Equals K is solved with prefix sums and a hash map: for each running sum, count earlier prefixes equal to sum-k. This is O(n) time and works with negative numbers, unlike a sliding window. Use this hashing answer to show the decision, trade-off, and evidence rather than a memorised definition.

4 minmid, senior

mediumCoding

Group a list of words so that words which are anagrams of each other end up together. What is your key, and what does it cost?

Every anagram class needs one canonical key: either the word's letters sorted, or a vector of letter counts. The counting key is cheaper but only if the counts are separated when they are turned into a string, because concatenating them lets a count of eleven and a count of one swap places unnoticed.

5 minentry, mid, senior

mediumCodingConcept

A cache must evict the least recently used entry and every operation has to be O(1). Which two structures do you need, and why is one of them not enough?

A hash map from key to a doubly linked list node, over one recency-ordered list. The map answers find-by-key, the list answers find-the-oldest, and neither answers the other in constant time. The detail that decides the answer is that the map stores the node rather than the value, which is what makes unlinking on a hit a fixed number of pointer writes.

5 minmid, senior, staff

All 4 in Hashing & Maps

Two Pointers & Sliding Window

4 questions

Linear-time techniques for subarray and pair-finding problems that naively look quadratic.

mediumCodingConcept

You need the longest palindrome in a string. Where does centre-expansion cost you, and what does it cost?

Every palindrome is fixed by its centre, and a string of length n has 2n minus 1 of them once the gaps between characters are counted. Expanding outwards from each is O(n squared) worst case in O(1) extra space, and the worst case is reached by a string of one repeated character, where the expansions from every centre run all the way to the boundary.

6 minmid, senior

mediumCoding

Find the length of the longest substring without repeating characters.

Maintain a sliding window with a map from character to its last seen index; when a duplicate appears inside the current window, jump the left boundary past that previous occurrence rather than shrinking one step at a time, giving a single-pass O(n) solution. It also connects two pointers to the point an interviewer is testing.

2 minentry, mid, senior

mediumCoding

Return every distinct triplet in the array that sums to zero.

Sort the array, fix each element as an anchor, then converge two pointers inwards from both ends of the remaining range. The sort is asymptotically free against the O of n squared scan, and it is what lets you skip duplicate values positionally instead of deduplicating a set of results afterwards. It also connects sorting to the point an interviewer is testing.

4 minentry, mid, senior

mediumCoding

Given the heights of a row of bars, work out how much rainwater is trapped between them. Do it in constant extra space.

Water above a bar is the smaller of the tallest bar to its left and the tallest to its right, minus its own height. Walking inwards from both ends and always advancing the shorter side works because that side's running maximum is the binding constraint there, whatever heights remain unseen in the middle.

5 minmid, senior, staff

All 4 in Two Pointers & Sliding Window

Linked Lists

2 questions

Pointer surgery: reversal, cycle detection, merging, and the off-by-one errors that reveal carelessness.

mediumCoding

Detect whether a linked list has a cycle, and return the node where the cycle begins.

Advance one pointer by one node and another by two; if they ever coincide there is a cycle. Then reset one pointer to the head and step both one node at a time, and they meet at the cycle's entry. O(n) time, O(1) space, and the arithmetic behind the second phase is what the follow-up asks for.

4 minentry, mid, senior

mediumCoding

Remove the nth node from the end of a singly linked list in a single pass.

Run one pointer n nodes ahead of another, then advance both until the leader reaches the last node, leaving the follower on the predecessor of the node to unlink. A dummy node in front of the head is what removes the separate case for deleting the head itself.

4 minentry, mid, senior

Stacks & Queues

4 questions

Monotonic stacks, deques, and the parsing and next-greater-element families.

hardCodingConcept

Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.

Keep a stack of bar indices with strictly increasing heights. When a bar no taller than the top arrives, pop: the popped bar's rectangle runs from just after the new top to just before the current bar. A height-zero sentinel flushes the stack. Each index is pushed once and popped at most once, so it is O(n).

5 minmid, senior

hardCodingConcept

Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?

Keep a deque of indices whose values strictly decrease from front to back. Each step drops the front if it has left the window, pops smaller or equal values from the back, then appends. The front is the window maximum. Each index enters and leaves once, so it is amortised O(n), against O(n log k) for a balanced tree.

5 minmid, senior

mediumCodingConcept

Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.

Push arrivals onto an inbound stack and serve departures from an outbound one, transferring everything across only when the outbound stack is empty. Transferring on every dequeue instead reverses the order and breaks FIFO, and the empty-only rule is also what makes the amortised cost constant.

4 minentry, mid, senior

mediumCodingConcept

For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.

Scan left to right holding a stack of indices whose answers are still unknown, kept strictly decreasing by value. Each new element resolves and pops everything smaller than it, then pushes itself. Every index is pushed once and popped at most once, so the scan is O(n) despite the inner loop.

4 minmid, senior

All 4 in Stacks & Queues

Trees & BSTs

3 questions

Traversals, recursion versus iteration, balancing, and lowest-common-ancestor problems.

mediumCoding

Find the lowest common ancestor of two nodes in a binary tree.

Recurse post-order and return the node whose left and right subtrees each report back one target; if only one side reports back, propagate that result upwards. This is O(n) time and O(h) stack. A BST lets you descend by value comparison instead, and parent pointers reduce it to list intersection. It also connects recursion to the point an interviewer is testing.

5 minentry, mid, senior

mediumCoding

Serialise a binary tree to a string and reconstruct exactly the same tree from it. What has to be in the string?

A bare traversal is not enough, because two different trees can produce identical node sequences. Emitting an explicit marker for every absent child makes a preorder walk unambiguous, and reading it back is the same walk consuming tokens in the same order from a single cursor.

5 minmid, senior, staff

mediumCoding

Given a binary tree, decide whether it is a valid binary search tree.

Every node must fall inside an open interval inherited from its ancestors, not merely compare correctly against its own two children. Recurse carrying a low and high bound, tightening one of them at each descent, or walk in-order and require the sequence to be strictly increasing.

5 minentry, mid, senior

All 3 in Trees & BSTs

Graphs

6 questions

BFS, DFS, topological sort, shortest paths, and union-find, including spotting a graph problem in disguise.

mediumCodingConcept

Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?

Plain Dijkstra minimises cost alone, so it can return a cheap route with too many stops, and settling each city once discards a dearer route that still has stops to spare. Make the state city plus edges used, or run Bellman-Ford for exactly K + 1 rounds, each reading only the previous round's distances.

5 minmid, senior, staff

mediumCoding

Count the islands in a grid of land and water. Then land is added one cell at a time, and you report the island count after every addition.

For one grid, number of islands is a flood fill: each unvisited land cell starts a BFS or DFS, O(rows x cols). For land arriving cell by cell, rerunning that is too slow, so use union-find. Each new cell adds one island, and each union with a neighbour in a different set removes one, at near-constant amortised cost.

5 minmid, senior

mediumCodingConcept

How do you decide between BFS and DFS - and how do you recognise a graph problem that nobody described as a graph?

Choose BFS when the question asks for the fewest steps in an unweighted graph or when you need results in distance order; choose DFS when you are asking a structural question such as connectivity, cycles or topological order, or when the graph is deep and narrow.

4 minmid, senior, staff

mediumCodingConcept

Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.

Dijkstra fails with negative edges because it finalises the current cheapest node under the assumption that no later edge can reduce it. Use Bellman-Ford when negative edges are possible, and reject graphs with negative cycles. It also connects shortest paths to the point an interviewer is testing.

5 minmid, senior, staff

mediumCodingConcept

You are given a set of tasks and their prerequisites. Produce a valid execution order, or report that none exists.

Topological sort produces an order only for a directed acyclic graph. Kahn's algorithm removes zero-in-degree nodes and detects a cycle when fewer than all nodes are emitted; DFS detects a cycle with a back edge into the active stack. Use this GRAPHS answer to show the decision, trade-off, and evidence rather than a memorised definition.

6 minmid, senior

mediumCoding

You are given a grid of letters and a word. When do you stop searching, and what stops you revisiting the same cell?

You stop on four conditions and the success check has to come first, before bounds or character comparison. Revisiting is prevented per path rather than globally: a cell is marked when the search enters it and unmarked when the search leaves it, because a cell that ruins one candidate path has to remain available to a different one.

6 minmid, senior

All 6 in Graphs

Heaps & Priority Queues

4 questions

Top-K, streaming medians, and merges where partial ordering beats full sorting.

mediumCodingConcept

You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?

Nothing about correctness - it works. It throws away the sortedness you were given and pays O of N log N to rebuild it, where merging costs O of N log k, and it requires every element resident at once where a merge requires k. On lists that arrive as streams the second objection is the one that disqualifies it outright.

6 minmid, senior, staff

mediumCodingConcept

Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?

Keep a min-heap holding exactly the K largest values seen. Its root is the answer, so the query is a read rather than a search, and every value smaller than that root is discarded the moment it arrives. What you give up is the ability to answer for any K larger than the one you chose, which is why the first thing to establish is whether K is fixed.

6 minmid, senior, staff

mediumCodingDesign

Numbers arrive one at a time and after each one I want the running median. How would you keep it?

Split the values across a max-heap of the lower half and a min-heap of the upper half, so the median is read off one or both tops. Balancing by size alone is what breaks it: a new value has to enter through the heap it belongs to by value and be transferred across, never pushed into whichever heap is currently smaller.

5 minmid, senior, staff

mediumCodingConcept

Return the k most frequent elements from a large stream of values. Why not just sort by frequency?

Count occurrences, then push counts through a min-heap capped at size k, evicting the smallest whenever the heap overflows. That is O(n log k) rather than the O(n log n) of a full sort, it needs only k items resident at once, and it works on a stream you cannot re-read.

4 minmid, senior

All 4 in Heaps & Priority Queues

Dynamic Programming

6 questions

Dynamic programming interview questions on state definition, recurrence transitions, memoisation, tabulation and recognising overlapping subproblems.

hardCodingConcept

Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?

Bitmask DP keeps the cheapest cost for every subset of workers already used. The number of set bits says which task comes next, so there are 2^n states with n moves each, O(2^n * n) time and 2^n memory. At n = 20 that is about a million states, where trying all 20! orders is hopeless.

4 minmid, senior

hardCoding

Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?

Russian doll envelopes reduce to a longest increasing subsequence. Sort by width ascending, break width ties by height descending, then run the O(n log n) tails search on heights. The descending tie-break stops equal widths from chaining, since a strictly increasing run then takes at most one per width.

4 minmid, senior, staff

mediumCodingConcept

Edit distance where insert costs 1, delete costs 2 and replace costs 3. Define the DP state and the recurrence, and tell me what changes from the classic version.

The state is unchanged - the minimum cost to transform the first i characters of one string into the first j of the other - because the subproblem structure does not depend on what operations cost. Only the recurrence changes, adding a per-operation weight instead of a uniform 1, and the base cases become multiples of the insert and delete costs rather than i and j.

4 minmid, senior

mediumCoding

Given a set of coin denominations and a target amount, return the fewest coins that make it exactly. Why would you not just take the largest coin first each time?

Largest-coin-first fails on denominations like 1, 3 and 4, so you fill a table where entry i is the fewest coins making amount i and each entry takes the best over all denominations. The unreachable case needs a sentinel that survives being incremented, which rules out the maximum integer.

4 minentry, mid, senior

hardCoding

Find the length of the longest strictly increasing subsequence, then get it under quadratic time.

The quadratic dynamic programme asks for the best chain ending at each index. The faster version keeps one array where slot j holds the smallest possible tail of an increasing subsequence of length j plus one; that array stays sorted, so each element is placed by binary search for O of n log n.

6 minmid, senior, staff

mediumCodingConcept

How do you know a problem is dynamic programming?

Dynamic programming interview questions usually need overlapping subproblems, optimal substructure and a precise state definition. Define the minimum state, write the transition, then choose memoisation or tabulation based on dependency order.

5 minmid, senior

All 6 in Dynamic Programming

Greedy Algorithms

2 questions

Exchange arguments and proving a locally optimal choice is globally safe.

mediumCoding

Given a list of meetings with start and end times, pick the largest set of them that do not overlap.

Sort by finishing time and take every meeting that starts no earlier than the last one you took. Earliest start and shortest duration both look reasonable and both give provably smaller answers, and the exchange argument for earliest finish is what the question is really asking for.

4 minentry, mid, senior

mediumCodingConcept

How do you know a greedy choice is safe and not merely plausible?

A greedy choice is safe when you can show at least one optimal solution contains it, usually via an exchange argument that swaps an optimum's first choice for yours without losing anything. Interval scheduling by earliest finish time admits that swap; coin change with arbitrary denominations does not.

4 minmid, senior, staff

Recursion & Backtracking

2 questions

Permutations, combinations, constraint satisfaction, and pruning to keep search tractable.

hardCoding

Count the ways to place N queens on an N by N board so that no two attack each other.

One queen per row is forced, so search row by row and keep sets of used columns, used sums and used differences to reject a conflict before recursing. The anti-diagonal is the row plus column and the main diagonal the row minus column, and that difference must be shifted into range, not reduced with an absolute value.

5 minmid, senior, staff

mediumCoding

Generate every permutation of an array that may contain duplicates, then tell me how large the search tree is

Backtracking builds each candidate incrementally and undoes the last choice on return; duplicates are suppressed by sorting and skipping a repeated value whose identical predecessor is unused. The tree holds under e times n factorial nodes, so pruning only pays when it removes subtrees near the root. It also connects recursion to the point an interviewer is testing.

4 minmid, senior

Sorting & Searching

4 questions

Binary search on answers, custom comparators, and sorting internals still asked about.

mediumCoding

Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.

Binary search for the rotation point by comparing the middle element with the right end. If it is larger, the break lies to the right; otherwise it is at mid or before it. That is O(log n). With duplicates an equal comparison says nothing, so you drop the right end, and the worst case becomes O(n).

4 minmid, senior

mediumCoding

Shipping packages within D days minimises a maximum. Now place m sensors at fixed positions so the closest pair is as far apart as possible. What changes in the binary search?

It is still binary search on the answer, over the gap rather than the positions, but the predicate flips. A gap that works means every smaller gap works, so you want the last feasible value, which needs lo = mid with a ceiling midpoint. Sort first, check each gap greedily, and the cost is O(n log n + n log R).

5 minmid, senior

mediumCoding

Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D days

When you cannot construct the answer but can cheaply test a candidate, and that test is monotone, binary search the answer's numeric range instead of the input. The feasibility check here is greedy day-packing, giving O(n log S) time, and the whole implementation hinges on one loop invariant. It also connects monotonicity to the point an interviewer is testing.

5 minmid, senior, staff

mediumCoding

You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.

Search a rotated sorted array in O(log n) by finding which half is sorted at each midpoint, then keeping the half where the target can legally fall. With duplicates, equal endpoints can hide the pivot, so the worst case becomes linear.

5 minmid, senior, staff

All 4 in Sorting & Searching

Intervals

3 questions

Merging, overlap detection, and sweep-line scheduling problems.

mediumCoding

Given everyone's busy calendar, find the slots when all of them are free. What do you sort, and what breaks at the boundaries?

Pool every busy interval, sort by start, and sweep with a cursor marking the end of the busy block so far. Any start beyond the cursor opens a common free slot. Use half-open intervals so back-to-back meetings leave no zero-length gap, and clip to the working day. Sorting costs O(N log N), or O(N log k) with a heap.

5 minentry, mid, senior

easyCoding

Merge a list of overlapping intervals, and justify the key you sorted by

Sorting by start time is what reduces the merge to a single scan carrying one scalar, the end of the open block; sorting by end breaks it, and sorting by end is instead correct for maximum non-overlapping selection. Both run in O(n log n), and equal timestamps decide the answer.

4 minentry, mid, senior

mediumCoding

Given a list of meetings with start and end times, tell me the minimum number of rooms needed to hold all of them.

The answer is the maximum number of meetings running at once, found by sweeping the start and end times in sorted order and tracking a running count. The starts and ends can be sorted independently of each other, and a meeting ending exactly when another begins must free its room or you will overcount.

5 minentry, mid, senior

All 3 in Intervals

Bit Manipulation

3 questions

Masks, XOR tricks, and the low-level questions in systems-leaning interviews.

mediumCodingConcept

Every number in the array appears three times except one. Find the single number in O(1) extra space, and make sure it works for negatives.

Count, for each of the 32 bit positions, how many numbers have that bit set, and keep the count modulo 3. Tripled values contribute multiples of 3, so the bits with a remainder belong to the single number. Setting bit 31 makes a Java int negative, so negative answers come out right in O(32n) time and constant space.

5 minentry, mid, senior

mediumCodingConcept

Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.

Shifting and masking works only if the shift does not sign-extend, so a signed right shift on a negative value never terminates. Either shift with the unsigned operator or clear the lowest set bit with n and n minus 1, which terminates for every input including the minimum value.

4 minentry, mid, senior

easyCodingConcept

Every value in an array appears twice except one. Find it, and tell me when bit tricks are worth reaching for

XOR-folding the array leaves the unpaired value because a^a is 0 and XOR is commutative and associative, giving O(n) time and O(1) space under a precondition worth stating. That specific trick is narrow; masks used as integer sets are the part of bit manipulation that earns real work.

5 minentry, mid, senior

All 3 in Bit Manipulation

Tries & Advanced Strings

3 questions

Prefix trees, autocomplete, and pattern matching for search-heavy roles.

mediumCodingConcept

You need to find a substring in linear time and the interviewer will not accept a library call. What do you compute, and what goes wrong on a collision?

Rabin-Karp computes a polynomial hash of the pattern and a rolling hash of each text window, updated in constant time per step modulo a large prime. Equal hashes only nominate a candidate, so you compare characters before reporting it. Skip that check and a collision is a wrong answer; keep it and collisions cost time.

5 minmid, senior

hardCodingConcept

Find every occurrence of a pattern in a text without ever moving backwards through the text. What does your precomputed table hold?

Precompute, for each prefix of the pattern, the length of the longest proper prefix of the pattern that is also a suffix of that prefix. On a mismatch you fall back to that length instead of rewinding the text, which is what turns the quadratic naive scan into a linear one.

5 minmid, senior, staff

mediumDesignCoding

Design the data structure behind a search box's autocomplete. Why a trie, and when would you not use one?

A trie stores one node per character, so finding a prefix is a walk of length k and its completions are the subtree below it. It costs far more memory than the strings themselves, so a hash map still wins for exact lookup and a sorted array with binary search wins for a static dictionary.

6 minmid, senior, staff

All 3 in Tries & Advanced Strings

Complexity Analysis

3 questions

Deriving and defending time and space bounds, including amortised reasoning.

mediumCodingConcept

The assistant wrote a working solution and the interviewer asks for its complexity and one input that breaks it. How do you verify code you did not write?

Read every loop and recursive call, then price each line inside them, because the expensive part is often a library call such as pop(0), a list membership test or string concatenation. Aim inputs at that worst case and at the edges the samples skip, and compare against a slow, simple version on random inputs.

5 minmid, senior

mediumConcept

Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.

Dynamic array append is amortized O(1) because capacity doubling makes the resize copy costs form a geometric series below 2n over n appends, even though one individual append can still be O(n). Use this complexity analysis answer to show the decision, trade-off, and evidence rather than a memorised definition. It also connects amortised analysis to the point an interviewer is testing.

5 minmid, senior, staff

mediumConceptScenario

A nightly job took 40 minutes last month and takes two hours forty on twice the data. What do you conclude about its complexity, and what would you measure next?

A fourfold cost for a doubled input is consistent with quadratic growth, but two points fit infinitely many curves and a one-off cliff such as spilling out of memory produces the same ratio. Get a series of ratios across several doublings, then confirm the exponent against the code.

4 minmid, senior, staff

All 3 in Complexity Analysis