STL algorithms
for programming interviews

Monday, September 28, 2020

Using C++ in a technical interview can be hazardous unless you have experience using it. Experienced C++ programmers will benefit from a collection of data structures and algorithms that will help them solve problems in real-time. These data structures and algorithms are part of the Standard Template Library (STL). In this post, I will list useful STL algorithms that anyone who’s preparing for technical interviews should be familiar with. I will be dividing my list into two categories: Non-modifying algorithms and modifying algorithms.

In many cases, using a library algorithm to solve a complete problem isn’t acceptable since the interviewer may want to see how you would implement it yourself but there are many cases in which using built-it library functions is perfectly fine. The best way to determine this is by asking the interviewer.

This list isn’t comprehensive, it presents algorithms I found useful for programming interviews over the years and how they can be used.


Non-modifying algorithms

  1. std::count, std::min_element, std::max_element
  2. std::accumulate
  3. std::find, std::find_if_not
  4. std::lower_bound, std::upper_bound

std::count
std::min_element
std::max_element

I’m bundling these algorithms together because they serve the same purpose: iterating through a range and reducing it into a single value. This task comes up often in programming interviews and these three operations are especially common: counting the number of times an element appears in a range and finding out the position of the min/max element in a range.

std::count has a single overload that takes a pair of iterators and the value we want to count. It’s using operator== for equality by default. If you want to pass your own predicate, look no further than std::count_if.

std::min_element and std::max_element in their basic form take two iterators. These algorithms use operator< for comparison by default. Unlike std::count, these algorithms return an iterator instead of a value which is useful if you need to perform additional operations on the range as is often the case. Also unlike std::count, they provide an overload that takes a comparison function.

These algorithms can be easily implemented with a for loop but using them will save you time and keep your code simple, something you should strive for during an interview. Suppose you need to get the index of the minimum element in a vector of integers and you find yourself writing something like this:

int MinElementIdx(const vector<int>& vec) {
    auto min_value = numeric_limits<int>::max();
    auto min_value_idx = 0;
    for (int i = 0; i < size(vec); ++i) {
        if (vec[i] < min_value) {
            min_value = vec[i];
            min_value_idx = i;
        }
    }
    return min_value_idx;
}

Know that there’s a better way:

int MinElementIdx(const vector<int>& vec) {
    return min_element(begin(vec), end(vec)) - begin(vec);
}

std::accumulate

std::accumulate is related to the algorithms presented above, it too summarizes a range into a single value, but it provides greater flexibility. It comes with some pitfalls as well so we will give it the attention it deserves.

All the algorithms we’re going to cover live in <algorithm> except for std::accumulate that’s hiding under <numeric>. Despite its location, std::accumulate can be used for non-numeric types.

In its basic form it takes a pair of iterators and returns the sum of the elements in the range using operator+. Since operator+ requires two values, it takes a starting value as well. In another form, std::accumulate also takes a function that lets you decide how to compute the sum.

It might sounds straight forward, but there are a couple of things to keep in mind:

  1. The starting value type has to much the container type. If you provide a range of double and a starting value of type int, the return value will be reduced to an int.
  2. The second overload of std::accumulate takes a function that makes it possible to do all kinds of things with it, but to maintain the expressivity of your code the return value should always represent a useful summary of the elements in the range.

If you’re asking yourself what kinds of things can be done with such a simple algorithm, I encourage you to watch “std::accumulate: Exploring an Algorithmic Empire” by Ben Deane. We will keep things simple with our example. Let’s write a function that takes an array of positive integers and returns the sum of all the even numbers in the array:

int sum_even_numbers(const vector<int>& arr) {
    return accumulate(begin(arr), end(arr), 0, [](int acc, int x){
        return x % 2 == 0 ? acc + x : acc;
    });
}

std::find
std::find_if
std:find_if_not

Looking for values in a container is one of the most common tasks you need to perform during technical interviews (second only to sorting), and the STL gives you several options to choose from. The most important thing to keep in mind is that “find algorithms” should only be used for unsorted ranges. The next group of algorithms will deal with sorted ranges and cover the difference.

std::find takes a pair of iterators and the value you are looking for. It’s using operator== for equality and returns an iterator to the first element that is matching it. If the value you are looking for is not found in the range std::find returns an iterator to the last element.

std::find_if and std::find_if_not are similar to std::find except they take a unary predicate as well as a pair of iterators to determine equality. The difference between the two is std::find_if looks for the first match while std::find_if_not looks for the first mismatch.

I’ve already mentioned that algorithms that return iterators can be useful so here’s an example. Let’s write a function that trims leading spaces from a string:

string trim_leading_spaces(const string& str) {
    return {
        find_if_not(begin(str), end(str), [](char c){
            return c == ' ';
        }),
        end(str)
    };
}

You might be wondering what’s the purpose of having std::find_if and std::find_if_not? We could have just as easily implemented the same function using std::find_if by negating the return value of the predicate:

find_if(begin(str), end(str), [](char c){
    return c != ' ';
});

The answer to this question, and the reason I’m presenting both algorithms, is expressivity. If we use std::find_if and negate its return value, the meaning of the algorithm that we derive from its name changes.

std::lower_bound
std::upper_bound

If you are preparing for technical interviews you should know all about binary search: an efficient search algorithm that only applies to sorted ranges. Many questions require you to identify and implement binary search yourself but there’s a case to be made for built-in algorithms that provide the same functionality, for example:

  1. If you want to test a quick solution to a binary search problem you can start with a built-in function and unpack it once your test cases have passed.
  2. If binary search is an implementation detail using a built-in algorithm can save you a significant amount of time.

Both algorithms take a pair of iterators that represent the range and value for comparison.

  • std::lower_bound returns an iterator that points to the first element equal to or greater than value.
  • std::upper_case returns an iterator that points to the first element that’s greater than value.

There’s a subtle but important difference between both algorithms. Suppose you have a sorted array of numbers [1, 3, 3, 5, 6, 7], and you want to find the position of the number 3, which index should be returned? Sometimes we want to find the lower-bound and sometimes we want to find the upper-bound:

int find_first_element(const vector<int>& vec, int val) {
    return lower_bound(begin(vec), end(vec), val) - begin(vec);
}

int find_last_element(const vector<int>& vec, int val) {
    return upper_bound(begin(vec), end(vec), val) - begin(vec) - 1; 
}

int main() {
    vector<int> vec = {1, 3, 3, 5, 6, 7};
    cout << find_first_element(vec, 3) << '\n'; // prints 1
    cout << find_last_element(vec, 3) << '\n'; // prints 2
}

While there are several sorted-range algorithms that employ binary search, the ones I found most useful for technical interviews are std::lower_bound and std::upper_bound. It’s important to remember that to maintain logarithmic time complexity these algorithms require random-access iterators (array, vector, string, and deque). They would work otherwise but the time complexity will most likely be linear. According to the standard, passing unsorted ranges to std::lower_bound and std::upper_bound is undefined behaviour so if you are seeing unexpected results, make sure this condition was met.