LRU Cache Implementation

Background

LRU caches are used in browser caching, database buffer pools, and memoization with memory bounds.

Problem

Create an LRUCache class with a capacity limit, where get and put operations run in O(1) and least recently used items are evicted first.

Input

A capacity number for the maximum cache size.

Output

An LRUCache instance with get(key) and put(key, value) methods.

Sample tests

Input: capacity=2, put(1,1), put(2,2), get(1), put(3,3), get(2)

Expected: 1, -1

Your solution

Learning objective

Understand cache eviction policies and leverage Map insertion-order semantics for O(1) LRU.