The blog of dlaa.me

A few days ago, Brent Simmons published a thoughtful blog post about one aspect of programming interviews. As someone who conducts interviews regularly for work, the topic is of interest to me. Rather than summarizing the post, I encourage you to go read Practicing the Coding Challenges now. (You might also enjoy some of the replies to Brent's tweet linking to it.)

After reading the post, I tweeted a response:

I agree with the spirit of this post - that clarity beats premature optimization - but feel the conclusion skips an important point. The "efficient" solution is correct for arbitrarily large numbers while the "clear" one fails after MAX_INT (or similar).

Brent replied:

I thought about discussing that, but felt like I'd be muddying up the post too much.

And I responded:

Understood, thanks! I don't know how it was posed on LeetCode, so that difference may not even be relevant. But if I were discussing this with a candidate during an interview, it's something I'd want them to raise for discussion as an indication they're thinking about edge cases.

And I kept thinking about this problem in the context of a programming interview. When I saw Olof Hellman's well-reasoned follow-up post Practicing the Coding Challenges, I realized I wasn't the only one.

I was curious what the "clear" and "efficient" solutions might look like in practice, so I decided to write them and see. I used JavaScript because it's my "go to" language. Things will look a little different in other languages, but I had to pick one and I chose something popular. I'm not including comments in the code below because they'll distract from it and I'm not validating parameters (for null-ness or range) per typical JavaScript practice.

As a reminder, here's the problem definition:

You need to add two numbers and get a sum. But, importantly, the digits of those numbers are stored in arrays, and they're backwards.

The return value also needs to be in a backwards array.

If inputs are [4,2,6] and [3,8,0,8], the function should return [7,0,7,8] - because 624 + 8083 == 8707.

Let's start with the "clear" approach. The point here is to be obvious and straightforward - like you normally want your code to be. Recall Brent's pseudocode proposal:

let num1 = number(from: array1)
let num2 = number(from: array2)
let sum = num1 + num2
return array(from: sum)

Now, in order to run that, we need to implement those two conversion functions. As John Siracusa pointed out, we can do anything we want inside there and because we want to handle arbitrarily large inputs, we'll use JavaScript's BigInt built-in.

As an aside, BigInt does not have widespread support across browsers. In fact, none of the three JavaScript tools I use on iOS support it and I had to switch to a "real" computer to finish this post.

Okay, here's what I came up with:

function clear(array1, array2) {
  const num1 = toBigInt(array1);
  const num2 = toBigInt(array2);
  const sum = num1 + num2;
  return toArray(sum);
}
function toBigInt(arr) {
  const copy = [...arr];
  copy.reverse();
  const numberAsString = copy.join("");
  return BigInt(numberAsString);
}
function toArray(num) {
  const numString = num.toString();
  const charArray = numString.split("");
  const digitArray = charArray.map(Number);
  digitArray.reverse();
  return digitArray;
}

Because this is the "clear" implementation, each line does a single thing and I've mostly avoided idiomatic JavaScript. You could argue map(Number) is a bit subtle, but it should be familiar to most JavaScript programmers. The BigInt constructor takes a Number or a String, so we need to bounce the input through a String on the way into/out of BigInt. We copy the input array to avoid mutating data we don't own.

Okay, so what does the "efficient" code look like? Here's what I came up with:

function efficient(array1, array2) {
  const length = Math.max(array1.length, array2.length);
  const res = new Array(length);
  let carry = 0;
  for (let i = 0; (i < length) || carry; i++) {
    const sum = (array1[i] || 0) + (array2[i] || 0) + carry;
    carry = (sum >= 10) ? 1 : 0;
    res[i] = sum % 10;
  }
  return res;
}

Because this isn't the "clear" solution, I took some liberties with this implementation in the interest of compactness and efficiency. The output array is pre-allocated (though it may need to grow by one) and there is a single loop over the input with no redundancy and fairly little overhead I see. I'll acknowledge some folks might be uncomfortable with the (deliberate) ignorance of array bounds and that the use of carry in the loop condition may be too clever by half. (It can be removed at the cost of a single additional line of code, but I like how this approach reuses the core logic for the final overflow.) Otherwise, I tried not to be unnecessarily obscure.

Conclusions?

The "clear" code is definitely clearer, but it's not as simple as it originally seemed to be. The need to implement helper functions basically tripled the amount of code that needed to be written. The "efficient" code is smaller and ought to be quite a bit cheaper to run considering the algorithmic efficiency and the fact that it doesn't require JIT-ing BigInt or the need for String parsing. In fact, by eschewing those dependencies, it's able to run in many environments (like iOS) where BigInt doesn't exist - so it's also the more "flexible" implementation!

Of course, there's no "right" answer here - just inspiration and food for thought. My thanks go out to everyone who contributed to the discussion and especially Brent, whose NetNewsWire app is my favorite RSS reader!