150. LRU Cache
Build a cache that remembers which resident entry was used least recently. A successful lookup or a put makes the affected entry most recent; adding a new entry to a full cache evicts the least recent entry.
A missing lookup does not change recency, and updating an existing key does not increase size. Zero capacity, missing-result representation, and independent cache instances are all part of the contract.
Example 1
Input
capacity=2; ops=[put(1,10),put(2,20),get(1),put(3,30),get(2),size()]
Output
[null,null,10,null,null,2]
Explanation: get(1) changes recency to [1,2], so inserting three evicts two; a miss does not promote anything.
Example 2
Input
capacity=2; ops=[put(1,-1),put(2,2),put(1,99),put(3,3),get(1),get(2)]
Output
[null,null,null,null,99,null]
Explanation: Updating one reuses and promotes its node. It does not consume another slot; adding three evicts two.
Example 3
Input
capacity=0; ops=[put(7,-1),get(7),size()]
Output
[null,null,0]
Explanation: The zero-capacity cache remains empty; its sentinel links stay valid.
Constraints
0 <= capacity <= 105-231 <= key, value <= 231 - 1- Capacity zero is valid. get returns an optional value, so a stored -1 is distinct from a miss.
Hints
Hint 1
Which structure finds a key directly, and which structure exposes the oldest access at one end?
Hint 2
Map each key to its exact list node so promotion does not require a list search.
Hint 3
Keep most recent after HEAD, least recent before TAIL, and preserve the map/list bijection at every public return.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A successful read changes the next eviction victim
2
[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}][null,null,10,null,null,2]