Lru Cache Solution for Amazon

Company: Amazon · Difficulty: Hard · Topics: Hash Table, Linked List, Design, Data Structure

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key 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 from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Examples

Example 1:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

Input: [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

• LRUCache lRUCache = new LRUCache(2);
• lRUCache.put(1, 1); // cache is {1=1}
• lRUCache.put(2, 2); // cache is {1=1, 2=2}
• lRUCache.get(1); // return 1
• lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
• lRUCache.get(2); // returns -1 (not found)
• lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
• lRUCache.get(1); // return -1 (not found)
• lRUCache.get(3); // return 3
• lRUCache.get(4); // return 4

Example 2:

Input: ["LRUCache", "put", "get"]

Input: [[1], [1, 1], [1]]

Output: [null, null, 1]

Explanation:

• LRUCache lRUCache = new LRUCache(1);
• lRUCache.put(1, 1); // cache is {1=1}
• lRUCache.get(1); // return 1

Intuition

The key insight is to use a combination of a hash table and a doubly linked list. The hash table provides O(1) access to elements, while the doubly linked list maintains the order of usage (most recently used at the front, least recently used at the back).

Approach

Approach 1: Hash Table + Doubly Linked List (Optimal)

1. Use a hash table to store key-value pairs for O(1) access

2. Use a doubly linked list to maintain usage order

3. When accessing an element, move it to the front of the list

4. When capacity is exceeded, remove the last element from the list

Approach 2: Hash Table + Array

1. Use a hash table for key-value storage

2. Use an array to maintain usage order

3. When accessing an element, move it to the front of the array

4. Less efficient due to array shifting

Approach 3: Simple Hash Table

1. Use only a hash table with timestamps

2. When capacity is exceeded, find the least recently used by checking timestamps

3. Inefficient for large caches

Dry Run

Let's trace through Example 1: capacity = 2

Hash Table + Doubly Linked List Approach:

• put(1,1): cache = {1:1}, list = [1]
• put(2,2): cache = {1:1, 2:2}, list = [2,1]
• get(1): cache = {1:1, 2:2}, list = [1,2], return 1
• put(3,3): cache = {1:1, 3:3}, list = [3,1], evict 2
• get(2): return -1 (not found)
• put(4,4): cache = {3:3, 4:4}, list = [4,3], evict 1
• get(1): return -1 (not found)
• get(3): cache = {3:3, 4:4}, list = [3,4], return 3
• get(4): cache = {3:3, 4:4}, list = [4,3], return 4

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Hash Table + Doubly Linked List (Optimal)

Time Complexity: O(1) - All operations are O(1)

Space Complexity: O(capacity) - Hash table and linked list

Solution 2: Hash Table + Array

Time Complexity: O(n) - Array shifting operations

Space Complexity: O(capacity) - Hash table and array

Solution 3: Simple Hash Table

Time Complexity: O(n) - Finding LRU element

Space Complexity: O(capacity) - Hash table

More Amazon coding questions