Today I decided to take the code challenge of a startup full of really smart people doing a social networking site. They use interviewstreet.com for their code test, and I think it’s a really good way to get the riff raff out if you’re looking to hire someone who is really top notch.
You get 1 hour to complete the two interview questions. I managed to successfully complete one of the questions. I chalk up not completing the other question due to it being poorly written. It’s possible that I just can’t read too. I’ll break down my thought process in solving the problem I did successfully solve, and maybe you too can know how I think.
Here is the problem:
A 7-digit number consists of 7 distinct digits (from 0-9). The product of the first 3 digits = product of central 3 digits = product of last 3 digits. Find the middle digit
There’s a lot of cool math things going on in this problem:
- Transitivity Property
- 7 digit number, made up of unique digits -> Permutation
- Even though the problem states 0 is part of the set of numbers, we can’t use it because 0 * any group of number is zero.
Ok, so knowing these characteristics of the problem, I set about a plan of attack:
- Find all permutations put them in a list.
- Iterate through list of permutations, use transitivity property to find answer
- ???
- profit
So I first set out to write a function to find all the permutations. How big of a problem is that?
P = n! / (n – k)!
With our problem set that’s 181,440 possibilities. Ok, so I gotta write an efficient program to do that…
My head started hurting, surely there’s a library that will help? Yes? Ok, python has itertools.permutations()… don’t re-invent the wheel… So here’s the final code:
import itertools
permutations = itertools.permutations([1,2,3,4,5,6,7,8,9],7)
for candidate in permutations:
val = candidate[0] * candidate[1] * candidate[2]
if val == candidate[2] * candidate[3] * candidate[4]:
if val == candidate[4] * candidate[5] * candidate[6]:
print candidate[3]
break
And the answer is 2. Cheers.