Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
A pipeline enriches every event by looking a customer up in a slow service. Repeated lookups for the same customer should be answered from memory. But memory is limited. So the cache keeps only the capacity keys that were used most recently, and throws away the key that has gone longest without a use.
Write run_cache(capacity, operations). It takes capacity, an integer, and operations, a list of ["put", key, value] or ["get", key] lists. It runs them in order. It returns a dict {"results": list, "keys": list}. The first is one result per get, in order (the value, or None on a miss). The second is the keys left at the end, least recently used first.
Function to write
run_cache(capacity: int, operations: list[list]) -> dictA dict with the get results in order and the final keys from least to most recently used.
How to approach it
Keep the keys in order of use. Every get that hits and every put moves its key to the newest end. When over capacity, remove from the oldest end.
Sample cases
+ 3 held back until you submit
a read protects a key
Reading `a` makes `b` the least recently used, so adding `c` evicts `b`, not `a`.
Input
Argument 1
2Argument 2
[
[
'put',
'a',
1
],
[
'put',
'b',
2
],
[
'get',
'a'
],
[
'put',
'c',
3
],
[
'get',
'b'
],
[
'get',
'a'
]
]Returns
{
'results': [
1,
None,
1
],
'keys': [
'c',
'a'
]
}an update refreshes a key
Writing `a` again counts as a use and replaces its value, so `b` is the one evicted.
Input
Argument 1
2Argument 2
[
[
'put',
'a',
1
],
[
'put',
'b',
2
],
[
'put',
'a',
10
],
[
'put',
'c',
3
],
[
'get',
'a'
],
[
'get',
'b'
]
]Returns
{
'results': [
10,
None
],
'keys': [
'c',
'a'
]
}misses return none
A get for a key that was never stored (or not yet stored) returns None and changes nothing.
Input
Argument 1
3Argument 2
[
[
'get',
'x'
],
[
'put',
'x',
5
],
[
'get',
'x'
],
[
'get',
'y'
]
]Returns
{
'results': [
None,
5,
None
],
'keys': [
'x'
]
}no operations
An unused cache has no results and no keys.
Input
Argument 1
2Argument 2
[] (empty list)
Returns
{
'results': [],
'keys': []
}Constraints
put stores the value. If the key exists, the value is replaced and the key counts as used now.get that finds the key returns its value and counts as a use. A get that misses returns None and changes nothing.put would take the cache above capacity, remove the least recently used key.capacity <= 0, nothing is ever stored: every get is a miss.results has one entry per get, in order. A put adds nothing to results.keys lists the final keys from least recently used to most recently used.OrderedDict does this; a list you search through does not.Worked example
Take capacity 2 and the operations: put a=1, put b=2, get a, put c=3, get b, get a. After the two puts the order is a (oldest), b. get a returns 1 and moves a to the newest end: order b, a. put c makes three keys, so the least recently used (b) is evicted: order a, c. get b is a miss, None. get a returns 1 and moves a to the newest end again: order c, a. The answer is {"results": [1, None, 1], "keys": ["c", "a"]}.
The trap: if a get does not count as a use, a is still the oldest when c arrives. The cache then evicts a, the key that was just read. That is a FIFO cache, not an LRU cache.
What this tests
The LRU cache, LeetCode 'LRU Cache', a classic design question. The data structure needs O(1) lookup and O(1) reordering at both ends. In an interview you may be asked to build it from a dict and a doubly linked list. In Python, OrderedDict with move_to_end and popitem(last=False) is the usual answer. Data engineers use this for lookup tables in enrichment jobs.
run_cache(capacity: int, operations: list[list]) -> dictSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.