STL Algorithms Q&A
Question 1: You have a std::vector<int> numbers containing integers. How would you count the number of even numbers present in the vector using an STL algorithm?
Solution:
int countEvens = std::count_if(numbers.begin(), numbers.end(), [](int n){ return n % 2 == 0; });
Question 2: Given two std::vector<std::string> vec1, vec2 containing strings, how would you check if the two vectors contain exactly the same set of strings (but not necessarily in the same order) using STL algorithms?
Solution:
bool areSame = (vec1.size() == vec2.size()) &&
std::is_permutation(vec1.begin(), vec1.end(), vec2.begin());
Question 3: Using STL algorithms, how can you reverse a std::string str?
Solution:
std::reverse(str.begin(), str.end());
Question 4: You have a std::vector<int> values containing integers. How would you use an STL algorithm to replace all occurrences of the number 5 with the number 10?
Solution:
std::replace(values.begin(), values.end(), 5, 10);
Question 5: Given a std::list<int> data containing integers, how would you use STL algorithms to remove all numbers less than 10 and then sort the remaining numbers in descending order?
Solution:
data.remove_if([](int n){ return n < 10; });
data.sort(std::greater<int>());
The std::list container is a bit unique in this aspect. Unlike vectors and many other containers, when you call remove_if on a std::list, it not only reorders the elements but also actually deletes them from the list. So, there's no need to call erase after remove_if for a std::list.
Question 6: You have a std::vector<std::string> words containing various words. How would you count the number of words that start with the letter 'A' using an STL algorithm?
Solution:
int countA = std::count_if(words.begin(), words.end(), [](const std::string& word){ return !word.empty() && word[0] == 'A'; });
Question 7: Given a std::vector<int> nums containing integers, how would you find the first number that's greater than its adjacent number on its left using STL algorithms?
Solution:
std::vector<int> nums = {3, 5, 7, 7, 9, 6, 4};
auto it = std::adjacent_find(nums.begin(), nums.end(), [](int left, int right){ return left < right; });
if (it != nums.end() && it != nums.begin()) {
int foundNumber = *it; // In this case, foundNumber will be 5
} else {
// No such number found
}
Question 8: You're given a std::vector<double> prices representing the prices of items in a store. Using STL algorithms, how would you find the average price?
Solution:
C++ Standard Library does not have a dedicated one-step mean or average function for containers. However, you can use std::accumulate to find the sum of all elements and then divide it by the number of elements to find the average.
double total = std::accumulate(prices.begin(), prices.end(), 0.0);
double average = (prices.size() > 0) ? total / prices.size() : 0.0;
Question 9: Given a std::vector<int> data containing integers, how would you check if all the numbers in this vector are positive using STL algorithms?
Solution:
bool allPositive = std::all_of(data.begin(), data.end(), [](int n){ return n > 0; });
Question 10: You're given two std::vector<int> vecA, vecB containing integers. Using STL algorithms, how would you check if the elements of vecB are a subset of the elements in vecA?
Solution:
bool isSubset = std::all_of(vecB.begin(), vecB.end(), [&](int elem){
return std::find(vecA.begin(), vecA.end(), elem) != vecA.end();
});
[&] captures all variables in the current scope by reference. This is required because we need to access vecA inside the lambda function.
Question 11: You have a std::vector<std::string> sentences containing various sentences. How would you find the longest sentence in terms of word count using STL algorithms?
Solution:
auto longest = *std::max_element(sentences.begin(), sentences.end(),
[](const std::string& a, const std::string& b) {
return std::count(a.begin(), a.end(), ' ') < std::count(b.begin(), b.end(), ' ');
});
The lambda function of std::max_element must accept 2 arguments of the same type as the elements of the container. In this case, the elements of sentences are strings, so the lambda function must accept 2 strings. The lambda function returns true if the first string is smaller than the second string. In this case, we're comparing the number of spaces in the strings to determine which string is smaller. The string with the smaller number of spaces will have a smaller word count, and hence, will be the shorter string.
Question 12: Given a std::vector<int> values, how would you find the second largest number using STL algorithms?
Solution:
std::sort(values.begin(), values.end());
int secondLargest = *(values.end() - 2);
std::sort sorts the elements in ascending order by default. So, the second largest element will be the second last element in the sorted vector.
Question 13: You're provided with a std::vector<int> numbers. How would you find the sum of all even numbers in the vector using STL algorithms?
Solution:
int sum = std::accumulate(numbers.begin(), numbers.end(), 0,
[](int total, int num) {
return num % 2 == 0 ? total + num : total;
});
std::accumulate accepts optional arguments for the initial value of the accumulator and a binary function that takes the current value of the accumulator and the next element of the vector and returns the new value of the accumulator. In this case, we're using the binary function to add the current element to the accumulator only if the current element is even.
Question 14: Given a std::list<int> data, how would you rearrange its elements so that all even numbers come before the odd numbers, preserving their relative order, using STL algorithms?
Solution:
data.sort([](int a, int b) { return a % 2 == 0 && b % 2 != 0; });
std::list has a sort member function that accepts a binary function that returns true if the first argument is smaller than the second argument. In this case, we're using the binary function to return true if the first argument is even and the second argument is odd. This will ensure that all even numbers come before odd numbers.
Question 15: You are given two std::vector<std::string> listA, listB. How would you identify the strings that appear in both lists using STL algorithms?
Solution:
std::vector<std::string> common;
std::set_intersection(listA.begin(), listA.end(), listB.begin(), listB.end(), std::back_inserter(common));
Besides std::vector, std::set_intersection is also applicable to the following containers: std::deque, std::list, std::forward_list, std::set, std::multiset, std::unordered_set, std::unordered_multiset.
Question 16: How would you rotate a std::vector<int> nums to the left by k positions using STL algorithms?
Solution:
std::rotate(nums.begin(), nums.begin() + k % nums.size(), nums.end());
"Rotation" here means shifting the elements of the vector to the left by k positions to the left, and every element that goes past the front of the vector is placed at the back of the vector. For example, if nums is {1, 2, 3, 4, 5} and k is 2, then the rotated vector will be {3, 4, 5, 1, 2}.
Question 17: Given a std::vector<std::string> words, how would you transform all the words to uppercase using STL algorithms?
Solution:
std::transform(words.begin(), words.end(), words.begin(),
[](const std::string& word) {
std::string upperWord = word;
std::transform(word.begin(), word.end(), upperWord.begin(), ::toupper);
return upperWord;
});
The outer std::transform transforms the elements of the vector in-place. The inner std::transform transforms each string in-place. The ::toupper function is a C-style function that converts a character to uppercase.
Question 18: You are provided with a std::vector<int> numbers. How would you use STL algorithms to partition the vector so that numbers divisible by 5 come before others?
Solution:
std::partition(numbers.begin(), numbers.end(), [](int n) { return n % 5 == 0; });
std::partition rearranges the elements of the vector such that all elements that satisfy the predicate come before the elements that don't satisfy the predicate. In this case, the predicate is n % 5 == 0, which returns true if n is divisible by 5.
To get the iterator to the first element that doesn't satisfy the predicate, you can instead use std::partition_point:
auto it = std::partition_point(numbers.begin(), numbers.end(), [](int n) { return n % 5 == 0; });
Question 19: You have a std::vector<int> values containing integers. How would you find the most frequently occurring number using STL algorithms?
Solution:
std::sort(values.begin(), values.end());
auto it = std::max_element(values.begin(), values.end(),
[&](int a, int b) {
return std::count(values.begin(), values.end(), a)
< std::count(values.begin(), values.end(), b);
});
int mostFrequent = *it;
However, the solution above is inefficient because std::count is called twice for each element of the vector. A more efficient solution would be to use std::unordered_map to count the occurrences of each number:
std::unordered_map<int, int> frequency;
for (int val : values) {
++frequency[val];
}
auto mostFrequentIt = std::max_element(frequency.begin(), frequency.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});
int mostFrequent = mostFrequentIt->first;
Then use std::max_element to find the element with the highest frequency.
Question 20: Given a std::string text, how would you shuffle its characters randomly using STL algorithms?
Solution:
std::random_shuffle(text.begin(), text.end());
In C++11 and onwards, std::random_shuffle is deprecated, and std::shuffle is preferred, but it requires an external random number generator:
#include <random>
#include <algorithm>
std::string text = "your_text_here";
std::random_device rd;
std::mt19937 generator(rd());
std::shuffle(text.begin(), text.end(), generator);
Here std::random_device is used to generate a random seed for the random number generator. std::mt19937 is a random number generator that generates random numbers using the Mersenne Twister algorithm.
Question 21: You're given a std::vector<int> data. How would you find the median of the values using STL algorithms?
Solution:
std::sort(data.begin(), data.end());
double median;
if (data.size() % 2 == 0) {
median = (data[data.size() / 2 - 1] + data[data.size() / 2]) / 2.0;
} else {
median = data[data.size() / 2];
}
Question 22: How can you merge two sorted std::vector<int> vecA, vecB into a third vector, maintaining the sorted order using STL?
Solution:
std::vector<int> merged(vecA.size() + vecB.size());
std::merge(vecA.begin(), vecA.end(), vecB.begin(), vecB.end(), merged.begin());
Question 23: Given a std::string sentence, how would you split it into words (assuming words are separated by spaces) using STL algorithms?
Solution:
std::istringstream stream(sentence);
std::vector<std::string> words(std::istream_iterator<std::string>(stream),
std::istream_iterator<std::string>());
The std::istringstream treats spaces as default delimiters, so when you use std::istream_iterator to iterate over the stream, it will return words separated by spaces. The syntax std::vector<T> vec(a.begin(), a.end()) is a shortcut to initialize a vector from a range of elements. std::istream_iterator<T>(stream) returns an iterator to the first element of the stream, and std::istream_iterator<T>() returns an iterator to the end of the stream.
Question 24: How would you generate a std::vector<int> numbers of size n containing random integers between a and b using STL?
Solution:
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(a, b);
numbers.resize(n);
std::generate(numbers.begin(), numbers.end(), [&]() { return distrib(gen); });
Here we see how random number generator is used along with std::generate to generate random numbers.
Question 25: You have two std::vector<int> listA, listB. How would you find the elements that appear only in listA but not in listB using STL algorithms?
Solution:
std::vector<int> difference;
std::sort(listA.begin(), listA.end());
std::sort(listB.begin(), listB.end());
std::set_difference(listA.begin(), listA.end(), listB.begin(), listB.end(), std::back_inserter(difference));
It's important to sort the vectors before calling std::set_difference because it expects the input ranges to be sorted. If we don't sort the vectors, the behavior is undefined.
Lastly, instead of pushing the elements of the difference vector one by one, we can use std::back_inserter to insert the elements at the back of the vector at once.
Question 26: Given a std::string text, how would you count the occurrences of each distinct word (ignoring case) in the text using STL?
Solution:
std::transform(text.begin(), text.end(), text.begin(), ::tolower);
std::istringstream stream(text);
std::map<std::string, int> wordCount;
std::string word;
while (stream >> word) {
wordCount[word]++;
}
Question 27: You're given a std::vector<int> values. How would you move all zeros in the vector to the end without changing the order of the non-zero elements using STL?
Solution:
std::stable_partition(values.begin(), values.end(), [](int x) { return x != 0; });
As opposed to std::partition, std::stable_partition preserves the relative order of the elements in the vector.
Question 28: How can you find the smallest and largest values in a std::vector<int> nums using STL algorithms?
Solution:
auto result = std::minmax_element(nums.begin(), nums.end());
int smallest = *result.first;
int largest = *result.second;
Or you can use std::minmax:
auto result = std::minmax(nums.begin(), nums.end());
int smallest = result.first;
int largest = result.second;
Question 29: You want to remove consecutive duplicate elements from a std::vector<int> data. How would you do that using STL algorithms?
Solution:
auto newEnd = std::unique(data.begin(), data.end());
data.erase(newEnd, data.end());
std::unique shifts all the unique elements to the front of the vector and returns an iterator to the element past the last unique element. Then we use std::vector::erase to remove the elements from the vector starting from the iterator returned by std::unique to the end of the vector.
Question 30: Given a std::vector<int> numbers, how would you find the element that appears more than n/2 times (majority element) in the vector using STL?
Solution:
std::nth_element(numbers.begin(), numbers.begin() + numbers.size() / 2, numbers.end());
int candidate = numbers[numbers.size() / 2];
int count = std::count(numbers.begin(), numbers.end(), candidate);
if (count > numbers.size() / 2) {
// candidate is the majority element
} else {
// No majority element found
}
The std::nth_element is a partial sorting algorithm that rearranges the elements such that the element at the nth position is the element that would be in that position if the elements were sorted. Now we use the fact that the majority element will be at the n/2 position if the elements were sorted. So, we find the element at the n/2 position using std::nth_element and then count the number of occurrences of that element in the vector. If the count is greater than n/2, then the element is the majority element. This algorithm is known as Boyer-Moore majority vote algorithm, and it spares us from sorting the entire vector and then counting the occurrences of each element.
Question 31: Given a std::string sentence, how would you transform all words to start with a capital letter and have the rest of the letters in lowercase using STL?
Solution:
std::istringstream stream(sentence);
std::string word;
std::string result;
while (stream >> word) {
word[0] = std::toupper(word[0]);
std::transform(word.begin() + 1, word.end(), word.begin() + 1, ::tolower);
result += word + " ";
}
result.pop_back(); // remove trailing space
Question 32: You have a std::vector<std::string> names containing people's names. How would you use STL algorithms to find the name(s) that appear the most times in the list?
Solution:
std::sort(names.begin(), names.end());
auto mostFrequent = std::max_element(names.begin(), names.end(), [&names](const std::string &a, const std::string &b) {
return std::count(names.begin(), names.end(), a) < std::count(names.begin(), names.end(), b);
});
Alternatively, you can use std::unordered_map to count the occurrences of each name:
std::unordered_map<std::string, int> frequency;
for (const std::string& name : names) {
++frequency[name];
}
auto mostFrequent = std::max_element(frequency.begin(), frequency.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
Question 33: How can you generate a std::vector<int> randomNumbers containing 100 random integers between 1 and 1000 using STL?
Solution:
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist(1, 1000);
std::vector<int> randomNumbers(100);
std::generate(randomNumbers.begin(), randomNumbers.end(), [&]() { return dist(mt); });
Question 34: You have a std::map<std::string, int> scores representing names and their respective scores. How would you extract all names whose score is greater than 50 using STL algorithms?
Solution:
std::vector<std::string> highScorers;
std::transform(scores.begin(), scores.end(), std::back_inserter(highScorers),
[](const std::pair<std::string, int>& p) {
if (p.second > 50)
return p.first;
return std::string("");
});
highScorers.erase(std::remove(highScorers.begin(), highScorers.end(), ""), highScorers.end());
Question 35: Given two std::vector<int> vecA, vecB, how would you determine if vecA is lexicographically smaller than vecB using STL?
Solution:
bool isLexSmaller = std::lexicographical_compare(vecA.begin(), vecA.end(), vecB.begin(), vecB.end());
Question 36: Given a std::vector<int> numbers, how would you rotate the elements of the vector three positions to the left using STL?
Solution:
std::rotate(numbers.begin(), numbers.begin() + 3, numbers.end());
Question 37: You have a std::vector<std::pair<std::string, int>> items representing items and their respective prices. How would you sort the items based on their prices in descending order?
Solution:
std::sort(items.begin(), items.end(), [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
return a.second > b.second;
});
Question 38: Given a std::string str, how would you check if the string is a palindrome using STL?
Solution:
bool isPalindrome = std::equal(str.begin(), str.end(), str.rbegin());
Question 39: How can you merge two sorted std::vector<int> vecA, vecB into a third vector std::vector<int> merged such that the merged vector is also sorted?
Solution:
merged.resize(vecA.size() + vecB.size());
std::merge(vecA.begin(), vecA.end(), vecB.begin(), vecB.end(), merged.begin());
Question 40: You have a std::multiset<int> numbers. How would you count the number of occurrences of the number 5 in the multiset?
Solution:
int countFives = numbers.count(5);
Question 41: You have a std::vector<std::string> names. How would you remove all names that start with the letter 'M' using STL?
Solution:
names.erase(std::remove_if(names.begin(), names.end(), [](const std::string& name) {
return !name.empty() && name[0] == 'M';
}), names.end());
Question 42: Given two std::set<int> setA, setB, how would you check if setA is a proper subset of setB using STL?
Solution:
bool isProperSubset = std::includes(setB.begin(), setB.end(), setA.begin(), setA.end()) && (setA.size() < setB.size());
Question 43: How would you split a std::string sentence into a std::vector<std::string> words based on whitespace using STL?
Solution:
std::istringstream stream(sentence);
std::copy(std::istream_iterator<std::string>(stream), std::istream_iterator<std::string>(), std::back_inserter(words));
Question 44: Given a std::vector<int> numbers, how would you find the nth smallest element using STL?
Solution:
std::nth_element(numbers.begin(), numbers.begin() + n - 1, numbers.end());
int nthSmallest = numbers[n - 1];
Question 45: You have a std::map<std::string, int> wordCount representing the count of each word in a document. How would you find the word with the highest count using STL?
Solution:
auto maxWord = std::max_element(wordCount.begin(), wordCount.end(), [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
return a.second < b.second;
});
std::string mostFrequentWord = maxWord->first;
Question 46: You are given a std::vector<std::pair<std::string, int>> items, where each pair contains an item name and its price. How would you use STL to find all items priced higher than 100?
Solution:
std::vector<std::string> expensiveItems;
std::transform(items.begin(), items.end(), std::back_inserter(expensiveItems),
[](const std::pair<std::string, int>& p) {
return p.second > 100 ? p.first : "";
});
expensiveItems.erase(std::remove(expensiveItems.begin(), expensiveItems.end(), ""), expensiveItems.end());
Question 47: How would you concatenate all strings from a std::list<std::string> words into a single string separated by commas using STL?
Solution:
std::string concatenated = std::accumulate(std::next(words.begin()), words.end(), words.front(),
[](const std::string& a, const std::string& b) {
return a + ',' + b;
});
Question 48: You're given a std::multiset<int> numbers. How would you count the occurrence of the number 5 in the multiset?
Solution:
int countOfFives = numbers.count(5);
Question 49: How would you find the length of the shortest string in a std::vector<std::string> strings using STL?
Solution:
auto shortestString = *std::min_element(strings.begin(), strings.end(),
[](const std::string& a, const std::string& b) {
return a.size() < b.size();
});
int shortestLength = shortestString.size();
Question 50: Given a std::vector<int> values, how would you shift all elements by one position to the right, with the last element wrapping around to the front, using STL?
Solution:
std::rotate(values.rbegin(), values.rbegin() + 1, values.rend());
Question 51: You have a std::vector<int> values. How can you find out the frequency of a particular number, say 4, using STL algorithms?
Solution:
int frequency = std::count(values.begin(), values.end(), 4);
Question 52: Given a std::vector<std::string> names containing names of people, how can you transform all names to uppercase using STL algorithms?
Solution:
std::transform(names.begin(), names.end(), names.begin(),
[](const std::string& name) {
std::string upperName = name;
std::transform(name.begin(), name.end(), upperName.begin(), ::toupper);
return upperName;
});
Question 53: You have a std::set<int> numsSet. How would you convert this set into a std::vector<int>?
Solution:
std::vector<int> numsVec(numsSet.begin(), numsSet.end());
Question 54: Given a std::map<int, std::string> students where keys are student IDs and values are student names, how can you extract all the student names into a std::vector<std::string>?
Solution:
std::vector<std::string> names;
std::transform(students.begin(), students.end(), std::back_inserter(names),
[](const std::pair<int, std::string>& entry) { return entry.second; });
Question 55: You have a std::vector<int> numbers. How would you rotate the elements of the vector three positions to the left using STL algorithms?
Solution:
std::rotate(numbers.begin(), numbers.begin() + 3, numbers.end());
Question 56: Given a std::vector<int> digits, which contains individual digits from 0 to 9, how would you form the largest possible number from the elements of this vector using STL algorithms?
Solution:
std::sort(digits.begin(), digits.end(), [](int a, int b){ return std::to_string(a) + std::to_string(b) > std::to_string(b) + std::to_string(a); });
std::string largestNum = std::accumulate(digits.begin(), digits.end(), std::string(""), [](const std::string &a, int b){ return a + std::to_string(b); });
Question 57: How can you identify the nth smallest element in a std::vector<int> nums without sorting the entire vector using STL?
Solution:
std::nth_element(nums.begin(), nums.begin() + n - 1, nums.end());
int nth_smallest = nums[n - 1];
Question 58: Given a std::vector<std::string> sentences, how would you concatenate all the strings into a single string separated by a comma using STL algorithms?
Solution:
std::string result = std::accumulate(std::next(sentences.begin()), sentences.end(), sentences[0],
[](std::string a, std::string b) { return a + ", " + b; });
Question 59: You have a std::map<std::string, int> wordCounts that maps words to their frequencies. How would you find the word with the highest frequency using STL algorithms?
Solution:
auto maxPair = std::max_element(wordCounts.begin(), wordCounts.end(),
[](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) { return a.second < b.second; });
std::string mostFrequentWord = maxPair->first;
Question 60: Given a std::vector<int> numbers, how can you count the number of unique elements in the vector using STL algorithms?
Solution:
std::sort(numbers.begin(), numbers.end());
auto last = std::unique(numbers.begin(), numbers.end());
numbers.erase(last, numbers.end());
int uniqueCount = numbers.size();