For the past year or so, I’ve been asking an interview question which seems like it should be straightforward, but has turned out to be deceptively hard. The reason I like it is that it requires a candidate to convert a very common, well-defined, well-understood task from paper into code. There’s no trick, no gotcha, no hidden depth – it simply requires that you be able to analyze, break down and express an algorithm you know well.
In short, I ask candidates to add two numbers. Here’s my script:
How’s your arithmetic? (candidate laughs nervously)
I would like for you to write a method that will add two numbers together. These numbers will be:
- positive integers (i.e., don’t worry about negative numbers or decimals)
- represented as Strings
- arbitrarily big (i.e., could theoretically be thousands or millions of digits long)
- valid (i.e., let’s not waste time worrying about invalid input)
You are not allowed to use BigDecimal or BigInteger. For obvious reasons, you can’t simply convert the Strings into ints, longs, doubles, etc. – there’s no guarantee the numbers would fit.
I then write the following code up on the board, to show them the method signature:
String result = add("1234","567");
And then, to set them on the right path, I work out the example in front of them, loudly mumbling “carry the one…”
1234 567 ---- 1801
Now, you may be thinking to yourself, “what a simple problem! I could do that with two prefrontal cortexes tied behind my back!” And I’ll grant you, I didn’t think that it would be that hard – I’d originally wanted to ask candidates to multiply two arbitrarily long numbers. But it turns out that there are a surprising number of places where things can go wrong.
So, I’m going to break this problem down and walk through all of the problem areas. I’ve done this a couple of times in the past, but this time there’s a twist. In order to get the dissection, I want you first to take a crack at the problem. If you code up a solution, and send it to me (as plain text, not an attachment, please), I’ll reply with the full breakdown. And, unless things get too crazy (please don’t hurt me, HackerNews), I’ll try to give specific feedback on each submission.
Let the games begin :)
Update: Whew! Thanks everyone for the incredible response! I need to get back to other things, so I’m officially ending the challenge (though you should still give it a try :). I’ve unlocked the solution page, for those who are interested.