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 oldfirstdrops tosecond,xbecomesfirst.- else if
x > second && x != first→xbecomessecond(the!= firsthandles 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
- Find the second largest element in one pass. Track
firstandsecond; updatesecondonly for values!= first. - Why not start the maximum at 0? All values may be negative; start at
INT_MIN/LLONG_MINor at the first element. - Rotate an array by k in O(n) time and O(1) space.
k %= n, thenstd::rotate, or the three-reversal trick: reverse all, reverse the first k, reverse the rest. - What happens with
k % nwhen n = 0? Division by zero: undefined behaviour, usually a SIGFPE crash. - Move zeros to the end keeping order. A write index (or
stable_partition); O(n), O(1). - Why is
eraseinside a forwardforloop dangerous? The next element slides into the current index and is skipped; it is also O(n) per call. - What does
std::rotatereturn? 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
firstandsecond,x != firstfor ties, starting atLLONG_MINand printingnonewhen nothing qualifies. - Rotate by k:
k %= n(after checkingn == 0!), thenstd::rotate(v.begin(), v.begin() + (n - k), v.end()). - Move zeros: a write index, then fill with zeros. Never
eraseinside a forwardforloop.
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).