Skip to content
Tutorials Center
My learning

Topics

Lesson 67 of 68 · Practice and Review

Discrete Math Interview Questions

Typical interview questions on logic puzzles, counting, probability, graphs and modular arithmetic, with short answers and runnable checks in Python.

Interviews for software, data and quant roles love discrete mathematics, because a small question reveals how you think: do you define terms, try small cases, spot a structure and check your answer? This lesson collects questions that come up again and again, grouped by topic, with a short model answer for each. Several answers come with a runnable check, so you can confirm the number instead of trusting your memory.

A good answer has a shape. Restate the question in your own words, work a tiny case, name the principle (product rule, pigeonhole, parity, invariant), give the answer and then sanity-check it. Interviewers care more about that path than about the final number. Try to answer each question aloud before you read the answer below it.

Five question families

Logic Implication, negation, puzzles.
Counting and chance Pigeonhole, Monty Hall.
Graphs Parity, trees, bipartite, cycles.
Modular Last digits, inverses, divisibility.

Five families cover most questions.

1 / 2

Logic and puzzles

Is "if p then q" the same as "if q then p"? No. The second statement is the converse. The statement that is equivalent to "if p then q" is its contrapositive, "if not q then not p", and also "not p or q". Give a concrete example: "If it is a square, it is a rectangle" is true, but "if it is a rectangle, it is a square" is false. See Implication and Biconditional.

What is the negation of "every swan is white"? "Some swan is not white", not "no swan is white". Negating a universal statement gives an existential one: ¬∀x P(x) is ∃x ¬P(x). In code it is not all(...) versus any(not ...). See Predicates and Quantifiers.

When is "if p then q" true if p is false? Always, which is called vacuous truth. "Every unicorn in this room can fly" is true because the room has no unicorns. The only way an implication fails is a true premise with a false conclusion.

A knight always tells the truth and a knave always lies. A says "We are both knaves." What are A and B? If A were a knight the statement would be true, but it says A is a knave, a contradiction. So A is a knave, the statement is false, so not both are knaves, which makes B a knight. The general method is to try every assignment of types and keep the consistent ones, which is just a small truth table.

How would you prove that a statement about all integers is false? Give one counterexample. To prove something true for all n you need a proof, usually induction; testing 10,000 values is evidence, not proof. See How Proofs Work.

Counting

How many handshakes happen if each of 10 people shakes hands once with everybody else? Each handshake is an unordered pair: C(10, 2) = 45. Alternative view: 10 · 9 counts ordered pairs, so divide by 2.

How many trailing zeros does 100! have? Each zero comes from a factor 10 = 2 · 5, and there are far more 2s than 5s, so count 5s: ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24.

A drawer holds red, blue and black socks in the dark. How many socks must you take to be sure of a matching pair? Four, by the pigeonhole principle: with three colors (holes), four socks (pigeons) must put two in the same color. Three socks can all differ, so three is not enough.

How many ways can you climb 10 stairs if you take one or two steps at a time? The last move is a single step (leaving 9 stairs) or a double step (leaving 8), so ways(n) = ways(n − 1) + ways(n − 2), the Fibonacci recurrence; ways(10) = 89. See Recurrence Relations.

What is the difference between a permutation and a combination, and how do you pick? Ask whether order matters. Choosing a president and a treasurer: order matters, 10 · 9 = 90. Choosing a committee of two: order does not matter, C(10, 2) = 45. See Permutations and Combinations.

How many subsets does an n-element set have? 2ⁿ: each element is in or out. This is also the number of binary strings of length n, which is why bit masks enumerate subsets.

Python Check the counting answers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output confirms 45 handshakes, 24 zeros by both methods, that three socks can differ while any four contain a pair, 89 ways to climb, and 32 subsets.

Probability

A family has two children, and at least one is a boy. What is the probability that both are boys? What if you know the older child is a boy? List the equally likely families (older, younger): BB, BG, GB, GG. "At least one boy" leaves three, of which one is BB, so 1/3. "The older is a boy" leaves BB and BG, so 1/2. The information you receive changes the sample space. See Discrete Probability.

Explain the Monty Hall problem. You pick one of three doors; the host, who knows where the car is, opens another door with a goat and offers a switch. Your first pick is right with probability 1/3 and stays 1/3, so the other closed door carries the remaining 2/3: switching wins twice as often. The key detail is that the host never opens the car door and never opens yours; he gives information.

What is the expected number of rolls of a fair die until you see a six? 6. The probability of success on each roll is 1/6, and the expected waiting time for a geometric distribution is 1/p. Expected values add even when events are dependent (linearity of expectation), which is the most useful trick in the area.

How many rolls does it take, on average, to see all six faces? The coupon collector: after you have i faces, the chance a roll is new is (6 − i)/6, so you wait 6/(6 − i) rolls on average. Summing over i gives 6 · (1 + 1/2 + … + 1/6) = 14.7.

What is the probability that a positive test means a sick patient? Use Bayes' theorem and the base rate: P(sick | positive) = P(positive | sick) P(sick) / P(positive). With 1% prevalence, 95% sensitivity and a 5% false-positive rate it is 19/118, about 16%. Candidates who answer "95%" are making the classic base-rate error.

Python Check the probability answers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The exact part prints 1/3 and 1/2 for the two-children questions, and 1/3 versus 2/3 for staying versus switching. The simulation (fixed seed) prints 0.66469 for switching, close to 2/3, and an average wait of 6.01 rolls for a six, close to 6. The coupon collector sum is exactly 147/10, which is 14.7.

Graphs

Can 7 people each shake hands with exactly 3 others? No. Treat people as vertices and handshakes as edges. The degrees would sum to 21, but every edge adds 2 to the degree sum (the handshake lemma), so the sum must be even. Equivalently, the number of odd-degree vertices is always even.

How many edges does a tree with n vertices have? n − 1. A connected graph with n vertices and n − 1 edges is a tree, and so is an acyclic graph with n − 1 edges. Adding any edge to a tree creates exactly one cycle. See Trees and Spanning Trees.

How do you check that a graph is bipartite (two-colorable)? Run BFS or DFS and color neighbors with opposite colors. If you ever find an edge between two same-colored vertices, there is an odd cycle, and a graph is bipartite exactly when it has no odd cycle. See Graph Coloring and Planarity.

When can you walk every edge exactly once and return to the start? When the graph is connected and every vertex has even degree (an Euler circuit). A Hamiltonian cycle, which visits every vertex exactly once, has no such simple test and is NP-complete. See Euler and Hamilton Paths.

How do you detect a circular dependency among tasks? Use Kahn's algorithm for a topological order: repeatedly remove vertices with no incoming edges. If vertices remain when none is left with in-degree 0, the rest contains a cycle. This is how build tools and package managers report "circular dependency".

Python Check the graph answers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line prints "False" for the evenness test: 21 is odd, so the handshake plan is impossible. The 5-cycle is not bipartite and the 6-cycle is. All 125 connected 4-edge graphs on 5 vertices are cycle-free (the assertion would fail otherwise), matching Cayley's count of trees. The dependency check reports no cycle for the chain and a cycle for a → b → c → a.

Modular arithmetic and number theory

What is the last digit of 7²⁰²⁵? Powers of 7 end in 7, 9, 3, 1 repeatedly, a cycle of length 4. Since 2025 ≡ 1 (mod 4), the digit is 7. In general, reduce the exponent by the cycle length, or call pow(7, 2025, 10). See Modular Arithmetic.

What is 2¹⁰⁰ mod 7? 2³ = 8 ≡ 1 (mod 7), so powers repeat every 3 steps. 100 = 3 · 33 + 1, so 2¹⁰⁰ ≡ 2.

How do you test divisibility by 11? Take the alternating sum of the digits from the right. It works because 10 ≡ −1 (mod 11), so 10ᵏ is ±1. For 918082: 2 − 8 + 0 − 8 + 1 − 9 = −22, divisible by 11, so the number is too.

Does 6x ≡ 4 (mod 9) have a solution? No. ax ≡ b (mod m) is solvable exactly when gcd(a, m) divides b. Here gcd(6, 9) = 3 and 3 does not divide 4. For 6x ≡ 3 (mod 9) there are three solutions: 2, 5 and 8.

When does a modular inverse exist? a has an inverse modulo m exactly when gcd(a, m) = 1, found with the extended Euclidean algorithm. If m is prime, every nonzero a is invertible. See GCD, LCM and the Euclidean Algorithm.

How many integers from 1 to 100 are coprime to 100? Euler's totient: φ(100) = 100 · (1 − 1/2) · (1 − 1/5) = 40.

Python Check the modular answers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How to practice

  • Keep a one-line toolbox in your head: product and sum rules, complement, inclusion-exclusion, pigeonhole, parity, invariants, induction, recursion on the last step.
  • Always test your formula on n = 2 or n = 3 by listing everything by hand. If you can write a ten-line brute force, do it; it turns a guess into a fact.
  • Say your assumptions out loud: ordered or unordered, repeats allowed or not, simple graph or multigraph, fair die or not.
  • Revisit Common Mistakes and Pitfalls and the two exercise sets before an interview.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Which statement is logically equivalent to 'if p then q'?

    The contrapositive of an implication always has the same truth value as the implication. The converse and inverse do not.
  2. 2. A drawer contains socks of 3 colors. What is the smallest number you must draw in the dark to be certain of a matching pair?

    Three socks can all differ, but with four socks and three colors the pigeonhole principle forces a repeat.
  3. 3. You pick door 1 in the Monty Hall game and the host opens a goat door. What is the probability of winning if you switch?

    Your first pick is right with probability 1/3. The other 2/3 is concentrated on the remaining closed door after the host reveals a goat.
  4. 4. Why can 7 people not each shake hands with exactly 3 others?

    The handshake lemma says the degree sum is 2|E|, which is always even, and 7 * 3 = 21 is odd.
  5. 5. Does 6x = 4 (mod 9) have a solution?

    A linear congruence ax = b (mod m) is solvable exactly when gcd(a, m) divides b. Primality of m is not required.

Summary

  • Interview answers show a method: restate, try small cases, name the principle, answer, check.
  • Logic questions hinge on the converse versus the contrapositive, negating quantifiers and vacuous truth.
  • Counting uses the product rule, combinations for unordered choices, pigeonhole for guarantees and recurrences for step-by-step processes.
  • Probability puzzles change the sample space when information arrives; Bayes' theorem and base rates explain the surprising ones; expectation adds up even for dependent events.
  • Graph questions are often solved by parity (handshake lemma), tree facts (n − 1 edges), bipartite tests (no odd cycle) and topological sorting.
  • Modular questions reduce to cycles of powers, gcd conditions and inverses; check every answer with a few lines of Python.

Next: Discrete Mathematics Cheat Sheet.