Module assignment: Cache and Lookup Service

What you will build

This assignment joins everything in the module into one program. You will write a small lookup service that reads a stream of commands from input and prints answers. The service keeps three kinds of state at once. It keeps an LRU cache of recent prices, so the newest entries stay and the oldest are evicted. It keeps a sorted multiset of all prices added, so it can count prices in a range and find the nearest price. It keeps a set of ids it has already seen, so it can tell a first visit from a repeat.

No single container does all three jobs well. The cache needs a hash map and a linked list. The range and nearest questions need a sorted container. The repeat check needs a hash set. Working out which container fits which job is the real exercise. Read the whole spec before you write any code, and then build the program in the order the hints suggest.

You may not add any library that is outside the C++ standard library. Use g++ -std=c++17, and read the input with cin.

The specification

The first line holds two integers. The first is c, the capacity of the LRU cache, with 1 <= c <= 100. The second is q, the number of commands that follow, with 1 <= q <= 1000.

After that come exactly q lines. Each line starts with one of six command words. The rest of the line holds that command's arguments. Every value is a whole number in the range 0 to 1000000000, except where the command says otherwise.

Three rules matter for the cache.

• A put for an id that is already cached updates its price and makes it the most recent entry. It does not evict anything.
• A put for a new id, when the cache already holds c entries, evicts the least recently used entry first. Then it stores the new one as most recent.
• A get that finds the id makes it the most recent entry. A get that misses prints -1 and changes nothing.

The -1 answer is safe because every stored price is between 0 and 1000000000. A real price is never negative, so -1 can only mean a miss.

The price list and the cache are separate. An add puts a price in the list, and that does not put anything in the cache. A put stores a price for an id in the cache, and that does not add the price to the list. The two never affect each other.

The once command has its own state. The set of seen ids starts empty and grows for the whole run. It is not cleared by evictions, and an id that was evicted from the cache still counts as seen.

Worked examples

The first example uses capacity 2 and eleven commands. Read it line by line, and check each answer against the rules above before you run your program.

2
11
add 40
add 15
add 40
count 10 40
nearest 16
nearest 41
once 7
once 7
put 7 99
put 8 15
get 7

The expected output is:

3
40
NONE
NEW
REPEAT
99

The count is 3, because the prices in the range from 10 to 40 are 15, 40 and 40. The nearest price at or above 16 is 40. Nothing is at or above 41, so the answer is NONE. The first once 7 prints NEW, and the second prints REPEAT. The two put lines fill the cache with ids 7 and 8, and the cache holds two entries. The get 7 finds the price 99, because id 7 was not evicted. The capacity of 2 was just enough to keep it.

The second example uses capacity 1, which makes every new id evict the only entry.

1
6
put 1 5
put 2 6
get 1
get 2
once 1
once 1

The expected output is:

-1
6
NEW
REPEAT

The put of id 2 evicts id 1, so get 1 misses and prints -1. The id 2 is still cached, so get 2 prints 6. The once lines are unrelated to the cache. Id 1 has never been seen by once, so the first call prints NEW, and the second prints REPEAT. This example checks that you keep the two kinds of memory separate.

Before you move on, write down the answer for one command of your own choosing, and check it against your program. Making your own small example is the fastest way to find a rule you have misread.

Starter code

The program below reads the header and the commands, and it prints nothing yet. It compiles, so you can build on it. Replace each TODO with the logic for that command. Keep reading the arguments for every command, even the ones you have not finished, so the input stays aligned.

To test the starter, type the first example into the Input box. It prints nothing, which is correct for a program that has not been built yet.

Requirements checklist

Tick each box as you finish the item. A program that passes the examples can still miss an item, so check the list before you submit.

• The program reads c and q from the first line, and then reads exactly q commands.
• Every command reads its own arguments, including the commands the program does not yet answer.
• add stores every price, including repeats, in a multiset.
• count lo hi uses lower_bound and upper_bound, and prints the distance between them.
• nearest v uses lower_bound and prints NONE when the result is end().
• once id uses a set or unordered_set, and prints NEW or REPEAT from the result of insert.
• The cache is an unordered_map from id to an iterator, with a list in usage order.
• put on an existing id updates the price and moves the entry to the front, without evicting.
• put on a new id evicts the back entry when the cache is full, and erases its id from the map first.
• get moves a hit to the front, and prints -1 on a miss without changing the cache.
• add and put print nothing.
• The cache and the price list never affect each other, and evictions do not clear the seen ids.
• Each command costs O(log n) or O(1) average, with no loop over all stored prices or entries.

The last item is the one most often missed. A solution that sorts or scans the whole price list for each nearest command is correct on small inputs and too slow on large ones. Test with a few hundred commands to see whether the program keeps up.

Grading rubric

The rubric describes what each score level looks like in practice. Your program is graded by running it on hidden inputs and comparing the output with the expected output.

Most points are lost on three things. The first is eviction order, because a get that does not move the node gives the wrong evictions. The second is the count boundaries, because the upper bound must be inclusive and the bounds are easy to swap. The third is inserting by accident with [], which changes the size of a container and then changes later answers.

Step-by-step hints

Work in this order. Each step builds on the one before it, and each one can be tested on its own. The hints are hidden, so try a step before you open its hint.

Reference solution

Try the whole program yourself before you open this section. The reference is a complete program that answers every command. Its structure is the same as the hints, combined into one class for the cache and one loop for the commands.

Stretch extension

Once the program passes every example, try one extension. Add a command top k that prints the k largest prices in descending order, with one price per line. Think about which end of the multiset to walk, and how to stop when fewer than k prices exist. Then test a case where the prices contain duplicates, and decide whether duplicates should appear more than once in the output. Explain your choice in a comment at the top of the program.

Final checks before you submit

Run the program on both examples and check each output line. Run it on an input where most commands are add or count, with a few hundred prices, to check speed. Then read through the checklist one more time and make sure every box is ticked for a reason you can explain.

A good submission also includes a short comment above each container. The comment says which command uses it and why that container was the right choice. A reviewer should be able to read the comments and see the design in less than a minute.

What you now know

• A hash map finds keys in O(1) average time, and it does not keep order.
• A sorted multiset counts ranges and finds the nearest value in O(log n), using lower_bound and upper_bound.
• An LRU cache combines a hash map and a linked list, so get and put both run in O(1) average time.
• A hash set answers the "have I seen this before?" question, and insert reports whether the value was new.
• Keeping separate pieces of state separate, and reading the arguments of every command, are the habits that keep a long program correct.