A page cache

caching hash table linked list networks interviews

A web server keeps the most recently needed files in memory so as not to read them from disk. Memory holds C files; when a request comes for a file not in memory and there is no room left, the file that has gone longest without being accessed is thrown out of memory, and the new one takes its place. For each request, say whether the file was found in memory.

One of the tests is the first 30,000 successful requests to the Kennedy Space Center server on 13 July 1995, the day Discovery launched, with memory for 100 files.

Input

The first line holds C and n (1 ≤ C ≤ 100,000, 1 ≤ n ≤ 200,000). Then n lines, each with a file path: a non-empty string of up to 100 characters without spaces. Memory is empty at first.

Output

One line of n characters: + if the file was found in memory and - if not.

Examples

Example 1

Input

3 10
/
/logo.gif
/
/news.html
/clock.pl
/logo.gif
/
/clock.pl
/clock.pl
/news.html

Output

--+----++-

Example 2

Input

1 5
a
a
b
a
a

Output

-+--+

Limits

Time · Python: 6000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

A list of files in order of last access answers all the questions: a found file moves to the end, and the first one is thrown out. What does each of these actions cost with a hundred thousand files in memory?

2Hint 2

A dictionary can find a file by name quickly. A doubly linked list can take an element out of the middle and put it at the end in O(1), if you know where the element lies. Let the dictionary store exactly that.

3The idea

An LRU cache: a dictionary “path → list node” and a doubly linked list of nodes in order of access. A hit: the dictionary finds the node, and the node moves to the front of the list. A miss with full memory: the last node of the list is removed from the list and from the dictionary, and a new node goes to the front. Each action is a few pointers and one dictionary operation.

4Walkthrough

In Python a ready-made pair of “dictionary and doubly linked list” is collections.OrderedDict: move_to_end refreshes a file, popitem(last=False) throws out the stalest. The paths need not be turned into strings: byte strings from sys.stdin.buffer work as dictionary keys as they are.

In Go, a map from the path to a container/list element: MoveToFront on a hit, Remove(Back()) on eviction. The node stores the path so that on eviction it can be removed from the map too.

4+Solution

5Complexity

O(1) on average per request, O(n) in all; memory O(C). A list without a dictionary is O(C) per request: searching the list, removing from the middle and shifting when the first element is removed.

6Common mistakes

A plain list. page in order, order.remove(page) and order.pop(0) are each O(C). On the first test it goes unnoticed, on the fourth with memory for a hundred thousand files it is twenty billion steps.
Not refreshing on a hit. Then you get FIFO, not LRU: a file is thrown out by the time it appeared, not by its last access. In the first example the sixth and tenth requests would become hits: the answer --+--+-+++ instead of --+----++-.
Evicting before checking for a hit. If memory is full and a file that is in it arrives, nobody needs to be thrown out.
A circle one file longer than memory. In the fifth test 50,001 files are requested in a circle with memory for 50,000: the correct answer is not a single hit. This is not a bug in the solution but a weak spot of the LRU rule itself.

Algorithms behind it

DS Data structure LRU cache A dictionary plus a doubly linked list: get and put in O(1), and out goes the one accessed longest ago. O(1) per get and put 2 problems