Simulate a Least Recently Used cache of the given capacity. ops is a list of operations, each ["put", key, value] or ["get", key]. Return the result of every get (-1 when the key is missing). put on a full cache evicts the key that was used longest ago. Both operations must be O(1): a hash map for lookup plus a doubly linked list ordered by recency.
Patterns: hashing, linked-list, design. Difficulty: medium.