These are the notes for C++ Coding Questions, episode 10, placement practice for people who finished the SyntaxPilot C++ course. Vectors, part three: three of the most asked interview questions of all time. Two sum with an unordered_map, the maximum subarray sum with Kadane's algorithm, and range sum queries with prefix sums. All three use one idea: remember something useful, so you never redo the work.
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.
The test blocks. Nobody can type 500,000 numbers, so the programs have a small test block: when the first number read is 0, the program builds a big input itself (for example 500,000 even numbers). Everything else reads normal input.
Real-life pictures
| In real life | In C++ |
|---|---|
| A Diwali gift voucher worth exactly ₹500: find two items that use all of it | two sum: two numbers that add up to a target |
| Trying every item with every other item | two nested loops, O(n²) |
| Writing each price in a notebook as you walk the shelf: "this is ₹120, did I already see a ₹380?" | an unordered_map from value to index, look up target - x |
| Raju's chai stall: profit some days, loss on others; the best stretch of days in a row | the maximum subarray sum |
| A running khata that went below zero is only a debt: start a fresh one | Kadane's algorithm: cur = max(x, cur + x) |
| The cricket scoreboard: runs in overs 11 to 20 = score after 20 − score after 10; 0 before the first ball | prefix sums: p[r + 1] - p[l], with p[0] = 0 |
Q1: Two sum
Problem. Given n numbers and a target, print the indexes of two different numbers that add up to the target, or -1 -1 if there are none. n can be 500,000.
| Input (n target / numbers) | Output |
|---|---|
| 4 9 / 2 7 11 15 | 0 1 |
| 3 6 / 3 2 4 | 1 2 |
| 2 6 / 3 3 | 0 1 |
| 3 10 / 1 2 3 | -1 -1 |
Think out loud. The same number can't be used twice (3 2 4 with target 6 is not 3 + 3). Equal values at different indexes are fine (3 3 with target 6). There may be no answer at all.
The obvious attempt: every pair
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> twoSum(const vector<int>& v, int target) {
int n = v.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (v[i] + v[j] == target) return {i, j};
return {-1, -1};
}
int main() {
int n, target;
while (cin >> n >> target) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers, no pair
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = 2 * i;
}
auto [i, j] = twoSum(v, target);
cout << i << " " << j << "\n";
}
return 0;
}
Input 4 9 / 2 7 11 15 / 3 6 / 3 2 4 / 2 6 / 3 3 / 3 10 / 1 2 3:
0 1
1 2
0 1
-1 -1
Correct. Now 0 1 (the test block: 500,000 even numbers, target 1, so no pair exists):
Time Limit Exceeded (no output: the program was stopped)
Why. Every pair means n × (n − 1) / 2 checks: about 125 billion for 500,000 numbers.
The idea. For each number x we don't need every other number. We need exactly one: target − x. "Is it there, and at which index?" is what a hash map answers, on average in O(1).
Attempt: put everything in the map first, then look up
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
pair<int, int> twoSum(const vector<int>& v, int target) {
unordered_map<int, int> pos; // value -> index
for (int i = 0; i < (int)v.size(); i++) pos[v[i]] = i;
for (int i = 0; i < (int)v.size(); i++) {
auto it = pos.find(target - v[i]);
if (it != pos.end()) return {i, it->second};
}
return {-1, -1};
}
int main() {
int n, target;
while (cin >> n >> target) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers, no pair
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = 2 * i;
}
auto [i, j] = twoSum(v, target);
cout << i << " " << j << "\n";
}
return 0;
}
0 1
0 0
0 1
-1 -1
The second test prints 0 0: index 0 is the 3, and 3 + 3 = 6, but there is only one 3. The number found itself, because the map already held every value.
Fix: look up first, then insert (one pass)
Walk the numbers once. For each v[i], first look for target - v[i] among the numbers before i, then write v[i] in the map. The map never contains v[i] itself when we look, so a number can't match itself, and 3 3 still works because the first 3 is already in the map when we reach the second.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
pair<int, int> twoSum(const vector<int>& v, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < (int)v.size(); i++) {
auto it = seen.find(target - v[i]);
if (it != seen.end()) return {it->second, i};
seen[v[i]] = i;
}
return {-1, -1};
}
int main() {
int n, target;
while (cin >> n >> target) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers, no pair
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = 2 * i;
}
auto [i, j] = twoSum(v, target);
cout << i << " " << j << "\n";
}
return 0;
}
0 1
1 2
0 1
-1 -1
And the 500,000-number test, almost instantly:
-1 -1
Complexity. O(n) time on average (each map lookup and insert is O(1) average, O(n) in the rare worst case), O(n) extra space for the map. A classic trade: memory for speed.
Watch out: target - v[i] can overflow an int when the numbers are near ±2 billion (-2000000000 - 2000000000). For such inputs use long long for the values and the map's key.
Q2: Maximum subarray sum
Problem. A subarray is a block of numbers next to each other, at least one number long. Print the largest sum of any subarray.
| Input | Output | Best block |
|---|---|---|
| -2 1 -3 4 -1 2 1 -5 4 | 6 | 4 -1 2 1 |
| 2 -1 2 -1 2 | 4 | the whole thing |
| 5 | 5 | 5 |
| -3 -1 -2 | -1 | -1 |
Think out loud. If every number is negative, the answer is the largest single number (not 0: an empty block is not allowed). One number. 500,000 numbers. The sum can be bigger than an int.
The obvious attempt: every block, with a running sum
Every start i, and a running sum that grows as j moves right, so each of the n(n + 1)/2 blocks costs one step (already better than three loops, O(n³)).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long maxSub(const vector<int>& v) {
int n = v.size();
long long best = v[0];
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = i; j < n; j++) {
sum += v[j];
best = max(best, sum);
}
}
return best;
}
int main() {
int n;
while (cin >> n) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
}
cout << maxSub(v) << "\n";
}
return 0;
}
6
4
5
Correct. Now 0 (500,000 numbers):
Time Limit Exceeded (no output: the program was stopped)
The idea: a running khata (Kadane's algorithm)
Let cur be the best sum of a block that ends at today. Today either joins yesterday's block (cur + x) or starts a fresh block (x). Take the bigger one:
cur = max(x, cur + x) // continue, or start fresh
best = max(best, cur) // the best ever seen
For -2 1 -3 4 -1 2 1: cur goes −2, 1, −2, 4, 3, 5, 6 and best ends at 6. Starting fresh is the same as Raju throwing away a khata that has gone into loss: carrying a debt forward can only make later totals smaller.
Attempt: the popular version with zero
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long maxSub(const vector<int>& v) {
long long best = 0, cur = 0;
for (int x : v) {
cur = max(0LL, cur + x);
best = max(best, cur);
}
return best;
}
int main() {
int n;
while (cin >> n) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
}
cout << maxSub(v) << "\n";
}
return 0;
}
Input with the all-negative test added (3 / -3 -1 -2):
6
4
5
0
The last answer is 0, but there is no 0 in -3 -1 -2. Starting best at 0 (and resetting cur to 0) quietly allows an empty block. With all losses, taking nothing beats every real block. The question says at least one number.
Fix: start from v[0]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long maxSub(const vector<int>& v) {
long long best = v[0], cur = v[0];
for (int i = 1; i < (int)v.size(); i++) {
cur = max((long long)v[i], cur + v[i]);
best = max(best, cur);
}
return best;
}
int main() {
int n;
while (cin >> n) {
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) { // test: 500,000 numbers
v.resize(500000);
for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
}
cout << maxSub(v) << "\n";
}
return 0;
}
6
4
5
-1
And 500,000 numbers (the pattern −5, −4, ..., 4 repeated), instantly:
10
Complexity. O(n) time, one pass. O(1) extra space: two numbers. Sums are long long: 500,000 numbers of up to a billion each don't fit in an int.
Q3: Range sum queries
Problem. Read n numbers, then q questions l r (0-based, inclusive). For each, print v[l] + ... + v[r]. n and q can be 300,000.
| Numbers | Question | Answer |
|---|---|---|
| 3 1 4 1 5 9 | 0 2 | 8 |
| 2 5 | 19 | |
| 4 4 | 5 |
Think out loud. A range starting at 0. A range of one number. Big totals.
The obvious attempt: a loop per question
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { n = q = 300000; v.assign(n, 100000); } // test
for (int k = 0; k < q; k++) {
int l = 0, r = n - 1;
if (!big) cin >> l >> r;
long long s = 0;
for (int i = l; i <= r; i++) s += v[i];
if (!big || k == q - 1) cout << s << "\n";
}
return 0;
}
8
19
5
Now 0 0 (the test block: 300,000 numbers of 100,000 each, 300,000 questions over the whole array; it prints only the last answer):
Time Limit Exceeded (no output: the program was stopped)
Why. q questions × up to n numbers each = 90 billion additions.
The idea: the scoreboard, p[i]
Build the running totals once. p[i] = the sum of the first i numbers, and p[0] = 0 (the score before the first ball):
v: 3 1 4 1 5 9
p: 0 3 4 8 9 14 23
sum(l..r) = p[r + 1] - p[l] sum(2..5) = 23 - 4 = 19
p has n + 1 entries, so a range starting at 0 just subtracts p[0] = 0: no special case.
Attempt: prefix sums in vector<int>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { n = q = 300000; v.assign(n, 100000); } // test
vector<int> p(n + 1, 0);
for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
for (int k = 0; k < q; k++) {
int l = 0, r = n - 1;
if (!big) cin >> l >> r;
long long s = p[r + 1] - p[l];
if (!big || k == q - 1) cout << s << "\n";
}
return 0;
}
8
19
5
Fast, but the big test prints a negative number:
-64771072
The total should be 300,000 × 100,000 = 30,000,000,000, and an int holds at most 2,147,483,647. Signed overflow is undefined behaviour in C++: the language promises nothing; here it wrapped around like an odometer. Writing long long s = p[r + 1] - p[l] does not help: int - int is computed as an int, already wrong, and only then converted.
Fix: vector<long long>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { n = q = 300000; v.assign(n, 100000); } // test
vector<long long> p(n + 1, 0);
for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
for (int k = 0; k < q; k++) {
int l = 0, r = n - 1;
if (!big) cin >> l >> r;
long long s = p[r + 1] - p[l];
if (!big || k == q - 1) cout << s << "\n";
}
return 0;
}
8
19
5
30000000000
Complexity. O(n) to build, then O(1) per question: O(n + q) in total. O(n) extra space.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| two sum, two loops | O(n²) | O(1) |
| two sum, map filled first | O(n) average, but wrong | O(n) |
| two sum, look up then insert | O(n) average | O(n) |
| max subarray, every block | O(n²) | O(1) |
| max subarray, Kadane | O(n) | O(1) |
| range sums, loop per question | O(n × q) | O(1) |
| range sums, prefix sums | O(n + q) | O(n) |
The pattern: remember something useful (values seen, the best block ending here, running totals) so the work is never redone.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| two loops for two sum on big inputs | Time Limit Exceeded | n² / 2 checks | unordered_map, one pass |
| fill the map first, then look up | 3 2 4, target 6 → 0 0 |
x finds itself | look up, then insert |
long long best = 0, cur = 0; in Kadane |
-3 -1 -2 → 0 |
0 is the empty block | start at v[0], loop from 1 |
int sums in Kadane or prefix sums |
a negative or wrong total | signed overflow (undefined behaviour) | long long |
long long s = p[r + 1] - p[l] with int p |
still wrong | the subtraction is done in int |
make p itself long long |
p of size n, answer p[r] - p[l - 1] |
l = 0 reads p[-1] |
out of bounds (undefined behaviour) | size n + 1, p[r + 1] - p[l] |
Your turn: count subarrays with sum k (solution)
Problem. Count how many subarrays (blocks of numbers next to each other) add up to k. 1 1 1, k = 2 → 2. 1 2 3, k = 3 → 2 (1 2 and 3).
Idea. A block from l to r adds up to k exactly when p[r + 1] - p[l] == k, that is p[l] == p[r + 1] - k. So walking the prefix sums is two sum again: for each new prefix p, count how many earlier prefixes equal p - k. Store counts (not indexes) in an unordered_map, and start with seen[0] = 1 for the empty prefix. This works with negative numbers too (a sliding window would not).
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
long long countK(const vector<int>& v, long long k) {
unordered_map<long long, long long> seen; // prefix sum -> how many times
seen[0] = 1; // the empty prefix, before the first number
long long p = 0, count = 0;
for (int x : v) {
p += x;
auto it = seen.find(p - k);
if (it != seen.end()) count += it->second;
seen[p]++;
}
return count;
}
int main() {
int n; long long k;
while (cin >> n >> k) {
vector<int> v(n);
for (int& x : v) cin >> x;
cout << countK(v, k) << "\n";
}
return 0;
}
Input 3 2 / 1 1 1 / 3 3 / 1 2 3 / 5 0 / 1 -1 1 -1 0:
2
2
7
O(n) average time, O(n) space.
Practice questions (with solutions)
1. Two sum on a sorted vector, without a map. Use two pointers: if the sum is too small, move the left one right; too big, move the right one left.
Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, target;
while (cin >> n >> target) {
vector<int> v(n);
for (int& x : v) cin >> x; // sorted
int i = 0, j = n - 1;
while (i < j && v[i] + v[j] != target) {
if (v[i] + v[j] < target) i++; // too small: a bigger left number
else j--; // too big: a smaller right number
}
if (i < j) cout << i << " " << j << "\n";
else cout << "-1 -1\n";
}
return 0;
}
Input 5 9 / 1 2 4 5 7 / 4 100 / 1 2 3 4:
1 4
-1 -1
O(n) time, O(1) space. (1 2 4 5 7 has two answers, 2 + 7 and 4 + 5; this finds the first one the pointers meet.)
2. Maximum product subarray. Like Kadane, but a negative number turns the smallest product into the biggest, so keep both.
Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<long long> v(n);
for (auto& x : v) cin >> x;
long long hi = v[0], lo = v[0], best = v[0];
for (int i = 1; i < n; i++) {
long long x = v[i];
if (x < 0) swap(hi, lo); // a negative flips the biggest and the smallest
hi = max(x, hi * x);
lo = min(x, lo * x);
best = max(best, hi);
}
cout << best << "\n";
}
return 0;
}
Input 4 / 2 3 -2 4 / 3 / -2 0 -1 / 4 / -2 3 -4 1:
6
0
24
O(n) time, O(1) space.
3. Sum of a rectangle with 2D prefix sums. p[i][j] = the sum of the top-left i × j block; a rectangle is one big block minus two strips plus the corner subtracted twice.
Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
int r, c, q;
cin >> r >> c >> q;
vector<vector<long long>> p(r + 1, vector<long long>(c + 1, 0));
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
long long x; cin >> x;
p[i + 1][j + 1] = x + p[i][j + 1] + p[i + 1][j] - p[i][j];
}
while (q--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2; // 0-based, inclusive corners
cout << p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1] << "\n";
}
return 0;
}
Input: a 3 × 3 grid 1 2 3 / 4 5 6 / 7 8 9, questions 0 0 1 1 and 1 1 2 2:
12
28
O(r × c) to build, O(1) per question.
Mini project: Raju's chai stall report
Read the daily profit or loss, print the best stretch of days (Kadane that also remembers where the block starts and ends), then answer "how much from day a to day b?" questions with prefix sums (1-based days here, like a calendar).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
// best stretch of days (Kadane, remembering where it starts and ends)
long long best = v[0], cur = v[0];
int start = 0, bestL = 0, bestR = 0;
for (int i = 1; i < n; i++) {
if (cur + v[i] < v[i]) { cur = v[i]; start = i; }
else cur += v[i];
if (cur > best) { best = cur; bestL = start; bestR = i; }
}
cout << "best stretch: day " << bestL + 1 << " to day " << bestR + 1 << ", profit " << best << "\n";
// range questions with prefix sums
vector<long long> p(n + 1, 0);
for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
int a, b;
while (cin >> a >> b) // 1-based days, inclusive
cout << "days " << a << "-" << b << ": " << p[b] - p[a - 1] << "\n";
return 0;
}
Input 7 / 40 -10 25 -70 30 20 -5, then 1 3, 5 6, 1 7:
best stretch: day 1 to day 3, profit 55
days 1-3: 55
days 5-6: 50
days 1-7: 30
Quick quiz
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {2, -5, 3, 1, -2, 4};
long long best = v[0], cur = v[0];
for (int i = 1; i < 6; i++) {
cur = max((long long)v[i], cur + v[i]);
best = max(best, cur);
}
cout << best;
return 0;
}
(A) 3 (B) 6 (C) 4 (D) 8
Answer
(B) 6. cur goes 2, −3, then starts fresh at 3, 4, 2, 6. The best block is 3 1 -2 4: the −2 is worth keeping because the 4 after it pays it back.
6
Interview questions
- Solve two sum in O(n). One pass with an
unordered_mapfrom value to index: look uptarget - x, then insert x. - Why look up before inserting? So a number can never be matched with itself; the map holds only earlier numbers.
- Two sum when the array is sorted? Two pointers from both ends, O(n) time and O(1) space.
- Explain Kadane's algorithm.
curis the best block ending at the current index:max(x, cur + x);bestis the maximumcurever seen. O(n), O(1). - What does Kadane return for all-negative input, and how do you make sure? The largest single number; start
bestandcuratv[0], not 0. - How do you answer many range-sum questions fast? Prefix sums: O(n) once, then
p[r + 1] - p[l]in O(1). - Why does the prefix array have n + 1 entries?
p[0] = 0stands for "nothing yet", so a range starting at 0 needs no special case. - Count subarrays with sum k when numbers can be negative. Prefix sums + an
unordered_mapof prefix counts, starting with{0: 1}. A sliding window only works for non-negative numbers. - Is integer overflow a crash? No: signed overflow is undefined behaviour; usually you just get a wrong number. Use
long longfor sums.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Two sum | Find two different elements that add up to a target | 2 + 7 = 9 → indexes 0 1 |
| Target | The value the two numbers must add up to | 9 |
std::unordered_map |
Key → value container with no order (a hash table) | unordered_map<int, int> seen; |
| Hash table | Finds a key by computing a number (hash) from it | O(1) average lookup |
find (on a map) |
Looks for a key without inserting it; returns end() if missing |
seen.find(target - x) |
| One pass | One walk through the data | look up and insert in the same loop |
| Subarray | A block of elements next to each other, at least one | 4 -1 2 1 in -2 1 -3 4 -1 2 1 |
| Maximum subarray sum | The largest sum of any subarray | 6 |
| Kadane's algorithm | cur = max(x, cur + x), best = max(best, cur) |
O(n), O(1) |
| Empty subarray | A block of zero elements, sum 0 (usually not allowed) | why best = 0 is wrong |
| Prefix sum | p[i] = sum of the first i elements, p[0] = 0 |
0 3 4 8 9 14 23 |
| Range sum query | The sum of v[l..r] |
p[r + 1] - p[l] |
| Inclusive range | Both ends are included | 2 5 means v[2], v[3], v[4], v[5] |
long long |
A 64-bit integer, up to about 9.2 × 10¹⁸ | vector<long long> p |
| Signed overflow | A signed result too big for its type: undefined behaviour | 30 billion in an int |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to: anything can happen | p[-1], int overflow |
| Structured binding | auto [i, j] unpacks a pair (C++17) |
auto [i, j] = twoSum(v, target); |
pair<int, int> |
Two values together | return {i, j}; |
| O(n²) | Work grows with the square of n | every pair |
| O(n + q) | Build once, then constant time per question | prefix sums |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | two loops on 500,000 numbers |
Summary
- Two sum: for each x, look for
target - xin anunordered_map, then insert x. O(n) average, O(n) space. Filling the map first lets a number find itself. - Maximum subarray (Kadane):
cur = max(x, cur + x),best = max(best, cur), both starting atv[0]. Starting at 0 returns 0 for all-negative input. - Range sums:
pof size n + 1,p[0] = 0, answerp[r + 1] - p[l]in O(1). Uselong long: the overflow happens before the subtraction is stored. - Remember something useful, so you never redo the work.
Next episode: Sorting questions: your own comparator for std::sort (and the >= that makes it crash), sorting by two keys with a tie-break and stable_sort, and sorting strings by length, then alphabetically.