James Pine Has A Blog

Jump to Comments

Problem #15
Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

I often used this question during interviews and suprisingly, very few candidates were able to make much progress with it. I wasn’t looking for a candidate to code it 100% correctly on a whiteboard, but I expected them to at least come up with a way to attack the problem as well as a way to optimize their code. I struggled to optimize it initially due to a stupid bug and the fact I had just driven 4hrs to Yosemite after work, but at least I had an idea 😉

Of course there is a way to arrive at the solution purely via combinatorics, but that’s no fun…the first step to breaking down the problem is to realize one can only move right or down at any given point in the grid. This leads to a simple recursive solution:

def computeSlow(d,r):
 if d == 0 or r == 0:
  return 1
 else:
  return computeSlow(d-1,r) + computeSlow(d,r-1)

# compute a 5x5 grid
print computeSlow(5,5)

This works, but an 11×11 grid gives my computer pause, and by 13×13 it doesn’t return. The problem is many of the sub-problems being solved by the recursion get solved over and over and over again. Using caching/memoization allows us to solve the problem in the blink of an eye:

cache = dict()

def compute(d,r):
 key = str(d) + "," + str(r)
 if r > d: #no point storing the same value for 3,5 and 5,3
  key = str(r) + "," + str(d)
 if d == 0 or r == 0:
  return 1
 else:
  if key in cache:
   return cache[key]
  else:
   temp = compute(d-1,r) + compute(d,r-1)
   cache[key] = temp
   return temp

Problem #16
What is the sum of the digits of the number 2^1000?

This can be solved easily via the commandline:

python -c 'sum(map(int,str(2**1000)))'

Problem #17
How many letters would be needed to write all the numbers in words from 1 to 1000?

I tried to solve this via pen and paper, but made an error along the way, so I ended up translating it to code. Computers are really good at not making arithmatic mistakes. First I broke the numbers down into reusable parts:

oneToNine = ["one","two","three","four","five","six","seven","eight","nine"]
tenToNineteen = ["ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"]
ties = ["twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"]

Then I totalled up the number of characters for the numbers 1-99:

oneToNinetynineCount = sum([len(x) for x in oneToNine])
oneToNinetynineCount += sum([len(x) for x in tenToNineteen])
oneToNinetynineCount += sum([len(x) for x in ties])
oneToNinetynineCount += sum([len(x)+len(y) for x in ties for y in oneToNine])

total = oneToNinetynineCount

Next I computed 100-999. It’s easy to shortcut since, for example the range 300-399 contains 1 threehundred, 99 threehundredand and then the counts for 1-99.

for x in oneToNine:
 xHundredCount = len(x) + 7 # hundred = 7 chars
 total += xHundredCount + (xHundredCount + 3) * 99 + oneToNinetynineCount # and = 3 chars

Lastly one just needs to add 11 to the total for the number onethousand.