Math and Geometry for Interviews

Objectives and sequence#

• Use GCD to normalize ratios and compute LCM by dividing before multiplying.
• Normalize signed remainders into a documented modular range.
• Translate points to vectors and compare squared distances without square roots.
• Test collinearity with an exact cross product under a stated integer-range assumption.

Recognition boundaries#

From baseline to method#

Simple baseline: For every pair of points, compare floating-point slopes and Euclidean distances, then merge apparently equal directions. This is quadratic and unstable around vertical lines, sign conventions, and floating equality.

1. Translate each point (x, y) relative to the origin (ox, oy) as (dx, dy). Translation preserves direction and collinearity.
2. For a nonzero vector, divide both components by gcd(|dx|, |dy|). Equal rays then receive the same signed primitive pair without division or floating-point equality.
3. Compare distances with dx² + dy². Square root is monotonic for nonnegative inputs, so it cannot change which point is nearer.
4. For three integer points a, b, and c, test (bx-ax)(cy-ay) = (by-ay)(cx-ax). State the product-width assumption before claiming this is overflow-safe.
5. For arithmetic periods, compute lcm(a, b) as |a / gcd(a, b) * b|, checking the multiplication in the target integer type. Normalize a remainder with ((value % modulus) + modulus) % modulus when the language remainder can be negative.

Worked example#

From origin (1, 1), group non-origin points by ray and return the nearest squared distance for every normalized direction.

Input

origin = (1, 1); points = [(3, 3), (2, 2), (-1, -1), (1, 4), (1, 1)]

Contract

Coordinates are integers whose coordinate differences and squared sums fit the chosen integer type. A point equal to the origin has no direction and is ignored.

Expected

{(-1, -1): 8, (0, 1): 9, (1, 1): 2}; the repeated origin is ignored

Trace summary: Translate each point, reduce the nonzero vector by its absolute-component GCD, and keep the smaller squared distance under that signed direction key.

Pseudocode and tested references#

The pseudocode expresses the mathematical normalization and an abstract pair-keyed map. The references below are executable implementations of the worked example; Python uses tuple keys, while Java supplies an immutable Direction record and long products.

nearestByDirection(origin, points):
  best = empty map from integer pair to integer
  for point in points:
    dx = point.x - origin.x
    dy = point.y - origin.y
    if dx == 0 and dy == 0: continue
    divisor = gcd(abs(dx), abs(dy))
    direction = (dx / divisor, dy / divisor)
    distanceSquared = dx * dx + dy * dy
    best[direction] = min(best.get(direction, infinity), distanceSquared)
  return best

from math import gcd

def nearest_by_direction(origin, points):
    ox, oy = origin
    best = {}
    for x, y in points:
        dx, dy = x - ox, y - oy
        if dx == 0 and dy == 0:
            continue
        divisor = gcd(abs(dx), abs(dy))
        direction = (dx // divisor, dy // divisor)
        distance_squared = dx * dx + dy * dy
        best[direction] = min(best.get(direction, distance_squared), distance_squared)
    return best

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class MathGeometryReference {
    public record Point(long x, long y) {}
    public record Direction(long dx, long dy) {}

    private static long gcd(long a, long b) {
        while (b != 0) {
            long remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    public static Map<Direction, Long> nearestByDirection(Point origin, List<Point> points) {
        Map<Direction, Long> best = new HashMap<>();
        for (Point point : points) {
            long dx = point.x() - origin.x();
            long dy = point.y() - origin.y();
            if (dx == 0 && dy == 0) continue;
            long divisor = gcd(Math.abs(dx), Math.abs(dy));
            Direction direction = new Direction(dx / divisor, dy / divisor);
            long distanceSquared = dx * dx + dy * dy;
            best.merge(direction, distanceSquared, Math::min);
        }
        return best;
    }
}

Time

O(n log C), where C is the largest absolute coordinate difference, because each point performs one Euclidean GCD.

Space

O(r), where r is the number of distinct rays and r ≤ n.

Assumptions

Hash-map operations are expected O(1); coordinate subtraction, squaring, cross products, and divide-before-multiply LCM checks must fit the stated integer representation.

Failure modes and edges#

Edge cases

• A point equal to the origin has no direction.
• Opposite rays such as (1,1) and (-1,-1) remain distinct; a line-through-origin problem would deliberately canonicalize their signs instead.
• Horizontal and vertical vectors normalize without slope division.
• gcd(0, k) is |k|; define gcd(0, 0) separately because it cannot normalize a direction.
• LCM with a zero argument is zero under the lesson contract; check the target language's minimum-integer absolute-value behavior.
• A negative dividend may produce a negative remainder in Java, so normalize it before using it as a circular index.

Wrong approaches

Three-stage hint ladder#

Narrated reasoning

I need equality of directions, not approximate angles, so I will preserve the coordinates as integers. After translating by the origin, all positive multiples of one vector describe the same ray. Dividing by the component GCD gives one primitive representative. The sign is part of a ray: northeast and southwest should not collapse unless the prompt asks for an undirected line. I only compare distances, so squared distance is sufficient. I will confirm the coordinate bounds make the products safe. I will test the origin, a vertical vector, repeated directions, and the opposite direction.

Reasoning checkpoints#

Guided exercises

• Given positive service periods 84 and 126, compute their first shared reset time with Euclid's algorithm and divide-before-multiply LCM; then normalize offset -17 into [0, 12).
  Checkpoint: gcd=42, lcm=252, and the normalized offset is 7. State the integer-width check before multiplication.
• For A=(1,2), B=(4,8), C=(7,14), decide collinearity without slopes and compare |AB| with |AC| without square roots.
  Checkpoint: Both cross products equal 36, so the points are collinear; AB²=45 and AC²=180, so B is nearer to A.

Practice and transfer#

Unseen variant: Count distinct undirected lines through an origin for integer points, so opposite rays must now be equal. Define a deterministic sign rule before coding.

Checkpoint: After GCD reduction, flip both components when dx<0 or dx==0 and dy<0; this maps opposite primitive vectors to one key.

Practice handoffs

• Practice exact distance comparisonTransfer squared-distance reasoning to a bounded-selection problem.
• Return to array practiceReinforce the scan and map mechanics without expanding into specialist geometry.

Follow-up constraints

• How would you report a checked overflow instead of silently wrapping an LCM?
• When would a tolerance-based floating comparison be the correct contract rather than integer cross products?
• Adapt the ray grouping to count points instead of storing the nearest squared distance.

Sources and review#

This original Engineering Foundry lesson received Codex self-review on 2026-09-05; independent human editorial review is not claimed.

• Euclidean algorithm for computing the greatest common divisor (opens in a new tab) - Euclid's algorithm and the divide-by-GCD LCM identity; machine overflow checks remain an Engineering Foundry implementation requirement.
• MIT 6.006 Introduction to Algorithms lecture notes (opens in a new tab) - Academic cross-check for algorithmic representation and complexity reasoning, not an interview-frequency claim.