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
getandputmust run in O(1) average time complexity.
type LRUCache struct {
// TODO: design your structs
}