Implement LRU Cache

Implement a LRU Cache. Implement the class LRUCache: LRUCache(int capacity) Initializes the LRU 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, int value)Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key. Implement the solution and validate using the following test cases: Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"], [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Expected output: [null, null, null, 1, null, -1, null, -1, 3, 4] Example Input LRUCache,put,put,get,put,get,put,get,get,get 2 1,1 2,2 1 3,3 2 4,4 1 3 4