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

Data Structures & Algorithms (DSA) Module 20

Randomisation and hard problems interview questions

Interview questions on randomisation and hard problems: warm-ups, then what each harder question tests and how a good answer starts.

12 questions: 4 warm-ups and 8 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

What is the difference between a Las Vegas and a Monte Carlo algorithm?

Answered in the lesson Randomised algorithms: expected time, sampling
Fresher to mid

Why is the shuffle that swaps every position with a random position biased?

Answered in the lesson Randomised algorithms: expected time, sampling
Fresher to mid

What is the difference between NP-hard and NP-complete?

Answered in the lesson P, NP and NP-completeness
Fresher to mid

What is the difference between an approximation algorithm and a heuristic?

Answered in the lesson Coping with NP-hard problems

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 live quiz receives correct answers through an API at an unknown rate, possibly tens of millions in an hour. You must pick 10 winners uniformly among them as the answers arrive, and an auditor must be able to repeat the draw afterwards. How do you design it?
What it tests

Reservoir sampling on a stream of unknown length, its uniformity argument, and making a random draw repeatable and verifiable without letting anyone predict or rerun it.

First step

Separate the two needs. Choosing 10 uniformly without storing the stream is reservoir sampling with k = 10. Repeating the draw needs a generator whose seed is fixed before the stream opens but revealed only after it closes, plus a record of the order in which answers were accepted.
Follow-ups
- How do you show that every answer had a 10 / n chance?
- The answers arrive at 12 servers in parallel. What changes?
- How do you stop an operator from rerunning the draw until a friend wins?
From the lesson Randomised algorithms: expected time, sampling
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
Fresher to senior

A login flow emails a 6-digit code made with Python's random.randint(0, 999999). The same process hands out random 32-bit request ids to clients from the same module. Is the design safe? What do you change, and how do you test it?
What it tests

Knowing that seeded generators are predictable, spotting the leak through other outputs, choosing the secrets module, and testing code that uses secure randomness.

First step

Notice the shared generator: the request ids are its outputs, and 624 consecutive 32-bit outputs are enough to rebuild the Mersenne Twister's state and predict every later code. Then move the codes to secrets.randbelow and limit guesses, since a 6-digit code has only a million values.
Follow-ups
- Without the leak, how many guesses does an attacker need, and how do you limit them?
- How do you write a unit test for code that uses the secrets module?
- Is a UUID made with uuid4 safe as a password-reset token?
From the lesson Randomised algorithms: expected time, sampling
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

An interviewer asks for the longest simple path in a graph of 10⁵ vertices and 3 × 10⁵ edges. What do you say, and what do you ask before writing any code?
What it tests

Recognising an NP-hard problem behind a familiar name, giving the reduction from Hamiltonian path, and finding the special cases, a DAG, a tree or small n, that make it tractable.

First step

Say first whether the problem is easy in general, and why: compare it with the Hamiltonian path problem on the same graph. Then ask about structure before writing code: is the graph a DAG or a tree, and how large can n really be?
Follow-ups
- The graph turns out to be a DAG. Now what?
- It is a tree. Now what?
- n is at most 18. Now what?
- Why doesn't Bellman-Ford with every weight negated solve it?
From the lesson P, NP and NP-completeness
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A colleague notes that 0/1 knapsack is NP-complete, yet your O(nW) table solves it in polynomial time, so you must have proved P = NP. What is wrong with the argument?
What it tests

Measuring running time against the length of the input in bits, pseudo-polynomial time, and strong NP-hardness.

First step

Write down the size of the input: n numbers and a capacity W, which takes only about log₂ W bits to write. O(nW) is polynomial in the value of W but exponential in its length, since a b-bit capacity can be as large as 2ᵇ.
Follow-ups
- When is the O(nW) table the right tool anyway?
- Which NP-complete problems have no such table?
- Can knapsack be approximated within a factor of 1 + ε in polynomial time?
From the lesson P, NP and NP-completeness
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

Your team assigns 500 engineers to on-call shifts. Some pairs of engineers must never share a shift, and each engineer lists shifts they cannot take. Product wants an exact optimal scheduler. How would you show the problem is NP-hard, and what would you propose instead?
What it tests

Choosing a known NP-hard problem to reduce from, getting the direction right, keeping the translation polynomial, and turning the result into an engineering plan.

First step

Look for a known NP-complete problem inside it. With three shifts and no other rules, the pairs that must not share a shift form a graph, and a valid schedule is a 3-colouring of it. So reduce 3-colouring to the scheduling problem: every graph becomes engineers and conflicts.
Follow-ups
- Why is translating your problem into SAT not enough?
- Which special cases might still be polynomial?
- What would you build for 500 engineers?
From the lesson P, NP and NP-completeness
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Given 40 positive integers up to 10¹² and a target, decide within a few seconds whether some subset sums exactly to the target. Which algorithm do you use, what does it cost, and what breaks first as n grows?
What it tests

Seeing that the values are too large for a table, choosing meet in the middle, estimating its time and memory, and knowing where it stops.

First step

Rule out the table first: sums reach 4 × 10¹³, far too many columns. Then split the 40 numbers into two halves of 20. Each half has 2²⁰ ≈ 10⁶ subset sums, which fit in memory, can be sorted, and can be matched against each other.
Follow-ups
- How do you return the subset itself, not only yes or no?
- n grows to 60. Now what?
- Some numbers may be negative. What changes?
From the lesson Coping with NP-hard problems
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to staff

A dispatch team wants the best delivery route through 150 stops every morning, computed in under 10 seconds on one machine. What do you build, and what do you promise them about the route?
What it tests

Recognising the travelling salesperson problem, combining a construction with local search inside a time budget, and reporting quality against a lower bound instead of claiming the optimum.

First step

Name the problem: the shortest round trip through 150 stops is the travelling salesperson problem, which is NP-hard, and Held-Karp would need about 2¹⁵⁰ states. So the plan is a heuristic with a time limit, and the promise must be a measured bound, never "optimal".
Follow-ups
- Road distances are not symmetric. What changes?
- Each stop has a delivery time window. What changes?
- How do you show the team that a route is good?
From the lesson Coping with NP-hard problems
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A warehouse wants cameras at junctions so that every corridor is watched, using as few cameras as possible. The operations head wants a promise about how many cameras the plan might waste. What do you offer?
What it tests

Recognising vertex cover, giving an approximation with a proven factor and its proof, and knowing when an exact answer is affordable.

First step

Model junctions as vertices and corridors as edges: watching every corridor is a vertex cover, NP-complete in general. Then look for an algorithm whose cover is provably at most a fixed factor above the smallest, and check whether the layout has structure, such as a tree, that allows the exact answer.
Follow-ups
- The corridor network is a tree. Now what?
- There are 60 junctions. Can you afford the optimum?
- Cameras at some junctions cost more. What changes?
From the lesson Coping with NP-hard problems
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

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

Warm-up questions

What is the difference between a Las Vegas and a Monte Carlo algorithm?

Why is the shuffle that swaps every position with a random position biased?

What is the difference between NP-hard and NP-complete?

What is the difference between an approximation algorithm and a heuristic?

Questions with model answers

A live quiz receives correct answers through an API at an unknown rate, possibly tens of millions in an hour. You must pick 10 winners uniformly among them as the answers arrive, and an auditor must be able to repeat the draw afterwards. How do you design it?

A login flow emails a 6-digit code made with Python's random.randint(0, 999999). The same process hands out random 32-bit request ids to clients from the same module. Is the design safe? What do you change, and how do you test it?

An interviewer asks for the longest simple path in a graph of 10⁵ vertices and 3 × 10⁵ edges. What do you say, and what do you ask before writing any code?

A colleague notes that 0/1 knapsack is NP-complete, yet your O(nW) table solves it in polynomial time, so you must have proved P = NP. What is wrong with the argument?

Your team assigns 500 engineers to on-call shifts. Some pairs of engineers must never share a shift, and each engineer lists shifts they cannot take. Product wants an exact optimal scheduler. How would you show the problem is NP-hard, and what would you propose instead?

Given 40 positive integers up to 10¹² and a target, decide within a few seconds whether some subset sums exactly to the target. Which algorithm do you use, what does it cost, and what breaks first as n grows?

A dispatch team wants the best delivery route through 150 stops every morning, computed in under 10 seconds on one machine. What do you build, and what do you promise them about the route?

A warehouse wants cameras at junctions so that every corridor is watched, using as few cameras as possible. The operations head wants a promise about how many cameras the plan might waste. What do you offer?