go-05-lru-cache

# Generic LRU cache

Implement **`solution.go`** in `package challenge` exporting a generic
least-recently-used cache:

```go
type LRUCache[K comparable, V any] struct { /* unexported fields */ }

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]

func (c *LRUCache[K, V]) Get(key K) (V, bool)
func (c *LRUCache[K, V]) Put(key K, value V)
func (c *LRUCache[K, V]) Len() int
```

Behavior:

- `NewLRUCache(capacity)` creates an empty cache that holds at most `capacity`
  entries. If `capacity <= 0`, treat it as `0`: the cache stores nothing and
  `Len()` is always `0`.
- `Get(key)` returns the stored value and `true` if `key` is present, or the
  zero value of `V` and `false` otherwise. A successful `Get` counts as a
  **use**, making `key` the most-recently-used entry.
- `Put(key, value)` inserts or updates `key`. Inserting or updating makes `key`
  the most-recently-used entry. If adding a **new** key would exceed `capacity`,
  the **least-recently-used** entry is evicted first. Updating the value of an
  existing key never evicts anything.
- `Len()` returns the current number of stored entries.
- Works for any `comparable` key type and any value type (e.g. `string`/`int`
  keys, struct or pointer values).

Examples:

```go
c := NewLRUCache[string, int](2)
c.Put("a", 1)
c.Put("b", 2)
c.Get("a")        // (1, true); now "b" is least-recently-used
c.Put("c", 3)     // evicts "b"
c.Get("b")        // (0, false)
c.Len()           // 2
```

package challenge

import "testing"

func TestLRUBasicGetPut(t *testing.T) {
	c := NewLRUCache[string, int](2)
	if _, ok := c.Get("missing"); ok {
		t.Fatalf("Get on empty cache returned ok=true")
	}
	c.Put("a", 1)
	c.Put("b", 2)
	if v, ok := c.Get("a"); !ok || v != 1 {
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	if v, ok := c.Get("b"); !ok || v != 2 {
		t.Fatalf("Get(b) = (%d, %v), want (2, true)", v, ok)
	}
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2", c.Len())
	}
}

func TestLRUZeroValueOnMiss(t *testing.T) {
	c := NewLRUCache[int, string](2)
	if v, ok := c.Get(99); ok || v != "" {
		t.Fatalf("Get(miss) = (%q, %v), want (\"\", false)", v, ok)
	}
}

func TestLRUEvictsLeastRecentlyUsed(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("c", 3) // capacity 2: "a" is LRU, evicted
	if _, ok := c.Get("a"); ok {
		t.Fatalf("expected a to be evicted")
	}
	if v, ok := c.Get("b"); !ok || v != 2 {
		t.Fatalf("Get(b) = (%d, %v), want (2, true)", v, ok)
	}
	if v, ok := c.Get("c"); !ok || v != 3 {
		t.Fatalf("Get(c) = (%d, %v), want (3, true)", v, ok)
	}
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2", c.Len())
	}
}

func TestLRUGetCountsAsUse(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	if v, ok := c.Get("a"); !ok || v != 1 { // "a" now most-recently-used
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	c.Put("c", 3) // "b" is LRU now, should be evicted
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted (Get should have refreshed a)")
	}
	if v, ok := c.Get("a"); !ok || v != 1 {
		t.Fatalf("Get(a) = (%d, %v), want (1, true)", v, ok)
	}
	if v, ok := c.Get("c"); !ok || v != 3 {
		t.Fatalf("Get(c) = (%d, %v), want (3, true)", v, ok)
	}
}

func TestLRUUpdateExistingKey(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("a", 100) // update value, refresh a; no eviction
	if c.Len() != 2 {
		t.Fatalf("Len = %d, want 2 (update must not evict)", c.Len())
	}
	if v, ok := c.Get("a"); !ok || v != 100 {
		t.Fatalf("Get(a) = (%d, %v), want (100, true)", v, ok)
	}
	c.Put("c", 3) // "b" is LRU, evicted
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted after updating a then inserting c")
	}
}

func TestLRUUpdateRefreshesRecency(t *testing.T) {
	c := NewLRUCache[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("a", 10) // refresh "a" via update => "b" becomes LRU
	c.Put("c", 3)  // evicts "b"
	if _, ok := c.Get("b"); ok {
		t.Fatalf("expected b to be evicted; updating a should refresh its recency")
	}
	if v, ok := c.Get("a"); !ok || v != 10 {
		t.Fatalf("Get(a) = (%d, %v), want (10, true)", v, ok)
	}
}

func TestLRUCapacityOne(t *testing.T) {
	c := NewLRUCache[int, int](1)
	c.Put(1, 10)
	c.Put(2, 20) // evicts 1
	if _, ok := c.Get(1); ok {
		t.Fatalf("expected key 1 evicted in capacity-1 cache")
	}
	if v, ok := c.Get(2); !ok || v != 20 {
		t.Fatalf("Get(2) = (%d, %v), want (20, true)", v, ok)
	}
	if c.Len() != 1 {
		t.Fatalf("Len = %d, want 1", c.Len())
	}
}

func TestLRUZeroCapacity(t *testing.T) {
	c := NewLRUCache[string, int](0)
	c.Put("a", 1)
	if _, ok := c.Get("a"); ok {
		t.Fatalf("zero-capacity cache must store nothing")
	}
	if c.Len() != 0 {
		t.Fatalf("Len = %d, want 0", c.Len())
	}
}

func TestLRUStringValues(t *testing.T) {
	c := NewLRUCache[int, string](3)
	c.Put(1, "one")
	c.Put(2, "two")
	c.Put(3, "three")
	c.Get(1) // refresh 1
	c.Put(4, "four") // evicts 2 (LRU)
	if _, ok := c.Get(2); ok {
		t.Fatalf("expected key 2 evicted")
	}
	for _, want := range []struct {
		k int
		v string
	}{{1, "one"}, {3, "three"}, {4, "four"}} {
		if v, ok := c.Get(want.k); !ok || v != want.v {
			t.Errorf("Get(%d) = (%q, %v), want (%q, true)", want.k, v, ok, want.v)
		}
	}
}

func TestLRUEvictionChain(t *testing.T) {
	c := NewLRUCache[int, int](3)
	for i := 0; i < 6; i++ {
		c.Put(i, i*i)
	}
	// Only the last 3 inserts survive: 3,4,5.
	for _, k := range []int{0, 1, 2} {
		if _, ok := c.Get(k); ok {
			t.Errorf("expected key %d evicted", k)
		}
	}
	for _, k := range []int{3, 4, 5} {
		if v, ok := c.Get(k); !ok || v != k*k {
			t.Errorf("Get(%d) = (%d, %v), want (%d, true)", k, v, ok, k*k)
		}
	}
	if c.Len() != 3 {
		t.Fatalf("Len = %d, want 3", c.Len())
	}
}

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```go
package challenge

type LRUCache[K comparable, V any] struct {
    capacity int
    items  map[K]*listNode[K, V]
    list   *doublyLinkedList[K, V]
}

type listNode[K comparable, V any] struct {
    key   K
    value V
    prev  *listNode[K, V]
    next  *listNode[K, V]
}

type doublyLinkedList[K comparable, V any] struct {
    head *listNode[K, V]
    tail *listNode[K, V]
}

func (l *doublyLinkedList[K, V]) pushBack(node *listNode[K, V]) {
    if l.tail == nil {
        l.head = node
        l.tail = node
    } else {
        l.tail.next = node
        node.prev = l.tail
        l.tail = node
    }
}

func (l *doublyLinkedList[K, V]) remove(node *listNode[K, V]) {
    if node.prev != nil {
        node.prev.next = node.next
    } else {
        l.head = node.next
    }
    
    if node.next != nil {
        node.next.prev = node.prev
    } else {
        l.tail = node.prev
    }
}

func (l *doublyLinkedList[K, V]) popFront() *listNode[K, V] {
    if l.head == nil {
        return nil
    }
    
    node := l.head
    l.head = node.next
    
    if l.head != nil {
        l.head.prev = nil
    } else {
        l.tail = nil
    }
    
    return node
}

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
    if capacity <= 0 {
        capacity = 0
    }
    
    return &LRUCache[K, V]{
        capacity: capacity,
        items:    make(map[K]*listNode[K, V]),
        list:     &doublyLinkedList[K, V]{},
    }
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
    node, exists := c.items[key]
    if !exists {
        var zero V
        return zero, false
    }
    
    // Move to end (most recently used)
    c.list.remove(node)
    c.list.pushBack(node)
    
    return node.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
    node, exists := c.items[key]
    if exists {
        // Update existing
        node.value = value
        c.list.remove(node)
        c.list.pushBack(node)
        return
    }
    
    // New entry
    newNode := &listNode[K, V]{
        key:   key,
        value:   value,
    }
    
    if len(c.items) >= c.capacity {
        // Evict least recently used
        lru := c.list.popFront()
        if lru != nil {
            delete(c.items, lru.key)
        }
    }
    
    c.list.pushBack(newNode)
    c.items[key] = newNode
}

func (c *LRUCache[K, V]) Len() int {
    return len(c.items)
}
```

[
  {
    "total": 10,
    "answer": "```go\npackage challenge\n\ntype LRUCache[K comparable, V any] struct {\n    capacity int\n    items  map[K]*listNode[K, V]\n    list   *doublyLinkedList[K, V]\n}\n\ntype listNode[K comparable, V any] struct {\n    key   K\n    value V\n    prev  *listNode[K, V]\n    next  *listNode[K, V]\n}\n\ntype doublyLinkedList[K comparable, V any] struct {\n    head *listNode[K, V]\n    tail *listNode[K, V]\n}\n\nfunc (l *doublyLinkedList[K, V]) pushBack(node *listNode[K, V]) {\n    if l.tail == nil {\n        l.head = node\n        l.tail = node\n    } else {\n        l.tail.next = node\n        node.prev = l.tail\n        l.tail = node\n    }\n}\n\nfunc (l *doublyLinkedList[K, V]) remove(node *listNode[K, V]) {\n    if node.prev != nil {\n        node.prev.next = node.next\n    } else {\n        l.head = node.next\n    }\n    \n    if node.next != nil {\n        node.next.prev = node.prev\n    } else {\n        l.tail = node.prev\n    }\n}\n\nfunc (l *doublyLinkedList[K, V]) popFront() *listNode[K, V] {\n    if l.head == nil {\n        return nil\n    }\n    \n    node := l.head\n    l.head = node.next\n    \n    if l.head != nil {\n        l.head.prev = nil\n    } else {\n        l.tail = nil\n    }\n    \n    return node\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n    if capacity <= 0 {\n        capacity = 0\n    }\n    \n    return &LRUCache[K, V]{\n        capacity: capacity,\n        items:    make(map[K]*listNode[K, V]),\n        list:     &doublyLinkedList[K, V]{},\n    }\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n    node, exists := c.items[key]\n    if !exists {\n        var zero V\n        return zero, false\n    }\n    \n    // Move to end (most recently used)\n    c.list.remove(node)\n    c.list.pushBack(node)\n    \n    return node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n    node, exists := c.items[key]\n    if exists {\n        // Update existing\n        node.value = value\n        c.list.remove(node)\n        c.list.pushBack(node)\n        return\n    }\n    \n    // New entry\n    newNode := &listNode[K, V]{\n        key:   key,\n        value:   value,\n    }\n    \n    if len(c.items) >= c.capacity {\n        // Evict least recently used\n        lru := c.list.popFront()\n        if lru != nil {\n            delete(c.items, lru.key)\n        }\n    }\n    \n    c.list.pushBack(newNode)\n    c.items[key] = newNode\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n    return len(c.items)\n}\n```",
    "passed": 9,
    "test_error": "07-03T00:39:38.745292022+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUCapacityOne\",\"Output\":\"--- PASS: TestLRUCapacityOne (0.00s)\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745292872+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestLRUCapacityOne\",\"Elapsed\":0}\n{\"Time\":\"2026-07-03T00:39:38.745293702+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestLRUZeroCapacity\"}\n{\"Time\":\"2026-07-03T00:39:38.745294822+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUZeroCapacity\",\"Output\":\"=== RUN   TestLRUZeroCapacity\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745295772+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUZeroCapacity\",\"Output\":\"    solution_test.go:118: zero-capacity cache must store nothing\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745297652+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUZeroCapacity\",\"Output\":\"--- FAIL: TestLRUZeroCapacity (0.00s)\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745299742+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestLRUZeroCapacity\",\"Elapsed\":0}\n{\"Time\":\"2026-07-03T00:39:38.745300932+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestLRUStringValues\"}\n{\"Time\":\"2026-07-03T00:39:38.745301732+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUStringValues\",\"Output\":\"=== RUN   TestLRUStringValues\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745303612+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUStringValues\",\"Output\":\"--- PASS: TestLRUStringValues (0.00s)\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745304752+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestLRUStringValues\",\"Elapsed\":0}\n{\"Time\":\"2026-07-03T00:39:38.745305702+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestLRUEvictionChain\"}\n{\"Time\":\"2026-07-03T00:39:38.745306492+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUEvictionChain\",\"Output\":\"=== RUN   TestLRUEvictionChain\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745309082+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestLRUEvictionChain\",\"Output\":\"--- PASS: TestLRUEvictionChain (0.00s)\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745309982+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestLRUEvictionChain\",\"Elapsed\":0}\n{\"Time\":\"2026-07-03T00:39:38.745310942+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745488003+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge\\t0.001s\\n\"}\n{\"Time\":\"2026-07-03T00:39:38.745507103+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0.001}"
  },
  {
    "total": 10,
    "answer": "Looking at the failing test, it seems like there's an issue with zero capacity handling. Let me analyze what might be wrong:\n\n1. When capacity is 0, the cache should store nothing\n2. The test expects \"zero-capacity cache must store nothing\"\n\nLet me trace through what happens when we have capacity 0:\n- `Put` should not actually store anything\n- `Get` should return false for any key\n- `Len()` should always be 0\n\nThe issue is likely in how I handle the zero capacity case. When capacity is 0, I should not even attempt to add items to the list or map.\n\nLet me fix this:\n\n```go\npackage challenge\n\ntype LRUCache[K comparable, V any] struct {\n    capacity int\n    items  map[K]*listNode[K, V]\n    list   *doublyLinkedList[K, V]\n}\n\ntype listNode[K comparable, V any] struct {\n    key   K\n    value V\n    prev  *listNode[K, V]\n    next  *listNode[K, V]\n}\n\ntype doublyLinkedList[K comparable, V any] struct {\n    head *listNode[K, V]\n    tail *listNode[K, V]\n}\n\nfunc (l *doublyLinkedList[K, V]) pushBack(node *listNode[K, V]) {\n    if l.tail == nil {\n        l.head = node\n        l.tail = node\n    } else {\n        l.tail.next = node\n        node.prev = l.tail\n        l.tail = node\n    }\n}\n\nfunc (l *doublyLinkedList[K, V]) remove(node *listNode[K, V]) {\n    if node.prev != nil {\n        node.prev.next = node.next\n    } else {\n        l.head = node.next\n    }\n    \n    if node.next != nil {\n        node.next.prev = node.prev\n    } else {\n        l.tail = node.prev\n    }\n}\n\nfunc (l *doublyLinkedList[K, V]) popFront() *listNode[K, V] {\n    if l.head == nil {\n        return nil\n    }\n    \n    node := l.head\n    l.head = node.next\n    \n    if l.head != nil {\n        l.head.prev = nil\n    } else {\n        l.tail = nil\n    }\n    \n    return node\n}\n\nfunc NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {\n    if capacity <= 0 {\n        capacity = 0\n    }\n    \n    return &LRUCache[K, V]{\n        capacity: capacity,\n        items:    make(map[K]*listNode[K, V]),\n        list:     &doublyLinkedList[K, V]{},\n    }\n}\n\nfunc (c *LRUCache[K, V]) Get(key K) (V, bool) {\n    // If capacity is 0, nothing can be stored\n    if c.capacity == 0 {\n        var zero V\n        return zero, false\n    }\n    \n    node, exists := c.items[key]\n    if !exists {\n        var zero V\n        return zero, false\n    }\n    \n    // Move to end (most recently used)\n    c.list.remove(node)\n    c.list.pushBack(node)\n    \n    return node.value, true\n}\n\nfunc (c *LRUCache[K, V]) Put(key K, value V) {\n    // If capacity is 0, nothing can be stored\n    if c.capacity == 0 {\n        return\n    }\n    \n    node, exists := c.items[key]\n    if exists {\n        // Update existing\n        node.value = value\n        c.list.remove(node)\n        c.list.pushBack(node)\n        return\n    }\n    \n    // New entry\n    newNode := &listNode[K, V]{\n        key:   key,\n        value:   value,\n    }\n    \n    if len(c.items) >= c.capacity {\n        // Evict least recently used\n        lru := c.list.popFront()\n        if lru != nil {\n            delete(c.items, lru.key)\n        }\n    }\n    \n    // Only add if we haven't exceeded capacity (this handles the case where we're at capacity)\n    if len(c.items) < c.capacity {\n        c.list.pushBack(newNode)\n        c.items[key] = newNode\n    }\n}\n\nfunc (c *LRUCache[K, V]) Len() int {\n    // If capacity is 0, nothing can be stored\n    if c.capacity == 0 {\n        return 0\n    }\n    return len(c.items)\n}\n```",
    "passed": 10,
    "test_error": ""
  }
]