LRU

lru-go.md

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

• LRUCache(capacity int) Initialize the cache with positive size capacity.
• int get(int key) Return the value of the key if it exists, otherwise return -1.
• void put(int key, value int) Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.
• Both get and put must run in O(1) average time complexity.

type LRUCache struct {
    // TODO: design your structs
}

func Constructor(capacity int) LRUCache {
    // TODO
}

func (this *LRUCache) Get(key int) int {
    // TODO: O(1)
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    // TODO: O(1)
}