Coder's Cat

2020-02-06

## Challenge Description

Design and implement a data structure for 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.

Follow up:

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

## Solution

For quick query operation, it’s easy to figure out to use map to store key and value.

How we could keep which node is least recently used node?

A clever approach is using double-linked-list, whenever we visiting a node, move the node to head. The least recently visited node is the tail of link list.

Another trivial optimization in my code is, when the cache is full, we use the in-place policy to set the least recently used node’s value to new value.

Preparing for an interview? Checkout this!