Design an LRU Cache

1. Problem Description

Design an LRU cache structure. Its size is determined when it is constructed. Assume the size is K, and it has the following two functions:

• set(key, value): insert the record (key, value) into the structure
• get(key): return the value corresponding to key

2. Approach

• map + doubly linked list

3. Implementation

3.1. Golang

3.1.1. map + list

package main

import (
	"container/list"
)

/**
 * lru design
 * @param operators 2D int array, the operations
 * @param k int, the capacity
 * @return 1D int array
 */

type data struct {
	key   int
	value int
}

type LruCache struct {
	eList    *list.List
	eMap     map[int]*list.Element
	capacity int
}

func NewLruCache(capacity int) *LruCache {
	return &LruCache{
		eList:    list.New(),
		eMap:     make(map[int]*list.Element, 0),
		capacity: capacity,
	}
}

func (l *LruCache) Set(key int, value int) {

	// Already exists but is not the head node
	element, ok := l.eMap[key]
	if ok {
		element.Value.(*data).value = value
		l.eList.MoveToFront(element)
		return
	}

	// Does not exist and is full
	if l.isFull() {
		lastElement := l.eList.Back()
		// Delete the tail node
		l.eList.Remove(lastElement)
		// Clean up the map
		delete(l.eMap, lastElement.Value.(*data).key)
	}

	// Does not exist and is not full
	element = l.eList.PushFront(&data{
		key:   key,
		value: value,
	})
	l.eMap[key] = element
}

func (l *LruCache) isFull() bool {
	return len(l.eMap) == l.capacity
}

func (l *LruCache) Get(key int) int {
	element, ok := l.eMap[key]
	if !ok {
		return -1
	}

	l.eList.MoveToFront(element)
	return element.Value.(*data).value
}

func LRU(operators [][]int, k int) []int {

	res := make([]int, 0)
	cache := NewLruCache(k)
	for _, operator := range operators {
		switch operator[0] {
		case 1:
			cache.Set(operator[1], operator[2])
		case 2:
			val := cache.Get(operator[1])
			res = append(res, val)
		}
	}

	return res
}

3.1.2. map + slice

type node struct {
	key   int
	value int
}

type LRUCache struct {
	m        map[int]*node
	lst      []*node
	capacity int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		m:        make(map[int]*node, 0),
		lst:      make([]*node, 0),
		capacity: capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	n, ok := this.m[key]
	if !ok {
		return -1
	}

	// If it exists, move the node to the head of the list
	this.moveToHead(key)
	return n.value
}

func (this *LRUCache) moveToHead(key int) {
	var movedNode *node
	var movedIndex int
	for i, n := range this.lst {
		if n.key == key {
			movedNode = n
			movedIndex = i
			break
		}
	}

	newList := append([]*node{movedNode}, this.lst[:movedIndex]...)
	newList = append(newList, this.lst[movedIndex+1:]...)
	this.lst = newList
}

func (this *LRUCache) Put(key int, value int) {
	n, ok := this.m[key]
	if ok {
		n.value = value
		// If it exists, move the node to the head of the list
		this.moveToHead(key)
		return
	}

	if len(this.m) == this.capacity {
		// Take the tail of the list and delete it
		tail := this.removeTail()
		// Delete the element from m
		delete(this.m, tail.key)
	}

	// Create a new node
	newNode := &node{
		key:   key,
		value: value,
	}
	// Insert at the head of the list
	this.addToHead(newNode)
	// Insert into the map
	this.m[key] = newNode
}

func (this *LRUCache) addToHead(n *node) {
	this.lst = append([]*node{n}, this.lst...)
}

func (this *LRUCache) removeTail() *node {
	tail := this.lst[len(this.lst)-1]
	this.lst = this.lst[:len(this.lst)-1]
	return tail
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

package main

import "fmt"


type node struct {
    key int
    value int
}

type LRU struct {
    m map[int]*node
    lst []*node
    capacity int
}

func (l *LRU)String() string {
    s := ""
    for _, n := range l.lst {
        s += fmt.Sprintf("%d:%d,", n.key,n.value)
    }
    
    return s
} 

func LRUCache(capacity int ) *LRU {
    return &LRU{
        m: make(map[int]*node),
        lst: make([]*node, 0),
        capacity:capacity,
    }
}


func (l *LRU) get(key int) int {
    n, ok := l.m[key]
    if !ok {
        return -1
    }
    
    idx := findNodeFromList(l.lst, n)
    newLst := []*node{l.lst[idx]}
    newLst = append(newLst, l.lst[:idx]...)
    newLst = append(newLst, l.lst[idx+1:]...)
    l.lst = newLst
    return n.value
}

func findNodeFromList(lst []*node, n *node) int {
    for idx,nd := range lst {
        if nd == n {
            return idx
        }
    }
    return 0
}


func (l *LRU) put(key, value int) {
    n, ok := l.m[key]
    if ok {
        n.value = value
        idx := findNodeFromList(l.lst, n)
        newLst := []*node{l.lst[idx]}
        newLst = append(newLst, l.lst[:idx]...)
        newLst = append(newLst, l.lst[idx+1:]...)
        l.lst = newLst
        return
    }
    

    
    if l.capacity == len(l.m) { 
        deleteNode := l.lst[len(l.lst)-1]
        l.lst = l.lst[:len(l.lst)-1]
        delete(l.m, deleteNode.key)
    }
    
    addNode := &node{
        key: key,
        value: value,
    }
    l.m[key] = addNode
    newLst := make([]*node, 0)
    newLst = append(newLst, addNode)
    newLst = append(newLst, l.lst...)
    l.lst = newLst
}



func main() {
    lru := LRUCache(3)
    
    fmt.Println(lru.get(1))
    lru.put(1,10)
    fmt.Println(lru.get(1))
    
    lru.put(2,20)
    lru.put(3,30)
    fmt.Println(lru)
    
    lru.put(4,40)
    fmt.Println(lru)
    
    lru.put(4,50)
    fmt.Println(lru)
}

3.2. Java

public class LRU
{
    public static void main(String[] args)
    {
        // By default LinkedHashMap is ordered by insertion order; the parameterized constructor can make it use access order
        Map<Integer,Integer> map = new LinkedHashMap<Integer, Integer>(3, (float) 0.75, true)
        {
            // Override removeEldestEntry and set the LRU capacity
            // When size is greater than 3 and new data is inserted, the node at the head of the list is removed
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest)
            {
                return size() > 3;
            }
        };

        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        System.out.println(map);//{1=1, 2=2, 3=3}
        map.put(4, 4);
        System.out.println(map);//{2=2, 3=3, 4=4}: delete 1 at the head and insert 4 at the tail
        map.get(2);
        System.out.println(map);//{3=3, 4=4, 2=2}: move 2 to the tail

    }
}

4. References

• Design an LRU Cache _ NowCoder
• 146. LRU Cache - LeetCode