CS
Problems Base course RU

Problem

LFU's eviction order

caching hash table linked list in production interviews

A cache of c pages works by the LFU rule. Each page in the cache has a counter: how many times it was requested since it last got into the cache. Requests come one at a time:

  • if the page is in the cache, it is a hit, and its counter grows by one;
  • if not and the cache has a free place, the page is put there with counter 1;
  • if not and the cache is full, first the page with the smallest counter is evicted; if there are several, the one gone longest without a request. An evicted page forgets its counter: on returning it starts from 1 again.

Count the hits and print the eviction queue after the last request: the cache’s pages in increasing order of counter, and with equal counters starting from the one gone longest without a request. Two tests are real requests to the Kennedy Space Center web server in July 1995, a page being its number.

Input

The first line holds c and the number of requests n (1 ≤ c ≤ n ≤ 5·105). The second holds n page numbers, integers from 0 to 106.

Output

The first line holds the number of hits. The second, the pages of the cache in eviction queue order.

In the first example pages 2 and 3 knock each other out in turn without managing a second request, while page 1 with counter 2 holds on. Then page 3 also reaches counter 2, and when 4 comes, 1 goes: the counters are equal, and 1 has gone longer without a request. On returning, 1 starts with counter 1 and is first in the queue at the end. In the second example pages 5, 6, 7 have counters of 2 each, and 5 goes first, as it was asked for earliest; at the end 5 has returned with counter 1 and is first in the queue.

Examples

Example 1

Input
2 9
1 2 1 3 2 3 3 4 1
Output
2
1 3

Example 2

Input
3 10
5 6 7 5 6 7 8 9 8 5
Output
3
5 6 7

Limits

Time · Python
10000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
8 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

Finding the page with the smallest counter by going through them all is O(c) per miss. With fifty thousand places and hundreds of thousands of misses that is billions of steps. What if the pages are kept grouped by counter?

2The idea

Keep buckets: bucket f holds the pages with counter f, in order of last access, from oldest to freshest. A hit moves a page from bucket f to the end of bucket f + 1. The first page of the smallest non-empty bucket is evicted. The number of this bucket is easy to maintain without a search: a new page always comes with counter 1, so after a miss the smallest counter is 1; and when a hit empties the bucket with the smallest counter, the smallest becomes f + 1, where the page has just gone.

3Walkthrough

You need a dictionary “page → counter” and a dictionary “counter → bucket”, where a bucket is an ordered set: in Python a dictionary (it remembers insertion order, and the first key is next(iter(d))), in Go a doubly linked list and a dictionary “page → its node”. All the operations, finding a page, taking it out of a bucket, appending at the end, taking out the first, cost O(1).

The queue at the end is the buckets in increasing order of counter, and inside a bucket from oldest to freshest. On the day of 13 July a cache of a hundred pages catches 103,127 requests of 128,932, the 79.99% from the article.

3+Solution
4Complexity

O(1) per request, O(n) for all. Sorting the buckets at the end is O(k log k) for k distinct counters, and there are no more of them than pages in the cache.

5Common mistakes
  • Remembering the counters of evicted pages. This is how “full” LFU works, but here a returning page starts from one. On the very first example the answers diverge.
  • Equal counters. Of several pages with the smallest counter, the one with the oldest last access goes, not the first to appear in the cache: after a hit a page goes to the end of the new bucket.
  • Searching on eviction. The fifth test: fifty thousand places and almost nothing but misses.

Algorithms behind it

SYS Algorithm LFU and ARC Caches that remember frequency: LFU in O(1) on counter buckets and ARC, which divides its places between fresh and frequent by itself. O(1) per request for both 2 problems 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
The algorithms catalogue