Data Structures & Algorithms

What this area actually covers

Data structures and algorithms is two questions asked together: how do you lay data out so the operations you need are cheap, and what sequence of steps gets you an answer without redundant work. A data structure is a layout plus the cost of its operations — a hash map buys constant-average lookup at the price of ordering and memory, a balanced binary search tree buys ordering back at logarithmic cost, an array buys cache locality at the price of insertion. An algorithm is a strategy over that data, and the interesting ones exploit some structure the naive approach ignores: sortedness, monotonicity, overlapping subproblems, or the fact that you only need the best K of something rather than all of it.

The interview scope is narrower than the academic field. You are expected to be fluent with arrays and strings, hash maps and sets, linked lists, stacks and queues, heaps, trees, graphs, and the technique families — two pointers, sliding window, binary search on the answer, dynamic programming, greedy, backtracking, union-find, monotonic stacks. You are not expected to derive amortised bounds for a Fibonacci heap.

Three things get wrongly bundled in. Competitive programming is a genuinely different sport, optimised for speed under contest constraints and reaching into number theory and geometry interviews do not touch. System design is a separate discipline with separate rounds. And language trivia — how CPython's list growth works — is a language question wearing an algorithms costume.

The sixteen topics underneath

This section is split into sixteen topics, and the split is not arbitrary. Roughly the first half is structures — layouts with costs, which you choose between — and the second half is techniques, which are strategies you apply once you have recognised the shape of a problem. It is worth reading them in the order below at least once, because several later topics assume you already have the earlier ones in your hands.

Arrays & Strings is where almost every coding round starts, because an array is the one structure every candidate has in every language and it needs no explanation. The topic covers in-place manipulation, prefix sums, and the family of single-pass scans over a string. It exists separately because the constraint that makes these problems interesting — do it without allocating a second array — is a constraint you will meet nowhere else, and it forces you to think about indices as state rather than as syntax.

Hashing & Maps is the single highest-yield topic on the list, because converting a nested loop into a hash lookup is both the most common interview improvement and the most common real one. Beyond the basic use, the topic covers what a hash map does not give you: no ordering, a worst case that is linear when keys collide, and a memory cost that is not small. Interviewers probe those caveats specifically because everyone knows the happy path.

Two Pointers & Sliding Window are two views of one idea, which is that when a predicate behaves monotonically as you move an index, you never have to go backwards. It is separated out because recognising the signal is a distinct skill from executing the technique, and the recognition step is what is being graded. Expect questions about subarrays with a constraint, pair-finding in a sorted array, and partitioning in place.

Linked Lists survive in interviews less for their practical value than because they expose carelessness with precision. Reversal, cycle detection with two pointers of different speeds, merging sorted lists and finding a midpoint all fit in a few lines and all have an off-by-one waiting in them. The topic exists as its own thing because the debugging discipline it demands — drawing the pointers on paper before typing — is the transferable part.

Stacks & Queues cover the problems where the order in which you process elements is the whole solution. Bracket matching and expression parsing are the classic stack family; the monotonic stack, which keeps its contents sorted by discarding elements that can never again be the answer, is the version that shows up in harder rounds and solves next-greater-element problems in one pass. Deques appear where you need both ends.

Trees & BSTs introduce recursion as a structural tool rather than a trick. Traversal orders, the difference between doing work before and after the recursive calls, converting a recursion into an explicit stack, and lowest-common-ancestor problems all live here. It is a separate topic from graphs because a tree's acyclicity lets you drop the visited set, and half of tree code is graph code with that simplification applied.

Graphs generalise trees and are where most candidates' recognition fails, because the hard part is noticing that a problem is a graph problem at all. Dependencies between build steps, mutual follows between users, a maze, a currency conversion chain and a state machine are all graphs. The topic covers breadth-first and depth-first search, topological ordering, shortest paths and union-find, along with the disguises.

Heaps & Priority Queues exist for the case where you need the extreme element repeatedly but never the whole order. Top-K selection, merging many sorted streams and maintaining a running median with two heaps facing each other are the recurring problems. It is worth its own topic because the instinct to sort everything is strong and usually wrong when you only need a few elements.

Dynamic Programming is the topic candidates fear, and the fear is mostly about presentation rather than difficulty. The work is defining what a state means, writing the transition between states, and then choosing between top-down memoisation and bottom-up tabulation. It is a separate topic because state definition is a skill in itself: get the state wrong and no amount of correct implementation recovers it.

Greedy Algorithms are the ones that are easy to write and hard to justify. Taking the locally best option is often correct and often subtly wrong, and the interview question is almost never "can you code this" but "why is this safe". The topic exists to teach the exchange argument — showing that any optimal solution can be transformed into your greedy one without getting worse — which is the standard proof shape.

Recursion & Backtracking covers exhaustive search done tidily: permutations, combinations, subsets, and constraint problems such as placing queens or filling a grid. The distinguishing skill is pruning, meaning abandoning a branch the moment it cannot lead to a valid answer, because the difference between a solution that finishes and one that does not is usually a single early return.

Sorting & Searching is partly foundational and partly a trap topic. You need custom comparators, you need to know which library sort is stable and what that guarantees, and you need enough of the internals to answer why merge sort is stable and quicksort is not. The high-value half is binary search on the answer, which applies to any problem with a monotonic feasibility test and is easy to miss.

Intervals are a small, self-contained family that appears far more often than its size suggests: merging overlapping ranges, detecting a conflict in a booking system, finding the minimum number of rooms for a set of meetings. It is its own topic because almost all of them collapse to the same first move — sort by one endpoint, then sweep — and once you see that, the family stops being difficult.

Bit Manipulation works directly on the binary representation rather than on the value, and it is disproportionately asked in systems-leaning and embedded interviews. Masks, shifts, the XOR identities that let you find a unique element without extra memory, and counting set bits are the standard content. It is a separate topic because none of it follows from anything else on this list.

Tries & Advanced Strings matter for autocomplete, prefix search and dictionary problems, where a hash map's inability to answer "which keys start with this" leaves a real gap. The topic covers the prefix tree and the pattern-matching techniques that come up in search-heavy roles. It is the most specialised structure here, and safe to leave until later unless you are targeting search or text infrastructure.

Complexity Analysis is placed last but used throughout, and it is the one topic that appears in every other round you will ever sit. It covers deriving a bound rather than recalling one, distinguishing worst case from average and amortised, accounting for the space your recursion consumes, and defending your analysis when an interviewer disputes it. If you only revise one topic here before a design interview, revise this one.

The vocabulary you will hit on day one

Most of the confusion beginners have with this subject is terminological rather than conceptual. The ideas are not difficult; the words are used loosely everywhere except in the one room where you are being graded on them. It is worth pinning them down before anything else, because an interviewer will assume you mean the precise thing.

Two of those rows carry more weight than the rest. Invariant is the word that turns an intuition into an argument: "the window always contains at most one of each character" is why a sliding-window solution is correct, and a candidate who can name the invariant has demonstrably designed the solution rather than recalled it. Amortised matters because it is the honest way to describe a dynamic array's push or a hash map's insert, both of which occasionally do expensive work and are cheap across any long run. Saying "constant time" about a dynamic array append is nearly right, and saying "amortised constant, because doubling makes the total copying work linear in the number of appends" is right in a way an interviewer notices.

The cost model underneath every structure

Before any technique family makes sense, you need the cost table in your head — not to recite it, but because choosing a structure is exactly choosing a row of it. Every structure is a bargain: it makes one or two operations cheap and pays for that somewhere else, and the somewhere else is what you have to be able to name.

Read the last column first. It is the one that answers interview follow-ups, and it is the one people skip. A hash map's worst case is linear because every key can collide into one bucket, which matters if an adversary controls your keys and does not matter in a coding round unless you are asked. A heap gives you the minimum in constant time and tells you nothing whatsoever about the second-smallest without doing work, which is precisely why "find the K largest" is a heap problem and "find the median of a stream" needs two heaps rather than one.

Big-O deliberately hides constant factors and memory hierarchy, and that omission is where theory and production diverge. A linked list and a dynamic array both traverse in linear time; the array is dramatically faster in practice at small and medium sizes because its elements sit next to each other and the processor's cache is designed for exactly that access pattern. A structure with a better asymptotic bound and terrible locality can lose to a linear scan for a long way up the size axis. You will not be asked to quantify that in an interview, but knowing it exists is what separates someone who has run code from someone who has read about it.

Where it sits in a real system

The honest answer is: mostly underneath you, already written by somebody else. When you call sort you get a hybrid someone spent years tuning; when you use a dictionary you get a hash table with a collision strategy and a resize policy you did not choose. Java's TreeMap is a red-black tree and you will very probably never write one. The abstractions are good and reimplementing them in production code is usually a mistake.

It surfaces in three places, and they are what make the subject more than an interview tax. The first is choosing between structures already available — realising the nested loop scanning a list for matches should be a set lookup, which is the most common real performance fix in application code. The second is recognising the shape of a problem: that a permissions hierarchy is a graph and a cycle in it is a bug, that a deduplication requirement over a stream is a sliding window, that a scheduling constraint is a topological sort. The third is crossing into the layer that builds the abstractions — query planners, storage engines, routing, compilers, ML infrastructure — where the algorithm is the product.

The second of those deserves an example, because it is the one that pays. A team ships a feature that checks, for each item in an incoming batch, whether it already exists in a list of previously seen identifiers. Written the obvious way it is a nested loop, and with a hundred items in each collection nobody notices. At ten thousand it is a hundred million comparisons per batch and the endpoint times out. The fix is one line — build a set from the second collection first, then test membership — and it is a fix nobody reaches for unless they carry the cost table above in their head. That is DSA in application code: not implementing anything, just knowing what a data structure costs.

Who does this work

Almost every engineering role uses DSA as background knowledge and a small minority uses it as the job. The engineers who genuinely implement algorithms daily work on databases and storage engines, compilers and runtimes, network routing, search and ranking infrastructure, quantitative trading, and the numerical kernels underneath machine learning. Their day involves reading papers, profiling, and arguing about constant factors and cache behaviour that Big-O deliberately hides.

For everyone else — most backend, frontend, mobile, platform and data engineers — a day looks like plumbing, and DSA appears as an occasional judgement call rather than a task. The asymmetry that makes this area strange is that the second group is far larger, yet is filtered on the first group's skill before being hired.

There is a third population worth naming: the people asking the questions. Coding rounds are administered by ordinary engineers on rotation, most of whom prepared for the interview themselves not long ago, working from a problem their company keeps in a shared bank along with a rubric. Understanding that changes how you behave in the room. Your interviewer is filling in a form with a small number of axes on it, they have usually seen this problem solved thirty times, and the thing they are least able to grade is silence. A partially complete solution narrated clearly scores better than a complete one produced without explanation, because the rubric has a communication axis and no axis for having finished early.

Demand, adoption and how that is changing

Demand is very high, and it is important to be plain about why: it is a hiring filter, not a reflection of daily work. Coding rounds survive because they are cheap to administer, apparently objective, comparable across candidates, and defensible to a hiring committee. That is an argument about interview logistics, not evidence the skill is used weekly. Anyone telling you that grinding problems is how you become a good engineer is selling something.

But the filter is not arbitrary either, and dismissing it entirely is the other mistake. What transfers is the pattern vocabulary. An engineer who has internalised what a graph traversal is will notice the mutual-follows feature is a connected-components problem; one who has not will write three nested loops and a bug. Knowing that binary search applies to any monotonic predicate, not just sorted arrays, is a genuine tool. Complexity reasoning transfers hardest of all, because "this is quadratic in the number of orders" is a sentence you will say in design reviews for the rest of your career.

What has changed recently is the format rather than the demand. Assistants that solve standard problems instantly have pushed many companies towards live rounds with heavy follow-up questioning, debugging exercises on existing code, or pairing sessions where explaining your reasoning under interruption is the point. That devalues memorised solutions specifically while leaving the underlying skill roughly where it was.

The practical consequence is that the shape of the round has widened even where the subject has not. A loop that once contained two identical algorithm problems is now more likely to contain one of them plus something adjacent: fixing a failing test in an unfamiliar file, extending a working solution to handle a constraint added halfway through, or reading a colleague's implementation aloud and saying where it breaks. All three reward the same underlying model of what code costs, and none of them reward having memorised an optimal solution.

How a technique family gets chosen

The skill that a coding round measures is not writing the solution. It is the ninety seconds between reading the statement and committing to an approach, and that period has a structure you can practise deliberately. You are looking for a small number of signals in the wording and the constraints, each of which rules a family in or out.

flowchart TD
    A[Read the statement and the input limits] --> B{Contiguous run over an array or string}
    B -- yes --> C[Sliding window or two pointers]
    B -- no --> D{Answer is a number with a monotonic feasibility test}
    D -- yes --> E[Binary search on the answer]
    D -- no --> F{Same subproblem recurs across choices}
    F -- yes --> G[Dynamic programming or memoisation]
    F -- no --> H[Model entities as nodes and traverse]

Follow the branch that is easiest to miss: the second one. Binary search is taught as a technique for finding a value in a sorted array, and the version that appears in interviews is usually the other one — you are searching the space of possible answers, and the array is never sorted because there is no array. "What is the smallest capacity that lets you ship everything in D days" is a binary search because feasibility is monotonic in capacity, and a candidate who only knows the sorted-array form will not see it.

The input limits are the other signal people underuse, and they are given to you for free. A constraint of n up to twenty is telling you an exponential solution over subsets is intended. n up to a few thousand accommodates a quadratic solution and often means a two-dimensional dynamic-programming table is expected. n up to a hundred thousand rules out quadratic and points at sorting, a single pass with a structure, or something logarithmic per element. Reading the limits before designing is a habit that costs nothing and eliminates whole families in a sentence.

What makes it hard

The first difficulty is that the skill is recognition, and recognition cannot be memorised. There are on the order of fifteen to twenty technique families and effectively unbounded problems, so the work is mapping an unfamiliar description onto a family within a couple of minutes. That mapping is built by solving a problem, then articulating why that technique applied — which invariant made it valid — and the second step is the one almost everybody skips.

Which leads directly to the plateau. Solving problem after problem produces steep early progress and then flattens, sometimes for months, because you are accumulating solutions instead of decision rules. The diagnostic is simple: take a problem you solved four weeks ago and, without looking at the code, say which family it belongs to and what in the statement told you. If you can recall the trick but not the signal, your count is going up and your ability is not. Two hundred problems worked this way beats a thousand skimmed.

Third, the transferable skill is complexity reasoning, and it is harder than the notation suggests. Stating that a solution is O(n log n) is easy; identifying what n is when there are three inputs, distinguishing worst case from amortised, noticing your recursion is exponential because it recomputes the same subproblem, and reasoning about space including the call stack — these are where candidates come apart. Interviewers lean on complexity questions because they are hard to bluff: you either built a model of what your code does or you are reading it off the page.

Fourth, the interview adds pressure the practice does not. Solving alone with unlimited time is a different task from narrating a partial idea to a stranger who interrupts, and that gap is where most well-prepared candidates fail. Where experience is not substitutable is judgement about constant factors: a theoretically superior structure that thrashes cache loses to a linear scan over a contiguous array at small sizes, and knowing where the crossover sits comes from having measured it.

The complexity mistakes that decide rounds

Because complexity is where candidates are separated, it is worth being specific about the four errors that recur, all of which are avoidable with a minute of thought.

The first is naming the wrong n. A problem with a grid has rows and columns, and "O(n squared)" is ambiguous when it could mean rows times columns or the square of one of them. A problem over a list of strings has a list length and a string length, and sorting it is not O(n log n) — it is O(n log n) comparisons, each of which costs up to the string length. State your variables before you state your bound and the ambiguity disappears.

The second is forgetting the space the language allocates for you. A recursive depth-first traversal of a skewed tree uses linear stack space even though you wrote no array. Slicing a string in most languages copies it, so a loop that takes a substring each iteration is quadratic in a way the source code does not show. Building a set of every prefix is quadratic in memory. Space bounds are asked less often than time bounds and are wrong more often when they are.

The third is confusing the cost of a call with the cost of what it does. Checking membership in a hash set is constant on average; checking membership in a list is linear, and both are one line of code that looks identical. Most accidental quadratics in real application code are exactly this: a cheap-looking call inside a loop that is not cheap.

The fourth is stopping at the bound and never sanity-checking it against the limits you were given. If the input can be a hundred thousand elements and your solution is quadratic, that is ten billion operations and it will not finish; noticing this yourself before the interviewer does is worth real credit, because it demonstrates that your complexity analysis is a tool you use rather than a label you attach at the end.

# Exponential: fib(n) recomputes fib(n-2) along two separate branches,
# so the call tree has roughly 2**n nodes.
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Linear: each subproblem is solved once and cached. The change is small;
# the change in the complexity class is total.
def fib_memo(n, seen=None):
    seen = {} if seen is None else seen
    if n < 2:
        return n
    if n not in seen:                       # the line that removes the branching
        seen[n] = fib_memo(n - 1, seen) + fib_memo(n - 2, seen)
    return seen[n]

The interesting thing about that pair is not the speed-up but the diagnosis. Nothing in the first function looks expensive line by line; the cost is entirely in the shape of the recursion, which is invisible unless you draw the call tree. "Overlapping subproblems" is the phrase for what you are looking for, and once you can spot it in a call tree you have most of dynamic programming, because memoising a correct recursion is usually a mechanical step afterwards.

Why study it

Study it if you are interviewing anywhere with a coding round, which is most places, because there is no way around the filter and it is a solved problem with a known method. Study it seriously if you want to work on infrastructure — databases, compilers, search, trading, ML systems — where it is the actual work and the interview is honest about that.

Some people can safely spend much less time here, and the pages that will not tell you this are the ones selling problem sets. If your loop is a take-home, a portfolio review or a domain conversation, your hours are better spent elsewhere. Senior and staff candidates should note that the coding round rarely decides their outcome — a competent, clearly explained solution is enough, and the design and behavioural rounds carry the weight. Specialists interviewed on their specialism — data engineers on SQL and modelling, SREs on debugging, mobile engineers on platform depth — need enough to clear a screen, not mastery. And anyone already employed, weighing a month of problems against a month of learning to operate distributed systems, should usually choose the latter unless the interview is imminent.

If you want to become a better engineer, this is not the fastest route. If you want to pass the gate standing in front of most engineering jobs, it is the only one.

What the room is actually grading

It helps to see the round as a sequence of exchanges rather than a task with a deadline, because the marks are distributed across the exchanges and not concentrated at the end. A strong candidate and a weak one often write similar final code; they diverge in the first five minutes and in the last five.

sequenceDiagram
    participant I as Interviewer
    participant C as Candidate
    I->>C: States the problem, often ambiguously
    C->>I: Restates it and asks about input size and edge inputs
    C->>I: Names a brute force and its cost out loud
    C->>I: States the invariant and the target complexity
    C->>I: Writes the code, then dry runs one awkward input
    I->>C: Adds a constraint that was not in the original
    C->>I: Says what changes and what the new cost would be

The exchange to look at is the sixth. The added constraint is where the round is decided at most companies, because it cannot be prepared for — it tests whether you understood your own solution well enough to modify it, or merely reproduced one. A candidate who has to start again from a blank editor when the constraint changes has told the interviewer that the first solution was recalled rather than derived.

Notice also what is missing from that sequence: any point at which the candidate is silent for ten minutes and then produces working code. That path exists and it scores badly, because the interviewer has nothing to write in the boxes marked communication and approach, and a hiring committee reading the feedback later sees only an outcome with no evidence behind it.

Your first hour

Do not open a problem list. Spend the hour building the artefact that makes later practice compound: a pattern-signal table, written by you, from problems you have solved.

Solve three easy problems of clearly different shapes — one two-pointer, one hash-map counting, one tree traversal. For each, once it passes, write the row before moving on:

Pattern       Sliding window
Signal        "longest / shortest contiguous subarray satisfying P"
Why valid     P is monotonic in window width, so shrinking from the
              left can never make an invalid window valid again
Complexity    O(n) time, O(k) space for the window state
Fails when    the subarray need not be contiguous  -> think DP
Solved        longest substring without repeating characters

The "why valid" and "fails when" rows are the whole exercise; anyone can fill in the pattern name. Then close your editor and, for each of the three, restate the signal from memory. You end the hour with three rows and a method — grow this to twenty rows over your preparation and the table, not the problem count, is what you will actually be revising the night before.

If you have a second hour, spend it differently: take one problem you have already solved and solve it again out loud, to a wall or a recording, without writing anything until you have finished describing the approach. The discomfort you feel doing that is precisely the gap between your practice conditions and your interview conditions, and it is cheaper to discover it now.

What this is not

It is not competitive programming, and the advice for the two diverges: contests reward speed and a much wider technique surface, interviews reward communicating a correct approach and its trade-offs.

It is not evidence of engineering ability, and treating a coding round as though it were is the mistake made in both directions — by candidates who conclude they cannot code, and by interviewers who conclude a strong solver will be a strong colleague. It measures one narrow thing under artificial conditions.

It is not a substitute for knowing your language and standard library well; the practical version of this skill is mostly choosing correctly among structures already provided, not writing them. Nor is it system design, though the two get bundled as "the technical rounds" — one asks for a provably correct function in twenty minutes, the other for a defensible architecture under stated ambiguity, and preparation for one does almost nothing for the other.

It is not a measure of raw intelligence either, which matters because candidates routinely draw that conclusion after a bad round. The strongest predictor of performance here is deliberate practice under conditions resembling the real thing, and the people who look effortless in a coding round have almost always done that practice somewhere you did not see.

And it is not, finally, about red-black trees. You will be asked to know that a balanced tree gives logarithmic ordered operations. You will almost certainly never be asked to implement the rebalancing, and if a page implies otherwise it is padding a curriculum.

Count how many patterns you can recognise from a problem statement, not how many problems you have solved — the first number is the skill and the second is only weakly correlated with it.