Top 50 Discrete Mathematics Interview Questions (2026)

Discrete mathematics studies structures that are countable and separate: integers, sets, logic, graphs, and sequences, rather than continuous quantities like the real number line. It's the math of things you can list or count one by one.

It matters for computer science because computers are discrete machines: bits are 0 or 1, memory holds finite states, and algorithms run in countable steps. Logic drives circuits and correctness proofs, sets and relations model data, counting gives you complexity analysis, and graphs model networks. Almost every core CS idea rests on it.

Discrete math works with separate, countable values and produces exact answers: how many, is this true, does a path exist. Continuous math (calculus, analysis) works with quantities that vary smoothly and deals in limits, rates of change, and areas.

The practical line: if you can list the possibilities or count the steps, it's discrete; if you're talking about smooth change or infinitely fine values, it's continuous. Computer science leans discrete because machines are finite and stepwise, though continuous math still shows up in graphics and machine learning.

A proposition is a declarative statement that's definitely either true or false, never both and never neither. "7 is prime" is a proposition because it has a definite truth value; "close the door" isn't, because a command has no truth value at all.

The basic connectives combine propositions: NOT (negation) flips truth, AND (conjunction) is true only when both parts are true, OR (disjunction) is true when at least one is, implication (p implies q) is false only when p is true and q is false, and biconditional (p if and only if q) is true when both sides match.

A truth table lists every possible combination of truth values for the variables in a logical expression and the resulting value of the whole expression. For n variables you get 2 to the n rows, because each variable is independently true or false.

You build it by listing all combinations in the leftmost columns, then evaluating the expression column by column following operator precedence. It's how you check whether two expressions are equivalent (identical output columns) or whether a statement is a tautology (always true).

A tautology is a statement that's true in every row of its truth table, like "p or not p". A contradiction is false in every row, like "p and not p". A contingency is neither: its truth depends on the variables, so its column has both true and false entries.

These matter because a valid logical argument is one where the implication from premises to conclusion is a tautology, and detecting contradictions is how you catch impossible conditions in code or in a set of constraints.

De Morgan's laws describe how negation distributes over AND and OR: not (p and q) equals (not p) or (not q), and not (p or q) equals (not p) and (not q). Negating a compound statement flips the connective and negates each part.

They come up constantly in programming when you simplify or invert conditionals. Rewriting "not (a and b)" as "not a or not b" is a direct application, and getting it wrong is a common source of logic bugs in guard clauses.

Predicate logic extends propositional logic with quantifiers over variables. The universal quantifier, for all, asserts a statement holds for every element in the domain. The existential quantifier, there exists, asserts it holds for at least one element.

Order matters: "for all x, there exists y" is very different from "there exists y, for all x". And negation swaps them: the negation of "for all x, P(x)" is "there exists x such that not P(x)". That swap is a favorite gotcha.

A set is an unordered collection of distinct elements. Order doesn't matter and duplicates don't count, so {1, 2, 3} and {3, 1, 2} are the same set. Membership is the core relation: an element is either in a set or not.

The basic operations: union (everything in either set), intersection (elements in both), difference (in the first but not the second), and complement (everything in the universe not in the set). The empty set has no elements and is a subset of every set.

The power set of a set S is the set of all subsets of S, including the empty set and S itself. For S = {a, b}, the power set is { {}, {a}, {b}, {a, b} }.

If S has n elements, its power set has exactly 2 to the n elements. The reasoning is a counting argument: each element is either in a given subset or not, that's two choices per element, so 2 multiplied by itself n times.

Cardinality is the number of elements in a set. For finite sets it's just a count. The inclusion-exclusion principle for two sets says the size of A union B equals size of A plus size of B minus size of A intersect B.

You subtract the intersection because elements in both sets got counted twice, once in each. It's the fix for double-counting, and it generalizes to three or more sets by adding singles, subtracting pairs, adding triples, and so on.

The Cartesian product A times B is the set of all ordered pairs where the first element comes from A and the second from B. For A = {1, 2} and B = {x, y}, it's { (1,x), (1,y), (2,x), (2,y) }.

Its size is the product of the sizes: if A has m elements and B has n, then A times B has m times n pairs. It's the foundation for defining relations and functions, which are just subsets of a Cartesian product.

A relation on a set is a set of ordered pairs, a subset of the Cartesian product of the set with itself. It says which elements are related. "Less than or equal to" on integers is a relation, holding the pair (2, 5) but not (5, 2).

The properties that matter: reflexive (every element relates to itself), symmetric (if a relates to b then b relates to a), antisymmetric (a to b and b to a forces a equals b), and transitive (a to b and b to c gives a to c). These properties classify relations into equivalence relations and orders.

An equivalence relation is one that's reflexive, symmetric, and transitive all at once. It captures a notion of "sameness" for some chosen purpose, like "has the same remainder mod 3" on the integers, which groups numbers by the remainder they leave.

Its effect is to partition the set into equivalence classes: disjoint groups where everything inside a group is related and nothing across groups is. Every element lands in exactly one class, so the classes cover the whole set without overlap.

A function maps each input to exactly one output. Injective (one-to-one) means distinct inputs give distinct outputs, no two inputs collide. Surjective (onto) means every element of the codomain is hit by some input. Bijective means both: a perfect one-to-one pairing.

Bijections matter for counting: if a bijection exists between two finite sets, they have the same size. They also matter because only bijective functions have an inverse, which underpins encoding, hashing collisions, and cryptography.

A permutation counts arrangements where order matters: how many ways to line up r items from n. A combination counts selections where order doesn't matter: how many ways to choose r items from n regardless of arrangement.

Permutations of r from n are n! / (n - r)!. Combinations are that divided by r!, because each unordered group was counted r! times, once per ordering. The one-line test: does swapping two picks make a different outcome? If yes, it's a permutation.

The rule of product says if one choice has m options and an independent second choice has n options, the number of combined outcomes is m times n. Picking a shirt (3 options) and pants (4 options) gives 12 outfits.

The rule of sum says if you must pick exactly one of two disjoint sets of options, sized m and n, you have m plus n choices total. Product is for "and" (do both), sum is for "or" (pick one). Mixing them up is the most common counting mistake.

The pigeonhole principle says if you place more items than containers, at least one container holds two or more items. Put 13 people in a room and at least two share a birth month, because there are only 12 months.

It's simple but surprisingly strong: it proves a collision must exist without telling you where. It's the reasoning behind why lossless compression can't shrink every file, and why hash tables must eventually have collisions once you exceed the number of buckets.

A direct proof assumes the hypothesis is true and, through a chain of valid logical steps, arrives at the conclusion. To prove "if n is even then n squared is even", you write n as 2k, square it to get 4k squared, which is 2 times (2k squared), and that's even by definition.

It's the default technique when the path from assumption to conclusion is straightforward. The skill is writing each step so it clearly follows from the previous one, and stating definitions explicitly, since a proof is only as solid as its weakest justified step.

A graph is a set of vertices (nodes) connected by edges, and it models relationships between things: cities and roads, people and friendships, web pages and the links between them. The vertices are the objects, and the edges are the connections that link pairs of them.

In an undirected graph, an edge is a two-way connection, like a friendship. In a directed graph, each edge has a direction, like a one-way street or a Twitter follow. The distinction changes everything downstream: degree, connectivity, traversal, and which algorithms apply.

A set is unordered and holds only distinct elements, so {1, 2, 2} is just {1, 2}. A list (or sequence) is ordered and allows duplicates, so [1, 2, 2] and [2, 1, 2] are different. A multiset is unordered like a set but allows duplicates, tracking how many times each element appears.

The distinction drives data-structure choices in code: use a set when you only care about membership and uniqueness, a list when order and repetition matter, and a multiset (like a counter or bag) when you need counts without caring about order.

A is a subset of B if every element of A is also in B, which allows A to equal B. A is a proper subset if it's a subset and strictly smaller, so A is contained in B but not equal to it. Every set is a subset of itself, but no set is a proper subset of itself.

The empty set is a subset of every set, and a proper subset of every non-empty set. The distinction matters when counting: a set with n elements has 2 to the n subsets but 2 to the n minus 1 proper subsets, since you exclude the set itself.

Induction proves a statement for all natural numbers n in two parts. The base case proves it for the smallest value, usually n = 0 or n = 1. The inductive step assumes it holds for an arbitrary k (the hypothesis) and proves it then holds for k + 1.

Together they form a domino chain: the base case knocks over the first domino, and the step guarantees each domino knocks over the next, so all of them fall. You reach for induction whenever a claim is indexed by an integer, like a summation formula, a loop invariant, or the size of a recursively defined structure.

In ordinary induction, the step assumes the claim for the single previous case k and proves k + 1. In strong induction, the step assumes the claim for all cases up to k and uses any of them to prove k + 1.

Strong induction is the right tool when a case depends on more than its immediate predecessor, like proving every integer above 1 has a prime factorization, where you split n into two smaller factors and invoke the hypothesis for both. The two forms are logically equivalent in power, but strong induction is cleaner when the recursion reaches back further.

You prove a statement by assuming its opposite is true and then deriving a logical impossibility from that assumption. Since the assumption led to something false or contradictory, the assumption itself must be wrong, which means the original statement has to be true.

The classic example is that the square root of 2 is irrational: assume it's a fraction in lowest terms, and you derive that both numerator and denominator are even, contradicting "lowest terms". It's the go-to when directly building the conclusion is hard but assuming the negation gives you something concrete to break.

The contrapositive of "if p then q" is the statement "if not q then not p", and the two are logically equivalent because they have identical truth tables. So a proof of the contrapositive counts as a full proof of the original implication.

It helps when the negations are easier to work with. To prove "if n squared is even then n is even", the contrapositive "if n is odd then n squared is odd" is a clean direct proof (odd times odd is odd), whereas the original is awkward to attack head-on.

To disprove a claim of the form "for all x, P(x)", you produce a single counterexample: one specific x where P is false. One counterexample is enough, because a universal statement claims to hold in every case.

For example, "every prime is odd" is disproved instantly by 2, which is prime and even. The asymmetry is worth stating: proving a universal claim needs a general argument, but disproving it needs just one bad case.

For three sets the count of the union is: add the three individual sizes, subtract the three pairwise intersections, then add back the triple intersection. The pattern alternates: add singles, subtract pairs, add triples.

You add the triple intersection back because elements in all three sets were added three times, then subtracted three times in the pairwise step, leaving them at zero, so you restore them once. It's the systematic way to count a union without double-counting overlaps.

The binomial theorem expands (x + y) to the n as a sum of terms C(n, k) times x to the (n - k) times y to the k, for k from 0 to n. The coefficients C(n, k) are the binomial coefficients, the same as the number of ways to choose k items from n.

Pascal's triangle is those coefficients arranged in rows, where each entry is the sum of the two above it. That sum rule is exactly the identity C(n, k) = C(n-1, k-1) + C(n-1, k), which has a clean combinatorial reading: an item is either chosen or not.

A recurrence relation defines each term of a sequence using earlier terms, plus base cases. Fibonacci is F(n) = F(n-1) + F(n-2). They naturally describe recursive algorithms, where the cost of a problem is expressed in terms of its subproblems.

You solve simple ones by finding a closed form: for linear recurrences you can use the characteristic equation, and for divide-and-conquer algorithm recurrences the Master Theorem gives the growth rate directly. The goal is to turn "defined by earlier terms" into a formula you can evaluate in one step.

Big-O describes how an algorithm's running time or space grows as the input size n grows, keeping only the dominant term and dropping constants. O(n) means the work scales linearly, O(n squared) means it scales with the square, and O(log n) means it grows very slowly.

It's discrete math because deriving a bound is a counting argument: you count how many operations run as a function of n, often by solving a recurrence or summing a series. Comparing O(n log n) to O(n squared) is comparing growth rates of functions on the integers.

Modular arithmetic works with remainders after division by a fixed modulus m. Numbers are equivalent (congruent) if they leave the same remainder mod m, so 17 and 5 are congruent mod 12, like clock arithmetic where 17:00 indicates 5.

It's everywhere in software: hash functions map keys into a table with a mod operation, cryptography like RSA relies on modular exponentiation, checksums and cyclic buffers use it, and random number generators lean on it. The wraparound behavior is the whole point.

The Euclidean algorithm finds the GCD of two numbers by repeatedly replacing the larger with the remainder of dividing it by the smaller, until the remainder is zero. The last nonzero remainder is the GCD.

It works because the GCD of a and b equals the GCD of b and (a mod b): any common divisor of a and b also divides the remainder. It's fast, running in a number of steps proportional to the number of digits, which is why it underpins fraction reduction and cryptographic key math.

The two standard representations are the adjacency matrix and the adjacency list. A matrix is a V by V grid where entry (i, j) marks whether an edge exists. A list stores, for each vertex, the vertices it connects to.

The trade-off is space versus lookup. A matrix uses V squared space regardless of edges, so it wastes memory on sparse graphs but checks "is there an edge from i to j" in constant time. A list uses space proportional to vertices plus edges, ideal for sparse graphs, but checking a specific edge takes longer. Most real graphs are sparse, so lists are the common default.

Breadth-first search explores the graph level by level, visiting all of a node's neighbors before going any deeper, and it uses a queue to do so. Depth-first search instead goes as deep as possible along one path before backtracking, using a stack or plain recursion.

BFS finds the shortest path in an unweighted graph because it reaches nodes in order of distance. DFS is natural for exploring full structure, detecting cycles, and topological sorting. Both visit every vertex and edge once, so both run in O(V + E) time.

A tree is a connected graph with no cycles. Equivalently, it's a graph where any two vertices are joined by exactly one path. Trees model hierarchies: file systems, org charts, parse trees, and the recursion structure of algorithms.

A tree with n vertices always has exactly n - 1 edges. That's the tight point: fewer edges and it's disconnected, one more edge and you create a cycle. Several definitions of a tree (connected and acyclic, connected with n-1 edges, unique path between any two nodes) all describe the same thing.

Graph coloring assigns colors to vertices so that no two adjacent vertices share a color. The chromatic number is the fewest colors needed. It models conflict-free assignment: things connected by an edge can't get the same resource.

Real uses: scheduling exams so no student has two at once (edge = shared student), assigning radio frequencies so nearby towers don't interfere, and register allocation in compilers, where variables live at the same time can't share a register. Finding the minimum coloring is computationally hard in general, which is itself worth knowing.

An Eulerian path uses every edge exactly once. A Hamiltonian path visits every vertex exactly once. One is about covering edges, the other about covering vertices, and that difference has a surprising consequence for difficulty.

Whether an Eulerian path exists is easy to check: it depends only on how many vertices have odd degree. Whether a Hamiltonian path exists is NP-complete, one of the hard problems with no known efficient general algorithm. Two similar-sounding definitions, wildly different computational cost.

A partial order is a relation that's reflexive, antisymmetric, and transitive, but some pairs may be incomparable. Subset inclusion is a partial order: {1} and {2} are neither a subset of the other. A total order adds that every pair is comparable, like less-than-or-equal on numbers.

The distinction drives topological sorting: a partial order (tasks with some dependencies) can be extended to a total order (a valid sequence to run them), and there may be many valid sequences precisely because some tasks are incomparable.

P is the class of problems solvable in polynomial time: the runtime grows as a polynomial in the input size, so they're considered tractable. NP is the class where a proposed solution can be verified in polynomial time, even if finding one might be slow. Every P problem is in NP.

NP-complete problems are the hardest in NP: every NP problem reduces to them, so a fast algorithm for one would solve all of NP fast. Whether P equals NP is the open question. In practice, recognizing that a problem is NP-complete tells you to stop hunting for an exact fast algorithm and reach for heuristics or approximations.

You show two things: the problem is in NP (a solution is verifiable in polynomial time), and it's NP-hard (a known NP-complete problem reduces to it in polynomial time). The reduction transforms instances of a known-hard problem into your problem, so solving yours would solve the known one.

It matters because it sets expectations. Once you've argued a problem is NP-complete, you stop promising an exact efficient solution and instead reach for approximation algorithms, heuristics, constraint on input size, or exact solvers that are fast in practice on real instances. It reframes the engineering goal from optimal to good-enough-and-fast.

Amortized analysis measures the average cost per operation over a sequence of operations, guaranteeing the total cost even when individual operations vary wildly. It's not average-case (which assumes a distribution of inputs); it's a worst-case guarantee spread across a sequence.

The classic example is a dynamic array. Appending is usually O(1), but occasionally the array doubles and copies everything, costing O(n). Amortized over many appends, the doubling cost spreads out to O(1) per operation. So you can promise cheap appends on average without lying about the occasional expensive resize.

Expected value is the probability-weighted average of outcomes. For a randomized algorithm, you model the random choices, then compute the expected number of operations by summing each possible cost times its probability. Linearity of expectation is the workhorse: the expected value of a sum equals the sum of expected values, even when the parts aren't independent.

Randomized quicksort is the standard case: a random pivot makes the O(n squared) worst case astronomically unlikely, and the expected running time is O(n log n). You prove that by computing the expected number of comparisons, which is where linearity of expectation makes the algebra clean.

The birthday paradox is that with just 23 people, there's about a 50% chance two share a birthday, which feels too low. The reason is you're comparing all pairs, and the number of pairs grows with the square of the group, so collisions arrive far sooner than intuition suggests.

For hashing and cryptography it's the key insight behind collision attacks: to find a collision in a hash with N possible outputs, you only need on the order of the square root of N attempts, not N. That's why a hash needs many more bits than you'd naively think to resist collision finding.

Boolean algebra is the algebra of true and false with AND, OR, and NOT, and it maps directly onto logic gates in hardware. Any Boolean function can be built from gates, and the algebraic laws (De Morgan's, distribution, absorption) are exactly the rules you use to simplify a circuit.

Simplifying a Boolean expression means fewer gates: less silicon, less power, less delay. Tools like Karnaugh maps and the fact that NAND or NOR alone is functionally complete (you can build any circuit from just one of them) come straight from this algebra. Logic isn't just abstract, it's the design layer of the chip.

A generating function encodes a sequence as the coefficients of a formal power series. The sequence a0, a1, a2 and so on becomes a0 + a1*x + a2*x squared and so on. Turning a sequence into a single function lets you use algebra to attack counting and recurrence problems.

It's useful for solving recurrences and hard counting problems: you translate the recurrence into an equation about the generating function, solve that with algebra, then read off the coefficients as a closed form. Problems that resist direct counting often fall out cleanly once framed this way, which is why they show up in advanced combinatorics.

A spanning tree of a connected weighted graph is a tree that includes every vertex using a subset of edges. A minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. It connects everything at the lowest cost with no redundant edges.

Prim's and Kruskal's algorithms find it greedily, and both are correct because of the cut property: the lightest edge crossing any partition of the vertices is safe to include. Uses include designing low-cost networks (cabling, roads, circuits), clustering, and as a building block in approximation algorithms for harder routing problems.

In a directed graph, you detect a cycle with a depth-first search that tracks three states per node: unvisited, in the current recursion stack, and finished. If DFS reaches a node that's already in the current stack, you've found a back edge, which means a cycle. An alternative is Kahn's algorithm: if a topological sort can't include every node, a cycle exists.

It matters because acyclicity is a precondition for a valid ordering. Build systems, task schedulers, package managers, and spreadsheet formula engines all need the dependency graph to be acyclic, a directed acyclic graph, or there's no valid order to process things and you must report the circular dependency.

A Bloom filter is a bit array plus k hash functions that tests set membership with no false negatives but a controlled false-positive rate. The math is a probability calculation: after inserting n items into m bits with k hashes, the chance a given bit is still zero is (1 - 1/m) to the power k*n, and a false positive happens when all k bits for a queried item are one.

From that you derive the optimal number of hash functions and the trade-off between memory (m), item count (n), and error rate. It's a clean example of probability and counting producing a tunable engineering knob: accept a small, calculable false-positive rate to save large amounts of memory.

Start by clarifying the alphabet and constraints: which characters are allowed, is length fixed at 8 or up to 8, and are there rules like at least one digit. Those questions decide the counting method, so state them before computing, exactly as you would clarify a system-design prompt.

For a fixed length of 8 from an alphabet of size A with no constraints, the count is A to the 8th by the rule of product: each position is an independent choice. For "at least one digit", count the total and subtract the arrangements with no digit at all, an inclusion-exclusion move. The structure that scores is clarify the rules, apply product for independent positions, and use complementary counting for at-least constraints.

In cryptography it's foundational: modular arithmetic and number theory drive RSA (modular exponentiation, Euler's theorem), finite fields underpin elliptic-curve cryptography, hash functions rely on the birthday bound for collision resistance, and much of the security is stated as the hardness of a discrete problem like factoring or discrete logarithm.

In machine learning it's more mixed, since a lot of ML is continuous optimization, but discrete structures appear in graph neural networks, combinatorial feature selection, discrete probability for classification, and the counting arguments behind sample complexity. The honest production-ready answer notes that ML leans continuous while cryptography leans hard on the discrete side.