These are the notes for C++ Coding Questions, episode 18, placement practice for people who finished the SyntaxPilot C++ course. The heap, which always keeps the best item on top, on three of the most asked interview questions: the k largest elements (a min-heap of size k, and why the default max-heap keeps exactly the wrong ones), the k-th smallest (why a set loses duplicates), and merging k sorted vectors (a heap of fronts, and the empty-list crash).
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++ |
|---|---|
| A hospital emergency room: the most serious patient is seen first | a priority queue (heap): top() is the best |
| Picking the top 3 run-scorers: the weakest selected player sits in the guard chair by the door | the k largest: a min-heap of size k, top() is the weakest kept |
| A new player only has to beat the guard | compare with pq.top(); pop() throws out the weakest |
| The 3rd shortest child in a photo, twins included | the k-th smallest, duplicates count |
| Writing down only the different heights | a set: each value once |
| The principal looks only at the top sheet of each teacher's sorted pile | merge k lists: a heap of the k fronts |
| A teacher who handed in no sheets | an empty vector has no [0] |
A heap in one minute: priority_queue
#include <queue>
priority_queue<int> pq; // MAX-heap: top() is the largest
pq.push(5); pq.top(); pq.pop(); pq.size(); pq.empty();
priority_queue<int, vector<int>, greater<int>> mn; // MIN-heap: top() is the smallest
pushandpopare O(log n);top,sizeandemptyare O(1).- The second template argument,
vector<int>, is where the values are stored; the third, the comparatorgreater<int>, flips the order.greater<>(empty brackets) works for any type that has>, such aspairortuple. pop()removes the top: the largest in a max-heap, the smallest in a min-heap.
What a heap looks like inside
A binary heap is a binary tree where every parent is ≥ its children (max-heap), so the largest is at the root. It is stored in a plain vector: the children of index i are at 2i + 1 and 2i + 2.
12
/ \
5 11 stored in a vector: 12 5 11 3 1 2
/ \ /
3 1 2
push adds at the end and swaps up while bigger than its parent; pop moves the last value to the root and swaps it down. The tree has about log₂ n levels, so both are O(log n). The same operations exist as functions on a plain vector: make_heap, push_heap, pop_heap.
Q1: The k largest elements
Problem. Given n numbers and k, print the k largest, the smallest of them first.
| Input | Output |
|---|---|
3 1 5 12 2 11, k = 3 |
5 11 12 |
Think out loud. Edge cases: k = n, duplicates. Big test (0 0): 1,000,000 numbers (a shuffle of 0 … 999,999), k = 100,000; the program prints how many were kept and the smallest of them.
The obvious attempt: find the max and erase it, k times
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kLargest(vector<int> a, int k) {
vector<int> top;
for (int t = 0; t < k; t++) {
auto it = max_element(a.begin(), a.end());
top.push_back(*it);
a.erase(it); // take the biggest out
}
reverse(top.begin(), top.end()); // smallest first
return top;
}
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 = 100,000
n = 1000000; k = 100000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
}
vector<int> top = kLargest(a, k);
if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
for (int x : top) cout << x << " ";
cout << "\n";
return 0;
}
5 11 12
On the big test:
Time Limit Exceeded
100,000 rounds, each scanning up to a million numbers, and erase shifts the rest too: around 100,000,000,000 steps. O(n · k).
Attempt: a heap of size k, with the default priority_queue<int>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> kLargest(const vector<int>& a, int k) {
priority_queue<int> pq;
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop(); // too many: drop one
}
vector<int> top;
while (!pq.empty()) { top.push_back(pq.top()); pq.pop(); }
return top;
}
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 = 100,000
n = 1000000; k = 100000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
}
vector<int> top = kLargest(a, k);
if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
for (int x : top) cout << x << " ";
cout << "\n";
return 0;
}
3 2 1
3 2 1: the three smallest. After 3 1 5 12 the heap has 4 values; pop() removes the top, and in a max-heap the top is 12, the best player.
Fix: a min-heap, greater<int>
To keep the k largest, the heap must throw out the weakest: a min-heap, whose top is the smallest kept value (the guard chair).
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> kLargest(const vector<int>& a, int k) {
priority_queue<int, vector<int>, greater<int>> pq; // min-heap
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop(); // too many: drop one
}
vector<int> top;
while (!pq.empty()) { top.push_back(pq.top()); pq.pop(); }
return top;
}
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 = 100,000
n = 1000000; k = 100000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
}
vector<int> top = kLargest(a, k);
if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
for (int x : top) cout << x << " ";
cout << "\n";
return 0;
}
5 11 12
The big test, instantly:
100000 kept, smallest 900000
O(n log k) time (the heap never holds more than k + 1 values), O(k) space. When n is huge and k small (the top 10 of a billion log lines), this is far better than sorting everything.
Q2: The k-th smallest element
Problem. Given n numbers and k, print the k-th smallest. Duplicates count.
| Input | Output |
|---|---|
7 10 4 3 20 15, k = 3 |
7 (3 4 7) |
7 10 4 3 20 15 4, k = 3 |
4 (3 4 4) |
The obvious attempt: a set
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int kthSmallest(const vector<int>& a, int k) {
set<int> s(a.begin(), a.end()); // sorted
auto it = s.begin();
advance(it, k - 1); // step to the k-th
return *it;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << kthSmallest(a, k) << "\n";
return 0;
}
7
7
7 again, but the answer is 4. A set keeps each value once: {3 4 7 10 15 20}, the second 4 is gone. (A multiset keeps duplicates but sorts all n values.)
Fix: a max-heap of size k
Q1 turned around: a max-heap of size k holds the k smallest so far; when it grows past k, pop() throws out the biggest. At the end, top() is the biggest of the k smallest: the k-th smallest.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int kthSmallest(const vector<int>& a, int k) {
priority_queue<int> pq; // max-heap: the k smallest
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop(); // drop the biggest
}
return pq.top(); // the biggest of the k smallest
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << kthSmallest(a, k) << "\n";
return 0;
}
4
7
O(n log k) time, O(k) space.
Another way: nth_element. nth_element(a.begin(), a.begin() + k - 1, a.end()) puts the k-th smallest at index k − 1, smaller-or-equal values before it and bigger-or-equal after, in O(n) on average (it changes the vector):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> a = {7, 10, 4, 3, 20, 15, 4};
int k = 3;
nth_element(a.begin(), a.begin() + k - 1, a.end());
cout << a[k - 1] << "\n";
return 0;
}
4
Q3: Merge k sorted vectors
Problem. Given k sorted vectors (each as its length m, then m numbers), print one sorted list.
| Input | Output |
|---|---|
1 4 7, 2 5 8, 3 6 9 |
1 2 3 4 5 6 7 8 9 |
1 4 7, (empty), 2 5, 0 3 6 9 |
0 1 2 3 4 5 6 7 9 |
Think out loud. Only the current front of each list can be next. Edge cases: an empty list, lists of different lengths. Big test (0): 50,000 lists of 20 numbers (1,000,000 in total).
The obvious attempt: scan all k fronts every time
#include <iostream>
#include <vector>
using namespace std;
vector<int> mergeK(const vector<vector<int>>& lists) {
int k = lists.size();
vector<int> pos(k, 0), all;
while (true) {
int best = -1; // the list with the smallest front
for (int i = 0; i < k; i++)
if (pos[i] < (int)lists[i].size() &&
(best == -1 || lists[i][pos[i]] < lists[best][pos[best]])) best = i;
if (best == -1) break; // every list is used up
all.push_back(lists[best][pos[best]++]);
}
return all;
}
int main() {
int k;
cin >> k;
vector<vector<int>> lists(k);
for (auto& v : lists) {
int m;
cin >> m;
v.resize(m);
for (int& x : v) cin >> x;
}
if (k == 0) { // test: 50,000 lists of 20
lists.assign(50000, vector<int>(20));
for (int i = 0; i < 50000; i++)
for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
}
vector<int> all = mergeK(lists);
if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
for (int x : all) cout << x << " ";
cout << "\n";
return 0;
}
1 2 3 4 5 6 7 8 9
On the big test:
Time Limit Exceeded
1,000,000 numbers × 50,000 fronts = 50,000,000,000 comparisons: O(N · k), and only one front changed each time.
The idea: the k fronts in a min-heap
The heap holds one entry per list, its current front, as a tuple {value, which list, index in that list} (a tuple groups several values into one; greater<> compares tuples by their first value, then the next). Pop the smallest; push the next value from the same list. The heap has at most k entries, so each step is O(log k).
auto [val, li, idx] = pq.top(); is a structured binding (C++17): it unpacks the tuple into three named variables.
Attempt: push lists[i][0] for every list
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
vector<int> mergeK(const vector<vector<int>>& lists) {
// {value, which list, index in that list}, smallest value on top
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
for (int i = 0; i < (int)lists.size(); i++)
pq.push({lists[i][0], i, 0});
vector<int> all;
while (!pq.empty()) {
auto [val, li, idx] = pq.top();
pq.pop();
all.push_back(val);
if (idx + 1 < (int)lists[li].size()) pq.push({lists[li][idx + 1], li, idx + 1});
}
return all;
}
int main() {
int k;
cin >> k;
vector<vector<int>> lists(k);
for (auto& v : lists) {
int m;
cin >> m;
v.resize(m);
for (int& x : v) cin >> x;
}
if (k == 0) { // test: 50,000 lists of 20
lists.assign(50000, vector<int>(20));
for (int i = 0; i < 50000; i++)
for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
}
vector<int> all = mergeK(lists);
if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
for (int x : all) cout << x << " ";
cout << "\n";
return 0;
}
On the test with an empty list:
Runtime Error (SIGSEGV)
The second list is empty and lists[1][0] reads an element that doesn't exist. [] never checks the size: undefined behaviour, here a segmentation fault before anything was printed. (lists[1].at(0) would throw std::out_of_range instead.) The scan version compared pos[i] with the size every time, so it never fell for this.
Fix: push only lists that have a front
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
vector<int> mergeK(const vector<vector<int>>& lists) {
// {value, which list, index in that list}, smallest value on top
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
for (int i = 0; i < (int)lists.size(); i++)
if (!lists[i].empty()) pq.push({lists[i][0], i, 0});
vector<int> all;
while (!pq.empty()) {
auto [val, li, idx] = pq.top();
pq.pop();
all.push_back(val);
if (idx + 1 < (int)lists[li].size()) pq.push({lists[li][idx + 1], li, idx + 1});
}
return all;
}
int main() {
int k;
cin >> k;
vector<vector<int>> lists(k);
for (auto& v : lists) {
int m;
cin >> m;
v.resize(m);
for (int& x : v) cin >> x;
}
if (k == 0) { // test: 50,000 lists of 20
lists.assign(50000, vector<int>(20));
for (int i = 0; i < 50000; i++)
for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
}
vector<int> all = mergeK(lists);
if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
for (int x : all) cout << x << " ";
cout << "\n";
return 0;
}
0 1 2 3 4 5 6 7 9
1 2 3 4 5 6 7 8 9
The big test, instantly:
1000000 merged, last 999999
O(N log k) time for N numbers in total, O(k) heap space (plus the output).
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| k largest, find max + erase k times | O(n · k): TLE | O(k) |
| k largest, sort everything | O(n log n) | O(1)–O(n) |
| k largest, min-heap of size k | O(n log k) | O(k) |
k-th smallest, set |
O(n log n), wrong with duplicates | O(n) |
| k-th smallest, max-heap of size k | O(n log k) | O(k) |
k-th smallest, nth_element |
O(n) average | O(1) |
| merge k lists, scan fronts | O(N · k): TLE | O(k) |
| merge k lists, heap of fronts | O(N log k) | O(k) |
Rule of thumb: k largest → min-heap; k smallest → max-heap. The heap's top is the one about to be thrown out.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
priority_queue<int> for the k largest |
3 2 1 |
pop() drops the biggest |
greater<int>: a min-heap |
greater<int> for the k-th smallest |
the k-th largest | the heap drops the smallest | the default max-heap |
a set for the k-th smallest |
7 instead of 4 |
duplicates vanish | a heap, multiset or nth_element |
lists[i][0] for every list |
Runtime Error (SIGSEGV) |
an empty list has no [0] |
if (!lists[i].empty()) |
| find max + erase k times | Time Limit Exceeded | O(n · k) | a heap of size k |
pq.top() on an empty heap |
undefined behaviour | nothing to read | check pq.empty() |
priority_queue<int, greater<int>> |
compile error | the 2nd argument must be the container | priority_queue<int, vector<int>, greater<int>> |
The last one, for example priority_queue<int, greater<int>> pq; on line 6, gives:
main.cpp: In function 'int main()':
main.cpp:6:36: error: no type named 'value_type' in 'struct std::greater<int>'
6 | priority_queue<int, greater<int>> pq;
| ^~
main.cpp:6:36: error: template argument 3 is invalid
main.cpp:7:8: error: request for member 'push' in 'pq', which is of non-class type 'int'
7 | pq.push(3);
| ^~~~
Your turn: sort a nearly sorted array (solution)
Problem. Every value is at most k places from its sorted position. Sort it in O(n log k). 6 5 3 2 8 10 9, k = 3 → 2 3 5 6 8 9 10.
Idea. The smallest remaining value is always among the next k + 1 values. Keep a min-heap of k + 1 values: push the next one, and once the heap has k + 1 values, pop the top into the answer.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
if ((int)pq.size() > k) { cout << pq.top() << " "; pq.pop(); }
}
while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
cout << "\n";
return 0;
}
Input 7 3 / 6 5 3 2 8 10 9:
2 3 5 6 8 9 10
Practice questions (with solutions)
1. The k most frequent numbers.
Solution
Count with a map, then keep a min-heap of {count, value} of size k.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_map<int, int> cnt;
for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // {count, value}
for (auto [value, c] : cnt) {
pq.push({c, value});
if ((int)pq.size() > k) pq.pop();
}
while (!pq.empty()) {
cout << pq.top().second << " (x" << pq.top().first << ")\n";
pq.pop();
}
return 0;
}
Input 9 2 / 1 1 1 2 2 3 3 3 3:
1 (x3)
3 (x4)
2. The k closest points to the origin.
Solution
A max-heap of {distance², x, y} of size k: the farthest kept point is on top and is thrown out first. Compare squared distances to stay in integers.
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<tuple<long long, int, int>> pq; // max-heap by distance²
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
pq.push({1LL * x * x + 1LL * y * y, x, y});
if ((int)pq.size() > k) pq.pop();
}
while (!pq.empty()) {
auto [d, x, y] = pq.top();
pq.pop();
cout << "(" << x << ", " << y << ") d2 = " << d << "\n";
}
return 0;
}
Input 4 2 / 3 3 5 -1 -2 4 1 1:
(3, 3) d2 = 18
(1, 1) d2 = 2
3. Running median with two heaps.
Solution
A max-heap low holds the smaller half, a min-heap high the larger half; keep their sizes equal or low one bigger. The median is low.top() (odd count) or the average of both tops.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
priority_queue<int> low; // smaller half
priority_queue<int, vector<int>, greater<int>> high; // larger half
int x;
while (cin >> x) {
if (low.empty() || x <= low.top()) low.push(x); else high.push(x);
if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); }
else if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
if (low.size() > high.size()) cout << low.top() << " ";
else cout << (low.top() + high.top()) / 2.0 << " ";
}
cout << "\n";
return 0;
}
Input 5 15 1 3 8:
5 10 5 4 5
Mini project: a hospital emergency queue
Patients arrive with a severity (higher = more urgent); next calls the most urgent, and among equal severity the one who came first. A heap of {severity, -arrival} does both.
#include <iostream>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
int main() {
priority_queue<tuple<int, int, string>> er; // {severity, -arrival order, name}
string cmd;
int arrival = 0;
while (cin >> cmd) {
if (cmd == "arrive") {
string name;
int severity;
cin >> name >> severity;
er.push({severity, -arrival, name});
arrival++;
} else if (er.empty()) {
cout << "nobody waiting\n";
} else {
auto [sev, order, name] = er.top();
er.pop();
cout << "now seeing " << name << " (severity " << sev << ")\n";
}
}
return 0;
}
now seeing Meena (severity 5)
now seeing Arjun (severity 5)
now seeing Ravi (severity 2)
now seeing Kavya (severity 1)
nobody waiting
Meena and Arjun both have severity 5; Meena arrived first, so -arrival is larger for her and she is seen first.
Quick quiz
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : {8, 3, 9, 1, 6}) {
pq.push(x);
if (pq.size() > 2) pq.pop();
}
cout << pq.top() << " " << pq.size() << "\n";
return 0;
}
(A) 8 2 (B) 1 2 (C) 9 2 (D) 3 2
Answer
(A) 8 2. A min-heap of size 2 keeps the 2 largest values (9 and 8); every pop() threw out the smallest. The top is the smaller of the two, 8.
8 2
Interview questions
- What is a heap? A complete binary tree where every parent is ≥ (max-heap) or ≤ (min-heap) its children, usually stored in an array.
- Costs of
priority_queue?push/popO(log n),topO(1); building a heap from n values withmake_heapis O(n). - How do you make a min-heap in C++?
priority_queue<int, vector<int>, greater<int>>, or push negated values into a max-heap. - k largest: min-heap or max-heap? A min-heap of size k: its top is the weakest kept value, the one to throw out.
- Why O(n log k) and not O(n log n)? The heap never holds more than k + 1 values.
- k-th smallest without a heap?
nth_element, O(n) on average (quickselect). - Why does a
setgive the wrong k-th smallest? It removes duplicates; use a heap, amultiset, ornth_element. - How do you merge k sorted lists? A min-heap of the k fronts
{value, list, index}: pop the smallest, push the next from that list. O(N log k). - What does
greater<>compare for a tuple? The first element, then the second on a tie, and so on. - Can you change or remove a value in the middle of a
priority_queue? No; use aset/multiset, or "lazy deletion" (skip stale entries when they reach the top).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Heap | A tree kept so the best value is always at the root | the largest at the top |
| Max-heap / min-heap | Top is the largest / the smallest | priority_queue<int> / greater<int> |
priority_queue |
The C++ heap container adaptor, from <queue> |
pq.push(5); pq.top(); |
| Comparator | The rule that decides the order | greater<int> |
greater<int> |
A comparator meaning "a > b", which turns the heap into a min-heap | priority_queue<int, vector<int>, greater<int>> |
| Binary tree | A tree where each node has at most two children | root 12, children 5 and 11 |
| k largest | The k biggest values | 5 11 12 from 3 1 5 12 2 11 |
| k-th smallest | The value at position k in sorted order, duplicates counted | 4 in 3 4 4 7 … |
set |
A sorted container of unique values | {3, 4, 7} |
multiset |
A sorted container that keeps duplicates | {3, 4, 4, 7} |
nth_element |
Puts the k-th value in its sorted place in O(n) average | nth_element(b, b + k - 1, e) |
tuple |
Several values grouped into one | {value, list, index} |
| Structured binding | Unpacking a pair or tuple into named variables (C++17) | auto [val, li, idx] = pq.top(); |
| Merge k sorted lists | Combine k sorted lists into one sorted list | 1 4 7 + 2 5 8 → 1 2 4 5 7 8 |
| O(n log k) | n steps, each costing log k | a heap of size k |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | O(n · k) for a million numbers |
Summary
priority_queue<int>is a max-heap;greater<int>makes a min-heap.push/popO(log n),topO(1).- k largest: a min-heap of size k (throw out the weakest). O(n log k).
- k-th smallest: a max-heap of size k,
top()at the end; duplicates count, so not aset. Ornth_element. - Merge k sorted vectors: a min-heap of
{value, list, index}; push only non-empty lists. O(N log k).
Next episode: Matrix questions: transpose and rotate a matrix by 90° in place, print it in spiral order, and search a row- and column-sorted matrix with the staircase method.