Quick Overview

This question evaluates competency in data structure design and algorithmic complexity by requiring a bounded key-value cache with O(1) average-time get and put operations.

Implement an LRU cache

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a key-value cache with a fixed capacity. It must support: - `get(key)`: return the value for the key if it exists, otherwise return `-1`. - `put(key, value)`: insert or update the key. If the cache is full, evict the least recently used key before inserting the new one. Both operations should run in O(1) average time.

Overview: This question evaluates competency in data structure design and algorithmic complexity by requiring a bounded key-value cache with O(1) average-time get and put operations.

Design and simulate a key-value cache with a fixed capacity using Least Recently Used (LRU) eviction. The cache stores integer keys and values and must support two operations: get(key), which returns the value for the key if it exists or -1 otherwise, and put(key, value), which inserts or updates a key. Whenever a key is accessed by get or inserted/updated by put, it becomes the most recently used key. If a new key is inserted when the cache is already full, evict the least recently used key first. Both operations should run in O(1) average time.

Constraints

  • 0 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Each operation is either ('get', key) or ('put', key, value)
  • Keys and values are integers in the range [-10^9, 10^9]

Examples

Input: (2, [("put", 1, 1), ("put", 2, 2), ("get", 1), ("put", 3, 3), ("get", 2), ("put", 4, 4), ("get", 1), ("get", 3), ("get", 4)])

Expected Output: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: After inserting 1 and 2, get(1) makes key 1 most recent. Putting 3 evicts key 2. Putting 4 later evicts key 1. Final gets return -1, 3, and 4.

Input: (1, [("put", 2, 1), ("get", 2), ("put", 2, 2), ("get", 2), ("put", 3, 3), ("get", 2), ("get", 3)])

Expected Output: [None, 1, None, 2, None, -1, 3]

Explanation: With capacity 1, updating key 2 changes its value to 2. Inserting key 3 then evicts key 2.

Hints

  1. You need one structure for O(1) key lookup and another structure that can remove and reinsert nodes in O(1) when recency changes.
  2. A doubly linked list with dummy head and tail nodes makes it easy to move a key to the most recently used position and evict the least recently used key.

Loading coding console...