LRU Cache

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **LRU Cache** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Doubly-linked list + hash map for O(1) ops **Edge Cases to Consider:** - (1) Capacity = 1 - (2) Get on non-existent key - (3) Put updates existing key

Examples

Example 1

Input: LRUCache(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; -1; 3; 4

Explanation: Classic example

Example 2

Input: LRUCache(1); put(1,1); get(1); put(2,2); get(1); get(2)

Output: 1; -1; 2

Explanation: Capacity 1

Example 3

Input: LRUCache(2); put(1,1); put(2,2); put(3,3); get(1)

Output: -1

Explanation: Key 1 evicted by put 3

Constraints

▪The number of nodes in the list is in the range [0, 500]
▪-100 <= Node.val <= 100
▪Solve in-place without copying node structures

Watch Out For Edge Cases

▪Capacity = 1
▪Get on non-existent key
▪Put updates existing key

Frequently Asked At

AmazonGoogleMicrosoftMetaUberZomatoFlipkart

Back to Arena

medium

LinkedList