# LRU Cache

## Intro

A LRU cache is "a cache with a fixed maximum size, evicting items that were used least-recently".

## Question ([LC.146](https://leetcode.com/problems/lru-cache/description/))

LRU supports two regular hash operations - get(key) and put(key, value). But the cache will operate under a limited capacity. The least recently used item will be deleted when running out of space.

## Analysis

This is a cache data structure, we should keep get and put in O(1) time. We'll need a HashMap internally.

> Q1: How to keep track of the recentness?

We want to keep the pairs in a relative order. We also want insert/delete to be O(1) so linked list!!

> Q2: How do we implement insert/delete? Do we need a DLL?

A DDL will make deletion a lot easier b/c you have the reference to the previous node.\
But then a SLL can just get a ref to the previous node then perform the same action.

## Using Java Build-in API

From Java doc, LinkedHashMap is a "Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries."

```
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
```

```java
public class LRUCache {
    private final int maxSize;
    Map<Integer, Integer> linkedHash;

    public LRUCache(int capacity) {
        maxSize = capacity;
        linkedHash = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) 
        {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > maxSize;
            }
        };
    }

    public int get(int key) {
        return linkedHash.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
        linkedHash.put(key, value);
    }
}
```

## DLL Implementation

```java
/**
 * This is a standard implementation of Least Recently Used (LRU) cache.
 * It supports two regular hash operations - get(key) and put(key, value) in O(1) time.
 * The least recently used item will be deleted when reaching the capacity.
 */
public class LRUCache {
    private class DLLNode {
        DLLNode prev;
        DLLNode next;
        int key;
        int value;
        DLLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private DLLNode dummyHead;
    private DLLNode dummyTail;
    private Map<Integer, DLLNode> map;

    /**
     * Initialize the LRU cache with a specified capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead = new DLLNode(0, 0);
        dummyTail = new DLLNode(0, 0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        map = new HashMap<Integer, DLLNode>(capacity);
    }

    /**
     * Return the value of the key if the key exists, otherwise return -1
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        updateRecent(key);
        return map.get(key).value;
    }

    /**
     * Put in a new (key, value) pair to the cache.
     * Only update the value of that key if the key already exists.
     * The least recently used cache will be removed before inserting the new pair 
     * when the cache reaches its capacity.
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            updateRecent(key);
            return;
        }
        if (map.size() >= capacity) {
            deleteOldest();
        }
        DLLNode newNode = new DLLNode(key, value);
        insertNewest(newNode);
        map.put(key, newNode);
    }

    private void deleteCurrent(DLLNode current) {
        DLLNode prevNode = current.prev;
        prevNode.next = current.next;
        current.next.prev = prevNode;       
    }

    private void deleteOldest() {
        map.remove(dummyHead.next.key);
        dummyHead.next = dummyHead.next.next;
        dummyHead.next.prev = dummyHead;
    }

    private void insertNewest(DLLNode newNode) {
        DLLNode secRecent = dummyTail.prev;
        newNode.next = dummyTail;
        newNode.prev = secRecent;
        secRecent.next = newNode;
        dummyTail.prev = newNode;
    }

    // move the most recently used node to the end
    private void updateRecent(int key) {
        DLLNode recent = map.get(key);
        deleteCurrent(recent);
        insertNewest(recent);       
    }
}
```

## Reference

* Java Doc [LinkedHashMap](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html)
* Twitter API DOCs [LRUCache](https://twitter.github.io/commons/apidocs/com/twitter/common/util/caching/LRUCache.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-4/advanced_data_structures/cache-replacement/lru-cache.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.