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

20 Interview idioms / Checkpoint

Final checkpoint — Interview idioms

30 min · +25 XP · 3 exercises · 15 questions

Exercises0/3
Quiz · 70% to clear15 q

The last checkpoint of the C++ plan. It covers the contest template and its costs, the STL idiom sheet, the pitfalls review pass, Vec<T> and the hash map by hand, clean-solution habits and the theory drill — and, being the last one, it reaches back across the whole track.

How it works. Fifteen questions and three programs; 70% on the questions and every program accepted clears the module. With every other module complete, that also completes the plan.

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

  • What 1LL * a * b fixes that (long long)(a * b) does not, and why -7 % 3 is -1.
  • Why i < v.size() - 1 runs on an empty vector, and what map[key] does inside a condition.
  • The rule of five in one sentence, and why a hand-written destructor silently loses the moves.
  • Why push_back is amortised O(1), and what a reallocation invalidates.
  • What Base b = derived; keeps, and why deleting through a base pointer needs a virtual destructor.
  • Which container gives an O(1) splice, and what std::endl does that '\n' does not.

The three programs are the classics interviewers set: an LRU cache from std::list and std::unordered_map, a shunting-yard evaluator with two stacks, and a polymorphic shape store behind std::unique_ptr.

Common questions

How do you implement an LRU cache in C++?

Combine a std::list of key–value pairs, ordered from most to least recently used, with a std::unordered_map from each key to its list iterator. A hit moves the node to the front with splice in O(1) without invalidating any iterator; an insert past capacity evicts the back node and erases its key from the map.

Why does a hand-written destructor lose the move operations?

A user-declared destructor, copy constructor or copy assignment suppresses the implicitly generated move constructor and move assignment, so the class falls back to copying wherever it could have moved. Declare the moves explicitly — the rule of five — or write none of the five and let the members manage themselves.

What does Base b = derived; keep?

Only the Base part: the derived members and the dynamic type are sliced off, and virtual calls on b run the base versions. Store polymorphic objects by reference, pointer or std::unique_ptr<Base> instead, and give the base a virtual destructor so deleting through a Base* destroys the whole object.

AI InterviewGet started

C++ Interview Quiz: LRU Cache, Pitfalls and Theory Practice

The final C++ practice test: 15 questions and three classic interview programs — an LRU cache, a shunting-yard evaluator and a polymorphic shape store.

  • Course: C++ study plan
  • Module: Interview idioms
  • Kind: Checkpoint — cleared at 70%
  • Reading time: 30 min
  • Runtime: Clang 18 · C++20

Final checkpoint — Interview idioms is the checkpoint that closes the Interview idioms module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

The last checkpoint of the C++ plan. It covers the contest template and its costs, the STL idiom sheet, the pitfalls review pass, Vec<T> and the hash map by hand, clean-solution habits and the theory drill — and, being the last one, it reaches back across the whole track.

How it works. Fifteen questions and three programs; 70% on the questions and every program accepted clears the module. With every other module complete, that also completes the plan.

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

  • What 1LL * a * b fixes that (long long)(a * b) does not, and why -7 % 3 is -1.
  • Why i < v.size() - 1 runs on an empty vector, and what map[key] does inside a condition.
  • The rule of five in one sentence, and why a hand-written destructor silently loses the moves.
  • Why push_back is amortised O(1), and what a reallocation invalidates.
  • What Base b = derived; keeps, and why deleting through a base pointer needs a virtual destructor.
  • Which container gives an O(1) splice, and what std::endl does that '\n' does not.

The three programs are the classics interviewers set: an LRU cache from std::list and std::unordered_map, a shunting-yard evaluator with two stacks, and a polymorphic shape store behind std::unique_ptr.

Common questions

How do you implement an LRU cache in C++?

Combine a std::list of key–value pairs, ordered from most to least recently used, with a std::unordered_map from each key to its list iterator. A hit moves the node to the front with splice in O(1) without invalidating any iterator; an insert past capacity evicts the back node and erases its key from the map.

Why does a hand-written destructor lose the move operations?

A user-declared destructor, copy constructor or copy assignment suppresses the implicitly generated move constructor and move assignment, so the class falls back to copying wherever it could have moved. Declare the moves explicitly — the rule of five — or write none of the five and let the members manage themselves.

What does Base b = derived; keep?

Only the Base part: the derived members and the dynamic type are sliced off, and virtual calls on b run the base versions. Store polymorphic objects by reference, pointer or std::unique_ptr<Base> instead, and give the base a virtual destructor so deleting through a Base* destroys the whole object.

Exercises

An LRU cache

Implement a least-recently-used cache with O(1) get and put from a std::list<std::pair<int, int>> in recency order (front = most recent) and a std::unordered_map<int, std::list<...>::iterator> from key to node. A get on a present key moves its node to the front with splice; a put on a present key updates the value and moves it to the front; a put of a new key into a full cache first evicts the node at the back.

Read the capacity C (C ≥ 1), then n, then n commands get <key> or put <key> <value>. For each get print hit <value> or miss. After all commands print hits=<h> misses=<m> and cache=<keys most recent first, space-separated> (or cache=empty).

2
7
put 1 1
put 2 2
get 1
put 3 3
get 2
get 3
get 1

prints

hit 1
miss
hit 3
hit 1
hits=3 misses=1
cache=1 3

A shunting-yard evaluator

Read lines until the end of input; each is an arithmetic expression over non-negative integer literals with + - * / %, parentheses and optional spaces (the input is always well-formed; there is no unary minus). Evaluate it in long long with the shunting-yard two-stack method — a value stack and an operator stack; * / % bind tighter than + -, every operator is left-associative, and an operator is applied whenever the one on top of the stack has precedence at least as high as the incoming one. Division truncates toward zero. Print the value, or error if a division or modulo by zero occurs anywhere in the expression.

1 + 2 * 3
(1 + 2) * 3
10 / 3

prints

7
9
3

Shapes behind unique_ptr

Write an abstract Shape with a virtual destructor and pure virtual name(), area() and perimeter(); derive Circle(r), Rect(w, h) and Square(s) (mark the leaves final and every override override). Keep them in a std::vector<std::unique_ptr<Shape>> and run n commands:

  • circle r, rect w h, square s — add a shape (dimensions are decimals)
  • list — one line per shape, <index>: <name> area=<a> perimeter=<p>
  • total — total area=<sum of areas>
  • largest — largest=<name> <area> for the largest area (earliest on a tie), or largest=none
  • remove i — erase the shape at index i, or print no such shape

Use std::numbers::pi and print every number with exactly two decimals.

5
circle 1
rect 2 3
square 2
list
total

prints

0: circle area=3.14 perimeter=6.28
1: rect area=6.00 perimeter=10.00
2: square area=4.00 perimeter=8.00
total area=13.14

In this module: Interview idioms

← The C++ theory drill — thirty questions, thirty answers