[Updated: This post is now public – commenting on submissions takes a lot of time to do right!]

Thank you for your submission! As promised, here’s the second half of the post – the actual dissection of the problem.

So first, let’s talk through the basic algorithm for addition:

1. Put one number on top, the other number on the bottom (traditionally, the number with more digits goes on top, but this is visual sugar, not a requirement)
2. There’s a third row used for the “carry”
3. Moving right to left, for each column:
   • Add the numbers in the column
   • Put the result%10 into the answer
   • If the result >= 10, put a one into the “carry” row for the next column to the left
4. Once you are past the last column on the left (including the carry), you’re done!

1234 + 567 = ?

1234
 567
----

  1
1234
 567
----
   1

 11
1234
 567
----
  01

 11
1234
 567
----
 801

 11
1234
 567
----
1801

OK, that’s a little pedantic, but it makes the point. So, how do you get your code to do that? First, as always, let’s start out with a stub.

String add(String a, String b) {
}

Next, we need to make sure we’re handling the carry correctly. Although conceptually there’s a third row, all we need to know is whether we had a carry from the last column.

String add(String a, String b) {
  boolean carry = false; // we start without a carry
}

Let’s set up a variable for an answer, move right to left, add the contents of each column with the carry and put it into the answer.

String add(String a, String b) {
  boolean carry = false; // we start without a carry
  String answer = "";
  for (every column, right to left) {
    int temp = a + b + (carry ? 1 : 0);
    answer = Integer.toString(temp % 10) + answer;
    carry = temp >= 10;
  }
  return answer;
}

Note that I’m pre-pending the sum to the answer – we’ll come back to this later.

Lastly, we have to specify what happens if there’s a carry at the very end (e.g., if you add “6” and “4”).

String add(String a, String b) {
  boolean carry = false; // we start without a carry
  String answer = "";
  for (every column, right to left) {
    int temp = a + b + (carry ? 1 : 0);
    answer = Integer.toString(temp % 10) + answer;
    carry = temp >= 10;
  }
  if (carry) {
    answer = "1" + answer;
  }
  return answer;
}

OK, so here are the outlines of an answer. It’s ugly, and there are a lot of details that need to get worked out, but the basic algorithm is there.

Before we go any further, and because it hurts my eyes, let’s handle the carry a little more elegantly. It makes intuitive sense to treat it as a boolean, but it’s faster, simpler, and more maintainable to replace it with an int, and to make the carry just like the other numbers in the column:

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  for (every column, right to left) {
    int temp = a + b + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  if (carry > 0) {
    answer = "1" + answer;
  }
  return answer;
}

The next problem we have is to actually get the numbers from the columns. Let’s assume we have a method atoi() to convert chars ‘0’ – ‘9’ to ints 0 – 9.

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  for (int i = each column index, from right to left) {
    int a_value = atoi(a.charAt(i));
    int b_value = atoi(b.charAt(i));
    int temp = a_value + b_value + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  if (carry > 0) {
    answer = "1" + answer;
  }
  return answer;
}

Well, this isn’t quite right. The two numbers might have a different number of digits, so 1) using the same index won’t necessarily give us numbers from the same column, and 2) we could run out of digits in one String before the other. What we want is to be counting from the end of the Strings.

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  for (int i = 0; i < a.length() || i < b.length(); i++) {
    int a_value = atoi(a.charAt(a.length() - i - 1));
    int b_value = atoi(b.charAt(b.length() - i - 1));
    int temp = a_value + b_value + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  if (carry > 0) {
    answer = "1" + answer;
  }
  return answer;
}

Let’s also make sure we aren’t running off the front of the Strings:

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  for (int i = 0; i < a.length() || i < b.length(); i++) {
    int a_value = i >= a.length() ? 0 : atoi(a.charAt(a.length() - i - 1));
    int b_value = i >= b.length() ? 0 : atoi(b.charAt(b.length() - i - 1));
    int temp = a_value + b_value + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  if (carry > 0) {
    answer = "1" + answer;
  }
  return answer;
}

We seem to be using a.length() and b.length() a lot. Let’s tidy that up.

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  int alen = a.length();
  int blen = b.length();
  for (int i = 0; i < alen || i < blen; i++) {
    int a_value = i >= alen ? 0 : atoi(a.charAt(alen - i - 1));
    int b_value = i >= blen ? 0 : atoi(b.charAt(blen - i - 1));
    int temp = a_value + b_value + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  if (carry > 0) {
    answer = "1" + answer;
  }
  return answer;
}

Lastly, that special case at the end of the method is bothering me a little. We don’t really have to change it, but let’s just get rid of it to make the code a little cleaner (if slightly less performant).

String add(String a, String b) {
  int carry = 0; // we start without a carry
  String answer = "";
  int alen = a.length();
  int blen = b.length();
  for (int i = 0; i < alen || i < blen || carry > 0; i++) {
    int a_value = i >= alen ? 0 : atoi(a.charAt(alen - i - 1));
    int b_value = i >= blen ? 0 : atoi(b.charAt(blen - i - 1));
    int temp = a_value + b_value + carry;
    answer = Integer.toString(temp % 10) + answer;
    carry = temp / 10;
  }
  return answer;
}

Voila! We’re done, right? No, not yet. First, let’s talk about atoi(). This is an area where people tend to completely blank. Some try to do the following:

int atoi(char ch) {
  return Integer.valueOf(ch);
}

This is nonsensical, of course – they’re trying to treat ch as a String. Others will explicitly convert the char into a String, then use Integer.valueOf() – which works, I guess, but is pretty ugly. It’s great to see a candidate who understands that chars are fundamentally numbers, and can do this:

int atoi(char ch) {
  return ch - '0';
}

Honestly, I used to care a lot more about this, but along with expecting coders to know key ASCII values, powers of two, and bit math, I’ve pretty much thrown up my hands and accepted that these are lost skills. Still, if you know how to do this, you’ll bring a smile to your interviewer’s face.

So what do you think the big-O time is for the code above? Most people will look at it and answer “O(n)”. Unfortunately, the answer is actually O(n²). Can you see why? As described in this post, concatenating Strings in a loop is a common but costly mistake. Not only is it O(n²) time, it also allocates O(n²) bytes of memory – most of this is immediately garbage collected, but that puts additional pressure on GC, and can have disastrous results. Luckily, avoiding this is straightforward – just use a StringBuilder.

String add(String a, String b) {
  int carry = 0; // we start without a carry
  int alen = a.length();
  int blen = b.length();
  StringBuilder answer = new StringBuilder();
  for (int i = 0; i < alen || i < blen || carry > 0; i++) {
    int a_value = i >= alen ? 0 : (a.charAt(alen - i - 1) - '0');
    int b_value = i >= blen ? 0 : (b.charAt(blen - i - 1) - '0');
    int temp = a_value + b_value + carry;
    answer.append(temp % 10);
    carry = temp / 10;
  }
  return answer.toString();
}

Hmm, well, that won’t work – we’re appending to the StringBuilder, not prepending, so our answer is going to come out reversed. Luckily, it’s easy to reverse a StringBuilder object:

String add(String a, String b) {
  int carry = 0; // we start without a carry
  int alen = a.length();
  int blen = b.length();
  StringBuilder answer = new StringBuilder();
  for (int i = 0; i < alen || i < blen || carry > 0; i++) {
    int a_value = i >= alen ? 0 : (a.charAt(alen - i - 1) - '0');
    int b_value = i >= blen ? 0 : (b.charAt(blen - i - 1) - '0');
    int temp = a_value + b_value + carry;
    answer.append(temp % 10);
    carry = temp / 10;
  }
  return answer.reverse().toString();
}

If you’re feeling plucky, you can do an in-place reversal of answer using charAt() and setCharAt(), but you get the idea. The only thing left is to set the StringBuilder capacity up-front, so as to avoid having to resize and copy it as it grows past the bounds of its buffer.

String add(String a, String b) {
  int carry = 0; // we start without a carry
  int alen = a.length();
  int blen = b.length();
  int max_answer_len = (alen > blen ? alen : blen) + 1;
  StringBuilder answer = new StringBuilder(max_answer_len);
  for (int i = 0; i < alen || i < blen || carry > 0; i++) {
    int a_value = i >= alen ? 0 : (a.charAt(alen - i - 1) - '0');
    int b_value = i >= blen ? 0 : (b.charAt(blen - i - 1) - '0');
    int temp = a_value + b_value + carry;
    answer.append(temp % 10);
    carry = temp / 10;
  }
  return answer.reverse().toString();
}

As you can see, there are a lot of places to make mistakes. Not knowing how to convert chars to ints. Not reversing the String, or forgetting to handle the case where there’s a carry at the end of the loop. Terrible big-O time. Messing up the column indexing. Logical errors. Off-by-one errors. Not handling Strings of different sizes.

Being able to translate an algorithm into code is the defining characteristic of a software engineer, and this is a straightforward algorithm that everyone knows (well, there was that one candidate who tried to convince me that he didn’t add often). If your code had problems, then now is the time to practice – especially if you’re about to start interviewing. Try adding a list of numbers. Try it with decimals, or negative numbers. Try multiplication (division is no fun – I’d recommend against it, unless you like pain). The nice thing about arithmetic is that it’s incredibly easy to test, so you can do these types of exercises on your own and still be confident that your solution works.

Anyway, thanks for taking part in the challenge – I hope you enjoyed it!