Beyond Big O

Bounded LRU cache

Bounded LRU cache

Medium

Your task

  • Build a small in-memory cache with get and put.
  • A put stores or replaces the value for a key.
  • A get returns its current value or an explicit missing result.
  • Empty strings are valid values.
  • Separate caches must not share state.

Required API

  • NewCache
    func NewCache(capacity int) *Cache
  • Cache.Get
    func (c *Cache) Get(key string) (string, bool)
  • Cache.Put
    func (c *Cache) Put(key, value string)

Behavior

  • In this part capacity is positive and the number of distinct keys never exceeds it.
  • Keep the capacity constructor argument.
  • Eviction and recency behavior come in the next part.
  • Keys are valid case-sensitive ASCII identifiers, 1–32 characters.
  • Values are ASCII strings, 0–64 characters.
  • There are at most 1,000 operations per cache.
  • Use only the standard library.
Notes and example notation
  • Examples specify capacity and operations ["put", key, value] or ["get", key].
  • Each output position corresponds to one operation; put produces null.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · missing

Calls in order; values are shown as data.
CallReturns
NewCache(2)
Instance 1
instance1.Get("x")
Missing (found = false)
Test data
Input
{"capacity":2,"ops":[["get","x"]]}
Expected output
[null]

Example 2 · store and overwrite

Calls in order; values are shown as data.
CallReturns
NewCache(2)
Instance 1
instance1.Put("A", "1")
No return value
instance1.Get("A")
"1"
instance1.Put("A", "2")
No return value
instance1.Get("A")
"2"
Test data
Input
{"capacity":2,"ops":[["put","A","1"],["get","A"],["put","A","2"],["get","A"]]}
Expected output
[null,"1",null,"2"]
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…