Implement LRU Cache

Question

Design and implement a data structure for Least Recently Used (LRU) cache.

Requirements:
- Get and Put operations should be O(1)
- When cache reaches capacity, remove least recently used item

Example:
LRUCache cache = new LRUCache(2); // capacity = 2
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)

Accepted Answer

LRU Cache Implementation:

1. Data Structure:
   - HashMap for O(1) lookup
   - Doubly Linked List for O(1) removal

2. Implementation:
```typescript
class LRUCache {
  private capacity: number;
  private cache: Map<number, Node>;
  private head: Node;
  private tail: Node;

constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

get(key: number): number {
    if (!this.cache.has(key)) return -1;
    
    // Move to front
    const node = this.cache.get(key);
    this.removeNode(node);
    this.addToFront(node);
    return node.value;
  }

put(key: number, value: number): void {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.removeNode(node);
      this.addToFront(node);
    } else {
      const newNode = new Node(key, value);
      this.cache.set(key, newNode);
      this.addToFront(newNode);
      
      if (this.cache.size > this.capacity) {
        const lru = this.tail.prev;
        this.removeNode(lru);
        this.cache.delete(lru.key);
      }
    }
  }
}
```

3. Time Complexity:
   - Get: O(1)
   - Put: O(1)
   - Space: O(capacity)

4. Edge Cases:
   - Cache capacity = 1
   - Duplicate keys
   - Key not found
   - Cache full

Company Context (Microsoft):
- Clean, maintainable code
- Efficient memory usage
- Thread safety considerations
- Error handling

Implement LRU Cache

Question Explain

Answer Example

Related Interview Questions