These are the notes for C++ Coding Questions, episode 14, placement practice for people who finished the SyntaxPilot C++ course. Three hashing questions where unordered_set and unordered_map turn O(n²) into O(n): the longest consecutive sequence (and a duplicate that breaks the sort-and-count answer), subarray sum equals k (prefix sums, and a count that overflows an int), and a duplicate within distance k (and insert, which never overwrites).
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++ |
|---|---|
| Notebook pages scattered on the floor: the longest unbroken run of page numbers | longest consecutive sequence |
| Start counting only at a page whose previous page is missing | start only where x - 1 is not in the set |
| A shopkeeper's cash book with the running balance after every sale | a prefix sum |
| Money made between two moments = later balance − earlier balance | sum(a[i+1..j]) = pre[j] - pre[i] |
| "When was the balance exactly (now − k)?" | seen[pre - k] in an unordered_map |
| A toll gate noting the latest time each number plate passed | unordered_map<value, latest index>; last[x] = i |
Hashing in one minute
A hash function turns a key into a number; that number chooses the bucket where the key lives. A lookup computes the hash and checks one bucket: O(1) on average, however many keys there are. The price: no order, and in a bad case (many keys in one bucket) it gets slow. map / set are always O(log n) and sorted.
| Container | Lookup | Order |
|---|---|---|
set, map |
O(log n) guaranteed | sorted |
unordered_set, unordered_map |
O(1) on average, O(n) worst case | none |
Q1: Longest consecutive sequence
Problem. Given n numbers in any order, print the length of the longest run of consecutive values x, x+1, x+2, ... (they need not be next to each other in the input).
| Input | Output |
|---|---|
100 4 200 1 3 2 |
4 (1 2 3 4) |
1 2 2 3 4 9 |
4 (the extra 2 doesn't break the run) |
Think out loud. Edge cases: duplicates, a single number, negatives. Big test: 200,000 numbers (the test block, when n is 0, builds 200000 down to 1).
The obvious attempt: sort and count runs
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestRun(vector<int> a) {
if (a.empty()) return 0;
sort(a.begin(), a.end());
int best = 1, run = 1;
for (int i = 1; i < (int)a.size(); i++) {
if (a[i] == a[i - 1] + 1) run++;
else run = 1;
best = max(best, run);
}
return best;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 200,000 numbers, 200000 down to 1
n = 200000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
cout << longestRun(a) << "\n";
return 0;
}
100 4 200 1 3 2, then 1 2 2 3 4 9:
4
3
Why 3. Sorted: 1 2 2 3 4 9; runs: 1 2 1 2 3 1. The second 2 is not "previous + 1", so the run reset. A duplicate should neither grow nor break the run.
Fix: skip equal neighbours
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestRun(vector<int> a) {
if (a.empty()) return 0;
sort(a.begin(), a.end());
int best = 1, run = 1;
for (int i = 1; i < (int)a.size(); i++) {
if (a[i] == a[i - 1]) continue; // a duplicate: skip it
if (a[i] == a[i - 1] + 1) run++;
else run = 1;
best = max(best, run);
}
return best;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 200,000 numbers, 200000 down to 1
n = 200000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
cout << longestRun(a) << "\n";
return 0;
}
4
4
200000
1
4
Correct, O(n log n) because of the sort. The interview follow-up: O(n), without sorting.
Attempt: an unordered_set, counting up from every number
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int longestRun(const vector<int>& a) {
unordered_set<int> s(a.begin(), a.end());
int best = 0;
for (int x : s) {
int len = 1;
while (s.count(x + len)) len++;
best = max(best, len);
}
return best;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 200,000 numbers, 200000 down to 1
n = 200000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
cout << longestRun(a) << "\n";
return 0;
}
4
The big test (0) runs for more than a minute on our machine: Time Limit Exceeded.
Why. From 1 it walks 200,000 steps, from 2 almost as many, ...: 200,000 + 199,999 + ... + 1 ≈ 20 billion lookups. Every run is counted again from each of its members.
Fix: count only from the start of a run
A number x is the start of a run when x - 1 is not in the set. Count up only from starts: every run is walked once, so about 2n lookups in total.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int longestRun(const vector<int>& a) {
unordered_set<int> s(a.begin(), a.end());
int best = 0;
for (int x : s) {
if (s.count(x - 1)) continue; // not the start of a run
int len = 1;
while (s.count(x + len)) len++;
best = max(best, len);
}
return best;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 200,000 numbers, 200000 down to 1
n = 200000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = n - i;
}
cout << longestRun(a) << "\n";
return 0;
}
4
4
200000
1
4
O(n) time on average, O(n) space. Duplicates are handled for free: the set keeps one copy. (For the empty input the loop never runs and the answer is 0.)
Q2: Subarray sum equals k
Problem. Given n numbers (negatives allowed) and k, count the subarrays (continuous slices a[i..j], at least one element) whose sum is exactly k.
| Input (k = 3) | Output |
|---|---|
1 2 1 -1 3 |
5: [1 2], [2 1], [1 2 1 -1], [1 -1 3], [3] |
Think out loud. Edge cases: negatives, zeros. Big test: 400,000 zeros with k = 0 (every slice counts).
The obvious attempt: every start, every end
#include <iostream>
#include <vector>
using namespace std;
long long countSubarrays(const vector<int>& a, int k) {
long long count = 0;
for (int i = 0; i < (int)a.size(); i++) {
long long sum = 0;
for (int j = i; j < (int)a.size(); j++) {
sum += a[j]; // sum of a[i..j]
if (sum == k) count++;
}
}
return count;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 400,000 zeros, k = 0
n = 400000;
a.assign(n, 0);
}
cout << countSubarrays(a, k) << "\n";
return 0;
}
5
The big test (0 0) takes about 35 seconds on our machine: Time Limit Exceeded. It does about n²/2 = 80 billion additions.
The idea: prefix sums
Let pre[j] = a[0] + ... + a[j] (the running balance). The sum of a slice is a difference of two prefix sums:
sum(a[i+1..j]) = pre[j] − pre[i] = k ⇔ pre[i] = pre[j] − k
So walk once, and at each j ask: how many earlier prefix sums equal pre − k? An unordered_map<long long, int> from prefix sum to how many times we've seen it answers in O(1). Start with seen[0] = 1, the empty prefix, so slices starting at index 0 are counted. (A sliding window would not work here: with negative numbers, growing the window can make the sum smaller.)
Attempt: prefix sums with an int count
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int countSubarrays(const vector<int>& a, int k) {
unordered_map<long long, int> seen; // prefix sum -> how many times
seen[0] = 1; // the empty prefix
long long pre = 0;
int count = 0;
for (int x : a) {
pre += x;
if (seen.count(pre - k)) count += seen[pre - k];
seen[pre]++;
}
return count;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 400,000 zeros, k = 0
n = 400000;
a.assign(n, 0);
}
cout << countSubarrays(a, k) << "\n";
return 0;
}
1 2 1 -1 3 with k = 3, then the big test:
5
-1604178624
Why negative. 400,000 zeros have n(n + 1)/2 = 80,000,200,000 slices, all with sum 0. An int holds at most 2,147,483,647: going past it is signed overflow, which is undefined behaviour; here it printed a negative number. A count of subarrays can be about n²/2, so it needs a long long (up to about 9.2 × 10¹⁸). The prefix sums too: 400,000 numbers of 10⁹ add up to 4 × 10¹⁴.
Fix: long long count
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
long long countSubarrays(const vector<int>& a, int k) {
unordered_map<long long, int> seen; // prefix sum -> how many times
seen[0] = 1; // the empty prefix
long long pre = 0;
long long count = 0;
for (int x : a) {
pre += x;
if (seen.count(pre - k)) count += seen[pre - k];
seen[pre]++;
}
return count;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 400,000 zeros, k = 0
n = 400000;
a.assign(n, 0);
}
cout << countSubarrays(a, k) << "\n";
return 0;
}
1 2 1 -1 3 (k = 3), the big test, 1 1 1 (k = 2), 3 -3 1 -1 2 -2 (k = 0) and 1 2 3 4 (k = 5):
5
80000200000
2
6
1
O(n) time on average, O(n) space. (The int values in seen are fine: each counts prefix positions, at most n + 1.)
Trace for 1 2 1 -1 3, k = 3.
| x | pre | pre − k | seen[pre − k] | count | seen after |
|---|---|---|---|---|---|
| — | 0 | — | — | 0 | {0:1} |
| 1 | 1 | −2 | 0 | 0 | {0:1, 1:1} |
| 2 | 3 | 0 | 1 | 1 | {…, 3:1} |
| 1 | 4 | 1 | 1 | 2 | {…, 4:1} |
| −1 | 3 | 0 | 1 | 3 | {…, 3:2} |
| 3 | 6 | 3 | 2 | 5 | {…, 6:1} |
Q3: Duplicate within distance k
Problem. Given n numbers and k, print true if some value appears at two positions i ≠ j with j − i ≤ k.
| Input | Output |
|---|---|
1 2 3 1, k = 3 |
true (distance 3) |
1 2 3 1, k = 2 |
false |
1 2 3 1 4 1, k = 2 |
true (the 1s at 3 and 5) |
Think out loud. Edge cases: k = 0 (always false), no duplicates, the same value three times.
The obvious attempt: a set of seen values
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
bool nearbyDuplicate(const vector<int>& a, int k) {
unordered_set<int> seen;
for (int x : a) {
if (seen.count(x)) return true;
seen.insert(x);
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << (nearbyDuplicate(a, k) ? "true" : "false") << "\n";
return 0;
}
k = 3, then k = 2:
true
true
Why. A set remembers that it saw a value, not where. k is never used.
Attempt: value → index with insert
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
bool nearbyDuplicate(const vector<int>& a, int k) {
unordered_map<int, int> last; // value -> index where we saw it
for (int i = 0; i < (int)a.size(); i++) {
if (last.count(a[i]) && i - last[a[i]] <= k) return true;
last.insert({a[i], i});
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << (nearbyDuplicate(a, k) ? "true" : "false") << "\n";
return 0;
}
1 2 3 1 with k = 2, then 1 2 3 1 4 1 with k = 2:
false
false
Why false. At i = 0 we store {1, 0}. At i = 3 the distance 3 is too far, and insert({1, 3}) does nothing, because 1 is already a key (insert returns a pair whose .second is false). At i = 5 we still compare with index 0: 5 > 2.
Fix: last[a[i]] = i, always the latest index
m[key] = value always overwrites. The nearest earlier copy is the only one that can be within k, so keep the latest index.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
bool nearbyDuplicate(const vector<int>& a, int k) {
unordered_map<int, int> last; // value -> index where we saw it
for (int i = 0; i < (int)a.size(); i++) {
if (last.count(a[i]) && i - last[a[i]] <= k) return true;
last[a[i]] = i; // always the latest index
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << (nearbyDuplicate(a, k) ? "true" : "false") << "\n";
return 0;
}
1 2 3 1 4 1 (k = 2), 1 2 3 1 (k = 2), 1 2 3 1 (k = 3), 1 1 2 3 (k = 0), 7 8 9 (k = 5):
true
false
true
false
false
O(n) time on average, O(n) space. (Another way: keep an unordered_set of only the last k values, a sliding window: insert a[i], and erase a[i - k] once i ≥ k. Space O(k).)
The pattern behind all three
| Question | The brute force's inner loop asked | Stored instead |
|---|---|---|
| Longest run | "is x + len here?" from every x | unordered_set, start only where x − 1 is missing |
| Subarray sum k | "which earlier start gives sum k?" | unordered_map<prefix sum, count> |
| Nearby duplicate | "where did I last see x?" | unordered_map<value, latest index> |
Hashing replaces an inner loop that searches the past with one lookup into what you stored. The skill is storing the right thing: a count, the first index, or the latest index.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| longest run, sort + count | O(n log n) | O(n) (the copy) |
| longest run, walk up from every x | O(n²): TLE for 200,000 | O(n) |
| longest run, walk from starts only | O(n) average | O(n) |
| subarray sum, two loops | O(n²): TLE for 400,000 | O(1) |
subarray sum, prefix sums + unordered_map |
O(n) average | O(n) |
| nearby duplicate, value → latest index | O(n) average | O(n) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| sorted run without skipping duplicates | 3 instead of 4 |
an equal neighbour resets the run | if (a[i] == a[i - 1]) continue; |
| walk up from every number | Time Limit Exceeded | the same run again and again | start only where x - 1 is missing |
forgetting seen[0] = 1 |
slices starting at index 0 are missed | the empty prefix | seen[0] = 1 before the loop |
int count of subarrays |
-1604178624 |
n²/2 overflows int (UB) |
long long count |
| a sliding window for subarray sum with negatives | wrong counts | the sum isn't monotonic | prefix sums + map |
| a set for "within distance k" | true instead of false |
the set forgets positions | value → index |
m.insert({x, i}) to update |
false instead of true |
insert never overwrites |
m[x] = i |
Your turn: the longest slice with sum 0 (solution)
Problem. Find the length of the longest subarray with sum 0. 15 -2 2 -8 1 7 10 23 → 5 (-2 2 -8 1 7).
Idea. If the same prefix sum appears at positions i and j, the slice a[i+1..j] sums to 0, with length j − i. To make it as long as possible, keep the first index of each prefix sum, so here insert (which doesn't overwrite) is exactly right. Index −1 for the empty prefix handles slices that start at 0.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> a(n);
for (int& x : a) cin >> x;
unordered_map<long long, int> first; // prefix sum -> FIRST index
first[0] = -1; // the empty prefix
long long pre = 0;
int best = 0;
for (int i = 0; i < n; i++) {
pre += a[i];
if (first.count(pre)) best = max(best, i - first[pre]);
else first[pre] = i; // keep the first, never overwrite
}
cout << best << "\n";
}
return 0;
}
Inputs 15 -2 2 -8 1 7 10 23, 1 2 3 0, 0 0 0 and 3 -3 5:
5
1
3
2
(1 2 3 0 has the zero slice 0, length 1; 0 0 0 → 3; 3 -3 5 → 2.) O(n) time on average, O(n) space. Compare with Q3: there the latest index was right because we wanted the nearest copy; here the first is right because we want the farthest.
Practice questions (with solutions)
1. Count subarrays whose sum is divisible by k.
Solution
a[i+1..j] is divisible by k ⇔ pre[i] and pre[j] have the same remainder. Count remainders; with negatives, fix the remainder with ((pre % k) + k) % k.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_map<long long, long long> cnt; // remainder -> how many prefixes
cnt[0] = 1;
long long pre = 0, ans = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
pre += x;
long long r = ((pre % k) + k) % k; // C++ % can be negative
ans += cnt[r];
cnt[r]++;
}
cout << ans << "\n";
return 0;
}
4 5 0 -2 -3 1 with k = 5:
7
2. Count pairs with difference k (values, i < j, |a[i] − a[j]| = k, k > 0).
Solution
Walk once; for each x, the earlier values x − k and x + k pair with it.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_map<long long, long long> cnt; // value -> how many seen so far
long long pairs = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (cnt.count(x - k)) pairs += cnt[x - k];
if (cnt.count(x + k)) pairs += cnt[x + k];
cnt[x]++;
}
cout << pairs << "\n";
return 0;
}
1 5 3 4 2 with k = 2: the pairs are {1, 3}, {5, 3} and {4, 2}:
3
3. Longest consecutive sequence: print the run itself.
Solution
Remember the start of the best run, then print start, start + 1, ....
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
unordered_set<int> s(a.begin(), a.end());
int best = 0, bestStart = 0;
for (int x : s) {
if (s.count(x - 1)) continue;
int len = 1;
while (s.count(x + len)) len++;
if (len > best || (len == best && x < bestStart)) { best = len; bestStart = x; }
}
for (int i = 0; i < best; i++) cout << bestStart + i << " ";
cout << "\n";
return 0;
}
9 10 11 12 13
3 4 5 6 has length 4 and 9 10 11 12 13 has length 5, so the second run is printed (on a tie, the smaller start wins).
Mini project: did a student swipe in twice within 10 minutes?
A gate log of minute rollNumber lines (in time order). Print every roll number that swiped twice within 10 minutes, with the two times: Q3 with real times instead of indexes.
#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;
int main() {
unordered_map<int, int> lastTime; // roll -> latest minute
set<int> flagged;
int t, roll;
while (cin >> t >> roll) {
if (lastTime.count(roll) && t - lastTime[roll] <= 10 && !flagged.count(roll)) {
cout << "roll " << roll << ": " << lastTime[roll] << " and " << t << "\n";
flagged.insert(roll);
}
lastTime[roll] = t; // latest time, like the toll gate
}
if (flagged.empty()) cout << "nobody\n";
return 0;
}
Log: 0 12, 2 7, 5 31, 14 12, 16 7, 30 12, 33 12:
roll 12: 30 and 33
Roll 12's swipes at 0, 14 and 30 are each more than 10 minutes apart; only 30 and 33 are close, and that works only because the map keeps the latest time. Roll 7 (2 and 16) is 14 minutes apart: not flagged.
Quick quiz
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<string, int> m;
m.insert({"chai", 1});
m.insert({"chai", 5});
m["tea"] = 2;
m["tea"] = 7;
cout << m["chai"] << m["tea"] << m.size() << "\n";
return 0;
}
(A) 572 (B) 172 (C) 174 (D) 122
Answer
(B) 172. The second insert is ignored (chai stays 1); m["tea"] = 7 overwrites; two keys.
172
C++17 also has m.insert_or_assign(key, value), which inserts or overwrites and tells you which happened.
Interview questions
- Why is the longest consecutive sequence O(n) with the "start of a run" check? Each number is the start of at most one walk, and each walk only visits members of its own run, so the total work is about 2n lookups.
- Why does subarray sum equals k need
seen[0] = 1? It is the empty prefix: a slice starting at index 0 has sumpre[j] − 0. - Can a sliding window solve subarray sum equals k? Only if all numbers are positive (then the sum grows as the window grows). With negatives or zeros, use prefix sums + a hash map.
- What type should the count of subarrays have?
long long: it can be about n²/2. insertvsoperator[]vsinsert_or_assign?insertnever overwrites;m[k] = vcreates or overwrites;insert_or_assignoverwrites and reports whether it inserted.- First index or latest index? Latest when you want the nearest earlier copy (distance ≤ k); first when you want the farthest (longest slice).
- Worst case of
unordered_map? O(n) per operation if many keys land in one bucket (bad hash or crafted input). Judges sometimes use anti-hash tests;mapis a safe O(log n) fallback. - What is a prefix sum?
pre[i] = a[0] + ... + a[i]; any slice sum is a difference of two prefix sums.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Hashing | Turning a key into a number to find its bucket fast | unordered_set<int> |
| Hash function | The function that computes that number | std::hash<int> |
| Bucket | One slot of a hash table | — |
| O(1) on average | Constant time for typical inputs; slower in a bad case | s.count(x) |
unordered_set |
Unique values, hashed, no order | unordered_set<int> s(a.begin(), a.end()) |
unordered_map |
Key → value, hashed, no order | unordered_map<long long, int> seen |
| Consecutive sequence | Values x, x+1, x+2, ... | 1 2 3 4 |
| Start of a run | A value x with x − 1 missing | 1 in {1, 2, 3, 4} |
| Subarray | A continuous slice a[i..j], at least one element |
[2 1] in 1 2 1 -1 3 |
| Prefix sum | The running total a[0] + ... + a[i] |
1 3 4 3 6 |
| Empty prefix | The sum before any element: 0 | seen[0] = 1 |
| Signed overflow | A signed result too big for its type: undefined behaviour | an int count of 8 × 10¹⁰ |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to | overflow |
long long |
A 64-bit integer, up to about 9.2 × 10¹⁸ | long long count |
insert |
Adds a key only if it is missing; never overwrites | m.insert({1, 3}) ignored |
m[k] = v |
Creates or overwrites | last[a[i]] = i |
insert_or_assign |
C++17: inserts or overwrites | m.insert_or_assign(1, 3) |
| Sliding window | A range [left, right] that moves forward | the last k values |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | O(n²) on 400,000 numbers |
Summary
- Longest run: an
unordered_set, and count only from starts (x - 1missing): O(n). After a sort, skip duplicates. - Subarray sum k: prefix sums;
count += seen[pre - k],seen[pre]++, starting withseen[0] = 1; the count is along long. - Nearby duplicate: value → latest index with
last[x] = i;insertnever overwrites. - Hashing replaces "search the past" loops with one lookup. Store the right thing: a count, the first index, or the latest index.
Next episode: Two pointers and the sliding window: a pair with a given sum in a sorted vector, the maximum sum of a window of size k, and the longest substring without repeating characters.