Designing data structures

package main
 
import (
	"fmt"
	"strings"
	"sync"
)
 
type entry[K comparable, V any] struct {
	key        K
	val        V
	prev, next *entry[K, V]
}
 
// LRU is a fixed-capacity cache, safe for concurrent use.
type LRU[K comparable, V any] struct {
	mu    sync.Mutex
	cap   int
	items map[K]*entry[K, V]
	head  entry[K, V] // sentinel: head.next is the most recent, head.prev the least
}
 
func NewLRU[K comparable, V any](capacity int) *LRU[K, V] {
	c := &LRU[K, V]{cap: capacity, items: make(map[K]*entry[K, V], capacity)}
	c.head.next, c.head.prev = &c.head, &c.head // an empty circle
	return c
}
 
func (c *LRU[K, V]) unlink(e *entry[K, V]) { e.prev.next, e.next.prev = e.next, e.prev }
 
func (c *LRU[K, V]) pushFront(e *entry[K, V]) {
	e.prev, e.next = &c.head, c.head.next
	c.head.next.prev = e
	c.head.next = e
}
 
func (c *LRU[K, V]) Get(k K) (V, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	e, ok := c.items[k]
	if !ok {
		var zero V
		return zero, false
	}
	c.unlink(e)
	c.pushFront(e)
	return e.val, true
}
 
func (c *LRU[K, V]) Put(k K, v V) (evicted K, didEvict bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if e, ok := c.items[k]; ok {
		e.val = v
		c.unlink(e)
		c.pushFront(e)
		return evicted, false
	}
	e := &entry[K, V]{key: k, val: v}
	c.items[k] = e
	c.pushFront(e)
	if len(c.items) > c.cap {
		last := c.head.prev
		c.unlink(last)
		delete(c.items, last.key)
		return last.key, true
	}
	return evicted, false
}
 
func (c *LRU[K, V]) String() string {
	var parts []string
	for e := c.head.next; e != &c.head; e = e.next {
		parts = append(parts, fmt.Sprintf("%v=%v", e.key, e.val))
	}
	return "[" + strings.Join(parts, " ") + "]  (most recent first)"
}
 
func main() {
	c := NewLRU[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	fmt.Println(c)
	v, ok := c.Get("a")
	fmt.Println("get a:", v, ok, c)
	k, ev := c.Put("c", 3)
	fmt.Println("put c evicts", k, ev, c)
	_, ok = c.Get("b")
	fmt.Println("get b:", ok)
 
	var wg sync.WaitGroup
	shared := NewLRU[int, int](100)
	for g := range 8 {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := range 1000 {
				shared.Put(g*1000+i, i)
				shared.Get(i)
			}
		}()
	}
	wg.Wait()
	fmt.Println("after 8 goroutines, entries:", len(shared.items))
}

[b=2 a=1]  (most recent first)
get a: 1 true [a=1 b=2]  (most recent first)
put c evicts b true [c=3 a=1]  (most recent first)
get b: false
after 8 goroutines, entries: 100

package main
 
import (
	"container/list"
	"fmt"
)
 
type lfuItem struct {
	key, val, freq int
	elem           *list.Element // position inside buckets[freq]
}
 
type LFU struct {
	cap, minFreq int
	items        map[int]*lfuItem
	buckets      map[int]*list.List // freq -> keys, front = most recent
}
 
func NewLFU(capacity int) *LFU {
	return &LFU{cap: capacity, items: map[int]*lfuItem{}, buckets: map[int]*list.List{}}
}
 
func (c *LFU) touch(it *lfuItem) {
	old := c.buckets[it.freq]
	old.Remove(it.elem)
	if old.Len() == 0 {
		delete(c.buckets, it.freq)
		if c.minFreq == it.freq {
			c.minFreq++ // the lowest bucket emptied; this key is now exactly one higher
		}
	}
	it.freq++
	if c.buckets[it.freq] == nil {
		c.buckets[it.freq] = list.New()
	}
	it.elem = c.buckets[it.freq].PushFront(it.key)
}
 
func (c *LFU) Get(k int) int {
	it, ok := c.items[k]
	if !ok {
		return -1
	}
	c.touch(it)
	return it.val
}
 
func (c *LFU) Put(k, v int) {
	if c.cap == 0 {
		return
	}
	if it, ok := c.items[k]; ok {
		it.val = v
		c.touch(it)
		return
	}
	if len(c.items) == c.cap {
		b := c.buckets[c.minFreq]
		victim := b.Remove(b.Back()).(int) // least recent among the least frequent
		if b.Len() == 0 {
			delete(c.buckets, c.minFreq)
		}
		delete(c.items, victim)
		fmt.Printf("  evict %d (freq %d)\n", victim, c.minFreq)
	}
	if c.buckets[1] == nil {
		c.buckets[1] = list.New()
	}
	c.items[k] = &lfuItem{key: k, val: v, freq: 1, elem: c.buckets[1].PushFront(k)}
	c.minFreq = 1
}
 
func main() {
	c := NewLFU(2)
	c.Put(1, 10)
	c.Put(2, 20)
	fmt.Println("get 1:", c.Get(1)) // key 1 now has freq 2
	fmt.Println("put 3:")
	c.Put(3, 30) // evicts 2 (freq 1)
	fmt.Println("get 2:", c.Get(2), " get 3:", c.Get(3))
	fmt.Println("put 4:")
	c.Put(4, 40) // 1 and 3 both have freq 2; 1 was used less recently
	fmt.Println("get 1:", c.Get(1), " get 3:", c.Get(3), " get 4:", c.Get(4))
}

get 1: 10
put 3:
  evict 2 (freq 1)
get 2: -1  get 3: 30
put 4:
  evict 1 (freq 2)
get 1: -1  get 3: 30  get 4: 40

package main
 
import (
	"container/heap"
	"fmt"
)
 
type Task struct {
	Name     string
	Priority int // higher runs first
	RunAt    int // earliest time it may start
	seq      int // submission order, for FIFO among equal priorities
}
 
type readyQ []*Task
 
func (q readyQ) Len() int { return len(q) }
func (q readyQ) Less(i, j int) bool {
	if q[i].Priority != q[j].Priority {
		return q[i].Priority > q[j].Priority
	}
	return q[i].seq < q[j].seq
}
func (q readyQ) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *readyQ) Push(x any)   { *q = append(*q, x.(*Task)) }
func (q *readyQ) Pop() any {
	old := *q
	t := old[len(old)-1]
	*q = old[:len(old)-1]
	return t
}
 
type delayQ []*Task
 
func (q delayQ) Len() int           { return len(q) }
func (q delayQ) Less(i, j int) bool { return q[i].RunAt < q[j].RunAt }
func (q delayQ) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q *delayQ) Push(x any)        { *q = append(*q, x.(*Task)) }
func (q *delayQ) Pop() any {
	old := *q
	t := old[len(old)-1]
	*q = old[:len(old)-1]
	return t
}
 
type Scheduler struct {
	ready   readyQ
	delayed delayQ
	seq     int
}
 
func (s *Scheduler) Submit(t *Task) {
	s.seq++
	t.seq = s.seq
	heap.Push(&s.delayed, t)
}
 
// Next returns the task to run at time now, or nil if nothing is ready.
func (s *Scheduler) Next(now int) *Task {
	for s.delayed.Len() > 0 && s.delayed[0].RunAt <= now {
		heap.Push(&s.ready, heap.Pop(&s.delayed)) // its time has come
	}
	if s.ready.Len() == 0 {
		return nil
	}
	return heap.Pop(&s.ready).(*Task)
}
 
func main() {
	var s Scheduler
	s.Submit(&Task{Name: "send newsletter", Priority: 1})
	s.Submit(&Task{Name: "resize images", Priority: 5})
	s.Submit(&Task{Name: "charge card", Priority: 9})
	s.Submit(&Task{Name: "nightly report", Priority: 9, RunAt: 3})
	s.Submit(&Task{Name: "thumbnail", Priority: 5})
 
	for now := 0; now < 6; now++ {
		if t := s.Next(now); t != nil {
			fmt.Printf("t=%d run %-15s (priority %d)\n", now, t.Name, t.Priority)
		} else {
			fmt.Printf("t=%d idle\n", now)
		}
	}
}

t=0 run charge card     (priority 9)
t=1 run resize images   (priority 5)
t=2 run thumbnail       (priority 5)
t=3 run nightly report  (priority 9)
t=4 run send newsletter (priority 1)
t=5 idle

package main
 
import (
	"fmt"
	"math/rand/v2"
	"sort"
)
 
type RandomizedSet struct {
	vals []int
	idx  map[int]int
	rng  *rand.Rand
}
 
func NewRandomizedSet() *RandomizedSet {
	return &RandomizedSet{idx: map[int]int{}, rng: rand.New(rand.NewPCG(1, 2))}
}
 
func (s *RandomizedSet) Insert(v int) bool {
	if _, ok := s.idx[v]; ok {
		return false
	}
	s.idx[v] = len(s.vals)
	s.vals = append(s.vals, v)
	return true
}
 
func (s *RandomizedSet) Remove(v int) bool {
	i, ok := s.idx[v]
	if !ok {
		return false
	}
	last := s.vals[len(s.vals)-1]
	s.vals[i] = last // move the last element into the hole
	s.idx[last] = i
	s.vals = s.vals[:len(s.vals)-1]
	delete(s.idx, v)
	return true
}
 
func (s *RandomizedSet) Random() int { return s.vals[s.rng.IntN(len(s.vals))] }
 
type versioned struct {
	ts  int
	val string
}
 
type TimeMap map[string][]versioned
 
func (m TimeMap) Set(k, v string, ts int) { m[k] = append(m[k], versioned{ts, v}) }
 
func (m TimeMap) Get(k string, ts int) string {
	h := m[k]
	i := sort.Search(len(h), func(i int) bool { return h[i].ts > ts }) // first entry after ts
	if i == 0 {
		return ""
	}
	return h[i-1].val
}
 
func main() {
	s := NewRandomizedSet()
	fmt.Println(s.Insert(10), s.Insert(20), s.Insert(30), s.Insert(20))
	fmt.Println(s.Remove(10), s.vals, s.idx)
	counts := map[int]int{}
	for range 6000 {
		counts[s.Random()]++
	}
	fmt.Println("roughly even picks:", counts[20] > 2700 && counts[30] > 2700)
 
	tm := TimeMap{}
	tm.Set("price", "100", 1)
	tm.Set("price", "120", 5)
	tm.Set("price", "90", 9)
	fmt.Printf("%q %q %q %q\n", tm.Get("price", 0), tm.Get("price", 4), tm.Get("price", 5), tm.Get("price", 100))
}

true true true false
true [30 20] map[20:1 30:0]
roughly even picks: true
"" "100" "120" "90"