# 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
- std::accumulate
- std::find, std::find_if_not
- 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:

- 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*. - 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:

- 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.
- 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.