Implement a recency cache and min-coins DP

Part 1: Least Recently Used (LRU) Cache

Design and implement a data structure for an LRU Cache. It should support the following operations:

• get(key): Return the value of the key if it exists, otherwise return -1.
• put(key, value): Update the value if the key exists, or add the key-value pair if it does not exist. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

get and put must run in O(1) average time complexity.

Part 2: Min-Coins Dynamic Programming

Given an array of coins representing different denominations and an integer amount, write a function minCoins(coins, amount) that returns the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1.

Constraints

• Capacity for LRU: 1 <= capacity <= 1000
• 1 <= amount <= 10^4
• 1 <= coins.length <= 12
• 1 <= coins[i] <= 10^4

Examples

# Part 1 Usage
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
lru.get(1)    # returns 1
lru.put(3, 3) # evicts key 2
lru.get(2)    # returns -1

# Part 2 Usage
minCoins([1, 2, 5], 11) # returns 3 (5 + 5 + 1)
minCoins([2], 3)        # returns -1