This page needs a newer browser to run its tools. You can still read everything here.

Data Structures & Algorithms (DSA) Module 21

Algorithms in practice interview questions

Interview questions on algorithms in practice: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

19 questions: 5 warm-ups and 14 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

What are spatial and temporal locality, and why do caches depend on them?

Answered in the lesson Why constant factors matter: caches and locality
Fresher to mid

Why can an algorithm with a worse Big-O run faster in practice?

Answered in the lesson Why constant factors matter: caches and locality
Fresher to mid

What does external merge sort do in each of its two phases, and why is it used?

Answered in the lesson Data that does not fit: external sort, streams
Fresher to mid

Why do databases store tables and indexes as B-trees rather than as binary search trees or hash tables?

Answered in the lesson Data structures inside real software
Fresher to mid

What do you ask before choosing a data structure for a new feature?

Answered in the lesson Choosing the right data structure

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Mid to senior

A billing job walks a linked list of 5 million order objects every second to add up their amounts, and profiling shows it waiting on memory rather than computing. Estimate what one walk costs and explain how you would restructure the data.
What it tests

Pointer chasing and cache misses, estimating a memory-bound loop from the latency of one read, and choosing a contiguous layout without losing what the list was for.

First step

Treat the walk as a chain of dependent reads. Nodes allocated over months are scattered, so most steps miss every cache and wait about 100 ns for main memory: 5 million × 100 ns is about half a second per walk, which explains a job that barely keeps up. Then ask what the list is used for besides the total.
Follow-ups
- The list exists because orders are inserted in the middle. Does that change your answer?
- How would you show that the change worked?
- Could you avoid the walk altogether?
From the lesson Why constant factors matter: caches and locality
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Senior to staff

A service answers 2 million lookups a second by binary search over a sorted array of 200 million 8-byte keys, and it has become too slow. Without changing the O(log n) bound, how would you make each lookup faster? Estimate the gain.
What it tests

How binary search uses the caches, why its deep levels miss, and layouts that cut misses: blocked nodes in the style of a B-tree, a breadth-first order, and overlapping the misses of several lookups.

First step

Count the reads before changing anything: log₂ of 200 million is about 28 comparisons per lookup. The first dozen probe the same few thousand middle keys, which stay cached; the last four fall inside one cache line; the ten or so in between land on a different line for every key and mostly miss. Estimate the time from those misses.
Follow-ups
- Why does a layout with 16 keys per node help, in numbers?
- Lookups arrive in batches of 1,000. What does that let you do?
- When is a hash table the better answer?
From the lesson Why constant factors matter: caches and locality
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

You must sort a 500 GB file of 64-bit customer IDs on a machine with 16 GB of RAM and an SSD that reads and writes about 1 GB/s. How many runs and passes will external merge sort make, how much data moves, and roughly how long will it take?
What it tests

Sizing runs from memory, choosing the fan-in from buffer sizes, counting passes, and turning bytes moved into time with the disk's bandwidth.

First step

Leave memory for the program and buffers: with about 12 GB usable, phase 1 writes ⌈500 ÷ 12⌉ = 42 runs. A 42-way merge needs only 42 read buffers, so one merge pass suffices. Two passes that each read and write 500 GB move 2 TB; at 1 GB/s that is about 2,000 seconds before any CPU time.
Follow-ups
- The IDs have many duplicates and the output must keep each ID once. What changes?
- How would you use 8 cores?
- What would change on a spinning disk?
From the lesson Data that does not fit: external sort, streams
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

Forty servers each log 250 million requests a day. Report the 100 client IP addresses with the most requests, using a few megabytes of memory per server and one central job. Which summary do you keep, what can go wrong, and how accurate is the result?
What it tests

Choosing a mergeable heavy-hitter summary, its error bound in numbers, merging across servers, and confirming candidates exactly.

First step

Work out the scale first: 10 billion requests a day, and an IP in the top 100 is likely to send well over a million. Per server, a Misra–Gries summary with a few thousand counters, or a count-min sketch with a heap of candidates, fits in megabytes. Then decide how the central job merges forty summaries without losing the bound.
Follow-ups
- What is the error bound of your summary, in requests?
- Could an IP that is just below the cut-off on every server be missed?
- How would you produce exact counts for the final 100?
From the lesson Data that does not fit: external sort, streams
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Pick 1,000 events uniformly at random from a stream whose length you do not know in advance, in one pass and with memory for 1,000 events. Give the algorithm and prove that every event has the same chance of being chosen.
What it tests

Reservoir sampling, an invariant proved by induction, and spotting tempting rules that bias the sample.

First step

Keep the first 1,000 events. For the i-th event after that, keep it with probability 1,000 / i, replacing a randomly chosen event of the sample. Then state the invariant to prove: after i events, each of them is in the sample with probability 1,000 / i.
Follow-ups
- Why is replacing a random slot with probability 1/2 wrong?
- The stream is split across 10 machines. How do you combine their samples?
- How would you sample with weights, such as the bytes of each request?
From the lesson Data that does not fit: external sort, streams
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A PostgreSQL table holds 300 million orders. Queries look orders up by customer, report on date ranges of the last few days, and search the free-text delivery notes for words. Which index would you build for each query, and what does each cost?
What it tests

Matching index types to query shapes, estimating index depth and size, and the costs of indexes on writes, storage and maintenance.

First step

Classify the three queries: equality on a key, a range on a value that rises with insertion time, and membership of words inside a text. Each shape has a documented index type, so name the type, then estimate how deep or large it gets at 300 million rows and what every insert now pays.
Follow-ups
- Why not one hash index for the customer lookups?
- The date range sometimes covers two years. Does your choice change?
- Inserts are slower since the indexes were added. What would you measure?
From the lesson Data structures inside real software
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A Python service builds a JSON response by iterating over a dict, and a client parses the fields by position. After the service is rewritten in Go, the client breaks on some requests but not others. Explain why, and how you would fix it on both sides.
What it tests

Which map orders the languages guarantee, why depending on an unpromised order is a latent bug, and fixing it with a defined order or a schema.

First step

Separate what each language promises. Python has guaranteed insertion order for dicts since 3.7, so the Python service always produced the same order. The Go specification leaves map iteration order unspecified and allows it to differ between loops, so the rewrite can emit fields in a different order on every request.
Follow-ups
- Why does the bug appear on some requests and not others?
- Would sorting the keys fix it for good?
- How do you stop a repeat when other services are ported?
From the lesson Data structures inside real software
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

The Linux CFS scheduler kept runnable tasks in a red-black tree ordered by virtual runtime. A colleague says a binary heap would be simpler and just as fast. Compare the two for the scheduler's operations, and say what you would choose.
What it tests

Deriving the structure from the operations, the cost of arbitrary removal in a heap, caching the minimum, and weighing simplicity against the operations a real scheduler performs.

First step

List what the scheduler does: take the task with the smallest virtual runtime, put the running task back, add a task that wakes up, and remove a task that blocks, exits or moves to another processor. A heap does the first three in O(1) or O(log n); the fourth decides the comparison.
Follow-ups
- How would you make removal from a heap O(log n)?
- How can the tree find the minimum in O(1)?
- Does the answer change for a processor that runs only two or three tasks?
From the lesson Data structures inside real software
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A game has 10 million players. Scores change 50,000 times a second, the top 100 are shown 1,000 times a second, and players ask for their rank 5,000 times a second. Which structures would you use, and what does each operation cost?
What it tests

Deriving structures from operations and frequencies, why a heap or a hash map alone fails, order-statistic trees or counting over score values, and estimates in steps a second.

First step

Price the obvious designs first. A hash map of scores updates in O(1) but answers a rank by scanning 10 million players, 5 × 10¹⁰ visits a second at 5,000 rank queries. A heap gives the top 100 but not a rank. So the rank query decides: it needs an ordered structure that can count the players above a score.
Follow-ups
- Scores are whole numbers from 0 to 1,000,000. Does that change your design?
- How would you shard the leaderboard across several machines?
- Two players have the same score. What rank does each see?
From the lesson Choosing the right data structure
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A search box suggests the 5 most popular product names that start with what the user has typed, over 2 million products, at 20,000 requests a second, and popularity changes every hour. Compare a sorted list with binary search against a trie, and choose.
What it tests

Prefix queries as ranges in sorted order, the cost of ranking the matches, caching the top results per trie node, memory, and updates.

First step

Notice that the prefix query has two parts: finding the products that match, and choosing the 5 most popular among them. A sorted list does the first with two binary searches, about 21 steps each, but a one-letter prefix matches tens of thousands of names, all of which must be ranked. Ask what makes the second part cheap.
Follow-ups
- How much memory does the trie take, and how could you shrink it?
- Popularity changes every hour. How do you update the cached results?
- Users mistype. What changes?
From the lesson Choosing the right data structure
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A colleague wants to replace a Python list of 100,000 order IDs with a linked list, because new IDs are inserted in the middle and "inserting into a linked list is O(1)". Evaluate the proposal with numbers, and say what you would measure.
What it tests

The hidden cost of finding the insertion point, constant factors of pointer chasing against block moves, and choosing by measurement.

First step

Ask where the O(1) comes from: a linked list inserts in O(1) only once you hold the node before the insertion point. Finding that node by walking from the head costs O(n), on average 50,000 steps of pointer chasing, while the list finds the point by binary search and moves the tail with one block copy.
Follow-ups
- When is a linked list the better choice?
- The inserts become 10,000 a second at 10 million IDs. What then?
- How would you benchmark the two fairly?
From the lesson Choosing the right data structure
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

In a coding interview you are given a problem you have never seen. Walk through what you do in the first ten minutes, before writing any code, and what you say out loud.
What it tests

A repeatable method: restating the problem and constraints, examples, a brute force with its cost, finding the bottleneck, and communicating while doing it.

First step

Restate the problem in your own words and ask about the input: its size, duplicates, empty input, the range of values. Work two small examples by hand, one of them an edge case, and confirm the expected outputs with the interviewer before thinking about speed.
Follow-ups
- You cannot see any approach better than the brute force. What now?
- The interviewer gives a hint that does not seem to fit. How do you use it?
- How do you decide when to start coding?
From the lesson How DSA is tested: GATE, assessments, interviews
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

In an online assessment your solution passes the sample tests but fails 4 of 10 hidden tests: 2 with a wrong answer and 2 with a time limit. What do you check, and in what order, with 25 minutes left?
What it tests

Reading verdicts, edge cases and overflow, complexity against the constraints, and triage under time pressure.

First step

Treat the two verdicts separately. A time limit means the complexity, or a hidden linear operation inside a loop, does not fit the largest inputs: compare your algorithm's step count with the constraints. A wrong answer on hidden tests usually means an edge case the samples missed: empty input, one element, duplicates, extremes.
Follow-ups
- Which edge cases would you try first, and why?
- How do you find a hidden O(n) inside a loop?
- Would you rather fix the wrong answers or the time limits first?
From the lesson How DSA is tested: GATE, assessments, interviews
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

An assessment problem allows n up to 2 × 10⁵ with a 2-second limit. You have an O(n²) solution. Will it pass in C++? In Python? What would you do, and what would you submit, with 20 minutes left?
What it tests

Turning constraints into a step budget per language, the cost of n² at this size, and choosing between improving and submitting.

First step

Count the steps: n² / 2 is 2 × 10¹⁰ comparisons at n = 2 × 10⁵. At about 10⁸ simple steps a second for compiled code, that is about 200 seconds in C++, and about ten times longer in CPython, against a limit of 2 seconds. Neither passes the large tests, so the question becomes what earns the most points in 20 minutes.
Follow-ups
- Which complexity would pass, in each language?
- Is it worth submitting the O(n²) version at all?
- Could a faster language alone rescue the solution?
From the lesson How DSA is tested: GATE, assessments, interviews
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

The lessons of this module

Why constant factors matter: caches and locality Free lesson, Pro answers: 25 minutes
Data that does not fit: external sort, streams Free core, Pro depth: 11 of 30 minutes free
Data structures inside real software Free core, Pro depth: 10 of 25 minutes free
Choosing the right data structure Free core, Pro depth: 10 of 25 minutes free
How DSA is tested: GATE, assessments, interviews Free intro, Pro: 6 of 20 minutes free

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track

Warm-up questions

What are spatial and temporal locality, and why do caches depend on them?

Why can an algorithm with a worse Big-O run faster in practice?

What does external merge sort do in each of its two phases, and why is it used?

Why do databases store tables and indexes as B-trees rather than as binary search trees or hash tables?

What do you ask before choosing a data structure for a new feature?

Questions with model answers

A billing job walks a linked list of 5 million order objects every second to add up their amounts, and profiling shows it waiting on memory rather than computing. Estimate what one walk costs and explain how you would restructure the data.

A service answers 2 million lookups a second by binary search over a sorted array of 200 million 8-byte keys, and it has become too slow. Without changing the O(log n) bound, how would you make each lookup faster? Estimate the gain.

You must sort a 500 GB file of 64-bit customer IDs on a machine with 16 GB of RAM and an SSD that reads and writes about 1 GB/s. How many runs and passes will external merge sort make, how much data moves, and roughly how long will it take?

Forty servers each log 250 million requests a day. Report the 100 client IP addresses with the most requests, using a few megabytes of memory per server and one central job. Which summary do you keep, what can go wrong, and how accurate is the result?

Pick 1,000 events uniformly at random from a stream whose length you do not know in advance, in one pass and with memory for 1,000 events. Give the algorithm and prove that every event has the same chance of being chosen.

A PostgreSQL table holds 300 million orders. Queries look orders up by customer, report on date ranges of the last few days, and search the free-text delivery notes for words. Which index would you build for each query, and what does each cost?

A Python service builds a JSON response by iterating over a dict, and a client parses the fields by position. After the service is rewritten in Go, the client breaks on some requests but not others. Explain why, and how you would fix it on both sides.

The Linux CFS scheduler kept runnable tasks in a red-black tree ordered by virtual runtime. A colleague says a binary heap would be simpler and just as fast. Compare the two for the scheduler's operations, and say what you would choose.

A game has 10 million players. Scores change 50,000 times a second, the top 100 are shown 1,000 times a second, and players ask for their rank 5,000 times a second. Which structures would you use, and what does each operation cost?

A search box suggests the 5 most popular product names that start with what the user has typed, over 2 million products, at 20,000 requests a second, and popularity changes every hour. Compare a sorted list with binary search against a trie, and choose.

A colleague wants to replace a Python list of 100,000 order IDs with a linked list, because new IDs are inserted in the middle and "inserting into a linked list is O(1)". Evaluate the proposal with numbers, and say what you would measure.

In a coding interview you are given a problem you have never seen. Walk through what you do in the first ten minutes, before writing any code, and what you say out loud.

In an online assessment your solution passes the sample tests but fails 4 of 10 hidden tests: 2 with a wrong answer and 2 with a time limit. What do you check, and in what order, with 25 minutes left?

An assessment problem allows n up to 2 × 10⁵ with a 2-second limit. You have an O(n²) solution. Will it pass in C++? In Python? What would you do, and what would you submit, with 20 minutes left?