The Simplest Interview Question

Possibly the simplest software developer interview question sounds like this:

📝 The Simplest Interview Question

Please write a function that sums all natural numbers up to n.

This seemingly simple question can tell a lot about the background and knowledge of the candidate and also how willing and ready are they to ask clarifying questions.

First they may ask is this really just: $1 + 2 + ... + n$?

A candidate with some mathematical background will ask if we are talking about N0 or N1, meaning does the set of natural numbers include 0 or is it starting with 1. Or they may state that since we are summing numbers including 0 makes no difference, so might as well start at 1.

Next they may ask about the other end of the range: does it include n or not? For this exercise we will include n.

As a rule, all candidates might be surprised by this question and may think that it is some kind of trick question, since it seems that there is a very simple solution to this. There is, or rather, there are many simple solutions. It is not a trick question. Or if you want to call it that way, the trick is that it is simple. And often the simple things are hard.

Once we get to this level of understanding, most candidates will provide the for loop answer. It looks like this in Swift:

func sum1(n: Int) -> Int {
    var sum = 0
    for i in 1...n {
      sum += i
    }
    return sum
}

Once we have some code written that possibly can work, we can talk about the performance characteristics of this function. Some will know and give the answer that it is O(n), since the performance is proportional with the input. The for loop will have to execute n times.

This is the point in the interview when things get a bit more interesting. I ask: “Is there a more “functional” way to solve this problem? Then some candidates offer that to make it “functional” they would have to use map, filter, or reduce, because that's what would make it functional. Then we can have a conversation on what is “functional” and why wouldn’t the solution provided already, sum1, would not be functional. We talk about the distinguishing characteristics of functional programming.

What is functional programming? A simple explanation is that it is a programming style that prefers pure functions without side effects. Pure functions depend only on their arguments, perform their computations without side effects, and return a value. A side effect is something that the function does to the outside world, like changing the value of a variable outside its scope, or writing to a disk or screen, making a network request. ¹

We conclude that sum1 is quite functional as it is a pure function. If they want to rewrite it, then go for it. They produce a solution using the map function:

func sum2(n: Int) -> Int {
    var sum = 0
    Array(1...n).map{ i in
        sum += i
    }
    return sum
}

Not that much different from the for loop. Also, it is somewhat of a misuse of map, since map is supposed to apply a transformation to some data while maintaining its structure. But the map in sum2 does no transformation at all.

Next someone might provide a solution using reduce. This is more in line with the design intent for this function.

func sum3(n: Int) -> Int {
    return Array(1...n).reduce(0, +)
}

And we arrive to recursion. Some remember that they read that in functional programming it is common practice to use recursion. They provide the following solution:

func sum4(n: Int) -> Int {
    if n == 1 { return 1 }
    return n + sum4(n: n-1)
}

Once the topic of recursion comes up, we can talk about the parts of a recursive function? First is the condition for the termination of the recursion, and second the recursive call. If they don't know how to write it, I help them along as much as needed.

📝 The value of questions that the candidate can't answer

I don’t expect that every candidate would know the answers to these questions. I tend to ask questions to which I expect that they won’t know the answers. There is no malice in this. I want to see how they carry themselves when they don’t know the answers. Do they make up stuff or simply admit that they don't know and promise to find out and get back with me. In our professions we encounter situations daily where we won’t know the answers. We need to know how to handle those situations.

Once we have at least one of the functions written I ask if they can tell me what do they consider to be the performance benefits of functional style programming?

Here they might recall that given that they are pure, side effect free functions, that means that for a given input they always return the same output. If that's so, then if the computation is very expensive, and the function is called often with the same input parameters, then the results can be cached.

This is a good place to draw some parallels to the web, like looking up a static web page. The reason we can have content delivery networks, is because those act as caches for the ”functions” built into the browsers that fetch those web pages.

After we bring the performance conversation to a closure, the next question tends to stun them: "Is there O(1) solution to this problem?" That's when the folks with some math background have an advantage. Once they recognize that this is $1 + 2 + ... + n = {\large\sum_{\substack{i=1}}^n i} = {\frac {n(n+1)} 2}$ then they write the simplest and fastest solution of it all.

func sum5(n: Int) -> Int {
    return n * (n+1) / 2
}

To sum it up, this simple interview question packs a big punch: allows us to have a conversation on a wide variety of computer science topics, and also allows us to see how well candidate thinks on their feet, since chances are that they don't remember or don’t know all these topics.

What are some of the questions that you like to ask that are deceptively simple? Drop me a line or contact me through LinkedIn.