#693 Image Cache With Least-Recent Eviction

A photo gallery keeps decoded images in memory, but only capacity of them. When a new image must be stored and the cache is full, it throws out the image that was used (read or stored) least recently. Write a class ImageCache:

• new ImageCache(capacity) creates an empty cache.
• get(id) returns the stored size for image id, or -1 if it isn't cached. A successful get counts as a use.
• put(id, size) stores or replaces image id with size and counts as a use. If this makes the cache hold more than capacity images, remove the least recently used one.

Both methods must run in O(1) average time.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new ImageCache(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Input: ["ImageCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,100],[2,200],[1],[3,300],[2],[4,400],[1],[3],[4]]
Output: [null,null,null,100,null,-1,null,-1,300,400]

Input: ["ImageCache","get"]
[[1],[5]]
Output: [null,-1]

Constraints

• 1 <= capacity <= 3000
• 0 <= id <= 10^4
• 0 <= size <= 10^5
• At most 2 * 10^5 calls.