Final: Browser Cache

Lab Java Intermediate 20 points

A browser keeps the last c pages it used in a cache. For each page request: if the page is in the cache, it's a hit and becomes the most recently used. If not, it's a miss: the page is added as most recently used, and if the cache is now over capacity, the least recently used page is removed. Print hits: h, misses: m, then the cache from most to least recently used.

Input

Line 1: c n (c ≥ 1). Line 2: n page names.

Output

hits: h, misses: m, then the cached pages separated by spaces.

Example

Input

3 7
home news home mail shop news home

Output

hits: 1
misses: 6
home news shop

Sample input available Sample output available

Editor

Java

Hints

Keep pages in an ArrayDeque with the most recent at the front.

On a hit, remove the page and add it to the front again. On a miss, drop the last page if the cache is full.

Solution explanation

This is the LRU (least recently used) policy used by real caches. Here each request is O(c). Production caches make it O(1) by pairing a HashMap with a doubly linked list – Java's LinkedHashMap can do exactly that.

Show solution

import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt(), n = sc.nextInt();
        ArrayDeque<String> cache = new ArrayDeque<String>();   // front = most recently used
        int hits = 0, misses = 0;
        for (int i = 0; i < n; i++) {
            String page = sc.next();
            if (cache.remove(page)) {          // O(c): fine for a small cache
                hits++;
            } else {
                misses++;
                if (cache.size() == c) cache.removeLast();      // drop the least recently used
            }
            cache.addFirst(page);
        }
        System.out.println("hits: " + hits);
        System.out.println("misses: " + misses);
        StringBuilder sb = new StringBuilder();
        Iterator<String> it = cache.iterator();
        while (it.hasNext()) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(it.next());
        }
        System.out.println(sb);
    }
}

Output

Answer