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

import "container/list"

type entry[K comparable, V any] struct {
	key   K
	value V
}

type LRUCache[K comparable, V any] struct {
	capacity int
	items    map[K]*list.Element
	order    *list.List
}

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]*list.Element),
		order:    list.New(),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	if elem, ok := c.items[key]; ok {
		c.order.MoveToFront(elem)
		return elem.Value.(*entry[K, V]).value, true
	}
	var zero V
	return zero, false
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if elem, ok := c.items[key]; ok {
		elem.Value.(*entry[K, V]).value = value
		c.order.MoveToFront(elem)
		return
	}
	if len(c.items) >= c.capacity {
		oldest := c.order.Back()
		if oldest != nil {
			oldestEntry := oldest.Value.(*entry[K, V])
			delete(c.items, oldestEntry.key)
			c.order.Remove(oldest)
		}
	}
	newElem := c.order.PushFront(&entry[K, V]{key: key, value: value})
	c.items[key] = newElem
}

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

The user wants a generic LRU cache implementation in Go.
The package name should be `challenge`.
The file should be `solution.go`.
The struct is `LRUCache[K comparable, V any]`.
Methods: `NewLRUCache`, `Get`, `Put`, `Len`.

Constraints:
- Capacity <= 0 means cache stores nothing.
- `Get` updates recency.
- `Put` inserts/updates and updates recency. Evicts LRU if capacity exceeded on new insert.
- `Len` returns current size.

I'll use a doubly linked list to maintain order and a map for O(1) lookups.
Since Go doesn't have a built-in doubly linked list that supports O(1) removal by node reference easily without some boilerplate, I'll implement a simple one or use `container/list` but `container/list` doesn't allow removing by value efficiently unless we store the element pointer in the map. Actually, `container/list` stores `*Element`, so we can store `*list.Element` in the map. That's perfect.

Let's use `container/list`.
Map: `map[K]*list.Element`
List: `*list.List`
Capacity: `int`
Current size: `int` (or just `list.Len()`)

Wait, `container/list` is fine.
Let's define the struct:
```go
type LRUCache[K comparable, V any] struct {
    capacity int
    items    map[K]*list.Element
    order    *list.List
}
```
We need a value type to store in the list.
```go
type entry[K comparable, V any] struct {
    key   K
    value V
}
```
Actually, we can just store `V` in the list, but we need the key to remove from the map if we evict. So storing `struct{ key K; value V }` is better.

Let's refine:
```go
type entry[K comparable, V any] struct {
    key   K
    value V
}

type LRUCache[K comparable, V any] struct {
    capacity int
    items    map[K]*list.Element
    order    *list.List
}
```

`NewLRUCache`:
```go
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]*list.Element),
        order:    list.New(),
    }
}
```

`Get`:
```go
func (c *LRUCache[K, V]) Get(key K) (V, bool) {
    if c.capacity == 0 {
        var zero V
        return zero, false
    }
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*entry[K, V]).value, true
    }
    var zero V
    return zero, false
}
```

`Put`:
```go
func (c *LRUCache[K, V]) Put(key K, value V) {
    if c.capacity == 0 {
        return
    }
    if elem, ok := c.items[key]; ok {
        elem.Value.(*entry[K, V]).value = value
        c.order.MoveToFront(elem)
        return
    }
    if len(c.items) >= c.capacity {
        oldest := c.order.Back()
        if oldest != nil {
            oldestEntry := oldest.Value.(*entry[K, V])
            delete(c.items, oldestEntry.key)
            c.order.Remove(oldest)
        }
    }
    newElem := c.order.PushFront(&entry[K, V]{key: key, value: value})
    c.items[key] = newElem
}
```

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

Wait, `container/list` requires importing `"container/list"`.
Is there any issue with generics and `container/list`? No, it's fine.
But `elem.Value` is `interface{}`, so type assertion `.(*entry[K, V])` is needed. That's fine.

Let's double check constraints.
"If capacity <= 0, treat it as 0: the cache stores nothing and Len() is always 0."
My code handles `capacity == 0` by returning early in `Get` and `Put`, and `Len` returns `len(c.items)` which will be 0. That's correct.

One minor thing: `container/list` is standard library. I'll import it.
The package name is `challenge`.
File: `solution.go`.

Let's assemble it.

```go
package challenge

import "container/list"

type entry[K comparable, V any] struct {
	key   K
	value V
}

type LRUCache[K comparable, V any] struct {
	capacity int
	items    map[K]*list.Element
	order    *list.List
}

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]*list.Element),
		order:    list.New(),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	if elem, ok := c.items[key]; ok {
		c.order.MoveToFront(elem)
		return elem.Value.(*entry[K, V]).value, true
	}
	var zero V
	return zero, false
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if elem, ok := c.items[key]; ok {
		elem.Value.(*entry[K, V]).value = value
		c.order.MoveToFront(elem)
		return
	}
	if len(c.items) >= c.capacity {
		oldest := c.order.Back()
		if oldest != nil {
			oldestEntry := oldest.Value.(*entry[K, V])
			delete(c.items, oldestEntry.key)
			c.order.Remove(oldest)
		}
	}
	newElem := c.order.PushFront(&entry[K, V]{key: key, value: value})
	c.items[key] = newElem
}

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

Wait, should I handle the case where `capacity` is 0 in `Len()`? `len(c.items)` will be 0 because `Put` returns early. So it's fine.

Let's test mentally with the example:
`c := NewLRUCache[string, int](2)`
`c.Put("a", 1)` -> items: {"a": elem_a}, order: [a]
`c.Put("b", 2)` -> items: {"a": elem_a, "b": elem_b}, order: [b, a]
`c.Get("a")` -> moves a to front, order: [a, b], returns (1, true)
`c.Put("c", 3)` -> new key, len(items)=2 >= capacity=2. evicts back (b). items: {"a": elem_a, "c": elem_c}, order: [c, a]
`c.Get("b")` -> not in items, returns (0, false)
`c.Len()` -> 2
Matches example.

One detail: `container/list` is fine, but sometimes in coding challenges they prefer not to use `container/list` if they want a pure implementation, but it's standard library so it's perfectly acceptable. I'll stick with it. Alternatively, I could implement a simple doubly linked list to avoid imports, but `container/list` is idiomatic. I'll keep it.

Wait, is there any issue with `elem.Value.(*entry[K, V])`? In Go, type assertions on generic types work fine.
Actually, `container/list` stores `interface{}`. So `elem.Value` is `interface{}`. The assertion `.(*entry[K, V])` is valid.

Let's consider if `capacity` is 0. `NewLRUCache` sets capacity to 0. `Get` return
…[4134 chars elided]…
I'll stick with `container/list` as it's idiomatic. If I want to be safe, I can implement a simple list. It's only ~20 lines. But `container/list` is standard. I'll keep it. Actually, implementing a simple doubly linked list is trivial and avoids imports. I'll stick to `container/list` for brevity and reliability. It's fine.

Final code structure:
```go
package challenge

import "container/list"

// ... types and functions ...
```
Matches exactly.
Proceeds. 
Output generation. 
[Done] 
(Self-Correction/Refinement during generation prep)
I'll quickly verify if `container/list` is allowed. Usually yes. If not, the prompt would say "without using container/list". It doesn't.
I'll output the code. 
All good. 
```go
package challenge

import "container/list"

type entry[K comparable, V any] struct {
	key   K
	value V
}

type LRUCache[K comparable, V any] struct {
	capacity int
	items    map[K]*list.Element
	order    *list.List
}

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]*list.Element),
		order:    list.New(),
	}
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
	if c.capacity == 0 {
		var zero V
		return zero, false
	}
	if elem, ok := c.items[key]; ok {
		c.order.MoveToFront(elem)
		return elem.Value.(*entry[K, V]).value, true
	}
	var zero V
	return zero, false
}

func (c *LRUCache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if elem, ok := c.items[key]; ok {
		elem.Value.(*entry[K, V]).value = value
		c.order.MoveToFront(elem)
		return
	}
	if len(c.items) >= c.capacity {
		oldest := c.order.Back()
		if oldest != nil {
			oldestEntry := oldest.Value.(*entry[K, V])
			delete(c.items, oldestEntry.key)
			c.order.Remove(oldest)
		}
	}
	newElem := c.order.PushFront(&entry[K, V]{key: key, value: value})
	c.items[key] = newElem
}

func (c *LRUCache[K, V]) Len() int {
	return len(c.items)
}
```
Looks perfect. Output matches.✅
Proceeds. 
[Output Generation] -> *Proceeds*