Happy number: the check, then serving it at scale

A phone screen that starts with a small coding problem and turns it into a service. First write the check; then the interviewer asks how you would answer it for a stream of requests.

Part 1: decide whether a number is happy

Start with a positive integer n. Replace it with the sum of the squares of its decimal digits, and repeat. Return True if the sequence reaches 1, or False if it falls into a cycle that never includes 1.

Unless you agree on a different interface with the interviewer, assume is_happy(n: int) -> bool, with 1 <= n <= 2^31 - 1.

is_happy(19)  ->  True     # 19 -> 82 -> 68 -> 100 -> 1
is_happy(4)   ->  False    # 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

A strong answer covers:

• A helper that sums squared digits with % 10 and // 10.
• Loop detection with a set of seen values, or Floyd's fast and slow pointers for O(1) space.
• Why the sequence must either reach 1 or cycle: after one step any 32-bit value is at most 10 × 81 = 810, so values stay bounded.
• Tests: 1, a happy number, a number in the cycle, a large input.

Part 2: serve the check at scale

A service receives a positive integer n per request. It repeatedly replaces n with the sum of the squares of its decimal digits and answers whether the sequence reaches 1. Design it to serve billions of requests over time with low latency, without recomputing the same work again and again.

A strong answer covers:

• The key observation: one step takes any 64-bit number (at most 20 digits) to at most 20 × 81 = 1620, so after one step every value is small.
• Precompute the answer for every value up to that bound once (a table of about 1,600 booleans) and ship it with each server; a request then costs one digit-square step and one lookup.
• Why a distributed cache is unnecessary for the computation itself, and when a cache in front still helps (request deduplication, very large inputs).
• Stateless servers behind a load balancer, autoscaling, rate limiting, and what to monitor.

Follow-ups

• Count the steps to reach 1.
• Return the number of steps to reach 1, not just yes or no.
• The rule changes to cubes of digits. What changes in the design?