Creating an LRU cache with Get and Put methods

It is necessary to implement an LRU cache data structure that provides two public methods. The Get(key) method returns the stored value for the given key, or -1 if the key is absent. The Put(key, value) method inserts a new pair or updates an existing one. When the cache reaches its maximum size, the element that was used the longest ago should be removed.

Type LRUCache struct {}

func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Example of usage:

cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
cache.Get(1)    // returns 1
cache.Put(3, 3) // removes key 2
cache.Get(2)    // returns -1 (not found)
cache.Put(4, 4) // removes key 1
cache.Get(1)    // returns -1 (not found)
cache.Get(3)    // returns 3
cache.Get(4)    // returns 4