# General

## LRU cache

1. Use HashMap and DoubleLinkedList, 

   Put the latest item to the tail of DoubleLinkedList

```java
public class LRUCache {

    private class Node{
        Node prev;
        Node next;
        int key;
        int val;

        public Node(int key, int val){
            this.key = key;
            this.val = val;
            prev = null;
            next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> cache = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)){
            return -1;
        }

        // remove cur
        Node cur = cache.get(key);
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;

        // move cur to tail        
        moveToTail(cur);
        return cache.get(key).val;
    }

    public void set(int key, int value) {
        if (get(key) != -1){
            cache.get(key).val = value;
            return;
        }

        if (cache.size() == capacity){
            cache.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        cache.put(key, insert);
        moveToTail(insert);
    }

    private void moveToTail(Node cur){
        cur.prev = tail.prev;
        cur.next = tail;
        tail.prev = cur;
        cur.prev.next = cur;
    }
}
```

1. Use the **LinkedHashMap**
   * LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

     > If access order, the latest entry will be updated Override the *removeEldestEntry* method

```java
public class LruCache extends LinkedHashMap{

  private int capacity;

  LruCache(final int capacity) {n
    super(capacity, 1, true); // true if access order, false if insertion order
    this.capacity = capacity;
  };

  @Override
  protected boolean removeEldestEntry(Map.Entry e) {
    return this.size() > capacity;
  }

  public Integer lookup(Integer key) {
    if (this.containsKey(key)){
      return (Integer)this.get(key);
    }else{
      return null;
    }
  }

  public void insert(Integer key, Integer value) {
    if (!this.containsKey(key)){
      this.put(key, value);
    }
  }

  public Boolean erase(Object key) {
    if (this.containsKey(key)){
      this.remove(key);
      return true;
    }else{
      return false;
    }
  }
}
```


---

# 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://netjimmy.gitbook.io/code-interview-note/hashtable/general.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.