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 node[K comparable, V any] struct {
	key   K
	value V
	prev  *node[K, V]
	next  *node[K, V]
}

type LRUCache[K comparable, V any] struct {
	capacity int
	size     int
	items    map[K]*node[K, V]
	head     *node[K, V] // Most recently used
	tail     *node[K, V] // Least recently used
}

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]*node[K, V]),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	n, ok := c.items[key]
	if !ok {
		var zero V
		return zero, false
	}
	c.moveToHead(n)
	return n.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if n, ok := c.items[key]; ok {
		n.value = value
		c.moveToHead(n)
		return
	}
	
	n := &node[K, V]{key: key, value: value}
	c.items[key] = n
	c.addToHead(n)
	c.size++
	
	if c.size > c.capacity {
		c.evictTail()
	}
}

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

func (c *LRUCache[K, V]) addToHead(n *node[K, V]) {
	n.prev = nil
	n.next = c.head
	if c.head != nil {
		c.head.prev = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

func (c *LRUCache[K, V]) removeNode(n *node[K, V]) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		c.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		c.tail = n.prev
	}
}

func (c *LRUCache[K, V]) moveToHead(n *node[K, V]) {
	if n == c.head {
		return
	}
	c.removeNode(n)
	c.addToHead(n)
}

func (c *LRUCache[K, V]) evictTail() {
	if c.tail != nil {
		delete(c.items, c.tail.key)
		c.removeNode(c.tail)
		c.size--
	}
}
```

The user wants a generic LRU cache implementation in Go.

Key requirements:
1. Package name: `challenge`
2. File name: `solution.go`
3. Type: `LRUCache[K comparable, V any]`
4. Functions: `NewLRUCache`, `Get`, `Put`, `Len`
5. Behavior:
   - Capacity constraint.
   - `capacity <= 0` means empty cache.
   - `Get` updates recency.
   - `Put` updates recency.
   - Eviction of LRU item when capacity exceeded on new insert.
   - Generic types.

Implementation details:
- To achieve O(1) for Get and Put, I need:
  - A hash map (`map[K]*node`) for fast lookup.
  - A doubly linked list to maintain order of usage (most recent at head, least recent at tail).
- When `Get` is called:
  - Check map. If not found, return zero value, false.
  - If found, move node to head of list (most recent). Return value.
- When `Put` is called:
  - If key exists:
    - Update value in node.
    - Move node to head.
  - If key does not exist:
    - Create new node.
    - Add to map.
    - Add to head of list.
    - If size > capacity:
      - Remove tail node from list.
      - Remove key from map.
- Edge case: `capacity <= 0`.
  - `NewLRUCache` should handle this. If capacity is 0, `Put` does nothing, `Get` always returns false.

Let's draft the code structure.

```go
package challenge

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

type LRUCache[K comparable, V any] struct {
    capacity int
    size     int
    items    map[K]*node[K, V]
    head     *node[K, V] // Most recently used
    tail     *node[K, V] // Least recently used
}

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]*node[K, V]),
    }
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
    if c.capacity == 0 {
        var zero V
        return zero, false
    }
    
    node, ok := c.items[key]
    if !ok {
        var zero V
        return zero, false
    }
    
    c.moveToHead(node)
    return node.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
    if c.capacity == 0 {
        return
    }

    if node, ok := c.items[key]; ok {
        node.value = value
        c.moveToHead(node)
        return
    }

    newNode := &node[K, V]{key: key, value: value}
    c.items[key] = newNode
    c.addToHead(newNode)
    c.size++

    if c.size > c.capacity {
        c.evictTail()
    }
}

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

// Helper methods
func (c *LRUCache[K, V]) addToHead(n *node[K, V]) {
    if c.head == nil {
        c.head = n
        c.tail = n
    } else {
        n.next = c.head
        c.head.prev = n
        c.head = n
    }
}

func (c *LRUCache[K, V]) removeNode(n *node[K, V]) {
    if n.prev != nil {
        n.prev.next = n.next
    } else {
        c.head = n.next
    }
    if n.next != nil {
        n.next.prev = n.prev
    } else {
        c.tail = n.prev
    }
}

func (c *LRUCache[K, V]) moveToHead(n *node[K, V]) {
    if n == c.head {
        return
    }
    c.removeNode(n)
    c.addToHead(n)
}

func (c *LRUCache[K, V]) evictTail() {
    if c.tail != nil {
        delete(c.items, c.tail.key)
        c.removeNode(c.tail)
        c.size--
    }
}
```

Wait, `removeNode` logic needs to be careful with pointers.
If `n` is head, `c.head` becomes `n.next`.
If `n` is tail, `c.tail` becomes `n.prev`.
The logic inside `removeNode` looks correct.

Let's double check the `capacity <= 0` logic.
If `capacity` is 0:
- `NewLRUCache` sets capacity to 0.
- `Get` returns false immediately.
- `Put` returns immediately.
- `Len` returns 0.
This satisfies the requirement "treat it as 0: the cache stores nothing".

One detail: `NewLRUCache` signature is `func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]`.
The type parameters are inferred from usage or specified explicitly.

Let's refine the code to be clean and robust.

```go
package challenge

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

type LRUCache[K comparable, V any] struct {
	capacity int
	size     int
	items    map[K]*node[K, V]
	head     *node[K, V] // Most recently used
	tail     *node[K, V] // Least recently used
}

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]*node[K, V]),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	n, ok := c.items[key]
	if !ok {
		var zero V
		return zero, false
	}
	c.moveToHead(n)
	return n.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if n, ok := c.items[key]; ok {
		n.value = value
		c.moveToHead(n)
		return
	}
	
	n := &node[K, V]{key: key, value: value}
	c.items[key] = n
	c.addToHead(n)
	c.size++
	
	if c.size > c.capacity {
		c.evictTail()
	}
}

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

func (c *LRUCache[K, V]) addToHead(n *node[K, V]) {
	n.prev = nil
	n.next = c.head
	if c.head != nil {
		c.head.prev = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

func (c *LRUCache[K, V]) removeNode(n *node[K, V]) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		c.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		c.tail = n.prev
	}
}

func (c *LRUCache[K, V]) moveToHead(n *node[K, V]) {
	if n == c.head {
		return
	}
	c.removeNode(n)
	c.addToHead(n)
}

func (c *LRUCache[K, V]) evictTail() {
	if c.tail != nil {
		delete(c.items, c.tail.key)
		c.removeNode(c.tail)
		c.size--
	}
}
```

Wait, `addToHead` sets `n.prev = nil` and `n.next = c.head`.
If `c.head` is not nil, `c.head.prev = n`.
Then `c.head = n`.
If `c.tail` is nil (list was empty), `c.tail = n`.
This looks correct.

`removeNode`:
If `n.prev` exists, link it to `n.next`. Else `n` was head, so `c.head` becomes `n.next`.
If `n.next` exists, link it to `n.prev`. Else `n` was tail, so `c.tail` becomes `n.prev`.
This looks correct.

`evictTail`:
Delete from ma
…[8408 chars elided]…
zero, false
	}
	n, ok := c.items[key]
	if !ok {
		var zero V
		return zero, false
	}
	c.moveToHead(n)
	return n.value, true
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if n, ok := c.items[key]; ok {
		n.value = value
		c.moveToHead(n)
		return
	}
	
	n := &node[K, V]{key: key, value: value}
	c.items[key] = n
	c.addToHead(n)
	c.size++
	
	if c.size > c.capacity {
		c.evictTail()
	}
}

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

func (c *LRUCache[K, V]) addToHead(n *node[K, V]) {
	n.prev = nil
	n.next = c.head
	if c.head != nil {
		c.head.prev = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

func (c *LRUCache[K, V]) removeNode(n *node[K, V]) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		c.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		c.tail = n.prev
	}
}

func (c *LRUCache[K, V]) moveToHead(n *node[K, V]) {
	if n == c.head {
		return
	}
	c.removeNode(n)
	c.addToHead(n)
}

func (c *LRUCache[K, V]) evictTail() {
	if c.tail != nil {
		delete(c.items, c.tail.key)
		c.removeNode(c.tail)
		c.size--
	}
}
```
I'll wrap it in the requested format.

Wait, I should check if `removeNode` needs to handle the case where `n` is not in the list?
In this implementation, `removeNode` is only called on nodes that are guaranteed to be in the list (either from `moveToHead` where `n` comes from `items`, or `evictTail` where `n` is `tail`). So it's safe.

One edge case: `moveToHead` calls `removeNode` then `addToHead`.
If `n` is head, `moveToHead` returns early.
If `n` is tail, `removeNode` updates `tail` to `n.prev`. `addToHead` puts `n` at head.
Correct.

The solution seems robust.

Final check on the prompt requirements:
- `solution.go`
- `package challenge`
- `LRUCache[K comparable, V any]`
- `NewLRUCache`, `Get`, `Put`, `Len`
- Behavior matches.

I'm ready.

One small style point: `var zero V` vs `var v V`. `zero` is descriptive.
Also, `c.items` map initialization. `make(map[K]*node[K, V])` is correct.

I will provide the code block now.