Chapter 21 Advanced 58 Questions

Practice Questions — STL Algorithms and Iterators

← Back to Notes

9 Easy

11 Medium

7 Hard

Topic-Specific Questions

Question 1

Easy

What is the output?

vector<int> v = {5, 3, 1, 4, 2};
sort(v.begin(), v.end());
for (int x : v) cout << x << " ";

sort arranges elements in ascending order by default.

1 2 3 4 5

Question 2

Easy

What is the output?

vector<int> v = {5, 3, 1, 4, 2};
sort(v.begin(), v.end(), greater<int>());
cout << v[0] << " " << v[4];

greater() sorts in descending order.

5 1

Question 3

Easy

What is the output?

vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin() + 2;
cout << *it;

begin() points to the first element. Adding 2 moves two positions forward.

30

Question 4

Easy

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
int sum = accumulate(v.begin(), v.end(), 0);
cout << sum;

accumulate adds all elements starting from the initial value 0.

15

Question 5

Easy

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
cout << v[0] << " " << v[4];

reverse flips the entire range.

5 1

Question 6

Easy

What is the output?

vector<int> v = {3, 1, 4, 1, 5, 9};
auto it = min_element(v.begin(), v.end());
cout << *it << " " << (it - v.begin());

min_element returns an iterator to the smallest element.

1 1

Question 7

Medium

What is the output?

vector<int> v = {1, 3, 3, 3, 5, 7, 9};
auto lo = lower_bound(v.begin(), v.end(), 3);
auto hi = upper_bound(v.begin(), v.end(), 3);
cout << (lo - v.begin()) << " " << (hi - v.begin()) << " " << (hi - lo);

lower_bound returns first >= 3, upper_bound returns first > 3.

1 4 3

Question 8

Medium

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
rotate(v.begin(), v.begin() + 2, v.end());
for (int x : v) cout << x << " ";

rotate moves the element pointed to by the second argument to the first position.

3 4 5 1 2

Question 9

Medium

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
cout << product;

multiplies() replaces addition with multiplication. The initial value is 1.

120

Question 10

Medium

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
vector<int> prefix(5);
partial_sum(v.begin(), v.end(), prefix.begin());
cout << prefix[2] << " " << prefix[4];

partial_sum computes running totals: prefix[i] = v[0] + v[1] + ... + v[i].

6 15

Question 11

Medium

What is the output?

vector<int> v = {1, 2, 3, 2, 4, 2, 5};
v.erase(remove(v.begin(), v.end(), 2), v.end());
cout << v.size() << ": ";
for (int x : v) cout << x << " ";

remove moves non-2 elements forward, erase shrinks the vector.

4: 1 3 4 5

Question 12

Medium

What is the output?

vector<int> v = {1, 1, 2, 2, 3, 3, 3};
auto last = unique(v.begin(), v.end());
cout << (last - v.begin());
v.erase(last, v.end());
cout << " " << v.size();

unique removes consecutive duplicates and returns an iterator to the new logical end.

3 3

Question 13

Hard

What is the output?

vector<int> v = {5, 2, 8, 1, 9, 3};
nth_element(v.begin(), v.begin() + 2, v.end());
cout << v[2];

nth_element places the element that would be at position 2 in a sorted array.

3

Question 14

Hard

What is the output?

string s = "CBA";
prev_permutation(s.begin(), s.end());
cout << s << endl;
prev_permutation(s.begin(), s.end());
cout << s;

prev_permutation generates the lexicographically previous permutation.

CAB
BCA

Mixed & Application Questions

Question 1

Easy

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
cout << *v.begin() << " " << *(v.end() - 1);

begin() points to first element. end() points past the last, so end()-1 is the last element.

1 5

Question 2

Easy

What is the output?

vector<int> v = {10, 20, 30, 40, 50};
auto it = find(v.begin(), v.end(), 30);
cout << (it - v.begin());

find returns an iterator to the found element.

2

Question 3

Easy

What is the output?

vector<int> v(5);
iota(v.begin(), v.end(), 3);
for (int x : v) cout << x << " ";

iota fills with incrementing values starting from the second argument.

3 4 5 6 7

Question 4

Medium

What is the output?

vector<int> v = {1, 2, 3, 4, 5, 6};
int cnt = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
cout << cnt;

count_if counts elements satisfying the predicate.

3

Question 5

Medium

What is the output?

vector<int> v = {1, 2, 3, 4};
vector<int> result(4);
transform(v.begin(), v.end(), result.begin(), [](int x) { return x * x; });
for (int x : result) cout << x << " ";

transform applies the lambda to each element.

1 4 9 16

Question 6

Medium

What is the output?

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
cout << dot;

inner_product computes sum of element-wise products.

32

Question 7

Medium

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
vector<int> w(5);
fill(w.begin(), w.end(), 7);
cout << accumulate(w.begin(), w.end(), 0);

fill sets all elements to 7. accumulate sums them.

35

Question 8

Hard

What is the output?

vector<pair<string,int>> v = {{"Arjun",85}, {"Priya",92}, {"Kiran",78}};
sort(v.begin(), v.end(), [](const pair<string,int>& a, const pair<string,int>& b) {
    return a.second > b.second;
});
cout << v[0].first << " " << v[2].first;

Sorting by second element in descending order.

Priya Kiran

Question 9

Hard

What is the output?

vector<int> v = {1, 2, 3};
sort(v.begin(), v.end());
int count = 0;
do { count++; } while (next_permutation(v.begin(), v.end()));
cout << count;

Starting from sorted, how many permutations does next_permutation generate?

6

Question 10

Hard

What is the output?

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << *lo << " " << *hi << " " << (hi - lo);

minmax_element returns iterators to the min and max elements.

1 9 4

Question 11

Hard

What is the output?

vector<int> v = {1, 2, 3, 4, 5};
replace_if(v.begin(), v.end(), [](int x) { return x > 3; }, 0);
for (int x : v) cout << x << " ";

replace_if replaces elements matching the predicate with the given value.

1 2 3 0 0

Question 12

Medium

What is the difference between stable_sort and sort? When would you use stable_sort?

Think about what happens to elements with equal keys.

sort is O(n log n) but does not preserve the relative order of equal elements. stable_sort is also O(n log n) but guarantees that equal elements maintain their original order. Use stable_sort when sorting students by marks and wanting students with the same marks to remain in their original order (e.g., alphabetical order from a previous sort).

Question 13

Hard

Why is lower_bound more useful than binary_search in competitive programming?

Think about what each returns.

binary_search returns only a bool (true/false). lower_bound returns an iterator to the first element >= the target value. This gives you the position, which lets you: (1) find the actual index, (2) count occurrences using upper_bound - lower_bound, (3) find the nearest value if the exact value does not exist. In competitive programming, you almost always need the position, not just existence.

Multiple Choice Questions

MCQ 1

Which header provides sort, find, and binary_search?

A. <vector>
B. <algorithm>
C. <numeric>
D. <iterator>

Answer: B
B is correct. The <algorithm> header provides sort, find, binary_search, reverse, rotate, and most STL algorithms.

MCQ 2

What does accumulate (from ) do?

A. Sorts a range
B. Finds the maximum element
C. Computes a fold/reduce (sum by default)
D. Reverses a range

Answer: C
C is correct. accumulate folds a range using an operation (addition by default). You can pass a custom binary operation like multiplies<int>().

MCQ 3

What does v.end() point to?

A. The last element
B. One position past the last element
C. The first element
D. nullptr

Answer: B
B is correct. end() returns a past-the-end iterator. It does not point to any element and must not be dereferenced.

MCQ 4

Which algorithm finds the first occurrence of a value in an unsorted range?

A. binary_search
B. lower_bound
C. find
D. search

Answer: C
C is correct. find performs a linear search and works on unsorted ranges. binary_search and lower_bound require sorted ranges.

MCQ 5

What type of iterator does std::vector provide?

A. Input Iterator
B. Forward Iterator
C. Bidirectional Iterator
D. Random Access Iterator

Answer: D
D is correct. std::vector provides random-access iterators, which support +, -, [], and comparison operators in O(1).

MCQ 6

What is the time complexity of std::sort?

A. O(n)
B. O(n log n) average, O(n^2) worst
C. O(n log n) guaranteed
D. O(n^2)

Answer: C
C is correct. std::sort uses introsort (hybrid of quicksort, heapsort, and insertion sort), which guarantees O(n log n) worst-case.

MCQ 7

What does lower_bound return when the target value is not in the sorted range?

A. end() iterator
B. Iterator to the first element greater than the target
C. Iterator to the last element less than the target
D. An invalid iterator

Answer: B
B is correct. lower_bound returns an iterator to the first element >= the target. If the target is not present, this is the first element greater than it (the insertion point).

MCQ 8

What does std::remove actually do?

A. Erases matching elements from the container
B. Moves non-matching elements to the front and returns a new logical end
C. Returns a count of removed elements
D. Sets matching elements to zero

Answer: B
B is correct. remove does not change the container's size. It rearranges elements so that non-removed ones are at the front and returns an iterator to the new logical end. Use the erase-remove idiom to actually shrink the container.

MCQ 9

Which algorithm would you use to compute prefix sums?

A. accumulate
B. partial_sum
C. inner_product
D. transform

Answer: B
B is correct. partial_sum computes running totals: result[i] = v[0] + v[1] + ... + v[i]. accumulate computes only the final total.

MCQ 10

Why can't you use std::sort on a std::list?

A. list does not support the < operator
B. list has bidirectional iterators, but sort requires random-access iterators
C. list is always sorted
D. sort only works on arrays

Answer: B
B is correct. std::sort requires random-access iterators for O(1) index arithmetic. std::list provides only bidirectional iterators. Use the member function lst.sort() instead.

MCQ 11

What is the time complexity of nth_element?

A. O(n log n)
B. O(n)
C. O(n^2)
D. O(log n)

Answer: B
B is correct. nth_element uses introselect (a hybrid of quickselect and median-of-medians) and runs in O(n) on average. It places the nth element in its correct sorted position without fully sorting the range.

MCQ 12

What does next_permutation return when the sequence is in descending order (last permutation)?

A. true and produces the next permutation
B. false and sorts the sequence to the first permutation
C. false and leaves the sequence unchanged
D. Throws an exception

Answer: B
B is correct. When the sequence is the last permutation (fully descending), next_permutation wraps around to the first permutation (ascending) and returns false.

MCQ 13

What is the difference between partial_sort(begin, begin+k, end) and sorting the entire range?

A. No difference
B. partial_sort is O(n log k) and only guarantees the first k elements are sorted
C. partial_sort is O(k log k) and only sorts the first k
D. partial_sort sorts the last k elements

Answer: B
B is correct. partial_sort has O(n log k) complexity. It places the k smallest elements in sorted order at the beginning. The remaining elements are in unspecified order. This is faster than full sort when k is much smaller than n.

MCQ 14

What does equal_range return?

A. A bool indicating if the value exists
B. An iterator to the value
C. A pair of iterators (lower_bound, upper_bound)
D. The count of the value

Answer: C
C is correct. equal_range returns a pair<iterator, iterator> where first = lower_bound and second = upper_bound. The distance between them is the count of the value.

MCQ 15

What does iota(v.begin(), v.end(), 5) fill the vector with?

A. All elements set to 5
B. 5, 6, 7, 8, ... (incrementing from 5)
C. 0, 1, 2, 3, ... (ignoring the 5)
D. 5, 10, 15, 20, ... (multiples of 5)

Answer: B
B is correct. iota fills the range with sequentially increasing values starting from the third argument. Each element is one more than the previous.

MCQ 16

What does reverse(v.begin(), v.end()) do?

A. Sorts in descending order
B. Reverses the elements in the range
C. Rotates the elements left
D. Returns a reversed copy

Answer: B
B is correct. reverse reverses the elements in-place. It does not sort and does not return a copy.

Coding Challenges

Challenge 1: Sort Students by Marks, Break Ties by Name

Easy

Given a vector of pairs where each pair is {name, marks}, sort the students by marks in descending order. If two students have the same marks, sort them alphabetically by name.

Sample Input

{"Arjun", 85}, {"Priya", 92}, {"Kiran", 85}, {"Neha", 92}, {"Ravi", 78}

Sample Output

Neha 92 Priya 92 Arjun 85 Kiran 85 Ravi 78

Use sort with a custom lambda comparator. Do not write your own sorting algorithm.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<pair<string, int>> students = {
        {"Arjun", 85}, {"Priya", 92}, {"Kiran", 85}, {"Neha", 92}, {"Ravi", 78}
    };
    sort(students.begin(), students.end(),
        [](const pair<string,int>& a, const pair<string,int>& b) {
            if (a.second != b.second) return a.second > b.second;
            return a.first < b.first;
        });
    for (auto& [name, marks] : students)
        cout << name << " " << marks << endl;
    return 0;
}

Challenge 2: Count Elements in Range Using Binary Search

Medium

Given a sorted vector and two values L and R, count the number of elements in the range [L, R] (inclusive) using lower_bound and upper_bound. Do not use a loop to count.

Sample Input

v = {1, 3, 3, 5, 7, 7, 7, 9, 11}, L = 3, R = 7

Sample Output

Count in [3, 7]: 6

Use lower_bound and upper_bound. O(log n) time complexity.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 7, 7, 9, 11};
    int L = 3, R = 7;
    auto lo = lower_bound(v.begin(), v.end(), L);
    auto hi = upper_bound(v.begin(), v.end(), R);
    cout << "Count in [" << L << ", " << R << "]: " << (hi - lo) << endl;
    return 0;
}

Challenge 3: Remove Duplicates From Unsorted Vector

Medium

Given an unsorted vector, remove all duplicate elements and keep only unique values in sorted order. Use sort and the erase-remove idiom with unique.

Sample Input

{5, 3, 1, 3, 5, 2, 1, 4, 2}

Sample Output

1 2 3 4 5

Use sort + unique + erase. Do not use a set or map.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 3, 1, 3, 5, 2, 1, 4, 2};
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Challenge 4: Find Kth Largest Element Without Full Sort

Hard

Given a vector of n integers, find the kth largest element using nth_element in O(n) average time. Do not fully sort the array.

Sample Input

v = {3, 2, 1, 5, 6, 4}, k = 2

Sample Output

2nd largest element: 5

Use nth_element. O(n) average time complexity.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 2, 1, 5, 6, 4};
    int k = 2;
    nth_element(v.begin(), v.begin() + k - 1, v.end(), greater<int>());
    cout << k << "nd largest element: " << v[k - 1] << endl;
    return 0;
}

Challenge 5: Generate All Permutations and Count Those Divisible by K

Hard

Given a vector of single-digit numbers, generate all permutations, form the number from each permutation, and count how many are divisible by a given value K.

Sample Input

digits = {1, 2, 3}, K = 3

Sample Output

123 divisible by 3 132 divisible by 3 213 divisible by 3 231 divisible by 3 312 divisible by 3 321 divisible by 3 Count: 6

Use sort + next_permutation. Assume digits fit in an int.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> digits = {1, 2, 3};
    int K = 3;
    sort(digits.begin(), digits.end());
    int count = 0;
    do {
        int num = 0;
        for (int d : digits) num = num * 10 + d;
        if (num % K == 0) {
            cout << num << " divisible by " << K << endl;
            count++;
        }
    } while (next_permutation(digits.begin(), digits.end()));
    cout << "Count: " << count << endl;
    return 0;
}

Challenge 6: Range Sum Queries Using partial_sum

Medium

Given an array and multiple queries of the form (L, R), answer each query with the sum of elements from index L to R (inclusive) in O(1) per query using prefix sums built with partial_sum.

Sample Input

v = {2, 4, 6, 8, 10}, queries = {(1,3), (0,4), (2,2)}

Sample Output

Sum [1, 3] = 18 Sum [0, 4] = 30 Sum [2, 2] = 6

Use partial_sum to build prefix array. Each query must be O(1).

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<int> v = {2, 4, 6, 8, 10};
    vector<int> prefix(v.size());
    partial_sum(v.begin(), v.end(), prefix.begin());

    auto rangeSum = [&](int l, int r) {
        return prefix[r] - (l > 0 ? prefix[l - 1] : 0);
    };

    vector<pair<int,int>> queries = {{1,3}, {0,4}, {2,2}};
    for (auto [l, r] : queries)
        cout << "Sum [" << l << ", " << r << "] = " << rangeSum(l, r) << endl;
    return 0;
}

Need to Review the Concepts?

Go back to the detailed notes for this chapter.

Read Chapter Notes

Want to learn C++ with a live mentor?

Explore our C++ Masterclass