Overview
Curated: · Written: · Reviewed:
Mathematics and geometry for interviews
Numeric and geometric problems fail differently from other algorithm problems: the code runs, produces a number, and the number is wrong. This guide is organised around those silent failures — intermediate overflow in an expression whose result fits, negative modulo results used as indices, floating-point equality on computed values, and catastrophic cancellation in the naive variance formula. It then covers the number-theory toolkit interviews actually use (Euclidean greatest common divisor, fast modular exponentiation, modular inverses, sieving) and the geometry that follows from a single exact predicate, the sign of a cross product: orientation, segment intersection, signed polygon area, point-in-polygon, and convex hulls.
integer overflow in intermediate results
An expression whose final value fits can still overflow in an intermediate step.
Multiplying two values before dividing is the usual case, and reordering to divide first — where divisibility permits — avoids it.
The result fits; the product on the way there does not.
// 32-bit: a = b = c = 100,000; the answer is 100,000.
(a * b) / c; // a * b = 10^10: signed int overflow before division
(a / c) * b; // exact because c divides a; every step fits
(int64_t)a * b / c; // the general fix: widen the intermediate
Interview trap. Checking only that the answer fits the type misses the intermediate product, which is where the overflow actually occurs.
Engineering practice. Reorder operations, use a wider intermediate type, or work in arbitrary precision, and say which strategy is in use.
modular arithmetic
Reducing at every operation keeps values bounded, and is required rather than optional in fixed-width arithmetic.
Addition and multiplication commute with reduction, so the result is the same as reducing only at the end but without the overflow.
Reduce at every step; the final reduction is far too late.
MOD = 10**9 + 7
acc = 1
for v in values: acc = acc * v % MOD # bounded at every step
# Without the inner %, 1,000 factors of ~10^9 is a number with ~9,000 digits.
Interview trap. Reducing only at the end overflows long before the end is reached for products of any length.
Engineering practice. Reduce after every addition and multiplication, and wrap the operations in helpers so no call site can forget.
negative values under modulo
The sign of a modulo result follows the language's convention, and several languages return a negative value for a negative dividend.
Adding the modulus before reducing normalises the result into the non-negative range regardless of the convention.
Normalise after subtraction; the sign convention differs by language.
-7 % 3 # 2 in Python
# -7 % 3 is -1 in C, C++, Java, Go and JavaScript.
idx = (a - b) % n # safe in Python
idx = ((a - b) % n + n) % n # the portable form
Interview trap. Using a raw modulo result as an array index crashes or silently reads the wrong element when it is negative.
Engineering practice. Normalise after any subtraction, and read the language's documented operator behaviour rather than assuming.
modular inverse
Division under a modulus is multiplication by a modular inverse, which exists only when the divisor and the modulus are coprime.
For a prime modulus the inverse is computed by Fermat's little theorem with fast exponentiation, and in general by the extended Euclidean algorithm.
Division is multiplication by an inverse, and it needs coprimality.
MOD = 10**9 + 7 # prime
inv = pow(x, MOD - 2, MOD) # Fermat
pow(x, -1, MOD) # Python 3.8+, works for any coprime modulus
(6 // 4) % 7 # 1 - wrong
6 * pow(4, -1, 7) % 7 # 5 - correct: 4 * 5 = 20 = 6 mod 7
Interview trap. Dividing directly and then reducing gives a wrong answer, because integer division does not commute with reduction.
Engineering practice. Compute the inverse explicitly, and verify the modulus is prime or the operand coprime before relying on the shortcut.
fast exponentiation
Raising to a power takes a logarithmic number of multiplications by squaring, rather than a linear number.
The exponent's binary representation decides which squarings are accumulated, which is why the loop halves the exponent each step.
Logarithmic multiplications, not linear.
pow(2, 1_000_000, 10**9 + 7) # 20 bit-steps; about 27 square/multiply operations
def power(b, e, m):
r = 1
while e:
if e & 1: r = r * b % m
b = b * b % m; e >>= 1
return r
Interview trap. Multiplying repeatedly is correct but linear in the exponent, which is infeasible for the exponents used in modular arithmetic.
Engineering practice. Use the squaring loop, and reduce after every multiplication when working modulo a value.
the greatest common divisor
The Euclidean algorithm computes the greatest common divisor in a number of steps logarithmic in the smaller argument.
Each step replaces the pair with the smaller value and the remainder, which decreases rapidly and terminates at zero.
Euclid is logarithmic; factorising is not.
import math
math.gcd(1_071, 462) # 21, in three steps: (1071,462) -> (462,147) -> (147,21) -> (21,0)
def lcm(a, b): return a // math.gcd(a, b) * b # divide first, or a*b may overflow
Interview trap. Computing it by factorising both numbers is correct but exponentially slower, since factorisation is far harder than the Euclidean algorithm.
Engineering practice. Use the Euclidean algorithm, and derive the least common multiple by dividing the product by it — dividing first to avoid overflow.
primality testing
Trial division up to the square root decides primality in time proportional to the square root of the value.
Any composite has a factor at or below its square root, which is what bounds the loop.
Bound the loop by the square root.
def is_prime(n):
if n < 2: return False
i = 2
while i * i <= n: # not `i < n`, not `i < n // 2`
if n % i == 0: return False
i += 1
return True
# n = 1,000,000,007: 31,621 divisor tests instead of about a billion.
Interview trap. Bounding the loop at half the value is the usual half-fix and is often described as the same optimisation, but it leaves the work proportional to the value rather than to its square root.
Engineering practice. Bound the loop by the square root, and use a probabilistic test such as Miller-Rabin for large values.
the sieve of Eratosthenes
All primes below a bound are found in near-linear time by marking multiples, rather than by testing each value.
Starting each prime's marking at its square avoids re-marking multiples already handled by smaller primes.
Start marking at p*p; the smaller multiples are already done.
def sieve(n):
prime = bytearray([1]) * (n + 1)
if n >= 0: prime[0] = 0
if n >= 1: prime[1] = 0
p = 2
while p * p <= n:
if prime[p]: prime[p*p::p] = bytearray(len(prime[p*p::p]))
p += 1
return prime
# Primes below 1,000,000: one sieve pass, versus 1,000,000 trial divisions.
Interview trap. Running trial division on every value in a range is far slower than one sieve when many primality queries are needed.
Engineering practice. Sieve once when the queries are dense within a bound, and test individually when they are sparse or very large.
floating-point is not real arithmetic
Binary floating point cannot represent most decimal fractions exactly, so equality comparisons on computed values are unreliable.
Each operation rounds to the nearest representable value, and the errors accumulate in ways that depend on the order of operations.
Equality on computed values is not a test.
0.1 + 0.2 == 0.3 # False
0.1 + 0.2 # 0.30000000000000004
import math
math.isclose(0.1 + 0.2, 0.3, rel_tol=1e-9) # True
Interview trap. Comparing two computed floating-point values for equality is the standard defect, and it passes on the values that happen to round the same way.
Engineering practice. Compare with an absolute and relative tolerance, or use exact integer or decimal representations when exactness is required.
catastrophic cancellation
Subtracting two nearly equal floating-point values destroys most of the significant digits in the result.
The leading digits cancel and the result is left with only the low-order bits, which carry the accumulated rounding error.
The naive variance formula can return a negative number.
xs = [1e8 + 1, 1e8 + 2, 1e8 + 3]
naive = sum(x*x for x in xs)/3 - (sum(xs)/3)**2 # 0.0 here; true population variance is 2/3
import statistics
statistics.pvariance(xs) # 0.6666666666666666
Welford's online algorithm avoids the subtraction of two large nearly equal quantities.
Interview trap. The naive variance formula subtracts two large nearly equal quantities and can return a negative variance.
Engineering practice. Use numerically stable formulations such as Welford's algorithm, and reformulate to avoid the subtraction where possible.
money and exact decimals
Monetary values must never be stored in binary floating point, because the rounding errors are visible to users and to auditors.
Integer minor units or a decimal type gives exact representation and predictable rounding under a documented rule.
Store minor units or a decimal type; never binary floats.
from decimal import Decimal
sum(0.1 for _ in range(3)) == 0.3 # False: 0.30000000000000004
sum(Decimal("0.10") for _ in range(3)) == Decimal("0.30") # True
Interview trap. Accumulating floating-point currency produces totals that disagree with the sum of the displayed values.
Engineering practice. Store integer minor units or a decimal type, and specify the rounding mode at every conversion.
integer-only geometry
Many geometric predicates can be evaluated exactly in sufficiently wide integer arithmetic, which removes the tolerance problem entirely.
Orientation, containment, and intersection tests are sign tests on cross products, which are exact for integer coordinates when the intermediate products cannot overflow.
Sign tests on cross products are exact for integer coordinates.
def cross(o, a, b):
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]) # exact in integers
# Converting to angles with atan2 throws that exactness away for no benefit.
Interview trap. Converting coordinates to floating point to compute an angle throws away the exactness for no benefit.
Engineering practice. Keep coordinates integral where the input allows, and phrase predicates as sign tests rather than as comparisons of computed angles.
the cross product and orientation
The sign of the two-dimensional cross product of two vectors says whether a turn is clockwise, counter-clockwise, or straight.
This single predicate underlies segment intersection, convex hulls, polygon area, and point-in-polygon tests.
One predicate underlies intersection, hulls, area and containment.
cross((0,0), (1,0), (1,1)) # 1 -> counter-clockwise turn
cross((0,0), (1,0), (1,-1)) # -1 -> clockwise
cross((0,0), (1,0), (2,0)) # 0 -> collinear
# Slopes instead: (1,0)->(1,5) is a division by zero.
Interview trap. Comparing slopes instead divides by zero for vertical segments and loses exactness for others.
Engineering practice. Use the cross-product sign rather than slopes, and treat the zero case — collinearity — explicitly.
segment intersection
Two segments intersect when each separates the endpoints of the other, tested by four orientation computations.
Collinear overlap is a separate case requiring a bounding-box check, since all four orientations are then zero.
Four orientations for the general case, a bounding box for the collinear one.
d1, d2 = cross(p3, p4, p1), cross(p3, p4, p2)
d3, d4 = cross(p1, p2, p3), cross(p1, p2, p4)
if d1 * d2 < 0 and d3 * d4 < 0: return True
# Any zero orientation is a boundary case: test whether that point lies in
# the other segment's bounding box, including the all-collinear case.
Interview trap. Handling only the general case reports no intersection for collinear overlapping segments, which is wrong.
Engineering practice. Implement the general case with orientations and the collinear case with interval overlap, and test both.
polygon area
The shoelace formula gives a polygon's area from its vertices in linear time, and its sign gives the winding direction.
Summing cross products of consecutive vertices and halving gives twice the signed area, which is exact in integer arithmetic before halving.
The shoelace sign is the winding direction; halve last.
def signed_area2(pts): # twice the signed area, exact in integers
return sum(pts[i][0]*pts[(i+1) % len(pts)][1] - pts[(i+1) % len(pts)][0]*pts[i][1]
for i in range(len(pts)))
signed_area2([(0,0), (4,0), (4,3), (0,3)]) # 24 -> area 12, counter-clockwise
Interview trap. Taking the absolute value too early discards the orientation information that many algorithms rely on.
Engineering practice. Compute the signed area, use its sign for orientation, and halve only at the end to preserve exactness.
point in polygon
The ray-casting test counts crossings of a ray from the point, with an odd count meaning inside.
Edges are counted using a half-open vertical rule so that a vertex exactly on the ray is counted once rather than twice or zero times.
A half-open edge rule counts a vertex on the ray once.
def inside(pt, poly):
x, y, c = pt[0], pt[1], False
for (x1,y1), (x2,y2) in zip(poly, poly[1:] + poly[:1]):
if (y1 > y) != (y2 > y): # half-open in y
if x < (x2-x1)*(y-y1)/(y2-y1) + x1: c = not c
return c
Interview trap. Counting vertex-touching edges without the half-open rule gives wrong results for points aligned with any vertex.
Engineering practice. Use the half-open edge convention, and handle points exactly on the boundary as a separate documented case.
convex hulls
The convex hull of a point set is computed in linearithmic time by sorting and then removing non-left turns.
Andrew's monotone chain builds the lower and upper hulls in two passes, each using the orientation predicate as its only test.
Decide the collinear rule once and apply it in both passes.
def hull(pts):
pts = sorted(set(pts))
if len(pts) <= 1: return pts
low, high = [], []
for p in pts:
while len(low) >= 2 and cross(low[-2], low[-1], p) <= 0: low.pop()
low.append(p)
for p in reversed(pts):
while len(high) >= 2 and cross(high[-2], high[-1], p) <= 0: high.pop()
high.append(p)
return low[:-1] + high[:-1]
# `<= 0` drops collinear boundary points; use the same rule in both passes.
Interview trap. Handling collinear points inconsistently between the two passes produces a hull that either includes or excludes them unpredictably.
Engineering practice. Decide whether collinear boundary points belong to the hull, and apply the same strict or non-strict comparison in both passes.
closest pair of points
The closest pair is found in linearithmic time by divide and conquer, not by comparing all pairs.
After solving both halves, only points within the current best distance of the dividing line need checking, and each has a constant number of candidates.
The strip check is a constant number of candidates per point.
# After recursing on both halves with best distance d, only points within d of the
# dividing line matter, and each can have at most 7 others within d in the strip.
# So the merge is O(n) and the whole algorithm is O(n log n), not O(n^2).
Interview trap. Assuming the strip check is quadratic misses the geometric argument that bounds the candidates per point by a constant.
Engineering practice. Sort by one coordinate once, and keep the strip sorted by the other so the constant-candidate bound applies.
avoiding square roots
Comparing distances does not require computing them, because squared distance preserves the ordering.
This keeps the computation exact for integer coordinates and avoids the cost and rounding of a square root.
Compare squared distances; the ordering is the same and it stays exact.
def d2(a, b): return (a[0]-b[0])**2 + (a[1]-b[1])**2
# Integer coordinates -> exact comparison. math.hypot introduces rounding for nothing.
Interview trap. Taking square roots before comparing introduces rounding that can invert the comparison for near-equal distances.
Engineering practice. Compare squared distances, and take the root only when the actual magnitude is reported.
combinatorial counting
Counting problems reduce to permutations, combinations, and the inclusion-exclusion principle, and choosing the wrong one is the usual error.
Permutations count ordered arrangements, combinations count unordered selections, and inclusion-exclusion corrects for over-counted overlaps.
Order and repetition decide the formula.
| Order matters | Repetition | Count |
|---|---|---|
| yes | no | n! / (n-k)! |
| yes | yes | n^k |
| no | no | C(n, k) |
| no | yes | C(n+k-1, k) |
Choosing 3 of 10: 720 ordered, 120 unordered - a factor of 6.
Interview trap. Applying a permutation count where order is irrelevant over-counts by a factorial factor.
Engineering practice. Ask explicitly whether order matters and whether repetition is allowed, and verify small cases by enumeration.
computing binomial coefficients safely
Binomial coefficients overflow quickly, so they are computed by alternating multiplication and division or in modular arithmetic.
Multiplying and dividing in an interleaved order keeps every intermediate an exact integer and bounded in size.
Interleave multiply and divide, or precompute modular factorials.
import math
math.comb(60, 30) # exact: 118,264,581,564,861,424
def comb_mod(n, k, mod):
return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod
Computing 60! then dividing overflows any fixed-width type long before the answer would.
Interview trap. Computing the factorials separately overflows for arguments well below where the result itself would.
Engineering practice. Interleave the operations, or precompute factorials and inverse factorials under a prime modulus.
the pigeonhole principle
The pigeonhole principle proves existence results that would otherwise need a search, and often bounds an algorithm's work.
It is the argument behind duplicate detection in a bounded range and behind cycle existence in a bounded-state sequence.
Proves existence; a construction is still needed for the item.
# In the 365-date, non-leap-day model, 366 people guarantee a shared birthday.
# The principle does not say which pair; finding it still takes a pass.
Interview trap. Using it to claim a specific location rather than mere existence overstates what the principle provides.
Engineering practice. Use it for existence and bounds, and pair it with a constructive method when the actual item is needed.
cycle detection in numeric sequences
A sequence over a finite state space must eventually cycle, and Floyd's algorithm finds the cycle in constant space.
The same fast-and-slow technique used on linked lists applies, since the sequence is a functional graph.
A finite state space must repeat; Floyd finds it in O(1) space.
slow, fast = f(x0), f(f(x0))
while slow != fast: slow, fast = f(slow), f(f(slow))
# Storing every seen value costs O(pre-period + cycle), which can be enormous.
Interview trap. Storing every seen value uses memory proportional to the pre-period plus the cycle, which can be far larger than needed.
Engineering practice. Use the constant-space walk for long sequences, and a set only when the state space is known to be small.
digit manipulation
Extracting digits by repeated division and modulo is exact and allocation-free, while formatted string conversion may add representation and locale concerns.
The loop yields digits from least significant upward, which is the opposite of reading order and must be reversed if order matters.
Special-case zero, and note the digit order.
def digits(n):
if n == 0: return [0] # the loop below yields nothing for 0
out = []
while n: out.append(n % 10); n //= 10
return out[::-1] # the loop produces least-significant first
Interview trap. Handling zero with the loop produces no digits at all, since the condition fails immediately.
Engineering practice. Special-case zero, and note the digit order the loop produces.
stating numeric assumptions
A numeric algorithm's correctness depends on assumptions about range, precision, and sign that must be stated rather than implied.
Coordinate bounds decide whether integer arithmetic suffices, and the input's sign domain decides whether the absolute-value and modulo edge cases arise.
Write the assumptions next to the function and test the negatives.
def midpoint(a, b):
"""Assumes 0 <= a <= b <= 2**63 - 1."""
return a + (b - a) // 2
# For a < 0 the floor division rounds towards negative infinity, which may not be
# what the caller means by "midpoint".
Interview trap. Assuming positive inputs is the single most common unstated assumption, and negative inputs then produce silent wrong answers.
Engineering practice. Write the assumptions next to the function, validate them at the boundary, and test the negative and zero cases.