These are the notes for C++ Coding Questions, episode 15, placement practice for people who finished the SyntaxPilot C++ course. Two ideas that turn O(n²) into O(n), usually with no extra memory: two pointers (a pair with a given sum in a sorted vector, and why while (i <= j) uses one element twice) and the sliding window, fixed (the best sum of k numbers in a row, and why best = 0 is wrong) and variable (the longest substring without repeating characters, and a left end that must never move backwards).
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 that runs too long (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| Two friends buying two gifts for exactly ₹10 from a price-sorted shelf, one at each end | two pointers i (left) and j (right) on a sorted vector |
| Too little: the cheap-end friend steps right; too much: the costly-end friend steps left | sum < target → i++, sum > target → j-- |
| They can't both take the same gift | while (i < j) |
| A shop's best 3 days in a row: add the new day, drop the oldest | a fixed sliding window: sum += a[i]; sum -= a[i - k]; |
| A bad month: the best stretch is the smallest loss, not 0 | start best at LLONG_MIN |
| A caterpillar on a string of beads: the head eats the next bead; on a repeated colour the tail jumps past the old bead, never backwards | a variable sliding window: left = max(left, last[c] + 1) |
Q1: Pair with a given sum in a sorted vector
Problem. Given n sorted numbers and a target, print two different elements (different positions) that add up to the target, or no pair.
| Input | Output |
|---|---|
1 3 5 6 9, target 10 |
1 9 |
1 3 5 8, target 10 |
no pair (5 + 5 would use one element twice) |
Think out loud. Edge cases: no pair, n = 1. Big test: 500,000 numbers with no pair (the test block, when n is 0, builds 0 2 4 ... and target 1).
The obvious attempt: every pair
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long target;
cin >> n >> target;
vector<long long> v(n);
for (auto& x : v) cin >> x;
if (n == 0) { // test: 500,000 even numbers, odd target
n = 500000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
target = 1;
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (v[i] + v[j] == target) {
cout << v[i] << " " << v[j] << "\n";
return 0;
}
cout << "no pair\n";
return 0;
}
1 9
The big test (0 0) checks all ≈ 1.25 × 10¹¹ pairs and runs for well over 25 seconds: Time Limit Exceeded. It never uses the fact that the numbers are sorted.
Why two pointers are allowed to skip
Put i at the start and j at the end.
v[i] + v[j] < target: even the biggest partner is too small forv[i], sov[i]is in no pair. Throw it away:i++.v[i] + v[j] > target: even the smallest partner is too big forv[j]. Throw it away:j--.
Each step throws one element away for good: at most n steps.
Attempt: two pointers with while (i <= j)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long target;
cin >> n >> target;
vector<long long> v(n);
for (auto& x : v) cin >> x;
if (n == 0) { // test: 500,000 even numbers, odd target
n = 500000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
target = 1;
}
int i = 0, j = n - 1;
while (i <= j) {
long long sum = v[i] + v[j];
if (sum == target) {
cout << v[i] << " " << v[j] << "\n";
return 0;
}
if (sum < target) i++; // need more: move the left end right
else j--; // too much: move the right end left
}
cout << "no pair\n";
return 0;
}
1 3 5 6 9 (10), then 1 3 5 8 (10):
1 9
5 5
Why 5 5. Trace: 1+8 = 9 → i++; 3+8 = 11 → j--; 3+5 = 8 → i++; now i = j = 2, and 5+5 = 10. When i == j both pointers are on the same element.
Fix: while (i < j)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long target;
cin >> n >> target;
vector<long long> v(n);
for (auto& x : v) cin >> x;
if (n == 0) { // test: 500,000 even numbers, odd target
n = 500000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
target = 1;
}
int i = 0, j = n - 1;
while (i < j) {
long long sum = v[i] + v[j];
if (sum == target) {
cout << v[i] << " " << v[j] << "\n";
return 0;
}
if (sum < target) i++; // need more: move the left end right
else j--; // too much: move the right end left
}
cout << "no pair\n";
return 0;
}
1 3 5 8 (10), the big test, 1 3 5 6 9 (10), a single 2 (4), and 1 3 5 8 (4):
no pair
no pair
1 9
no pair
1 3
O(n) time, O(1) extra space. Needs sorted input; for unsorted input use the hash map of episode 10 (O(n) average, O(n) space) or sort first (O(n log n)).
Q2: Maximum sum of a window of size k
Problem. Given n numbers (negatives allowed) and k (1 ≤ k ≤ n), print the largest sum of k numbers in a row.
| Input | Output |
|---|---|
2 1 5 1 3 2, k = 3 |
9 (5 1 3) |
-3 -1 -2 -5 -4, k = 2 |
-3 (-1 -2) |
Think out loud. Edge cases: k = n, every number negative. Big test: 1,000,000 numbers with k = 500,000 (the test block, when n is 0, builds 0 1 2 ... 99 0 1 ...).
The obvious attempt: add up every window again
#include <iostream>
#include <vector>
using namespace std;
long long bestWindow(const vector<int>& a, int k) {
long long best = 0;
for (int i = 0; i + k <= (int)a.size(); i++) {
long long sum = 0;
for (int j = i; j < i + k; j++) sum += a[j];
best = max(best, sum);
}
return best;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 100;
}
cout << bestWindow(a, k) << "\n";
return 0;
}
9
The big test does (n − k + 1) · k ≈ 2.5 × 10¹¹ additions: Time Limit Exceeded (still running after 30 seconds on our machine).
Why. Neighbouring windows share k − 1 numbers; only one comes in and one leaves:
[2 1 5] 1 3 2 = 8
2 [1 5 1] 3 2 = 8 + 1 - 2 = 7
2 1 [5 1 3] 2 = 7 + 3 - 1 = 9
2 1 5 [1 3 2] = 9 + 2 - 5 = 6
Attempt: the sliding window, with best = 0
#include <iostream>
#include <vector>
using namespace std;
long long bestWindow(const vector<int>& a, int k) {
long long sum = 0, best = 0;
for (int i = 0; i < (int)a.size(); i++) {
sum += a[i]; // the new number comes in
if (i >= k) sum -= a[i - k]; // the oldest one leaves
if (i >= k - 1) best = max(best, sum);
}
return best;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 100;
}
cout << bestWindow(a, k) << "\n";
return 0;
}
2 1 5 1 3 2 (k = 3), the big test, then -3 -1 -2 -5 -4 (k = 2):
9
24750000
0
Why 0. best = 0 is a fake window with sum 0. When every real window is negative, the fake one wins. The brute force has the same line; it just never got a negative test.
Fix: best = LLONG_MIN
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long bestWindow(const vector<int>& a, int k) {
long long sum = 0, best = LLONG_MIN;
for (int i = 0; i < (int)a.size(); i++) {
sum += a[i]; // the new number comes in
if (i >= k) sum -= a[i - k]; // the oldest one leaves
if (i >= k - 1) best = max(best, sum);
}
return best;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 100;
}
cout << bestWindow(a, k) << "\n";
return 0;
}
-3 -1 -2 -5 -4 (k = 2), 2 1 5 1 3 2 (k = 3), the big test, and 4 -1 2 (k = 3, the whole vector):
-3
9
24750000
5
O(n) time: each number enters once and leaves once. O(1) extra space. (Equivalent: start with best = the sum of the first window.) LLONG_MIN comes from <climits>; numeric_limits<long long>::min() from <limits> is the same value.
Q3: Longest substring without repeating characters
Problem. For each word, print the length of the longest substring (continuous) with all characters different.
| Input | Output |
|---|---|
abcabcbb |
3 (abc) |
bbbbb |
1 |
pwwkew |
3 (wke; pwke isn't continuous) |
dvdf |
3 (vdf) |
abba |
2 (ab, ba) |
The obvious attempt: clear the window on a repeat
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int longestUnique(const string& s) {
unordered_set<char> window;
int best = 0;
for (char c : s) {
if (window.count(c)) window.clear(); // a repeat: start again
window.insert(c);
best = max(best, (int)window.size());
}
return best;
}
int main() {
string s;
while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 2
Why 2 for dvdf. The window was d v; the second d cleared everything, leaving d, then d f. But v was fine: only the old d had to go. Move the left end to just past the old copy, which needs the latest index of every character.
Attempt: left = last[c] + 1
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int longestUnique(const string& s) {
unordered_map<char, int> last; // character -> latest index
int left = 0, best = 0;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (last.count(c)) left = last[c] + 1;
last[c] = i;
best = max(best, i - left + 1);
}
return best;
}
int main() {
string s;
while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 3
abba: 3
Why 3 for abba.
| i | c | last[c] before | left | window |
|---|---|---|---|---|
| 0 | a | — | 0 | a |
| 1 | b | — | 0 | ab |
| 2 | b | 1 | 2 | b |
| 3 | a | 0 | 1 (backwards!) | bba: length 3, with two b's |
The old a at index 0 was already outside the window; it must not move left back.
Fix: left = max(left, last[c] + 1)
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int longestUnique(const string& s) {
unordered_map<char, int> last; // character -> latest index
int left = 0, best = 0;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (last.count(c)) left = max(left, last[c] + 1);
last[c] = i;
best = max(best, i - left + 1);
}
return best;
}
int main() {
string s;
while (cin >> s) cout << s << ": " << longestUnique(s) << "\n";
return 0;
}
abcabcbb: 3
bbbbb: 1
pwwkew: 3
dvdf: 3
abba: 2
x: 1
tmmzuxt: 5
O(n) time: i and left each move forward at most n times. O(alphabet) space: at most 256 different char values. (An int last[256] filled with −1 is a faster replacement for the map.)
Why two pointers and windows are fast
- Two pointers: every step proves one element is in no answer and throws it away.
- Fixed window: reuse the previous sum: one number in, one out.
- Variable window: grow on the right; shrink from the left only as much as needed.
- In every case both ends only move forward: at most 2n moves, O(n).
| Pattern | Use when | Example |
|---|---|---|
| Two pointers from both ends | sorted data, pairs | pair sum, container with most water |
| Fixed window of size k | "k in a row" | best k days, average of every k |
| Variable window | "longest/shortest stretch such that ..." | no repeats, shortest sum ≥ target |
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| pair sum, every pair | O(n²): TLE for 500,000 | O(1) |
| pair sum, two pointers (sorted) | O(n) | O(1) |
| best window, re-add each window | O(n · k): TLE | O(1) |
| best window, sliding | O(n) | O(1) |
| longest unique substring, window + last index | O(n) | O(alphabet) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| every pair on big input | Time Limit Exceeded | O(n²) | two pointers on sorted data |
while (i <= j) |
5 5 for 1 3 5 8, target 10 |
i == j is one element |
while (i < j) |
| two pointers on unsorted data | no pair when a pair exists |
the skip rule needs sorted order | sort first, or a hash map |
| re-adding every window | Time Limit Exceeded | O(n · k) | add the new, subtract the oldest |
long long best = 0; |
0 instead of -3 |
a fake window wins | best = LLONG_MIN or the first window |
| comparing before the window is full | a "best" of fewer than k numbers | i < k - 1 |
only update when i >= k - 1 |
| clearing the window on a repeat | dvdf: 2 |
good characters thrown away | left = last[c] + 1 |
left = last[c] + 1 alone |
abba: 3 |
left moves backwards |
left = max(left, last[c] + 1) |
Your turn: the shortest stretch reaching a target (solution)
Problem. Positive numbers and a target: the length of the shortest subarray with sum ≥ target (0 if none). 2 3 1 2 4 3, target 7 → 2 (4 3).
Idea. A variable window. Grow it on the right; while the sum is at least the target, record the length and shrink from the left. All numbers are positive, so shrinking always lowers the sum: each index enters and leaves once.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
long long target;
while (cin >> n >> target) {
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long sum = 0;
int left = 0, best = INT_MAX;
for (int right = 0; right < n; right++) {
sum += a[right]; // grow on the right
while (sum >= target) { // good enough: try shorter
best = min(best, right - left + 1);
sum -= a[left++]; // shrink from the left
}
}
cout << (best == INT_MAX ? 0 : best) << "\n";
}
return 0;
}
2 3 1 2 4 3 (7), 1 4 4 (4), 1 1 1 1 (10):
2
1
0
O(n) time, O(1) extra space.
Practice questions (with solutions)
1. Container with most water. Heights of vertical lines; pick two lines so that min(h[i], h[j]) × (j − i) is the largest.
Solution
Two pointers from both ends; move the shorter line inward (moving the taller one can never help: the width shrinks and the height is still limited by the shorter line).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> h(n);
for (auto& x : h) cin >> x;
int i = 0, j = n - 1;
long long best = 0;
while (i < j) {
best = max(best, min(h[i], h[j]) * (j - i));
if (h[i] < h[j]) i++;
else j--;
}
cout << best << "\n";
return 0;
}
1 8 6 2 5 4 8 3 7:
49
2. Remove duplicates from a sorted vector in place (two pointers).
Solution
w is where the next new value is written; r reads every element.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
int w = 0;
for (int r = 0; r < n; r++)
if (r == 0 || v[r] != v[w - 1]) v[w++] = v[r];
v.resize(w);
for (int x : v) cout << x << " ";
cout << "| " << w << " unique\n";
return 0;
}
1 2 3 5 8 | 5 unique
3. Count the windows of size k whose average is at least x.
Solution
Average ≥ x ⇔ sum ≥ k · x (no division, no floating point).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
long long x;
cin >> n >> k >> x;
vector<long long> a(n);
for (auto& v : a) cin >> v;
long long sum = 0;
int count = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
if (i >= k) sum -= a[i - k];
if (i >= k - 1 && sum >= k * x) count++;
}
cout << count << "\n";
return 0;
}
2 2 2 2 5 5 5 8 with k = 3, x = 4:
3
Mini project: the best 7-day streak of a step counter
A month of daily step counts: print the best 7-day total, which days it covers, and the best 7-day average. A fixed window that also remembers where the best window starts.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
vector<long long> steps;
long long s;
while (cin >> s) steps.push_back(s);
const int k = 7;
if ((int)steps.size() < k) { cout << "need at least 7 days\n"; return 0; }
long long sum = 0, best = LLONG_MIN;
int bestStart = 0;
for (int i = 0; i < (int)steps.size(); i++) {
sum += steps[i];
if (i >= k) sum -= steps[i - k];
if (i >= k - 1 && sum > best) { best = sum; bestStart = i - k + 1; }
}
cout << "Best 7 days: day " << bestStart + 1 << " to day " << bestStart + k << "\n";
cout << "Total: " << best << " steps, average " << best / k << " a day\n";
return 0;
}
Fourteen days of steps:
Best 7 days: day 4 to day 10
Total: 56600 steps, average 8085 a day
Quick quiz
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 4, 7, 11, 15};
int i = 0, j = 5, steps = 0;
while (i < j) {
steps++;
int s = v[i] + v[j];
if (s == 15) break;
if (s < 15) i++; else j--;
}
cout << v[i] << " " << v[j] << " " << steps << "\n";
return 0;
}
(A) 4 11 4 (B) 4 11 3 (C) 1 15 1 (D) 7 7 5
Answer
(A) 4 11 4. 1+15 = 16 (too big, j--), 1+11 = 12 (too small, i++), 2+11 = 13 (i++), 4+11 = 15: found in 4 steps.
4 11 4
Interview questions
- Why do two pointers need sorted input for pair sum? The skip rule ("v[i] + the biggest is too small, so v[i] is useless") relies on order.
- Two pointers on unsorted input? Sort first (O(n log n)), or use a hash map of seen values (O(n) average, O(n) space).
while (i < j)orwhile (i <= j)? For a pair of different elements,i < j: wheni == jthere is only one element.- What is a sliding window? A range [left, right] over the array that moves forward, keeping some summary (sum, counts, last positions) up to date as elements enter and leave.
- Fixed vs variable window? Fixed: the size k never changes (one in, one out). Variable: grows and shrinks to keep a condition true ("no repeats", "sum < target").
- Why is the variable window O(n) even with an inner
while?leftonly moves forward, at most n times over the whole run, so the total work is at most 2n. - Why does the "shortest sum ≥ target" window need positive numbers? With negatives, shrinking can increase the sum, so the window logic breaks; use prefix sums with a monotonic deque instead.
- Why
left = max(left, last[c] + 1)? The old copy of c may already be left of the window;leftmust never move backwards. - What should
beststart at for a maximum? The smallest possible value (LLONG_MIN) or the first real candidate, never 0 when values can be negative.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Two pointers | Two indexes that move through the data, often from both ends | i = 0, j = n - 1 |
| Sorted vector | Elements in non-decreasing order | 1 3 5 6 9 |
| Pair sum | Two different elements adding up to a target | 1 + 9 = 10 |
| Sliding window | A range [left, right] that moves forward through the data | [5 1 3] in 2 1 5 1 3 2 |
| Fixed window | A window of constant size k | the best 3 days |
| Variable window | A window that grows and shrinks to keep a condition | no repeated characters |
| Running sum | A sum kept up to date as elements enter and leave | sum += a[i]; sum -= a[i - k]; |
LLONG_MIN |
The smallest long long (from <climits>) |
best = LLONG_MIN |
| Substring | A continuous part of a string | wke in pwwkew |
last[c] |
The latest index where character c appeared | last['a'] = 3 |
| Amortised O(n) | Total work O(n) even if one step does more | left moves at most n times |
| Off-by-one error | A condition wrong by exactly one | i <= j instead of i < j |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | O(n²) on 500,000 numbers |
Summary
- Pair sum (sorted):
ifrom the left,jfrom the right; too small →i++, too big →j--;while (i < j). O(n), O(1). - Best window of size k: one running sum, add
a[i], subtracta[i - k]; startbestatLLONG_MIN. O(n), O(1). - Longest substring without repeats:
last[c]= latest index;left = max(left, last[c] + 1); lengthi - left + 1. O(n). - Both ends only move forward: that's why these are O(n).
Next episode: Stack questions: balanced brackets (and the empty-stack trap), the next greater element with a monotonic stack, and evaluating a postfix expression.