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

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 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. This algorithm is using operator== for equality by default. If you want to pass your own predicate, look no further than std::count_if.

Example:

Write a function that takes an array of integers and returns the number of elements equal to zero.

int equal_to_zero(const vector<int>& nums) {
    return count(begin(nums), end(nums), 0);    
}

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, both algorithms provide an overload that takes a comparison function.

Example:

Write a function that takes an array of integers and returns a subarray starting at the position of the minimum element.

vector<int> subarray_from_min_element(const vector<int>& nums) {
    return {
        min_element(begin(nums), end(nums)),
        end(nums)
    };
}

std::accumulate

std::accumulate is related to the algorithms presented above, it too summarizes a range into a single value, but it’s more flexible and it comes with some warnings 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, std::accumulate takes a starting value as well. In another overload, std::accumulate also takes a function that lets you decide how to compute the sum. This is what makes it so flexible, but with great flexibility comes great responsibility:

  • The type of the starting value has to match the type of the values that are in the container. If you provide a range of doubles and a starting value of type int, the return value will be narrowed to an int.
  • The overload of std::accumulate that accepts a function lets us do all kinds of crazy 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 kind of crazy things can possibly be done with a single algorithm, I encourage you to watch “std::accumulate: Exploring an Algorithmic empire” by Ben Deane.

Example:

Write a function that takes an array of integers and returns the sum of all even integers 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.

Example:

Write a function that takes a string with leading spaces and returns a copy of it without leading spaces.

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