A long time ago in a job interview I was asked the following question:
How many consecutive zeros are at the end of one thousand factorial?
After a little bit of thinking I managed to figure out the trick (hint: think about the factors of 1000! that would produce zeros at the end of the product when you multiply - then count those factors). I didn't get the job, but I liked the question so much I often use it when I conduct interviews.
I happen to think that asking a question like this out the blue isn't a very good way to evaluate whether someone will be a good developer or not. What I like to do instead is have a conversation about factorials that eventually leads to the above question. For example, I get them to write both an iterative and a recursive function to calculate factorials. That leads to a discussion of topics like error handling, input validation, stack overflow, and tail recursion. The strong candidates breeze through this stuff. I'm constantly amazed by how many "senior" developers don't breeze through this stuff.
If they're doing reasonably well I will eventually pull out the above question out and we will discuss it. It's the last technical question that I ask and it seems to wrap things up nicely.
One time I was interviewing a developer who I will call Ted. Ted was obviously smart, and he had tons of experience, more than me in fact. He breezed through all of my questions, and his coding skills were solid. We progressed quickly through the topics I wanted to talk about. When we got to my last question, the one listed above, I figured that he would breeze through that too. But I figured wrong. For some reason he struggled with it. He kept getting himself confused and going around in circles. I ended up walking him through the steps to a solution, but I don't think he ever really understood what I was saying. It was like he was a different person. Eventually I ended the interview and sent him on his way.
I figured that I would never see him again.
Once again I figured wrong.
The next day Ted showed up at my office and asked to see me. He had a printout in his hand which he handed to me. There were numbers all over it.
"What's this?" I asked.
"It's one thousand factorial," he said. "I wrote a program to calculate it and count the zeros on the end."
I squinted at the paper. Sure enough, there was an enormous number followed by the number 249 at the bottom, which is in fact the right answer for the number of zeros. I had never actually bothered to calculate 1000!, so I had no idea if his enormous number was correct or not.
Intrigued, I asked him how his program worked. It turns out that Ted had write a multiplication function that worked on string representation of numbers, like this:
string strProduct = MultiplyStrings("1000","999");We were both C++ guys and this seemed like a perfectly fine solution. After Ted left I sat down and wrote my own version of a program to do this. Instead of using strings I used integer vectors. Writing the MultiplyVector function was a little tricky but soon I had calculated 1000! for myself. Ted's number matched mine. I happily filed the program away and went back to whatever it was I was doing before Ted showed up. And then I forgot all about it.
Many months went by and
I decided to learn python. Today I read the
Wikipedia page for the python programming language. I figured that it was as good a place as any to start. About halfway down it says that an int is "an immutable fixed precision number of unlimited magnitude". Immediately I thought of the factorial problem. It would be trivial to calculate 1000! if you had integers of unlimited magnitude. Five minutes later I had written my first python program:
import sys
sys.setrecursionlimit(1001)
def factorial(n):
if (n < 2):
return 1
return n * factorial(n - 1)
def count_zeros(n):
if (n % 10 != 0):
return 0
return 1 + count_zeros(n / 10)
a = factorial(1000)
print a
print
print count_zeros(a)
When I first tried this I didn't have the bit about setting the recursion limit and I got a "maximum recursion depth exceeded" error. Python doesn't support tail recursion, so my options were to rewrite it using a loop or else figure out how to increase the recursion limit. A Google search quickly lead me to the setrecursionlimit function, and I was on my way. Ironically, the default recursion limit is 1000. I only had to increase the limit by 1. Of course, rewriting this using a loop would have been trivial as well, but using recursion to solve factorials is not only natural, it's the canonical example.
My entire experience with Python consists of walking through the Google Application Engine tutorial, reading the aforementioned Wikipedia page, and then writing this program. The syntax is very easy to learn because there is almost no syntax. The one hard thing you have do for this program, storing and multiplying really big integers, is already taken care of. So I was able to write a program in Python, a language I don't know, in about 5 minutes. By comparison it took me about 30 minutes to write the same program in C++, a language I've been programming in for about 15 years. To be fair, I could have used a "big number" library in C++, but I wanted to work out the details out for myself. I was thinking that it might make a good interview question. But still, 5 minutes in a language I don't even know? Awesome.
I wonder what else Python can do.
