Reference: LeetCode
Difficulty: Medium

## Problem

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Example:

Follow up: Could you do both operations in O(1) time complexity?

## Analysis

From official documentation:

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. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Inside:

In HashMap, there are three callback methods that allow LinkedHashMap post-actions.

removeEldestEntry is a method that we can override. It is usually invoked after put operation. If it returns true, the first entry would be deleted; otherwise, nothing happens.

Then we can see how put and get work. In LinkedHashMap, put is not re-implemented, but all new features are implemented in afterNodeAccess and afterNodeInsertion callbacks.

accessOrder:

accessOrder is a boolean that indicates two modes of structural modification, which are access-ordered and insertion-ordered modes.

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification.

In other words, when accessOrder is set as true, calls of put, get, and so on would trigger affection on iteration order. The accessed entry will be put at the end of the linked list.

Basic Usage:

accessOrder is false:

accessOrder is true:

Code for this problem:

We can make the class LRUCache extend from LinkedHashMap. get and put are overloaded, and removeEldestEntry is overridden. It means that we would delete the first entry when this.size() > capacity.

Note: capacity member is a fixed value, while the capacity passed into LinkedHashMap is for speculative purpose (just guessing? optimization?).

The second approach is similar to the object adapter pattern. A LinkedListMap object is wrapped inside LRUCache.

Time: $O(1)$
Space: $O(capacity)$

### Do It By Yourself

Time: $O(1)$
Space: $O(capacity)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.