SyntaxPilot
Courses/C++ Coding Questions/Lesson 14
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 14 of 30

Hashing questions

longest consecutive sequencesubarray sum equals k (prefix sum + unordered_map)duplicate within distance k

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

  1. 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.
  2. Why does subarray sum equals k need seen[0] = 1? It is the empty prefix: a slice starting at index 0 has sum pre[j] − 0.
  3. 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.
  4. What type should the count of subarrays have? long long: it can be about n²/2.
  5. insert vs operator[] vs insert_or_assign? insert never overwrites; m[k] = v creates or overwrites; insert_or_assign overwrites and reports whether it inserted.
  6. First index or latest index? Latest when you want the nearest earlier copy (distance ≤ k); first when you want the farthest (longest slice).
  7. 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; map is a safe O(log n) fallback.
  8. 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 - 1 missing): O(n). After a sort, skip duplicates.
  • Subarray sum k: prefix sums; count += seen[pre - k], seen[pre]++, starting with seen[0] = 1; the count is a long long.
  • Nearby duplicate: value → latest index with last[x] = i; insert never 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.