Math & Geometry
Problems that lean on a specific mathematical insight — number theory, combinatorics, or coordinate geometry — rather than a general algorithmic pattern.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain how the Sieve of Eratosthenes finds all primes up to n efficiently.(show answer)
Start with all numbers from 2 to n marked as potentially prime. For each number p starting from 2, if it's still marked prime, mark all of its multiples (2p, 3p, 4p, ...) as not prime — since any multiple of p greater than p itself is composite. Repeat for the next unmarked number. This avoids checking primality of each number individually (which would be at least O(sqrt(n)) each); the sieve's total work across all numbers works out to O(n log log n).
Q2.Explain the Euclidean algorithm for computing GCD(a, b).(show answer)
GCD(a, b) = GCD(b, a mod b), applied repeatedly until the second argument reaches 0 — at which point the first argument is the GCD. This works because any common divisor of a and b must also divide a mod b (since a mod b = a - k*b for some integer k). Because a mod b shrinks quickly (at least halving every two steps), the algorithm runs in O(log(min(a,b))) time, far faster than checking every possible divisor.
Q3.How is the cross product used to determine whether three points make a clockwise or counter-clockwise turn?(show answer)
For points A, B, C, compute the cross product of vectors (B-A) and (C-A): (Bx-Ax)*(Cy-Ay) - (By-Ay)*(Cx-Ax). A positive result means a counter-clockwise turn at B, negative means clockwise, and zero means the three points are collinear. This is the core building block of algorithms like the convex hull, which repeatedly need to determine turn direction to decide which points form the hull's boundary.
Q4.How would you efficiently compute the area of a simple polygon given its vertices in order?(show answer)
The Shoelace formula: sum (x_i * y_{i+1} - x_{i+1} * y_i) across all consecutive vertex pairs (wrapping the last vertex back to the first), then take half the absolute value of that sum. This computes the signed area in O(n) time for n vertices, without needing to decompose the polygon into triangles manually.