Cache Behavior

• Each cache entry maps one dasherId to one deliveryId.
• Calling put makes the dasher the most recently updated entry.
• Calling get does not change the entry's update order.
• If an insertion causes the cache size to exceed its capacity, remove the dasher whose entry was updated least recently.

Methods

Initialize Cache

void init(int capacity)

Add or Update Delivery

void put(int dasherId, int deliveryId)

• If dasherId is not in the cache, add it with the given deliveryId.
• If dasherId is already in the cache, replace its current delivery with deliveryId.
• The inserted or updated dasher becomes the most recently updated entry.
• If the cache exceeds its capacity, remove the least recently updated entry.

Get Most Recent Delivery

int get(int dasherId)

• Return the stored deliveryId for dasherId.
• Return -1 if dasherId is not in the cache.
• This operation does not change the update order of any cache entry.

Important Difference from an LRU Cache

Constraints

• 1 ≤ capacity ≤ 100,000
• 1 ≤ dasherId ≤ 1,000,000,000
• 1 ≤ deliveryId ≤ 1,000,000,000
• init is called exactly once before any call to put or get.

Examples

Example 1: Reading an Entry Does Not Protect It from Eviction

1. init(capacity = 2)
2. put(dasherId = 11, deliveryId = 701)
3. put(dasherId = 22, deliveryId = 702)
4. get(dasherId = 11) returns 701
5. put(dasherId = 33, deliveryId = 703)
6. get(dasherId = 11) returns -1
7. get(dasherId = 22) returns 702

Example 2: Updating an Existing Dasher Changes Its Order

1. init(capacity = 2)
2. put(dasherId = 40, deliveryId = 810)
3. put(dasherId = 50, deliveryId = 820)
4. put(dasherId = 40, deliveryId = 830)
5. put(dasherId = 60, deliveryId = 840)
6. get(dasherId = 40) returns 830
7. get(dasherId = 50) returns -1
8. get(dasherId = 60) returns 840

Example 3: Capacity of One

1. init(capacity = 1)
2. put(dasherId = 7, deliveryId = 901)
3. get(dasherId = 7) returns 901
4. put(dasherId = 8, deliveryId = 902)
5. get(dasherId = 7) returns -1
6. get(dasherId = 8) returns 902