Implement an LRU Cache
Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.
Problem
Implement an LRU (Least Recently Used) cache that supports:
LRUCache(capacity): initialize the cache with the given positive capacity.
get(key): return the value if the key exists and mark it as most recently used; otherwise return -1.
put(key, value): insert or update the key with the value and mark it as most recently used; if the cache exceeds capacity, evict the least recently used entry.
Requirements:
Target time complexity: O(1) per get/put.
Constraints
Number of operations: 1 <= N <= 2 * 10^5
key, value are 32-bit integers
Sample Tests
Input:
capacity=2
put(1,1)
put(2,2)
get(1)
put(3,3)
get(2)
put(4,4)
get(1)
get(3)
get(4)
Output:
1
-1
3
4
Input:
capacity=1
put(1,1)
put(2,2)
get(1)
get(2)
Output:
-1
2
Input:
capacity=2
put(1,1)
put(1,10)
get(1)
Output:
10
Input:
capacity=3
get(42)
Output:
-1
Input:
capacity=2
put(1,1)
put(2,2)
put(3,3)
get(1)
get(2)
get(3)
Output:
-1
2
3
Example
Input
capacity=2
put(1,1)
put(2,2)
get(1)
put(3,3)
get(2)
put(4,4)
get(1)
get(3)
get(4)
Output
1
-1
3
4
Complete solveLRUCacheOperations. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.
input = "capacity=2\nput(1,1)\nput(2,2)\nget(1)\nput(3,3)\nget(2)\nput(4,4)\nget(1)\nget(3)\nget(4)" return = ["1", "-1", "-1", "3", "4"]
The returned string array must match the expected standard output lines for the sample input.
Use the limits and requirements stated in the prompt.
public String[] solveLRUCacheOperations(String input) {
// write your code here
}