This post is also available in Italian.

Recently I did a batch of interviews for three positions in my team, and part of my standard interview is a coding question. I tend to focus on problems that will take at most 50% of the time I have, so the ideal question for me is apparently easy, but hides a much better solution that needs a bit of reasoning to be extracted.

Part of my interview is about how a person reasons (if they solve the problem), and part is really how a person reacts to a series of situations that go beyond the question (how they get to the solution, and beyond it). During the interview, for example, I look at how the candidates react to hints: are they capable of explaining their reasoning process or not? If they need help, are they capable of grasping an idea from few words, or do they need a detailed explanation? All these details tell me how they’ll fit in the team, and how I’ll have to interact with them if they get hired.

Usually, once they answered the question fully, I propose a series of changes to the code that might or might not be improving the outcome, and then ask to discuss these changes. Sometimes the changes might be convenient for some cases only (e.g., in a generic function, they will be only beneficial for some types and not for others). I expect the candidate to be able to understand the implications and agree or disagree with my proposals. This is still part of the interview.

The most important question I ask myself as an interviewer is very simple: would I enjoy working with this person?

Since it seems most of these details are not apparent to the interviewee, today I’m writing a series of posts where I analyze some coding interviews, present possible solutions, and give some ideas on how to prepare for what an interviewer wants to see in a coding interview.

Note: this is not one of the questions I usually ask, but I use this as an example on how you should conduct your coding interview, highlighting what an interviewer would love to hear and see.

Question

Given an unsorted array (sequence) of non-negative integers, find a continuous sub-array (sub-sequence) which adds to a given number S. Implement the solution as a generic algorithm, but visualize the results with indices that are 1-based.

Prototype

When implementing a generic algorithm, it’s always convenient to stick to conventions: in this case we will try to imitate the standard library. We take two iterators as input (exactly like all the pre-c++20 <algorithm>s), together with a value that has the same type as the elements of the sequence, and we produce as output a pair of iterators (like std::equal_range).

To respect the behavior of the standard library, we will make the first iterator to be inclusive, and the last iterator to be exclusive. In this solution we decided to return the range {end(sequence), end(sequence)} to signal that we couldn’t find a solution. Another option could be to return an optional<pair<...>>.

We’re ready to write the prototype of our function:

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
// ...
    return {e, e};
}

Here, I wanted to deduce the type of the parameter sum. This will allow to use this function with any collection of any type, as long as the type respects the precondition. As another extra here, I added a static_assert to check the precondition on the element type (that is also the type of sum). If you can write this kind of code without thinking too much, go ahead and write it; but if you are unsure, it’s better if you just suggest the idea of having such a deduction/test, rather than spending time trying to guess how to actually implement those things (that are, after all, unimportant details).

Test case

If you’re not provided with test code already, it’s always better to write some, to show the interviewer you understood the question.

Since we’re requested to present the results with indices that are 1-based, we have to add 1 to the position for begin, but we don’t have to do the same for the end (as in our case that is compensated by the end being exclusive).

int main() {
    unsigned int sum = 15;
    unsigned int A[] =  {1,2,3,4,5,6,7,8,9,10};

    auto result = find_range(std::begin(A), std::end(A), sum);
    std::cout << "from " << result.first - std::begin(A) + 1 << " to " <<  result.second - std::begin(A);
}

An interesting addition, in a non-interview test, would be verifying that the result is not the pair {std::end(A), std::end(A)}, but during an interview time might also be important, and this case can be skipped. But don’t forget to inform your interviewer that you know the problem and you’re skipping this step on purpose.

Naïve solution

It is always a good practice to think about the naïve solution first. You don’t always want to implement it, but sometimes it could be a good base to start writing your final solution. If you’re unsure, and you already have a better idea, ask your interviewers if they want to see the simpler solution too.

In this case, the simpler solution is to consider all the subsequences starting with begin(sequence) and ending with any element, then those starting with begin(sequence) + 1, and so on.

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
    Iterator start_of_range = b;
    for(Iterator start_of_range = b; start_of_range != e; ++start_of_range) {
        for(Iterator end_of_range = start_of_range; end_of_range != e; ++end_of_range) {
            if (std::accumulate(start_of_range, end_of_range, result_t{}) == sum) {
                return {start_of_range, end_of_range};
            }
        }
    }
    return {e, e};
}

This version isn’t very useful for the final solution that will be presented below, but it allows us to calculate the complexity of this solution, O(N³), as we have 3 nested loops (with N being the number of elements in the sequence). Remember to always provide complexity with the naïve solution, this will help you to visualize how to attack the problem.

This solution will clearly consider sequences that are nowhere near the target S, and that information gives us the idea to focus only on the subsequences that are around the target.

Solution

The “smart” idea is to scan the array once, keeping track of a pair of iterators: one is the beginning of the subsequence being analyzed, and the other is the end.

We start with the subsequence {begin(sequence), begin(sequence)}, for which we know the sum is 0 (we’ll keep track of this sum incrementally, so we won’t have to scan the sequence further to calculate the sum).

When one element is added to the subsequence (by advancing the end of the subsequence), the running sum of the subsequence is increased with the value of the element added, and conversely when an element is removed from the subsequence (by advancing the beginning of the subsequence), the running sum in decreased by the value of the element removed.

One element is added when the running sum is below the target S, and removed when above. If we reach the target we have our solution, otherwise if we reach the situation where the subsequence is {end(sequence), end(sequence)} we have no solution.

In this way, we force the algorithm to consider all the sequences that are around the target value S, and only those, ignoring all the subsequences that are far away from our target. We expect this algorithm to have complexity O(N).

Code

In the code, the beginning of the subsequence is reusing the parameter b, while the end of it is denoted by the variable end_of_range. With respect to the discussion, there is an extra caveat, when we reach the end of the sequence for the first time, if we’re below target, there’s no way to reach the target anymore, and thus we have an early exit with an invalid subsequence {end(sequence), end(sequence)}.

#include <cstdint>
#include <utility>
#include <iterator>
#include <iostream>
#include <type_traits>

template<typename Iterator>
std::pair<Iterator, Iterator> find_range(Iterator b, Iterator e, std::decay_t<decltype(*b)> sum) {
    using result_t = std::decay_t<decltype(*b)>;
    static_assert(std::is_unsigned_v<result_t>);
    result_t s = 0;
    Iterator end_of_range = b;
    while (sum != s && b != e) {
        if (s < sum) {
            if (end_of_range == e) {
                return {e, e};
            }
            s += *end_of_range;
            ++end_of_range;
        } else {
            // s > sum
            s -= *b;
            ++b;
        }
    }
    return {b, end_of_range};
}

int main() {
    unsigned int sum = 15;
    unsigned int A[] =  {1,2,3,4,5,6,7,8,9,10};

    auto result = find_range(std::begin(A), std::end(A), sum);
    std::cout << "from " << result.first - std::begin(A) + 1 << " to " <<  result.second - std::begin(A);
}

Extra questions

What the interviewer can ask more, after you provided your solution?

For the solution above, I can think a couple of questions:

• Can we get rid of the extra check when end_of_range == e?
• Can we move that check to the while condition, instead of b == e?

Another kind of questions could be

• Can you think of a counterexample where this fails? (maybe your solution isn’t perfect, after all)
• Can we further improve the complexity?

I’m not sure if I should provide all the answers here, try to think about the alternatives.

Note: Huge thanks to Alberto Invernizzi who proofread this post together with the Italian translation.