LRU Cache Implementation

Design and implement an LRU (Least Recently Used) Cache which supports the following operations:

• get(key) - Get the value associated with key if it exists in the cache. Otherwise, return -1.
• put(key, value) - Insert or update the value associated with key. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

The cache should work in O(1) average time for both operations. Formally, if the number of items in the cache is denoted by \(n\) and its capacity by \(C\), then after a put operation, if \(n > C\) the cache must perform an eviction such that

\[ |\text{cache}| > C \quad \Longrightarrow \quad \text{evict the least recently used element} \]

This is a typical system design question used in coding competitions. The input will describe the cache capacity and a sequence of operations. You must output the results of the get operations.

inputFormat

The first line contains two integers, capacity and Q, where capacity is the maximum number of items the cache can hold and Q is the number of operations to perform.

Each of the following Q lines contains an operation. An operation is either:

• put key value: Insert (or update) the value for key.
• get key: Retrieve the value for the given key from the cache. If the key does not exist, output -1.

All input is from standard input (stdin).

outputFormat

For each get operation, output the result on a separate line to standard output (stdout).

## sample

2 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
-1
-1
3
4

</p>