Program for Least Recently Used (LRU) Page Replacement algorithm

The problem, simply

A computer keeps a few pages of memory in a small fast place called the cache, which has room for c pages. Programs ask for pages one after another. If the page is already in the cache, that is a hit. If not, that is a page fault: the page must be brought in, and if the cache is full, one page has to leave.

The Least Recently Used rule says: throw out the page whose last use is the furthest in the past. Given the list of requests and c, count the page faults.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the cache as a plain list in order of use, oldest first. For each request, search the list.

1. If the page is in the list, remove it and add it again at the end, because it is now the newest.
2. If not, count a fault. If the list is full, remove the first item, the oldest. Add the page at the end.

import java.util.*;

class Solution {
    public int pageFaults(int[] pages, int c) {
        List<Integer> cache = new ArrayList<>();   // oldest first, newest last
        int faults = 0;
        for (int p : pages) {
            int at = cache.indexOf(p);             // walk the whole list to search
            if (at >= 0) {
                cache.remove(at);
                cache.add(p);                      // now the newest
            } else {
                faults++;
                if (c == 0) continue;
                if (cache.size() == c) cache.remove(0);   // the oldest leaves
                cache.add(p);
            }
        }
        return faults;
    }
}

How long it takes: each request may search and shift a list of c pages, so O(n * c) for n requests. Extra room: the list, O(c).

Way 2: the clever way

The list is slow in two places: finding a page, and taking it out of the middle. Fix each one with the right tool.

• A map from page to its box finds any page in one step.
• A chain of boxes linked both ways (each box knows the box before and after it) can unhook a box from the middle and hook it in at the front by changing a few arrows.

Add two dummy boxes, one at each end, so a box always has neighbours and there are no special cases.

1. Hit: find the box in the map, unhook it, hook it in at the front.
2. Fault: count it. If the cache is full, the box just before the right dummy is the oldest. Unhook it and remove it from the map. Then make a new box at the front and put it in the map.

import java.util.*;

class Solution {
    static class Box {
        int page;
        Box prev, next;
        Box(int page) { this.page = page; }
    }

    private final Box front = new Box(-1), back = new Box(-1);   // dummy ends
    private final Map<Integer, Box> where = new HashMap<>();

    public int pageFaults(int[] pages, int c) {
        if (c == 0) return pages.length;           // nothing can ever stay
        front.next = back;
        back.prev = front;
        int faults = 0;
        for (int p : pages) {
            Box box = where.get(p);
            if (box != null) {                     // hit: move it to the front
                unhook(box);
                hookAtFront(box);
                continue;
            }
            faults++;                              // fault
            if (where.size() == c) {
                Box oldest = back.prev;            // the least recently used page
                unhook(oldest);
                where.remove(oldest.page);
            }
            box = new Box(p);
            hookAtFront(box);
            where.put(p, box);
        }
        return faults;
    }

    private void unhook(Box b) {
        b.prev.next = b.next;
        b.next.prev = b.prev;
    }

    private void hookAtFront(Box b) {
        b.next = front.next;
        b.prev = front;
        front.next.prev = b;
        front.next = b;
    }
}

How long it takes: every request is one map lookup and a few arrow changes, O(1) on average, so O(n) in total. Extra room: at most c boxes and c map entries, O(c).

Watch out for

• Remove the page from the map when you throw its box out, or the map will say it is still cached.
• A singly linked chain is not enough: to unhook a box from the middle you need its previous box, and finding that would take a walk.
• c = 0 means every request is a fault. Guard it, or the code tries to unhook a dummy.
• Count faults, not hits, unless the problem asks for hits. Hits are n - faults.

What interviewers ask next

• Build an LRUCache class with get(key) and put(key, value) in O(1). Same chain and map; store the value in the box too. This is one of the most asked design questions.
• Can Java do it for you? new LinkedHashMap<>(c, 0.75f, true) keeps access order, and overriding removeEldestEntry to return size() > c gives an LRU cache in a few lines.
• How is LRU different from FIFO and LFU? FIFO throws out the page that came in first, even if it is used all the time. LFU throws out the page used the fewest times. On some lists FIFO even gets more faults with a bigger cache, which is called Belady's anomaly. LRU never does that.
• Make it safe for many threads. Put a lock around get and put, or split the cache into parts with their own locks.

Remember this

Grown-up words: the shelf is the cache, fetching from the basement is a page fault, the chain linked both ways is a doubly linked list, the dummy end boxes are sentinel nodes, and the map is a hash map from page to node.