AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

13 STL containers / Checkpoint

Checkpoint — STL containers

25 min · +25 XP · 3 exercises · 14 questions

Exercises0/3
Quiz · 70% to clear14 q

This checkpoint covers the whole module: the container families and the complexity table, std::vector's size–capacity model and the erase–remove idiom, std::deque, std::list and the adaptors, std::map/std::set with lower_bound, the unordered containers and the sort-before-printing rule, and iterators with the invalidation table.

How it works. Thirteen questions and three programs. You need 70% on the questions and every program accepted to clear the module. You can retake it as often as you like; your best score counts.

Before you start, make sure you can answer these from memory:

  • Which operation is O(1) on a std::list but O(n) on a std::vector, and what must you already hold for it to be O(1)?
  • What does push_back do to every iterator into a vector when size() == capacity()?
  • Why does std::stack::pop() return void?
  • When does a std::priority_queue comparator return true?
  • What does m[key] do when key is absent, and which calls look up without inserting?
  • Why must an std::unordered_map be sorted before it is printed?
  • What is the one correct shape of an erase-while-iterating loop?

The three programs are a breadth-first search over a grid with std::queue, an LRU cache built from a std::list and an std::unordered_map of iterators, and a leaderboard kept in a std::map and a std::set with a custom comparator.

Common questions

What does push_back do to iterators when size() == capacity()?

It reallocates: the vector allocates a larger block, moves or copies every element into it and frees the old one, so every iterator, pointer and reference into the vector is invalidated. Reserve capacity in advance or keep indices instead.

What does m[key] do when the key is absent?

It inserts the key with a value-initialised value — 0 for numbers, an empty string — and returns a reference to it. To look up without inserting, use find, count, contains or at.

When does a std::priority_queue comparator return true?

When its first argument has lower priority than its second, meaning it should come out later. That is why the default std::less gives a max-heap with the largest element on top, and std::greater gives a min-heap.

AI InterviewGet started

C++ STL Containers Quiz: Vector, Map and Iterators Practice

Test your C++ STL containers knowledge: 13 questions and three programs — a BFS grid walk, an LRU cache from a list and a hash map, and a map leaderboard.

  • Course: C++ study plan
  • Module: STL containers
  • Kind: Checkpoint — cleared at 70%
  • Reading time: 25 min
  • Runtime: Clang 18 · C++20

Checkpoint — STL containers is the checkpoint that closes the STL containers module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

This checkpoint covers the whole module: the container families and the complexity table, std::vector's size–capacity model and the erase–remove idiom, std::deque, std::list and the adaptors, std::map/std::set with lower_bound, the unordered containers and the sort-before-printing rule, and iterators with the invalidation table.

How it works. Thirteen questions and three programs. You need 70% on the questions and every program accepted to clear the module. You can retake it as often as you like; your best score counts.

Before you start, make sure you can answer these from memory:

  • Which operation is O(1) on a std::list but O(n) on a std::vector, and what must you already hold for it to be O(1)?
  • What does push_back do to every iterator into a vector when size() == capacity()?
  • Why does std::stack::pop() return void?
  • When does a std::priority_queue comparator return true?
  • What does m[key] do when key is absent, and which calls look up without inserting?
  • Why must an std::unordered_map be sorted before it is printed?
  • What is the one correct shape of an erase-while-iterating loop?

The three programs are a breadth-first search over a grid with std::queue, an LRU cache built from a std::list and an std::unordered_map of iterators, and a leaderboard kept in a std::map and a std::set with a custom comparator.

Common questions

What does push_back do to iterators when size() == capacity()?

It reallocates: the vector allocates a larger block, moves or copies every element into it and frees the old one, so every iterator, pointer and reference into the vector is invalidated. Reserve capacity in advance or keep indices instead.

What does m[key] do when the key is absent?

It inserts the key with a value-initialised value — 0 for numbers, an empty string — and returns a reference to it. To look up without inserting, use find, count, contains or at.

When does a std::priority_queue comparator return true?

When its first argument has lower priority than its second, meaning it should come out later. That is why the default std::less gives a max-heap with the largest element on top, and std::greater gives a min-heap.

Exercises

Shortest path on a grid with std::queue

Read R C, then R rows of C characters: . open, # wall, S the start and E the exit (each appears exactly once). Print the length of the shortest path from S to E moving up, down, left or right through open cells, or -1 when the exit cannot be reached.

Use breadth-first search with a std::queue of cells and a std::vector<std::vector<int>> of distances initialised to -1, which doubles as the visited set — mark a cell when it is pushed.

Input: R C, then R rows. Output: one integer.

3 4
S..#
.#..
...E

prints 5.

LRU cache from a std::list and an std::unordered_map

Implement a least-recently-used cache. Read its capacity (at least 1), then commands until the end of input: get <key> prints hit <value> and marks the key most recently used, or miss; put <key> <value> inserts or updates the key and marks it most recently used, and when that pushes the size past the capacity it evicts the least recently used key and prints evict <key>. After the last command print cache: followed by every <key>=<value> from most to least recently used.

Keys and values are integers. The recency order lives in a std::list<std::pair<int, int>> (most recent at the front); a std::unordered_map<int, std::list<…>::iterator> finds a key's node in O(1). Moving a node to the front is one splice, and list iterators stay valid across it — which is why the map may hold them. The final line comes from the list, never from the map.

Input: the capacity, then commands. Output: one line per get and per eviction, then the cache: line.

2
put 1 10
put 2 20
get 1
put 3 30
get 2
get 3
put 1 11

prints

hit 10
evict 2
miss
hit 30
cache: 1=11 3=30

Leaderboard on a std::set with a custom order

Keep a leaderboard. Commands arrive one per line until the end of input:

  • set <name> <score> — add the player or replace their score;
  • remove <name> — remove the player, or print remove <name>=unknown;
  • rank <name> — print rank <name>=<r>, the player's 1-based position, or rank <name>=unknown;
  • top <k> — print top: followed by the first k players as <name>(<score>), space-separated (fewer if there are fewer players);
  • above <s> — print above <s>: <count>, the number of players whose score is strictly greater than s.

The order is highest score first, ties by name ascending. Use two containers: a std::map<std::string, int> from name to score, and a std::set<Entry, Comparator> of {score, name} structs ordered by a comparator struct. Updating a score means erasing the old entry from the set and inserting the new one. above is std::distance(board.begin(), board.lower_bound({s, ""})) — with this ordering the key {s, ""} sorts before every real entry that has score s.

Input: commands until end of input. Output: one line per rank, top, above or failed remove.

set ada 50
set bob 70
set cy 50
top 2
rank cy
set ada 90
rank ada
above 50
remove bob
top 5
rank bob

prints

top: bob(70) ada(50)
rank cy=3
rank ada=1
above 50: 2
top: ada(90) cy(50)
rank bob=unknown

In this module: STL containers

← Iterators and invalidation — the contract behind every loop · The algorithm library — ranges, predicates and the first dozen calls →