Implement LRUCache with O(1) Operations and Thread Safety
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
High-traffic API needs constant-time eviction cache.
##### Question
Implement an LRUCache supporting get(key) and put(key,val) in O(
1). Describe thread-safety considerations for concurrent access.
##### Hints
Combine hash map with doubly-linked list; lock striping or concurrent linked hash map for threads.
Quick Answer: This question evaluates a candidate's ability to implement a constant-time LRU cache and reason about thread-safety and concurrent access, testing data structure design and concurrency competencies in the Coding & Algorithms domain.
Implement lru_ops(ops, capacity) to simulate an LRU cache with the given capacity. Each operation is either ["put", key, value] or ["get", key]. get(key) returns the value for key or -1 if absent, and marks the key as most-recently-used. put(key, value) inserts or updates key, marking it most-recently-used; if capacity is exceeded, evict the least-recently-used key. Return a list of integers containing the results of get operations in order. Assume single-threaded execution for testing.
Constraints
- 1 <= capacity <= 100000
- 0 <= len(ops) <= 200000
- Each op is ["get", key] or ["put", key, value]
- Keys and values are 32-bit signed integers
- Average O(1) time per operation
- Space O(capacity)
Hints
- Combine a hash map (key -> node) with a doubly linked list to track recency.
- Move a node to the list head on every get/put; evict from the tail.
- For thread-safety in real systems, guard the cache with a single mutex; for higher concurrency, consider a read-write lock or segmenting (lock striping) while keeping list and map updates atomic.