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

Interview round

LRU cache (list + unordered_map)top k frequent words (tie-break)a mini inventory system with classes and the STL

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).
  • erase and insert at 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, then pop_back(). Forgetting the map leaves an iterator to a freed node (a dangling iterator).
  • Cost: get and put are O(1) on average; space O(capacity).
  • A capacity of 0 should make put do nothing; with this code, put on a 0-capacity cache would pop_back an empty list (undefined behaviour). Add if (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_map hands out its entries in no fixed order (it depends on hashes and bucket count).
  • std::sort is 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() handles k bigger 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 in sort.
  • 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-initialised Item{0, 0} and returns a reference to it. Reading or subtracting through operator[] therefore creates entries. (operator[] also doesn't exist on a const 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

  1. What is an LRU cache? A fixed-size cache that, when full, evicts the least recently used entry.
  2. How do you make get and put O(1)? A hash map from key to a node of a doubly linked list ordered by recency; move nodes with splice.
  3. 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.
  4. What does list::splice do? Moves nodes from one position (or list) to another by relinking pointers: no copying, O(1) for one node, iterators stay valid.
  5. LRU vs LFU? LRU evicts the least recently used; LFU the least frequently used (with recency as a tie-break).
  6. Is std::sort stable? No; use std::stable_sort to keep the original order of equal elements, or add a tie-break to the comparator.
  7. What is a strict weak ordering? The rule a comparator must follow: irreflexive (comp(a, a) is false), and consistent and transitive.
  8. Top k in O(n log k)? A min-heap (worst on top) of size k; pop whenever it exceeds k.
  9. map vs unordered_map? map: sorted, O(log n), a balanced tree. unordered_map: unsorted, O(1) average, a hash table.
  10. Why does map::operator[] insert? It must return a reference to a value; for a missing key it creates one, value-initialised.
  11. How do you read a map without inserting? find, count, at (throws std::out_of_range), or C++20 contains.
  12. Why return bool from sell? The caller learns whether the operation happened, without exceptions; for unexpected errors, throw an exception instead.
  13. 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: list for the order (most recent first) + unordered_map from key to list iterator; splice to 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::sort is not stable and unordered_map has no order); O(n + u log u), or O(u log k) with a heap.
  • Inventory: map::operator[] inserts missing keys: read with find() / at(), check before you change, return bool.

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.