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

Data Structures & Algorithms (DSA) Module 18

Maths for DSA interview questions

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

16 questions: 4 warm-ups and 12 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

Fresher

Why does trial division only need to try divisors up to √n, and how many divisions does it make on a prime near 10¹²?

Answered in the lesson Primes: trial division, sieves and factorisation
Fresher

Why do so many programming problems ask for the answer modulo 10⁹ + 7?

Answered in the lesson Modular arithmetic and fast exponentiation
Fresher

What does C(n, k) count, and why is C(n, k) equal to C(n, n − k)?

Answered in the lesson Counting: nCr modulo p and Catalan numbers
Fresher

Why does 0.1 + 0.2 == 0.3 evaluate to false in most languages, and how should you compare floating-point values?

Answered in the lesson Big integers, floating point and precision

Questions with model answers

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

Mid to senior

Service A answers a million questions a day of the form "is n prime?" with n at most 10⁷. Service B checks single 64-bit numbers that users type in. What do you build for each, with memory and time, and what breaks if you reuse A's design for B?
What it tests

Matching a primality method to the size of the numbers and the number of questions, sizing memory, and knowing where a sieve stops scaling.

First step

Write both workloads down as numbers. A asks many questions about a small range, so a table built once pays for itself; B asks few questions about numbers up to about 1.8 × 10¹⁹, where any table, and any loop up to √n, is out of reach. Then estimate the memory and the time of each candidate.
Follow-ups
- How much memory does A's table take as a list of booleans, a bytearray and a bitset?
- Which bases make Miller–Rabin exact for every 64-bit number?
- B must also show why a number is composite. What do you return?
From the lesson Primes: trial division, sieves and factorisation
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 3 minutes
Mid

You must factorise a million numbers, each at most 10⁷, within a second. Compare trial division with a smallest-prime-factor table using operation counts, give the table's memory in Python and in a compiled language, and say when the table is the wrong choice.
What it tests

Estimating work with counts instead of guesses, sizing a factor table per language, and spotting the workloads where building it does not pay.

First step

Count the work of each method before choosing. Trial division of x tries up to √x divisors, about 3,162 for a prime near 10⁷; a table answers with one lookup per prime factor, at most 23 below 10⁷, after a build of roughly n log log n steps.
Follow-ups
- How long does the build take in CPython and in a compiled language?
- Only 100 numbers need factorising. Which method now?
- The numbers grow to 10¹². What changes?
From the lesson Primes: trial division, sieves and factorisation
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Senior

Count the primes between 10¹² and 10¹² + 10⁷. Why not sieve from 1, how does a segmented sieve work, how much memory and time does it need, and how would you check the count?
What it tests

Knowing that small primes suffice for a window, computing the first multiple inside it, sizing memory, and validating the result with an independent method.

First step

Every composite in the window has a prime factor no larger than the square root of 10¹² + 10⁷, which is just over 10⁶. Sieve the primes up to that bound once, then cross out their multiples inside the window only.
Follow-ups
- How do you find the first multiple of p inside the window?
- The window is 10¹⁰ numbers wide. What changes?
- How do you know the count is right?
From the lesson Primes: trial division, sieves and factorisation
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Mid

A Java service computes (a * b) % m on long values with m = 10¹² + 39. Some results are negative, and others are wrong but look normal. Explain both, and give two fixes with their costs.
What it tests

Knowing when a 64-bit product overflows, why the result can be negative or plausibly wrong, and which exact fix suits Java.

First step

Bound the product first: a and b are below m, about 10¹², so a × b can reach 10²⁴, about 2⁸⁰, far past the largest long, about 9.22 × 10¹⁸. Java keeps the low 64 bits of the product and raises no error, so % works on a different number.
Follow-ups
- Which products come out negative, and which give a wrong positive number?
- How fast are BigInteger and multiplication by doubling compared with a plain multiplication?
- How would you test the fixed code?
From the lesson Modular arithmetic and fast exponentiation
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A problem asks for the average of n values as a residue modulo 10⁹ + 7, that is, the sum times the inverse of n. How do you compute it, what goes wrong if n is a multiple of the modulus, and what changes if the modulus is 10⁹?
What it tests

Turning a division into a multiplication by an inverse, knowing exactly when the inverse exists, and handling a modulus that is not prime.

First step

Reduce the sum modulo p as you add, then multiply it by the inverse of n: pow(n, p − 2, p) by Fermat's little theorem, since p is prime, or pow(n, -1, p) in Python. Check the answer by multiplying it back by n.
Follow-ups
- n is 2 × (10⁹ + 7). What happens?
- Why can't you divide the reduced sum by n with ordinary integer division?
- With the modulus 10⁹, which values of n have an inverse?
From the lesson Modular arithmetic and fast exponentiation
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Senior

Compute the n-th term of a linear recurrence of order k modulo a prime, for n up to 10¹⁸. What does matrix exponentiation cost, when does it become too slow, and what do you use then?
What it tests

Building the companion matrix, costing repeated squaring of matrices, and knowing the polynomial method for large orders.

First step

Write one step of the recurrence as a k × k matrix acting on the vector of the last k terms. The n-th term then needs that matrix to the power n: one squaring per binary digit of n plus one product per digit 1, each product k³ multiplications.
Follow-ups
- How large can k be before the matrix method misses a one-second limit?
- How do you check an answer for n = 10¹⁸?
- What changes if each step also adds a constant?
From the lesson Modular arithmetic and fast exponentiation
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid

Answer 10⁶ queries of C(n, k) modulo 10⁹ + 7 with n up to 10⁶. Give the design, its memory and its cost per query, and say what changes if the modulus is 10⁹, which is not prime.
What it tests

Building factorial and inverse-factorial tables, sizing them per language, and changing method when the modulus has no inverses.

First step

The modulus is prime and larger than every n, so every factorial up to 10⁶ has an inverse. Build the factorials upwards and the inverse factorials downwards from a single Fermat inverse, then answer each query with two multiplications.
Follow-ups
- How much memory do the tables take in Python and in Java?
- Which queries need care before any table lookup?
- With the modulus 10⁹, what do you use instead, and what does it cost?
From the lesson Counting: nCr modulo p and Catalan numbers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Fresher to mid

How many structurally different binary search trees hold the keys 1 to n, and how would you list all of them for n = 15? Estimate the size of the output before writing any code.
What it tests

Deriving the Catalan recurrence, estimating the output before generating it, and choosing between counting, listing and sampling.

First step

Count first. Choosing each key in turn as the root splits the others into a left and a right subtree, which gives the Catalan recurrence; for n = 15 it is 9,694,845 trees, so a full list holds millions of trees before any work is done on them.
Follow-ups
- How much memory would the full list for n = 15 take?
- How do you produce the trees one at a time instead?
- How would you pick one of them uniformly at random?
From the lesson Counting: nCr modulo p and Catalan numbers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Mid to senior

A robot moves on a grid from (0, 0) to (n, n) with right and up steps and may never go above the diagonal y = x. How many paths are there for n = 10⁶, modulo 10⁹ + 7, and how do you show that the formula is right?
What it tests

Recognising a Catalan count, proving it with the reflection argument, and computing it modulo a prime with factorial tables.

First step

Count all the paths first, C(2n, n), then count the bad ones, which touch the line y = x + 1. Reflecting a bad path after its first touch gives a path that ends at (n − 1, n + 1), and that matching is one to one.
Follow-ups
- What changes if the robot may touch y = x + 1 but never go above it?
- How do you test the formula before trusting it for n = 10⁶?
- How do you compute the answer modulo 10⁹ + 7?
From the lesson Counting: nCr modulo p and Catalan numbers
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Mid to senior

Order IDs are 64-bit integers. The web front end shows some IDs a few units off, and links built from them open the wrong order. Explain what happens, and fix it from the database to the page.
What it tests

Knowing where JavaScript Numbers stop being exact, tracing a value through serialisation, and fixing the contract rather than one screen.

First step

Find where precision is lost. The database and the service hold the IDs exactly as 64-bit integers, but JSON.parse in the browser turns every JSON number into a Number, which is exact only up to 2⁵³ − 1, so any ID above about 9.007 × 10¹⁵ is rounded to the nearest double.
Follow-ups
- Why are only some IDs affected, and by how many units?
- What do the server, the API contract and the front end each need to change?
- How would you test that the fix holds?
From the lesson Big integers, floating point and precision
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Mid

Report the exact total of 10⁷ transaction amounts with two decimal places. Which types do you use in Python, Java and JavaScript, what goes wrong with plain floats, and how large can the total grow before your choice breaks?
What it tests

Choosing exact representations for money, estimating float error with numbers, and sizing the integer type for the total.

First step

Turn every amount into a whole number of the smallest unit, cents or paise, as it is parsed, and add integers. Then size the total: 10⁷ amounts of up to 10⁷ units each reach 10¹⁴ units, comfortably inside 64 bits.
Follow-ups
- Roughly how large is the float error after 10⁷ additions?
- How do you apply a percentage fee and round it?
- What breaks in JavaScript, and what do you use there?
From the lesson Big integers, floating point and precision
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes
Fresher to mid

The loop x = 0.0; while x != 1.0: x += 0.1 never stops. Explain why, fix it, and design an equality check for a geometry library that sees both tiny and huge coordinates.
What it tests

Understanding accumulated rounding, removing float equality from loop conditions, and combining relative and absolute tolerances.

First step

Print x on every round: after ten additions it is 0.9999999999999999, not 1.0, so x steps past 1.0 and x != 1.0 stays true for ever. Loop over an integer counter instead and compute x from it.
Follow-ups
- Why is 0.1 added ten times not 1.0, when 0.1 * 10 is?
- Which tolerance would you choose for coordinates from 10⁻⁶ to 10⁶?
- When is an exact comparison of floats correct?
From the lesson Big integers, floating point and precision
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 2 minutes

The lessons of this module

Euclid's algorithm: GCD, LCM and Bézout Free: 25 minutes
Primes: trial division, sieves and factorisation Free core, Pro depth: 10 of 30 minutes free
Modular arithmetic and fast exponentiation Free core, Pro depth: 11 of 30 minutes free
Counting: nCr modulo p and Catalan numbers Free core, Pro depth: 11 of 30 minutes free
Big integers, floating point and precision Free core, Pro depth: 8 of 25 minutes free

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

Warm-up questions

Why does trial division only need to try divisors up to √n, and how many divisions does it make on a prime near 10¹²?

Why do so many programming problems ask for the answer modulo 10⁹ + 7?

What does C(n, k) count, and why is C(n, k) equal to C(n, n − k)?

Why does 0.1 + 0.2 == 0.3 evaluate to false in most languages, and how should you compare floating-point values?

Questions with model answers

Service A answers a million questions a day of the form "is n prime?" with n at most 10⁷. Service B checks single 64-bit numbers that users type in. What do you build for each, with memory and time, and what breaks if you reuse A's design for B?

You must factorise a million numbers, each at most 10⁷, within a second. Compare trial division with a smallest-prime-factor table using operation counts, give the table's memory in Python and in a compiled language, and say when the table is the wrong choice.

Count the primes between 10¹² and 10¹² + 10⁷. Why not sieve from 1, how does a segmented sieve work, how much memory and time does it need, and how would you check the count?

A Java service computes (a * b) % m on long values with m = 10¹² + 39. Some results are negative, and others are wrong but look normal. Explain both, and give two fixes with their costs.

A problem asks for the average of n values as a residue modulo 10⁹ + 7, that is, the sum times the inverse of n. How do you compute it, what goes wrong if n is a multiple of the modulus, and what changes if the modulus is 10⁹?

Compute the n-th term of a linear recurrence of order k modulo a prime, for n up to 10¹⁸. What does matrix exponentiation cost, when does it become too slow, and what do you use then?

Answer 10⁶ queries of C(n, k) modulo 10⁹ + 7 with n up to 10⁶. Give the design, its memory and its cost per query, and say what changes if the modulus is 10⁹, which is not prime.

How many structurally different binary search trees hold the keys 1 to n, and how would you list all of them for n = 15? Estimate the size of the output before writing any code.

A robot moves on a grid from (0, 0) to (n, n) with right and up steps and may never go above the diagonal y = x. How many paths are there for n = 10⁶, modulo 10⁹ + 7, and how do you show that the formula is right?

Order IDs are 64-bit integers. The web front end shows some IDs a few units off, and links built from them open the wrong order. Explain what happens, and fix it from the database to the page.

Report the exact total of 10⁷ transaction amounts with two decimal places. Which types do you use in Python, Java and JavaScript, what goes wrong with plain floats, and how large can the total grow before your choice breaks?

The loop x = 0.0; while x != 1.0: x += 0.1 never stops. Explain why, fix it, and design an equality check for a geometry library that sees both tiny and huge coordinates.