The Interview Challenge

Posted by James Lord on March 21, 2015

The Interview Challenge

Years ago during the first dot-com boom, I had an interview at a company populated by a bunch of Caltech grads. During the interview, they wanted to get a sense of my thinking process and asked a classic “difficult” question – prove that a number is divisible by three if the sum of its digits is divisible by three. My response was to talk about how I would approach the problem (mathematical induction, watch how digits roll over as you keep increasing the number, etc., etc.). I didn’t solve the problem, but must have been convincing since I got an offer.

Fast forward 15 years (yikes!). When working out on a treadmill these days, I often watch Khan Academy videos. Last month I was working my way through cryptography to understand how the RSA algorithm worked. Part of the series consisted of someone showing aspects of modular arithmetic by breaking apart a set of beads into sets of equal size and showing remainders, and grouping them different ways. I highly recommend the series for anyone interested in the underpinnings of crypto.

Thinking about the crypto series during my evening commute, my mind went back to working that problem of long ago, visualizing beads in my head… how many times does 3 go into 1000? Hmm… 333 groups of 3 beads leaving 1. Remainder 1, sum of digits is 1… Eureka! Problem solved with modular arithmetic! Here is the insight from that car ride and how it works:

  1. Think about a number that consists of a 1 followed by all zeros such as 1000. The largest multiple of three less than 1000 is 999 – leaving a remainder of 1. 1 also happens to be the first digit. Let’s take another example 3000. If we use the same approach, we can subtract 3*999 which leaves 3, also the first digit. This same approach holds whether the number is 10, 200, 5000, or 700000000. If we subtract multiples of 99… from the number, only the first digit will remain.

  2. Now let’s consider a more complicated number, like 1200. We use the same approach, but in this case we first break apart the number into the thousands and hundreds part. So 1200 becomes 1000 + 200. We do the 1000 (leaving 1) and we do the 200 (leaving 2). When we add the remainders together you get three, which is divisible by three. So 1200 is divisible by 3. To recap, we are just “grouping” the number into a sum of groups that we know are divisible by three, and what is left is then checked to see if it is divisible by three.

    1200

    1000 + 200

    (1 + 999) + (2 + 99 +99)

    Since 999 and 99 are both divisible by three, we remove them

    1 + 2

    3

    Since 3 is divisible by three, 1200 is divisible by three.

  3. This approach works for any arbitrary number by breaking it apart in a similar fashion.

It’s not a formal proof, but it’s enough to convince me. It would have been fun to have nailed it during the 45 minute inteview, but I lacked the insight to break apart the number into the different units (tens, hundreds, etc…) In case you’re wondering, no, I did not accept the offer. I had one from a company with a “better” business model – two years later to up in a billion dollar puff of smoke.