These are the notes for C++ Coding Questions, episode 30, the last episode of the series and its interview round. In a real interview the questions get bigger: you design a small class, choose the right STL containers, and prove it works on the edge cases. Today: an LRU cache in O(1) with list + unordered_map, the top k frequent words with a tie-break, and a mini inventory system where map::operator[] quietly invents items.
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 cost.
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. Timings (ms) change from machine to machine and run to run.
Real-life pictures
| In real life | In C++ |
|---|---|
| A phone that keeps only 2 apps open in the background | a cache with a capacity |
| Reopening maps moves it to the front | get makes a key the most recently used |
| Opening the camera closes the app used least recently | LRU eviction |
| A chai stall's order book: the two most ordered snacks | count with unordered_map, sort, take k |
| Two helpers giving two answers for a tie | std::sort with no tie-break: any order |
| "More orders first, then A to Z" | a comparator with a tie-break |
| A new clerk writing a fresh line "paneer roll -2" | map::operator[] inserts a missing key |
| Checking the register before writing | find(), then check the stock |
Q1: LRU cache
Problem. Design a cache with a fixed capacity. get(key) returns the value or -1, and makes the key the most recently used. put(key, value) adds or updates a key; when the cache is full, it first evicts the least recently used (LRU) key. Both must be O(1).
LRUCache c(2); put(1,1) put(2,2) get(1) → 1
put(3,3) → evicts 2 get(2) → -1
put(4,4) → evicts 1 get(1) → -1 get(3) → 3 get(4) → 4
A cache is a small, fast store that keeps recent answers so they don't have to be fetched or computed again: CPU caches, browser caches, database buffer pools, and CDNs all evict this way.
The obvious attempt: one vector, most recent first
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
class SlowLRU { // front = most recently used
int cap;
vector<pair<int, int>> items; // (key, value)
public:
SlowLRU(int c) : cap(c) {}
int get(int key) {
for (size_t i = 0; i < items.size(); i++) // search: O(n)
if (items[i].first == key) {
auto kv = items[i];
items.erase(items.begin() + i); // shift: O(n)
items.insert(items.begin(), kv);
return kv.second;
}
return -1;
}
void put(int key, int value) {
if (get(key) != -1) { items[0].second = value; return; }
if ((int)items.size() == cap) items.pop_back(); // drop the oldest
items.insert(items.begin(), {key, value});
}
};
int main() {
SlowLRU c(2);
c.put(1, 1); c.put(2, 2);
cout << c.get(1) << " "; // 1
c.put(3, 3); // evicts 2
cout << c.get(2) << " "; // -1
c.put(4, 4); // evicts 1
cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n";
auto t0 = chrono::steady_clock::now();
SlowLRU big(30000);
for (int i = 0; i < 60000; i++) { big.put(i, i); big.get(i / 2); }
auto t1 = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(t1 - t0);
cout << "60000 puts and gets: " << ms.count() << " ms\n";
return 0;
}
Real output (one run):
1 -1 -1 3 4
60000 puts and gets: 1189 ms
Correct answers, but over a second for 60,000 operations.
Why
- Finding a key walks the vector: O(n).
eraseandinsertat the front shift every element after the position: O(n).
So each get / put is O(n), and n operations cost O(n²).
The fix: list for the order, unordered_map to find
| Container | Job | Cost |
|---|---|---|
list<pair<int, int>> |
the keys in order of use, most recent at the front | push/pop at either end O(1) |
unordered_map<int, list::iterator> |
key → its node in the list | find O(1) on average |
list::splice |
move one node to the front without copying | O(1) |
std::list is a doubly linked list: each node points to the one before and after. Moving or erasing a node never moves the other nodes, so the iterators (pointers to nodes) stored in the map stay valid.
#include <iostream>
#include <list>
#include <unordered_map>
#include <chrono>
using namespace std;
class LRUCache {
using Node = list<pair<int, int>>::iterator;
int cap;
list<pair<int, int>> order; // front = most recent
unordered_map<int, Node> where; // key -> its list node
public:
LRUCache(int c) : cap(c) {}
int get(int key) {
auto it = where.find(key);
if (it == where.end()) return -1;
order.splice(order.begin(), order, it->second); // to front: O(1)
return it->second->second;
}
void put(int key, int value) {
if (get(key) != -1) { order.front().second = value; return; }
if ((int)order.size() == cap) { // evict the oldest
where.erase(order.back().first);
order.pop_back();
}
order.push_front({key, value});
where[key] = order.begin();
}
};
int main() {
LRUCache c(2);
c.put(1, 1); c.put(2, 2);
cout << c.get(1) << " "; // 1
c.put(3, 3); // evicts 2
cout << c.get(2) << " "; // -1
c.put(4, 4); // evicts 1
cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n";
auto t0 = chrono::steady_clock::now();
LRUCache big(30000);
for (int i = 0; i < 60000; i++) { big.put(i, i); big.get(i / 2); }
auto t1 = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(t1 - t0);
cout << "60000 puts and gets: " << ms.count() << " ms\n";
return 0;
}
Real output (one run):
1 -1 -1 3 4
60000 puts and gets: 3 ms
order.splice(order.begin(), order, it->second)relinks that node at the front.- Eviction:
order.back()is the least recently used; erase its key from the map first, thenpop_back(). Forgetting the map leaves an iterator to a freed node (a dangling iterator). - Cost:
getandputare O(1) on average; space O(capacity). - A capacity of 0 should make
putdo nothing; with this code,puton a 0-capacity cache wouldpop_backan empty list (undefined behaviour). Addif (cap == 0) return;when that case is allowed.
Q2: Top k frequent words
Problem. Given a text and k, return the k most frequent words; equal counts in alphabetical order.
"vada chai samosa chai pav vada samosa dosa"
k = 2 → chai samosa (chai 2, samosa 2, vada 2, dosa 1, pav 1)
k = 4 → chai samosa vada dosa
k = 10 → all 5 words
"" → nothing
Plan. Count with unordered_map<string, int>; copy the pairs into a vector; sort with a comparator (a function that says whether a comes before b); take the first k. Read words with a stringstream: ss >> w skips spaces.
The obvious attempt: sort by count only
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<string> topK(const string& text, int k) {
unordered_map<string, int> freq;
stringstream ss(text);
string w;
while (ss >> w) freq[w]++; // count every word
vector<pair<string, int>> v(freq.begin(), freq.end());
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
return a.second > b.second; // most frequent first
});
vector<string> out;
for (int i = 0; i < k && i < (int)v.size(); i++)
out.push_back(v[i].first);
return out;
}
int main() {
string orders = "vada chai samosa chai pav vada samosa dosa";
for (const string& w : topK(orders, 2)) cout << w << " ";
cout << " <- expected: chai samosa\n";
return 0;
}
Real output:
samosa chai <- expected: chai samosa
Why
- An
unordered_maphands out its entries in no fixed order (it depends on hashes and bucket count). std::sortis not stable: elements that compare equal can come out in any order.- The comparator only compared counts, so the three-way tie at 2 was left to chance.
The fix: a comparator with a tie-break
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<string> topK(const string& text, int k) {
unordered_map<string, int> freq;
stringstream ss(text);
string w;
while (ss >> w) freq[w]++; // count every word
vector<pair<string, int>> v(freq.begin(), freq.end());
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first; // tie: A to Z
});
vector<string> out;
for (int i = 0; i < k && i < (int)v.size(); i++)
out.push_back(v[i].first);
return out;
}
void test(const string& text, int k) {
cout << "k = " << k << ": ";
for (const string& w : topK(text, k)) cout << w << " ";
cout << "\n";
}
int main() {
string orders = "vada chai samosa chai pav vada samosa dosa";
test(orders, 2);
test(orders, 4);
test(orders, 10);
test("", 3);
return 0;
}
Real output:
k = 2: chai samosa
k = 4: chai samosa vada dosa
k = 10: chai samosa vada dosa pav
k = 3:
i < k && i < (int)v.size()handleskbigger than the number of distinct words.- A comparator must be a strict weak ordering:
comp(a, a)must be false (use>/<, never>=). A comparator that returns true for equal elements is undefined behaviour insort. - Cost: O(n) to count n words + O(u log u) to sort the u distinct words; O(u) space. With a heap of size k: O(u log k) (see the practice questions).
Q3: A mini inventory system
Problem. Design struct Item { price, qty } and class Inventory (a map<string, Item>) with add, sell and report. Selling an unknown item, or more than the stock, must be refused. The report lists items A to Z, marks low stock (< 10) and prints the total stock value.
A std::map keeps its keys sorted (a balanced binary search tree), so the report is A to Z for free.
The obvious attempt
#include <iostream>
#include <map>
#include <string>
using namespace std;
struct Item {
int price = 0; // rupees
int qty = 0;
};
class Inventory {
map<string, Item> items; // sorted by name
public:
void add(const string& name, int price, int qty) {
items[name].price = price; // adding may create it
items[name].qty += qty;
}
void sell(const string& name, int qty) {
items[name].qty -= qty; // take it off the shelf
}
void report() const {
int value = 0;
for (const auto& [name, it] : items) {
cout << name << ": " << it.qty << " left";
if (it.qty < 10) cout << " (low!)";
cout << "\n";
value += it.price * it.qty;
}
cout << "stock value: Rs " << value << "\n";
}
};
int main() {
Inventory shop;
shop.add("samosa", 15, 40);
shop.add("chai", 10, 100);
shop.sell("samosa", 43); // more than we have
shop.sell("paneer roll", 2); // not on the menu
shop.report();
return 0;
}
Real output:
chai: 100 left
paneer roll: -2 left (low!)
samosa: -3 left (low!)
stock value: Rs 955
A phantom item, negative stock, and a wrong value (1000 − 45 = 955). No error, no warning.
Why
items[name]on a missing key inserts a new, value-initialisedItem{0, 0}and returns a reference to it. Reading or subtracting throughoperator[]therefore creates entries. (operator[]also doesn't exist on aconst map, for exactly this reason.)- Nothing checked the quantity before subtracting.
The fix: find() never inserts; check, then change
#include <iostream>
#include <map>
#include <string>
using namespace std;
struct Item {
int price = 0; // rupees
int qty = 0;
};
class Inventory {
map<string, Item> items; // sorted by name
public:
void add(const string& name, int price, int qty) {
items[name].price = price; // adding may create it
items[name].qty += qty;
}
bool sell(const string& name, int qty) {
auto it = items.find(name); // find never inserts
if (it == items.end()) {
cout << "no such item: " << name << "\n";
return false;
}
if (it->second.qty < qty) {
cout << "only " << it->second.qty << " " << name << " left\n";
return false;
}
it->second.qty -= qty;
return true;
}
void report() const {
int value = 0;
for (const auto& [name, it] : items) {
cout << name << ": " << it.qty << " left";
if (it.qty < 10) cout << " (low!)";
cout << "\n";
value += it.price * it.qty;
}
cout << "stock value: Rs " << value << "\n";
}
};
int main() {
Inventory shop;
shop.add("samosa", 15, 40);
shop.add("chai", 10, 100);
shop.sell("samosa", 43); // more than we have
shop.sell("paneer roll", 2); // not on the menu
shop.sell("samosa", 35); // fine
shop.report();
return 0;
}
Real output:
only 40 samosa left
no such item: paneer roll
chai: 100 left
samosa: 5 left (low!)
stock value: Rs 1075
1075 = 100 × 10 (chai) + 5 × 15 (samosa). sell returns bool so the caller knows whether it worked. at(name) is another safe read: it throws std::out_of_range for a missing key instead of inserting.
Cost: add, sell, find are O(log n) in a map (O(1) average in an unordered_map, but then the report would need sorting); report is O(n).
Cost summary
| Question | Obvious attempt | Result | Fix | Time |
|---|---|---|---|---|
| LRU cache | vector, search + shift | 60000 ops: 1189 ms | list + unordered_map + splice |
O(1) per operation |
| Top k words | sort by count only | samosa chai |
comparator with a tie-break | O(n + u log u) |
| Inventory | items[name].qty -= qty |
phantom item, -3 stock | find(), check, then change |
O(log n) per sale |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
LRU cache in a vector |
correct, but 60000 operations take over a second | search and shift are O(n) | list + unordered_map + splice |
| erase from the list, forget the map | works at first, then a crash or garbage | the map points at a freed node | erase the key from the map, then pop_back |
| storing list values in the map, not iterators | can't find the node in O(1) | you'd search the list again | store list<...>::iterator |
| sort by count only | samosa chai |
ties come out in any order | if (a.second != b.second) ...; return a.first < b.first; |
comparator with >= |
undefined behaviour, can crash | not a strict weak ordering | > / < only |
items[name] to read or sell |
paneer roll: -2 left |
operator[] inserts missing keys |
find() or at() |
| no stock check | samosa: -3 left |
nothing refused the sale | check first; return bool |
Mini project
The episode's three answers already make one small system: an inventory (Q3) whose report could be cached (Q1) and whose sales feed a "top sellers" board (Q2). Build it by combining them; the your-turn solution below adds the sales counts you need.
Practice questions (with solutions)
1. Your turn: restock, best seller, low stock.
Solution
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int price = 0;
int qty = 0;
int sold = 0; // units sold so far
};
class Inventory {
map<string, Item> items;
public:
void add(const string& name, int price, int qty) {
items[name].price = price;
items[name].qty += qty;
}
bool restock(const string& name, int qty) {
auto it = items.find(name);
if (it == items.end()) { cout << "no such item: " << name << "\n"; return false; }
it->second.qty += qty;
return true;
}
bool sell(const string& name, int qty) {
auto it = items.find(name);
if (it == items.end() || it->second.qty < qty) return false;
it->second.qty -= qty;
it->second.sold += qty;
return true;
}
string bestSeller() const {
string best;
int most = -1;
for (const auto& [name, it] : items) // map: A to Z already
if (it.sold > most) { most = it.sold; best = name; } // > keeps the first on ties
return best;
}
vector<string> lowStock(int limit) const {
vector<pair<int, string>> low;
for (const auto& [name, it] : items)
if (it.qty < limit) low.push_back({it.qty, name});
sort(low.begin(), low.end()); // fewest first, then A to Z
vector<string> out;
for (const auto& p : low) out.push_back(p.second);
return out;
}
};
int main() {
Inventory shop;
shop.add("samosa", 15, 40);
shop.add("chai", 10, 100);
shop.add("vada", 12, 30);
shop.restock("paneer roll", 5);
shop.sell("samosa", 35);
shop.sell("vada", 25);
shop.sell("chai", 35);
shop.restock("samosa", 2);
cout << "best seller: " << shop.bestSeller() << "\n";
cout << "low stock:";
for (const string& n : shop.lowStock(10)) cout << " " << n;
cout << "\n";
return 0;
}
Real output:
no such item: paneer roll
best seller: chai
low stock: vada samosa
Chai and samosa both sold 35; the map visits names A to Z, and > keeps the first one, so ties go A to Z. lowStock sorts (qty, name) pairs: fewest first, then A to Z.
2. Top k words with a priority_queue of size k: O(u log k).
Solution
Keep a heap of at most k entries whose top is the worst kept so far; push each word and pop when the heap grows past k.
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<string> topK(const string& text, int k) {
unordered_map<string, int> freq;
stringstream ss(text);
string w;
while (ss >> w) freq[w]++;
// "a is better than b": more orders, or equal and earlier A to Z
auto better = [](const pair<int, string>& a, const pair<int, string>& b) {
return a.first != b.first ? a.first > b.first : a.second < b.second;
};
// a heap whose top is the WORST of the k kept so far
priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(better)> heap(better);
for (const auto& [word, count] : freq) {
heap.push({count, word});
if ((int)heap.size() > k) heap.pop(); // drop the worst: O(log k)
}
vector<string> out;
while (!heap.empty()) { out.push_back(heap.top().second); heap.pop(); }
reverse(out.begin(), out.end()); // best first
return out;
}
int main() {
string orders = "vada chai samosa chai pav vada samosa dosa";
for (int k : {2, 4}) {
for (const string& w : topK(orders, k)) cout << w << " ";
cout << "\n";
}
return 0;
}
Real output:
chai samosa
chai samosa vada dosa
3. Undo the last sale with a stack.
Solution
A stack is last in, first out: the newest sale is on top, so undo pops it and puts the stock back.
#include <iostream>
#include <map>
#include <stack>
#include <string>
using namespace std;
int main() {
map<string, int> stock = {{"chai", 100}, {"samosa", 40}};
stack<pair<string, int>> sales; // last sale on top
auto sell = [&](const string& name, int qty) {
auto it = stock.find(name);
if (it == stock.end() || it->second < qty) return false;
it->second -= qty;
sales.push({name, qty});
return true;
};
auto undo = [&]() {
if (sales.empty()) { cout << "nothing to undo\n"; return; }
auto [name, qty] = sales.top();
sales.pop();
stock[name] += qty; // the key exists: safe here
cout << "undid " << qty << " " << name << "\n";
};
sell("chai", 3);
sell("samosa", 5);
undo();
undo();
undo();
for (const auto& [name, qty] : stock) cout << name << ": " << qty << "\n";
return 0;
}
Real output:
undid 5 samosa
undid 3 chai
nothing to undo
chai: 100
samosa: 40
4. An LFU cache: evict the Least FREQUENTLY used key (ties: the least recently used).
Solution
Keep, for each use count, a list of keys (most recent first), plus the smallest count in use (minFreq). Every get/put moves the key from list f to list f + 1 in O(1).
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
class LFUCache {
struct Entry { int value, freq; list<int>::iterator pos; };
int cap, minFreq = 0;
unordered_map<int, Entry> entries; // key -> value, use count, place
unordered_map<int, list<int>> byFreq; // use count -> keys, most recent first
void touch(int key) { // one more use of key
Entry& e = entries[key];
byFreq[e.freq].erase(e.pos);
if (byFreq[e.freq].empty() && minFreq == e.freq) minFreq++;
e.freq++;
byFreq[e.freq].push_front(key);
e.pos = byFreq[e.freq].begin();
}
public:
LFUCache(int c) : cap(c) {}
int get(int key) {
if (!entries.count(key)) return -1;
touch(key);
return entries[key].value;
}
void put(int key, int value) {
if (cap == 0) return;
if (entries.count(key)) { entries[key].value = value; touch(key); return; }
if ((int)entries.size() == cap) { // evict: least uses, then least recent
int old = byFreq[minFreq].back();
byFreq[minFreq].pop_back();
entries.erase(old);
}
byFreq[1].push_front(key);
entries[key] = {value, 1, byFreq[1].begin()};
minFreq = 1;
}
};
int main() {
LFUCache c(2);
c.put(1, 1); c.put(2, 2);
cout << c.get(1) << " "; // 1 (key 1 used twice now)
c.put(3, 3); // evicts 2 (used once)
cout << c.get(2) << " " << c.get(3) << " "; // -1 3
c.put(4, 4); // 1 and 3 both used twice: evict the older use, 1
cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n"; // -1 3 4
return 0;
}
Real output:
1 -1 3 -1 3 4
Quick quiz
1. Which key is evicted? (the episode quiz)
LRUCache c(3);
c.put(1, 10); c.put(2, 20); c.put(3, 30);
c.get(1);
c.get(2);
c.put(4, 40); // which key is evicted?
(A) 1 (B) 2 (C) 3 (D) 4
Answer
(C) 3. After the puts the order (most → least recent) is 3, 2, 1; get(1) makes it 1, 3, 2; get(2) makes it 2, 1, 3. The cache is full, so put(4) evicts 3.
2. After map<string, int> m; if (m["x"] == 0) {}, what is m.size()?
Answer
1: m["x"] inserted "x" with value 0. Use m.count("x"), m.find("x") or (C++20) m.contains("x") to test without inserting.
3. Why does the LRU cache use list and not vector for the order?
Answer
A list moves or removes a node in O(1) (splice, erase) and never invalidates iterators to other nodes, so the map can keep iterators. A vector shifts elements (O(n)) and invalidates iterators when it does.
4. Is sort with return a.second >= b.second; correct?
Answer
No. A comparator must return false for equal elements (a strict weak ordering). >= breaks that, which is undefined behaviour and can read out of bounds.
Interview questions
- What is an LRU cache? A fixed-size cache that, when full, evicts the least recently used entry.
- How do you make
getandputO(1)? A hash map from key to a node of a doubly linked list ordered by recency; move nodes withsplice. - Why a doubly linked list? O(1) removal from the middle (it knows the node before), O(1) insert at the front and removal at the back.
- What does
list::splicedo? Moves nodes from one position (or list) to another by relinking pointers: no copying, O(1) for one node, iterators stay valid. - LRU vs LFU? LRU evicts the least recently used; LFU the least frequently used (with recency as a tie-break).
- Is
std::sortstable? No; usestd::stable_sortto keep the original order of equal elements, or add a tie-break to the comparator. - What is a strict weak ordering? The rule a comparator must follow: irreflexive (
comp(a, a)is false), and consistent and transitive. - Top k in O(n log k)? A min-heap (worst on top) of size k; pop whenever it exceeds k.
mapvsunordered_map?map: sorted, O(log n), a balanced tree.unordered_map: unsorted, O(1) average, a hash table.- Why does
map::operator[]insert? It must return a reference to a value; for a missing key it creates one, value-initialised. - How do you read a map without inserting?
find,count,at(throwsstd::out_of_range), or C++20contains. - Why return
boolfromsell? The caller learns whether the operation happened, without exceptions; for unexpected errors, throw an exception instead. - How would you make the inventory thread-safe? Guard every member function with a
std::mutex(lock_guard).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Cache | A small, fast store of recent answers | the recent apps screen |
| Capacity | The most entries the cache may hold | LRUCache c(2) |
| Eviction | Removing an entry to make room | put(3,3) evicts 2 |
| LRU | Least Recently Used: evict the entry used longest ago | the phone closes music |
| LFU | Least Frequently Used: evict the entry used fewest times | practice question 4 |
| STL | The C++ Standard Template Library: containers and algorithms | list, map, sort |
std::list |
A doubly linked list | list<pair<int, int>> |
| Doubly linked list | Nodes that point to the next and the previous node | O(1) remove anywhere |
| Iterator | An object that points to an element of a container | list<...>::iterator |
splice |
Moves list nodes by relinking, O(1) | order.splice(order.begin(), order, it) |
| Dangling iterator | An iterator to an element that was erased | forgetting to erase from the map |
unordered_map |
A hash table: key → value, O(1) average, no order | freq[w]++ |
map |
A sorted key → value tree, O(log n) | map<string, Item> |
| Hash table | Stores entries in buckets chosen by a hash of the key | unordered_map |
stringstream |
Reads words out of a string like cin |
ss >> w |
| Comparator | A function saying whether a comes before b | the sort lambda |
| Tie-break | The rule for ordering equal keys | A to Z |
| Stable sort | Keeps equal elements in their original order | stable_sort |
| Strict weak ordering | The rules a comparator must follow (comp(a, a) is false) |
use <, not <= |
| Priority queue / heap | A container that always gives the top element in O(1), push/pop O(log n) | priority_queue |
| Stack | Last in, first out | undo the last sale |
struct |
A class whose members are public by default | struct Item |
| Default member initialiser | A member's starting value written in the class | int qty = 0; |
operator[] (map) |
Access by key; inserts the key if missing | items[name] |
find |
Looks up a key without inserting; returns end() if missing |
items.find(name) |
at |
Access by key; throws std::out_of_range if missing |
items.at(name) |
| Structured binding | Unpacks a pair or struct into names | auto& [name, it] |
Summary
- LRU cache:
listfor the order (most recent first) +unordered_mapfrom key to list iterator;spliceto the front on every use; evict from the back and the map. O(1) per operation. A vector version was correct but O(n): 60,000 operations took over a second. - Top k frequent words: count with
unordered_map, sort with a comparator that breaks ties (std::sortis not stable andunordered_maphas no order); O(n + u log u), or O(u log k) with a heap. - Inventory:
map::operator[]inserts missing keys: read withfind()/at(), check before you change, returnbool.
This was the last episode of C++ Coding Questions: 30 episodes, 90 questions, from basics to the interview round. Go back to any episode and solve its questions again without watching; every solution is in these notes.