SyntaxPilot
Courses/C++ Coding Questions/Lesson 8
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 8 of 30

Vector questions I

largest and second largest (duplicates)rotate by k (k % n, std::rotate)move zeros to the end keeping order

These are the notes for C++ Coding Questions, episode 8, placement practice for people who finished the SyntaxPilot C++ course. Vectors, part one: the largest and second largest element (with ties and negative numbers), rotating a vector by k (k % n, std::rotate, and the empty-vector crash), and moving all zeros to the end while keeping the order.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In C++
Marks 3 9 4 9 7: two toppers tie at 9, so the second-highest mark is 7 second largest = the biggest value strictly smaller than the max
Leh at dawn: −3, −1, −7 °C; a "warmest so far" that starts at 0 reports 0 °C, which nobody measured don't start a maximum at 0: start at "nothing yet" (LLONG_MIN)
Everyone scored 5: there is no second mark print none
A merry-go-round with 5 seats turned 7 places = turned 2 places only k % n matters
Ration-shop queue: people without a token go to the back; a careless clerk moves on without checking the person who just moved up erase inside a for loop skips the next element
Token holders step forward in order, the rest go to the back a write index

Q1: Largest and second largest

Problem. Read n integers; print the largest and the second largest (the biggest value strictly smaller than the largest), or none.

Input Output
3 9 4 9 7 largest 9, second 7
5 5 5 5 largest 5, second none
−3 −1 −7 largest −1, second −3
42 largest 42, second none

The obvious attempt: sort descending, take v[0] and v[1]

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        sort(v.begin(), v.end(), greater<int>());
        cout << "largest " << v[0] << ", second " << v[1] << "\n";
    }
    return 0;
}

Output:

largest 9, second 9
largest 5, second 5
largest -1, second -3

Wrong on ties: v[1] is just the other 9. Also O(n log n) work to find two numbers, and with n = 1, v[1] is out of bounds (undefined behaviour).

One pass: first and second

  • x > first → the old first drops to second, x becomes first.
  • else if x > second && x != first → x becomes second (the != first handles ties).
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int first = 0, second = 0;
        for (int x : v) {
            if (x > first) {
                second = first;
                first = x;
            } else if (x > second && x != first) {
                second = x;
            }
        }
        cout << "largest " << first << ", second " << second << "\n";
    }
    return 0;
}

Output:

largest 9, second 7
largest 5, second 0
largest 0, second 0

Ties are fixed, but starting at 0 is wrong: −3, −1, −7 never beat 0, so it reports largest 0; and 5 5 5 5 reports second 0. Zero is a real value that may not be in the input.

Fix: start at LLONG_MIN and print none

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        long long first = LLONG_MIN, second = LLONG_MIN;
        for (int x : v) {
            if (x > first) {
                second = first;
                first = x;
            } else if (x > second && x != first) {
                second = x;
            }
        }
        cout << "largest " << first << ", second ";
        if (second == LLONG_MIN) cout << "none\n";
        else cout << second << "\n";
    }
    return 0;
}

Input (the three tests and 1 / 42):

largest 9, second 7
largest 5, second none
largest -1, second -3
largest 42, second none

LLONG_MIN (from <climits>) is smaller than every int, so it means "nothing yet"; first/second are long long so the sentinel can never collide with a real input value. O(n) time, O(1) space.

Q2: Rotate right by k

Problem. Read n and k (k up to 2,000,000,000) and n integers; rotate them right by k.

Input Output
1 2 3 4 5, k = 2 4 5 1 2 3
1 2 3 4 5, k = 7 4 5 1 2 3
1 2 3 4 5, k = 2,000,000,000 1 2 3 4 5
9, k = 3 9
(empty), k = 3 (empty line)

The obvious attempt: rotate by one, k times

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

int main() {
    int n;
    long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        for (long long step = 0; step < k; step++) {
            int last = v[n - 1];
            for (int i = n - 1; i > 0; i--) v[i] = v[i - 1];
            v[0] = last;
        }
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

k = 2 and k = 7:

4 5 1 2 3 
4 5 1 2 3 

k = 2,000,000,000: Time Limit Exceeded (2 billion rotations × 5 moves = 10 billion steps).

Fix: k %= n, then std::rotate

std::rotate(first, middle, last) (from <algorithm>) rotates the range so that middle becomes the new first element. Rotating right by k means the element at index n - k comes to the front.

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

int main() {
    int n;
    long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        k %= n;
        rotate(v.begin(), v.begin() + (n - k), v.end());
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 5 2 / 5 7 / 5 2000000000 / 1 3:

4 5 1 2 3 
4 5 1 2 3 
1 2 3 4 5 
9 

Input 0 3 (an empty vector): the program crashes with Floating point exception (signal SIGFPE). k % 0 is a division by zero: undefined behaviour, and on x86 the CPU traps it. The name says "floating point", but it is raised for integer division by zero too.

Fix: check n == 0 first

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

int main() {
    int n;
    long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) { cout << "\n"; continue; }
        k %= n;
        rotate(v.begin(), v.begin() + (n - k), v.end());
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 5 2 / 0 3 / 1 3:

4 5 1 2 3 

9 

Complexity: O(n) time (rotate moves each element a constant number of times), O(1) extra space.

Q3: Move the zeros to the end

Problem. Move every 0 to the end, keeping the other numbers in their original order, in the same vector.

Input Output
0 1 0 3 12 1 3 12 0 0
0 0 1 1 0 0
1 2 3 4 1 2 3 4
0 0 0 0 0 0

The obvious attempt: erase each zero and push one to the back

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        for (int i = 0; i < n; i++) {
            if (v[i] == 0) {
                v.erase(v.begin() + i);
                v.push_back(0);
            }
        }
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Output:

1 3 12 0 0 
0 1 0 
1 2 3 4 
0 0 0 

Wrong for 0 0 1. At i = 0 the first 0 is erased; everything slides left, so the second 0 is now at index 0, but the loop moves on to i = 1 and never checks it. Also, each erase shifts the rest of the vector: O(n) per erase, O(n²) in total.

Fix: a write index

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        int write = 0;
        for (int i = 0; i < n; i++)
            if (v[i] != 0) v[write++] = v[i];
        while (write < n) v[write++] = 0;
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Output:

1 3 12 0 0 
1 0 0 
1 2 3 4 
0 0 0 

Every non-zero is copied forward to v[write++] (in order), then the rest is filled with zeros. O(n) time, O(1) space. The library equivalent: stable_partition(v.begin(), v.end(), [](int x) { return x != 0; });.

Complexity summary

Program Time Extra space
second largest, sort O(n log n) O(1) (wrong on ties)
second largest, one pass O(n) O(1)
rotate by one, k times O(n · k) O(1)
k %= n, std::rotate O(n) O(1)
move zeros, erase in a loop O(n²) O(1) (and skips zeros)
move zeros, write index O(n) O(1)

Common mistakes (and the real results)

Mistake What you see Why Fix
sort, then v[1] second 9 for 3 9 4 9 7 ties one pass with x != first
int first = 0, second = 0; largest 0 for −3 −1 −7 0 is a real value LLONG_MIN, then none
v[1] when n = 1 undefined behaviour out of bounds check the size
rotate one step k times Time Limit Exceeded O(n · k) k %= n, rotate
k %= n with n = 0 Floating point exception (SIGFPE) division by zero if (n == 0) first
erase(v.begin() + i) in for (i...) 0 0 1 → 0 1 0 the next element slides into i a write index

Your turn: the third largest distinct value (solution)

Problem. Print the third largest distinct value; if there are fewer than three distinct values, print the largest.

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        long long a = LLONG_MIN, b = LLONG_MIN, c = LLONG_MIN;   // a > b > c
        for (int x : v) {
            if (x == a || x == b || x == c) continue;          // distinct values only
            if (x > a) { c = b; b = a; a = x; }
            else if (x > b) { c = b; b = x; }
            else if (x > c) { c = x; }
        }
        cout << (c == LLONG_MIN ? a : c) << "\n";
    }
    return 0;
}

Input 3 2 1 / 2 2 3 1 / 1 2 / -1 -1 -2 -3 -3:

1
1
2
-3

O(n) time, O(1) space.

Practice questions (with solutions)

1. Rotate LEFT by k (1 2 3 4 5, k = 2 → 3 4 5 1 2). The element at index k comes to the front.

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

int main() {
    int n;
    long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) { cout << "\n"; continue; }
        k %= n;
        rotate(v.begin(), v.begin() + k, v.end());   // left by k: the element at k comes to the front
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 5 2 / 1 2 3 4 5 / 5 7 / 1 2 3 4 5:

3 4 5 1 2 
3 4 5 1 2 

2. Move all negatives to the front, keeping the order of both groups.

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        vector<int> out;
        for (int x : v) if (x < 0) out.push_back(x);    // negatives, in order
        for (int x : v) if (x >= 0) out.push_back(x);   // then the rest, in order
        for (int x : out) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 6 / 3 -1 4 -5 9 -2:

-1 -5 -2 3 4 9 

O(n) time, O(n) extra space (stable_partition does it in the same vector).

3. Is the vector sorted (non-decreasing)? One pass comparing neighbours.

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        bool sorted = true;
        for (int i = 1; i < n; i++)
            if (v[i] < v[i - 1]) { sorted = false; break; }
        cout << (sorted ? "sorted\n" : "not sorted\n");
    }
    return 0;
}

Input 4 / 1 2 2 5 / 3 / 3 1 2 / 1 / 7:

sorted
not sorted
sorted

The library way: is_sorted(v.begin(), v.end()).

Mini project: a vector toolkit

Largest and second largest, then zeros moved to the end, then a right rotation.

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

int main() {
    int n;
    long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        long long first = LLONG_MIN, second = LLONG_MIN;
        for (int x : v) {
            if (x > first) { second = first; first = x; }
            else if (x > second && x != first) second = x;
        }
        int write = 0;
        for (int i = 0; i < n; i++) if (v[i] != 0) v[write++] = v[i];
        while (write < n) v[write++] = 0;
        if (n > 0) { k %= n; rotate(v.begin(), v.begin() + (n - k), v.end()); }
        cout << "largest " << first << ", second ";
        if (second == LLONG_MIN) cout << "none"; else cout << second;
        cout << " | zeros moved, rotated by " << k << ": ";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

Input 6 1 / 0 5 0 9 5 2:

largest 9, second 5 | zeros moved, rotated by 1: 0 5 9 5 2 0 

Quick quiz

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};
    int k = 8 % v.size();
    rotate(v.begin(),
           v.begin() + (v.size() - k),
           v.end());
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

(A) 5 6 1 2 3 4 (B) 3 4 5 6 1 2 (C) 1 2 3 4 5 6 (D) 6 1 2 3 4 5

Answer

(A) 5 6 1 2 3 4. 8 % 6 = 2: a right rotation by 2, so the element at index 6 − 2 = 4 (the 5) comes to the front.

5 6 1 2 3 4 

Interview questions

  1. Find the second largest element in one pass. Track first and second; update second only for values != first.
  2. Why not start the maximum at 0? All values may be negative; start at INT_MIN/LLONG_MIN or at the first element.
  3. Rotate an array by k in O(n) time and O(1) space. k %= n, then std::rotate, or the three-reversal trick: reverse all, reverse the first k, reverse the rest.
  4. What happens with k % n when n = 0? Division by zero: undefined behaviour, usually a SIGFPE crash.
  5. Move zeros to the end keeping order. A write index (or stable_partition); O(n), O(1).
  6. Why is erase inside a forward for loop dangerous? The next element slides into the current index and is skipped; it is also O(n) per call.
  7. What does std::rotate return? An iterator to the new position of the old first element.

Glossary

Term Meaning Example
Vector A resizable array, std::vector<int> vector<int> v(n);
Second largest The biggest value strictly smaller than the max 7 in 3 9 4 9 7
Tie Equal values the two 9s
Sentinel A special value meaning "nothing yet" LLONG_MIN
LLONG_MIN The smallest long long, from <climits> −9223372036854775808
Rotate right by k The last k elements move to the front 1 2 3 4 5 → 4 5 1 2 3
Modulo % The remainder of a division 7 % 5 = 2
std::rotate Rotates a range so middle becomes the first rotate(b, b + (n - k), e)
SIGFPE The signal for an arithmetic error such as dividing by zero k % 0
Undefined behaviour (UB) Code the standard gives no meaning dividing by zero, v[1] when n = 1
In place Changing the vector itself, no copy write index
Write index Where the next kept element is written v[write++] = v[i]
erase Removes elements and shifts the rest left v.erase(v.begin() + i)
O(n · k) Work grows with n times k rotating one step k times
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here

Summary

  • Second largest: one pass with first and second, x != first for ties, starting at LLONG_MIN and printing none when nothing qualifies.
  • Rotate by k: k %= n (after checking n == 0!), then std::rotate(v.begin(), v.begin() + (n - k), v.end()).
  • Move zeros: a write index, then fill with zeros. Never erase inside a forward for loop.

Next episode: Vector questions II: remove duplicates from a sorted vector (the erase-unique idiom), the missing number from 1 to n (overflow and XOR), and the majority element (Boyer-Moore voting).