Concurrency-Safe LRU Cache: Generics, Doubly-Linked Lists & sync.RWMutex Optimization

package main

import "fmt"

type Node struct {
	val  int
	next *Node
}

type List struct {
	head *Node
	// tracking tail separately makes InsertTail O(1); without it we'd have
	// to walk the whole list on every append
	tail *Node
}

func (l *List) InsertHead(v int) {
	n := &Node{val: v, next: l.head}
	l.head = n
	// first node ever inserted is both head and tail
	if l.tail == nil {
		l.tail = n
	}
}

func (l *List) InsertTail(v int) {
	n := &Node{val: v}
	// empty list: head and tail both need to point at the new node,
	// there's no existing tail to link from
	if l.tail == nil {
		l.head = n
		l.tail = n
		return
	}
	l.tail.next = n
	l.tail = n
}

func (l *List) Delete(v int) bool {
	// prev starts nil so deleting the head is just "no prev to relink"
	var prev *Node
	cur := l.head
	for cur != nil {
		if cur.val == v {
			if prev == nil {
				// deleting the head: no predecessor to relink, just advance head
				l.head = cur.next
			} else {
				prev.next = cur.next
			}
			// deleting the tail: tail must move back to the predecessor,
			// otherwise tail would dangle on a node no longer reachable from head
			if cur == l.tail {
				l.tail = prev
			}
			return true
		}
		prev = cur
		cur = cur.next
	}
	return false
}

func (l *List) String() string {
	s := ""
	for cur := l.head; cur != nil; cur = cur.next {
		if s != "" {
			s += " -> "
		}
		s += fmt.Sprintf("%d", cur.val)
	}
	return s
}

func main() {
	l := &List{}
	l.InsertTail(1)
	l.InsertTail(2)
	l.InsertTail(3)
	l.InsertHead(0)
	fmt.Println("After inserts:", l.String())

	l.Delete(2)
	fmt.Println("After deleting 2:", l.String())

	l.Delete(0)
	fmt.Println("After deleting head 0:", l.String())

	l.InsertTail(4)
	fmt.Println("After inserting tail 4:", l.String())
}

package main

import "fmt"

type Node struct {
	val  int
	next *Node
}

func build(vals []int) *Node {
	// keep a tail pointer so appending stays O(1) instead of walking the
	// whole list to find the end on every insert
	var head, tail *Node
	for _, v := range vals {
		n := &Node{val: v}
		if head == nil {
			head = n
			tail = n
		} else {
			tail.next = n
			tail = n
		}
	}
	return head
}

func reverse(head *Node) *Node {
	// prev trails cur by one step; once cur passes a node, prev is the
	// only link back to it, so nothing is lost even though we're about
	// to overwrite that node's forward pointer
	var prev *Node
	cur := head
	for cur != nil {
		// stash next before we clobber cur.next, or we'd lose the rest of the list
		next := cur.next
		cur.next = prev
		prev = cur
		cur = next
	}
	// when cur becomes nil, prev is sitting on the old tail, i.e. the new head
	return prev
}

func print(head *Node) string {
	s := ""
	for cur := head; cur != nil; cur = cur.next {
		if s != "" {
			s += " -> "
		}
		s += fmt.Sprintf("%d", cur.val)
	}
	return s
}

func main() {
	head := build([]int{1, 2, 3, 4, 5})
	fmt.Println("Original:", print(head))

	reversed := reverse(head)
	fmt.Println("Reversed:", print(reversed))

	// a one-node list is its own reverse; exercises the loop running exactly once
	single := build([]int{42})
	fmt.Println("Single node reversed:", print(reverse(single)))
}

package main

import "fmt"

type Node struct {
	val  int
	next *Node
}

func hasCycle(head *Node) bool {
	// Floyd's tortoise and hare: fast moves twice as fast as slow. If there's
	// a cycle, fast eventually laps slow inside the loop and they collide; if
	// the list is acyclic, fast simply runs off the end first
	slow, fast := head, head
	// checking fast and fast.next (not just fast) lets fast.next.next below
	// run safely without a nil dereference
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next
		if slow == fast {
			return true
		}
	}
	return false
}

func main() {
	// Build a clean list: 1 -> 2 -> 3 -> 4 -> nil
	n4 := &Node{val: 4}
	n3 := &Node{val: 3, next: n4}
	n2 := &Node{val: 2, next: n3}
	n1 := &Node{val: 1, next: n2}
	fmt.Println("List without cycle, hasCycle:", hasCycle(n1))

	// Introduce a cycle: n4 -> n2 (loop back)
	n4.next = n2
	fmt.Println("List with cycle (4 -> 2), hasCycle:", hasCycle(n1))

	// Single node pointing to itself: a cycle of length 1, so slow and fast
	// collide on the very first step of the loop
	self := &Node{val: 99}
	self.next = self
	fmt.Println("Single self-looping node, hasCycle:", hasCycle(self))

	// Empty list: head is nil, so the loop condition fails immediately
	// rather than needing a special-case check
	fmt.Println("Empty list, hasCycle:", hasCycle(nil))
}

package main

import "fmt"

type Node struct {
	val  int
	next *Node
}

func build(vals []int) *Node {
	// tail pointer avoids re-walking the list to find the append point
	var head, tail *Node
	for _, v := range vals {
		n := &Node{val: v}
		if head == nil {
			head = n
			tail = n
		} else {
			tail.next = n
			tail = n
		}
	}
	return head
}

func middle(head *Node) *Node {
	// fast covers two nodes for every one slow covers, so when fast runs
	// out of list, slow has covered exactly half the distance -- one pass,
	// no need to count the length first
	slow, fast := head, head
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next
	}
	// for even-length lists fast runs out one step early, leaving slow on
	// the second (upper) of the two middle nodes
	return slow
}

func main() {
	odd := build([]int{1, 2, 3, 4, 5})
	fmt.Println("Odd length [1..5], middle:", middle(odd).val)

	even := build([]int{1, 2, 3, 4, 5, 6})
	fmt.Println("Even length [1..6], middle:", middle(even).val)

	single := build([]int{7})
	fmt.Println("Single node [7], middle:", middle(single).val)

	two := build([]int{10, 20})
	fmt.Println("Two nodes [10,20], middle:", middle(two).val)
}

package main

import (
	"errors"
	"fmt"
)

// a slice already grows from one end in amortized O(1), which is exactly
// the shape a stack needs -- no separate node/pointer bookkeeping required
type Stack struct {
	items []int
}

func (s *Stack) Push(v int) {
	// the end of the slice is the top of the stack
	s.items = append(s.items, v)
}

func (s *Stack) Pop() (int, error) {
	// return an error instead of panicking so callers can decide how to
	// handle "nothing to pop" rather than crashing the program
	if s.IsEmpty() {
		return 0, errors.New("stack is empty")
	}
	n := len(s.items) - 1
	v := s.items[n]
	// re-slicing to drop the last element reuses the backing array --
	// no allocation, the old last element just becomes unreachable
	s.items = s.items[:n]
	return v, nil
}

func (s *Stack) Peek() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("stack is empty")
	}
	return s.items[len(s.items)-1], nil
}

func (s *Stack) IsEmpty() bool {
	return len(s.items) == 0
}

func main() {
	s := &Stack{}
	s.Push(1)
	s.Push(2)
	s.Push(3)

	top, _ := s.Peek()
	fmt.Println("Peek:", top)

	v, _ := s.Pop()
	fmt.Println("Pop:", v)

	v, _ = s.Pop()
	fmt.Println("Pop:", v)

	fmt.Println("IsEmpty:", s.IsEmpty())

	v, _ = s.Pop()
	fmt.Println("Pop:", v)

	fmt.Println("IsEmpty:", s.IsEmpty())

	_, err := s.Pop()
	fmt.Println("Pop on empty, error:", err)
}

package main

import (
	"errors"
	"fmt"
)

type Queue struct {
	items []int
}

func (q *Queue) Enqueue(v int) {
	// new items always join at the back; combined with Dequeue reading
	// from index 0, this is what gives FIFO order (vs. a stack's LIFO)
	q.items = append(q.items, v)
}

func (q *Queue) Dequeue() (int, error) {
	if q.IsEmpty() {
		return 0, errors.New("queue is empty")
	}
	v := q.items[0]
	// re-slicing off the front is simple and correct, but note it just
	// advances the slice's start pointer -- the backing array still holds
	// the dequeued elements until the whole array is garbage collected, so
	// a long-lived, high-churn queue would want a ring buffer instead
	// (see the circular buffer example)
	q.items = q.items[1:]
	return v, nil
}

func (q *Queue) Front() (int, error) {
	if q.IsEmpty() {
		return 0, errors.New("queue is empty")
	}
	return q.items[0], nil
}

func (q *Queue) IsEmpty() bool {
	return len(q.items) == 0
}

func main() {
	q := &Queue{}
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)

	front, _ := q.Front()
	fmt.Println("Front:", front)

	v, _ := q.Dequeue()
	fmt.Println("Dequeue:", v)

	v, _ = q.Dequeue()
	fmt.Println("Dequeue:", v)

	fmt.Println("IsEmpty:", q.IsEmpty())

	v, _ = q.Dequeue()
	fmt.Println("Dequeue:", v)

	fmt.Println("IsEmpty:", q.IsEmpty())

	_, err := q.Dequeue()
	fmt.Println("Dequeue on empty, error:", err)
}

package main

import "fmt"

// StackTwoQueues implements a LIFO stack using two FIFO queues.
type StackTwoQueues struct {
	q1 []int
	q2 []int
}

// dequeue pops the front element by reslicing past index 0 (no shifting
// or copying of the remaining elements).
func dequeue(q *[]int) int {
	v := (*q)[0]
	*q = (*q)[1:]
	return v
}

// Push makes the new element the front of q1 by rotating existing
// elements through q2, keeping the most recently pushed item first.
func (s *StackTwoQueues) Push(v int) {
	s.q2 = append(s.q2, v)
	for len(s.q1) > 0 {
		s.q2 = append(s.q2, dequeue(&s.q1))
	}
	s.q1, s.q2 = s.q2, s.q1
}

// Pop is O(1) because all the reordering work happened in Push: q1 is
// always kept with the most-recently-pushed item at the front.
func (s *StackTwoQueues) Pop() int {
	return dequeue(&s.q1)
}

func (s *StackTwoQueues) IsEmpty() bool {
	return len(s.q1) == 0
}

func main() {
	s := &StackTwoQueues{}
	s.Push(1)
	s.Push(2)
	s.Push(3)

	fmt.Println("Pop:", s.Pop())
	fmt.Println("Pop:", s.Pop())

	s.Push(4)
	fmt.Println("Pop:", s.Pop())
	fmt.Println("Pop:", s.Pop())

	fmt.Println("IsEmpty:", s.IsEmpty())
}

package main

import "fmt"

// QueueTwoStacks implements a FIFO queue using two LIFO stacks.
type QueueTwoStacks struct {
	in  []int
	out []int
}

// Enqueue is always O(1): new items just pile onto in, in reverse-of-
// dequeue order, and get flipped into out lazily by shift.
func (q *QueueTwoStacks) Enqueue(v int) {
	q.in = append(q.in, v)
}

// shift moves all elements from in to out (reversing order) only when
// out is empty, so dequeue returns them in original insertion order.
func (q *QueueTwoStacks) shift() {
	if len(q.out) == 0 {
		for len(q.in) > 0 {
			n := len(q.in) - 1
			q.out = append(q.out, q.in[n])
			q.in = q.in[:n]
		}
	}
}

// Dequeue only pays the O(n) shift cost once per batch of enqueues;
// each element is moved from in to out exactly once over its lifetime,
// so the amortized cost per operation is still O(1).
func (q *QueueTwoStacks) Dequeue() int {
	q.shift()
	n := len(q.out) - 1
	v := q.out[n]
	q.out = q.out[:n]
	return v
}

func (q *QueueTwoStacks) IsEmpty() bool {
	return len(q.in) == 0 && len(q.out) == 0
}

func main() {
	q := &QueueTwoStacks{}
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)

	fmt.Println("Dequeue:", q.Dequeue())
	fmt.Println("Dequeue:", q.Dequeue())

	q.Enqueue(4)
	fmt.Println("Dequeue:", q.Dequeue())
	fmt.Println("Dequeue:", q.Dequeue())

	fmt.Println("IsEmpty:", q.IsEmpty())
}

package main

import "fmt"

type DNode struct {
	val  int
	prev *DNode
	next *DNode
}

type DoublyList struct {
	head *DNode
	tail *DNode
}

// PushBack wires n.prev up front (from the current tail) so the two
// pointer updates below only ever have to look one direction: forward
// from the old tail, or straight into head/tail if the list was empty.
func (l *DoublyList) PushBack(v int) *DNode {
	n := &DNode{val: v, prev: l.tail}
	if l.tail != nil {
		l.tail.next = n
	} else {
		// list was empty: n is both the first and last node
		l.head = n
	}
	l.tail = n
	return n
}

// PushFront is PushBack's mirror image: n.next is set from the old
// head instead of n.prev from the old tail.
func (l *DoublyList) PushFront(v int) *DNode {
	n := &DNode{val: v, next: l.head}
	if l.head != nil {
		l.head.prev = n
	} else {
		// list was empty: n is both the first and last node
		l.tail = n
	}
	l.head = n
	return n
}

// Remove is O(1) given a node pointer, unlike a singly linked list where
// you'd need to walk from head to find the predecessor first. Each side
// is patched independently: if n has no prev/next, it was the head/tail,
// so the list's head/tail pointer moves instead of a neighbor's link.
func (l *DoublyList) Remove(n *DNode) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		l.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		l.tail = n.prev
	}
}

func (l *DoublyList) Forward() string {
	s := ""
	for cur := l.head; cur != nil; cur = cur.next {
		if s != "" {
			s += " <-> "
		}
		s += fmt.Sprintf("%d", cur.val)
	}
	return s
}

// Backward walks via prev pointers instead of next - the whole reason
// to pay for a second pointer per node is to support this in O(n) instead
// of needing to reverse or re-walk from head each time.
func (l *DoublyList) Backward() string {
	s := ""
	for cur := l.tail; cur != nil; cur = cur.prev {
		if s != "" {
			s += " <-> "
		}
		s += fmt.Sprintf("%d", cur.val)
	}
	return s
}

func main() {
	l := &DoublyList{}
	l.PushBack(2)
	l.PushBack(3)
	mid := l.PushFront(1)
	l.PushBack(4)
	fmt.Println("Forward: ", l.Forward())
	fmt.Println("Backward:", l.Backward())

	l.Remove(mid)
	fmt.Println("After removing 1:")
	fmt.Println("Forward: ", l.Forward())
	fmt.Println("Backward:", l.Backward())
}

package main

import "fmt"

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

type BST struct {
	root *TreeNode
}

func (t *BST) Insert(v int) {
	t.root = insertNode(t.root, v)
}

// insertNode returns the (possibly new) subtree root so each caller on
// the way back up can rewire its left/right pointer - this is what lets
// a brand-new leaf get attached without the caller needing a nil check
// of its own. Equal values are silently dropped (no else branch), so the
// tree only ever holds one node per distinct key.
func insertNode(n *TreeNode, v int) *TreeNode {
	if n == nil {
		return &TreeNode{val: v}
	}
	if v < n.val {
		n.left = insertNode(n.left, v)
	} else if v > n.val {
		n.right = insertNode(n.right, v)
	}
	return n
}

// Search follows the same left/right comparison as insertNode but can
// be a plain loop instead of recursion: it never needs to rewire a
// pointer on the way back up, only to answer yes/no.
func (t *BST) Search(v int) bool {
	cur := t.root
	for cur != nil {
		if v == cur.val {
			return true
		} else if v < cur.val {
			cur = cur.left
		} else {
			cur = cur.right
		}
	}
	return false
}

// InOrder visits left-subtree, node, right-subtree in that order, which
// for a BST always produces keys in sorted order - that's the defining
// property this traversal is used to demonstrate.
func (t *BST) InOrder() []int {
	var result []int
	// declared separately so the closure can reference walk recursively
	var walk func(n *TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			return
		}
		walk(n.left)
		result = append(result, n.val)
		walk(n.right)
	}
	walk(t.root)
	return result
}

func main() {
	t := &BST{}
	for _, v := range []int{8, 3, 10, 1, 6, 14, 4, 7, 13} {
		t.Insert(v)
	}

	fmt.Println("In-order traversal:", t.InOrder())
	fmt.Println("Search 6:", t.Search(6))
	fmt.Println("Search 9:", t.Search(9))
	fmt.Println("Search 13:", t.Search(13))
}

package main

import (
	"container/heap"
	"fmt"
)

// MinHeap is a min-heap of ints implementing container/heap.Interface.
type MinHeap []int

func (h MinHeap) Len() int            { return len(h) }
// Less is the only line that decides min-heap vs max-heap: reporting the
// smaller element as "less" is what keeps the minimum at index 0.
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
// Push/Pop only manage the backing slice's length; they are never called
// directly. Package heap wraps them: heap.Push appends here then sifts
// the new element up, and heap.Pop swaps the root to the last slot and
// sifts down before calling this Pop - which is why it's always safe to
// take the element off the end rather than off the front.
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	v := old[n-1]
	*h = old[:n-1]
	return v
}

func main() {
	h := &MinHeap{}
	heap.Init(h)

	for _, v := range []int{5, 2, 9, 1, 7, 3} {
		heap.Push(h, v)
	}
	fmt.Println("Heap size after pushes:", h.Len())

	fmt.Print("Popped in order: ")
	for h.Len() > 0 {
		fmt.Print(heap.Pop(h), " ")
	}
	fmt.Println()

	heap.Push(h, 42)
	heap.Push(h, 10)
	fmt.Println("Min after two pushes:", (*h)[0])
}

package main

import "fmt"

type lruNode struct {
	key, val   int
	prev, next *lruNode
}

// LRUCache gives O(1) Get/Put using a map for lookup plus a doubly
// linked list to track recency: front is most-recently-used, back is
// least-recently-used and the first to be evicted.
type LRUCache struct {
	capacity   int
	items      map[int]*lruNode
	head, tail *lruNode // head = most recent, tail = least recent
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{capacity: capacity, items: make(map[int]*lruNode)}
}

// remove unlinks n from the list in O(1) - no need to search for it,
// since the map already gave us the node pointer directly.
func (c *LRUCache) remove(n *lruNode) {
	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
	}
	n.prev, n.next = nil, nil
}

// pushFront marks n as the most-recently-used entry by making it the
// new head. remove+pushFront together are how both Get and Put "touch"
// a key without duplicating the splice logic.
func (c *LRUCache) pushFront(n *lruNode) {
	n.next = c.head
	n.prev = nil
	if c.head != nil {
		c.head.prev = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

// Get is itself a "write": a successful read counts as a use, so the
// node has to move to the front or it would look stale next eviction.
func (c *LRUCache) Get(key int) (int, bool) {
	n, ok := c.items[key]
	if !ok {
		return 0, false
	}
	c.remove(n)
	c.pushFront(n)
	return n.val, true
}

func (c *LRUCache) Put(key, val int) {
	// key already present: overwrite in place and just re-touch it -
	// no eviction check needed since the map size isn't growing.
	if n, ok := c.items[key]; ok {
		n.val = val
		c.remove(n)
		c.pushFront(n)
		return
	}
	// only a genuinely new key can push us over capacity, and c.tail is
	// by construction the least-recently-used node - the one to evict.
	if len(c.items) >= c.capacity {
		lru := c.tail
		c.remove(lru)
		delete(c.items, lru.key)
	}
	n := &lruNode{key: key, val: val}
	c.items[key] = n
	c.pushFront(n)
}

func main() {
	c := NewLRUCache(2)
	c.Put(1, 100)
	c.Put(2, 200)
	v, ok := c.Get(1)
	fmt.Println("Get(1):", v, ok)

	c.Put(3, 300) // evicts key 2 (least recently used)
	_, ok = c.Get(2)
	fmt.Println("Get(2) after eviction:", ok)

	v, ok = c.Get(3)
	fmt.Println("Get(3):", v, ok)

	c.Put(4, 400) // evicts key 1 (least recently used now)
	_, ok = c.Get(1)
	fmt.Println("Get(1) after eviction:", ok)

	v, ok = c.Get(4)
	fmt.Println("Get(4):", v, ok)
}

package main

import "fmt"

type dnode struct {
	val        int
	prev, next *dnode
}

type dlist struct {
	head, tail *dnode
}

func (l *dlist) pushBack(v int) {
	n := &dnode{val: v}
	// empty list is a special case: head and tail both point at the sole node
	if l.head == nil {
		l.head, l.tail = n, n
		return
	}
	n.prev = l.tail
	l.tail.next = n
	l.tail = n
}

// a doubly linked list reverses in O(n) with no new nodes: every node already
// holds both neighbors, so reversing just means swapping each node's prev/next,
// then swapping which end of the list is called head vs tail.
func (l *dlist) reverse() {
	cur := l.head
	// flip the list's own head/tail pointers first, before touching individual nodes
	l.head, l.tail = l.tail, l.head
	for cur != nil {
		// swap this node's own prev/next so traversal direction inverts locally
		cur.prev, cur.next = cur.next, cur.prev
		cur = cur.prev // after the swap, .prev holds the old .next, so this still walks forward
	}
}

func (l *dlist) forward() []int {
	var out []int
	for n := l.head; n != nil; n = n.next {
		out = append(out, n.val)
	}
	return out
}

func (l *dlist) backward() []int {
	var out []int
	for n := l.tail; n != nil; n = n.prev {
		out = append(out, n.val)
	}
	return out
}

func main() {
	l := &dlist{}
	for _, v := range []int{1, 2, 3, 4, 5} {
		l.pushBack(v)
	}
	fmt.Println("before:", l.forward())
	l.reverse()
	fmt.Println("after: ", l.forward())
	fmt.Println("backward from tail:", l.backward())
}

package main

import "fmt"

type node struct {
	val  int
	next *node
}

// a dummy head node sidesteps the need to special-case "which list starts the
// result": we always have a node to hang tail.next off of, even before the
// first real element is chosen.
func mergeSorted(a, b *node) *node {
	dummy := &node{}
	tail := dummy
	for a != nil && b != nil {
		// splice the smaller node in directly and reuse it, rather than allocating
		// a new node and copying the value, so the merge is O(1) extra space
		if a.val <= b.val {
			tail.next = a
			a = a.next
		} else {
			tail.next = b
			b = b.next
		}
		tail = tail.next
	}
	// one list is exhausted, but the other is still sorted, so its remaining
	// tail can be attached in one shot instead of walking it node by node
	if a != nil {
		tail.next = a
	} else {
		tail.next = b
	}
	return dummy.next // skip past the dummy to return the real head
}

func build(vals []int) *node {
	dummy := &node{}
	tail := dummy
	for _, v := range vals {
		tail.next = &node{val: v}
		tail = tail.next
	}
	return dummy.next
}

func toSlice(n *node) []int {
	var out []int
	for ; n != nil; n = n.next {
		out = append(out, n.val)
	}
	return out
}

func main() {
	a := build([]int{1, 3, 5, 7})
	b := build([]int{2, 4, 6, 8, 10})
	fmt.Println("list a:", toSlice(a))
	fmt.Println("list b:", toSlice(b))
	merged := mergeSorted(a, b)
	fmt.Println("merged: ", toSlice(merged))
}

package main

import "fmt"

type node struct {
	val  int
	next *node
}

func build(vals []int) *node {
	dummy := &node{}
	tail := dummy
	for _, v := range vals {
		tail.next = &node{val: v}
		tail = tail.next
	}
	return dummy.next
}

func toSlice(n *node) []int {
	var out []int
	for ; n != nil; n = n.next {
		out = append(out, n.val)
	}
	return out
}

// removeNthFromEnd deletes the nth node counting from the end (1-indexed)
// using two pointers separated by n steps, in a single pass.
func removeNthFromEnd(head *node, n int) *node {
	// dummy precedes head so slow can end up pointing at the node *before* the
	// one to remove even when that's the real head itself (n == length)
	dummy := &node{next: head}
	fast, slow := dummy, dummy
	// walk fast n steps ahead first, so the gap between fast and slow is fixed at n
	for i := 0; i < n; i++ {
		fast = fast.next
	}
	// advance both until fast falls off the end; slow is then exactly n nodes
	// behind, i.e. sitting right before the node to delete
	for fast.next != nil {
		fast = fast.next
		slow = slow.next
	}
	slow.next = slow.next.next // unlink the target node
	return dummy.next
}

func main() {
	head := build([]int{1, 2, 3, 4, 5})
	fmt.Println("original:", toSlice(head))

	head = removeNthFromEnd(head, 2)
	fmt.Println("remove 2nd from end:", toSlice(head))

	head = removeNthFromEnd(head, 1)
	fmt.Println("remove last:", toSlice(head))

	head = removeNthFromEnd(head, 3)
	fmt.Println("remove head (3rd from end of 3):", toSlice(head))
}

package main

import "fmt"

// a fixed-size array indexed by letter is a common trie shortcut when the
// alphabet is known and small (lowercase a-z); a map[rune]*trieNode would be
// needed for arbitrary characters, at the cost of extra allocation per node
type trieNode struct {
	children [26]*trieNode
	isEnd    bool // marks "a real word ends here", distinct from "a prefix passes through here"
}

type trie struct {
	root *trieNode
}

func newTrie() *trie {
	return &trie{root: &trieNode{}}
}

func (t *trie) Insert(word string) {
	cur := t.root
	for _, c := range word {
		i := c - 'a' // map the letter directly to its slot in the 26-wide array
		if cur.children[i] == nil {
			cur.children[i] = &trieNode{} // lazily create nodes only for paths that are actually used
		}
		cur = cur.children[i]
	}
	cur.isEnd = true // only the final letter's node is flagged as a complete word
}

// find walks as far down the shared prefix path as the string allows, and is
// shared by both Search and StartsWith since they differ only in what they
// check once they reach the end of the path (isEnd vs simply existing)
func (t *trie) find(word string) *trieNode {
	cur := t.root
	for _, c := range word {
		i := c - 'a'
		if cur.children[i] == nil {
			return nil // path breaks partway through: neither a word nor a prefix exists
		}
		cur = cur.children[i]
	}
	return cur
}

func (t *trie) Search(word string) bool {
	n := t.find(word)
	// reaching the node isn't enough on its own: "gop" reaches a real node in
	// this trie (via "gopher") but was never inserted as its own word
	return n != nil && n.isEnd
}

func (t *trie) StartsWith(prefix string) bool {
	return t.find(prefix) != nil // merely existing on the path is enough, isEnd is irrelevant here
}

func main() {
	t := newTrie()
	words := []string{"go", "gopher", "golang", "goroutine", "channel"}
	for _, w := range words {
		t.Insert(w)
	}

	fmt.Println("Search(go):", t.Search("go"))
	fmt.Println("Search(gop):", t.Search("gop"))
	fmt.Println("StartsWith(gop):", t.StartsWith("gop"))
	fmt.Println("Search(golang):", t.Search("golang"))
	fmt.Println("StartsWith(chan):", t.StartsWith("chan"))
	fmt.Println("StartsWith(chart):", t.StartsWith("chart"))
	fmt.Println("Search(channel):", t.Search("channel"))
}

package main

import "fmt"

type graph struct {
	adj map[string][]string
}

func newGraph() *graph {
	return &graph{adj: make(map[string][]string)}
}

// undirected graph: every edge is recorded on both endpoints' adjacency lists
func (g *graph) addEdge(u, v string) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *graph) bfs(start string) []string {
	// start is marked visited immediately (not when dequeued) so it can never
	// be queued a second time by another node that also points to it
	visited := map[string]bool{start: true}
	queue := []string{start}
	var order []string

	for len(queue) > 0 {
		// FIFO queue is what makes this breadth-first: all nodes at the current
		// distance are visited before any node one hop further out
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)

		for _, next := range g.adj[node] {
			// mark visited at discovery time, not dequeue time, so the same
			// neighbor reached via two different paths is only queued once
			if !visited[next] {
				visited[next] = true
				queue = append(queue, next)
			}
		}
	}
	return order
}

func main() {
	g := newGraph()
	edges := [][2]string{
		{"A", "B"}, {"A", "C"}, {"B", "D"},
		{"C", "D"}, {"D", "E"}, {"E", "F"},
	}
	for _, e := range edges {
		g.addEdge(e[0], e[1])
	}

	fmt.Println("BFS from A:", g.bfs("A"))
	fmt.Println("BFS from E:", g.bfs("E"))
}

package main

import "fmt"

type graph struct {
	adj map[string][]string
}

func newGraph() *graph {
	return &graph{adj: make(map[string][]string)}
}

func (g *graph) addEdge(u, v string) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

// dfs performs an iterative depth-first traversal using an explicit stack:
// swapping bfs's queue for a LIFO stack is the only structural change needed
// to turn breadth-first into depth-first, since it's the pop order that
// decides whether we fan out sideways or plunge down one path first.
func (g *graph) dfs(start string) []string {
	visited := map[string]bool{}
	stack := []string{start}
	var order []string

	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		// unlike the BFS version, duplicates can still be pushed onto the stack
		// before being marked visited, so the check has to happen here on pop,
		// not at push time, and repeats are just skipped rather than prevented
		if visited[node] {
			continue
		}
		visited[node] = true
		order = append(order, node)

		neighbors := g.adj[node]
		// push neighbors in reverse order so that, since a stack pops last-in-
		// first-out, they still get visited in their original left-to-right order
		for i := len(neighbors) - 1; i >= 0; i-- {
			if !visited[neighbors[i]] {
				stack = append(stack, neighbors[i])
			}
		}
	}
	return order
}

func main() {
	g := newGraph()
	edges := [][2]string{
		{"A", "B"}, {"A", "C"}, {"B", "D"},
		{"C", "D"}, {"D", "E"}, {"E", "F"},
	}
	for _, e := range edges {
		g.addEdge(e[0], e[1])
	}

	fmt.Println("DFS from A:", g.dfs("A"))
	fmt.Println("DFS from E:", g.dfs("E"))
}

package main

import "fmt"

type tnode struct {
	val         int
	left, right *tnode
}

// height returns -1 as a sentinel through balanced to short-circuit
// once an imbalance is found anywhere in the subtree.
func height(n *tnode, balanced *bool) int {
	if n == nil {
		return 0
	}
	lh := height(n.left, balanced)
	rh := height(n.right, balanced)
	diff := lh - rh
	// AVL-style balance invariant: sibling subtree heights may differ
	// by at most 1, at every node, not just at the root.
	if diff < -1 || diff > 1 {
		*balanced = false
	}
	if lh > rh {
		return lh + 1
	}
	return rh + 1
}

func isBalanced(root *tnode) bool {
	balanced := true
	height(root, &balanced)
	return balanced
}

func main() {
	// Balanced tree:
	//        4
	//       / \
	//      2   6
	//     / \ / \
	//    1  3 5  7
	balancedTree := &tnode{4,
		&tnode{2, &tnode{val: 1}, &tnode{val: 3}},
		&tnode{6, &tnode{val: 5}, &tnode{val: 7}},
	}

	// Skewed / unbalanced tree: 1 -> 2 -> 3 -> 4 (all left children)
	unbalancedTree := &tnode{val: 1, left: &tnode{val: 2, left: &tnode{val: 3, left: &tnode{val: 4}}}}

	fmt.Println("balancedTree isBalanced:", isBalanced(balancedTree))
	fmt.Println("unbalancedTree isBalanced:", isBalanced(unbalancedTree))
	fmt.Println("nil tree isBalanced:", isBalanced(nil))
}

package main

import "fmt"

type tnode struct {
	val         int
	left, right *tnode
}

// levelOrder returns node values grouped level by level using a
// queue and a per-level size snapshot.
func levelOrder(root *tnode) [][]int {
	if root == nil {
		return nil
	}
	var levels [][]int
	queue := []*tnode{root}

	for len(queue) > 0 {
		// Snapshot the queue length *before* enqueuing this level's
		// children: children get pushed onto the same queue, so without
		// freezing size up front the inner loop would drift into the
		// next level instead of stopping at the current one.
		size := len(queue)
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			// Dequeue from the front (FIFO) so nodes are visited in the
			// order they were discovered, which is what gives BFS its
			// level-by-level shape.
			n := queue[0]
			queue = queue[1:]
			level = append(level, n.val)
			if n.left != nil {
				queue = append(queue, n.left)
			}
			if n.right != nil {
				queue = append(queue, n.right)
			}
		}
		levels = append(levels, level)
	}
	return levels
}

func main() {
	root := &tnode{1,
		&tnode{2, &tnode{val: 4}, &tnode{val: 5}},
		&tnode{3, nil, &tnode{val: 6}},
	}

	for i, level := range levelOrder(root) {
		fmt.Printf("level %d: %v\n", i, level)
	}
}

package main

import "fmt"

type tnode struct {
	val         int
	left, right *tnode
}

func insert(root *tnode, v int) *tnode {
	if root == nil {
		return &tnode{val: v}
	}
	if v < root.val {
		root.left = insert(root.left, v)
	} else {
		// Duplicates fall through to the right subtree; this input
		// has no repeats, so it doesn't matter here, but the ordering
		// invariant the LCA search below relies on still holds either way.
		root.right = insert(root.right, v)
	}
	return root
}

// lowestCommonAncestor exploits the BST ordering property: the LCA is the
// first node where p and q's values fall on opposite sides (or match it).
func lowestCommonAncestor(root *tnode, p, q int) *tnode {
	cur := root
	for cur != nil {
		switch {
		case p < cur.val && q < cur.val:
			cur = cur.left
		case p > cur.val && q > cur.val:
			cur = cur.right
		default:
			// p and q no longer agree on a side (one is <= cur.val and
			// the other is >=), or cur itself equals one of them: this
			// is the deepest node both still descend from, so it's the LCA.
			return cur
		}
	}
	return nil
}

func main() {
	var root *tnode
	for _, v := range []int{8, 3, 10, 1, 6, 14, 4, 7, 13} {
		root = insert(root, v)
	}

	lca1 := lowestCommonAncestor(root, 4, 7)
	fmt.Println("LCA(4, 7):", lca1.val)

	lca2 := lowestCommonAncestor(root, 1, 7)
	fmt.Println("LCA(1, 7):", lca2.val)

	lca3 := lowestCommonAncestor(root, 3, 14)
	fmt.Println("LCA(3, 14):", lca3.val)

	lca4 := lowestCommonAncestor(root, 13, 14)
	fmt.Println("LCA(13, 14):", lca4.val)
}

package main

import "fmt"

// ringBuffer is a fixed-capacity circular buffer. When full, Push
// overwrites the oldest element rather than rejecting the write.
type ringBuffer struct {
	data []int
	head int // index of oldest element
	size int
	cap  int
}

func newRingBuffer(capacity int) *ringBuffer {
	return &ringBuffer{data: make([]int, capacity), cap: capacity}
}

func (r *ringBuffer) Push(v int) {
	// tail is derived from head+size (mod cap) instead of stored
	// separately, and size is tracked explicitly rather than inferred
	// from head==tail, because head==tail alone can't tell an empty
	// buffer apart from a full one.
	tail := (r.head + r.size) % r.cap
	r.data[tail] = v
	if r.size < r.cap {
		r.size++
	} else {
		// full: overwrite oldest, advance head
		r.head = (r.head + 1) % r.cap
	}
}

func (r *ringBuffer) Pop() (int, bool) {
	if r.size == 0 {
		return 0, false
	}
	v := r.data[r.head]
	r.head = (r.head + 1) % r.cap
	r.size--
	return v, true
}

func (r *ringBuffer) Snapshot() []int {
	out := make([]int, 0, r.size)
	for i := 0; i < r.size; i++ {
		out = append(out, r.data[(r.head+i)%r.cap])
	}
	return out
}

func main() {
	rb := newRingBuffer(3)
	rb.Push(1)
	rb.Push(2)
	rb.Push(3)
	fmt.Println("after pushing 1,2,3:", rb.Snapshot())

	rb.Push(4) // overwrites 1 (oldest)
	fmt.Println("after pushing 4 (full, overwrite oldest):", rb.Snapshot())

	v, ok := rb.Pop()
	fmt.Println("pop:", v, ok)
	fmt.Println("after pop:", rb.Snapshot())

	rb.Push(5)
	rb.Push(6)
	fmt.Println("after pushing 5,6:", rb.Snapshot())
}

package main

import "fmt"

// unionFind implements disjoint-set with path compression and union by rank.
type unionFind struct {
	parent []int
	rank   []int
	count  int // number of distinct sets
}

func newUnionFind(n int) *unionFind {
	uf := &unionFind{parent: make([]int, n), rank: make([]int, n), count: n}
	for i := range uf.parent {
		uf.parent[i] = i
	}
	return uf
}

func (uf *unionFind) Find(x int) int {
	if uf.parent[x] != x {
		// path compression: rewire x straight to the set's root as we
		// unwind, so every future Find along this path is O(1) instead
		// of re-walking the same chain
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) Union(a, b int) bool {
	ra, rb := uf.Find(a), uf.Find(b)
	if ra == rb {
		return false
	}
	// Union by rank: always hang the shorter (or equal) tree under the
	// taller one's root, so ra ends up the root either way. This keeps
	// tree depth logarithmic instead of letting chains of unions build
	// a long, slow-to-Find spine. Rank only grows when two trees of
	// equal height merge, since that's the one case that increases the
	// worst-case depth of the result.
	switch {
	case uf.rank[ra] < uf.rank[rb]:
		ra, rb = rb, ra
	case uf.rank[ra] == uf.rank[rb]:
		uf.rank[ra]++
	}
	uf.parent[rb] = ra
	uf.count--
	return true
}

func (uf *unionFind) Connected(a, b int) bool {
	return uf.Find(a) == uf.Find(b)
}

func main() {
	uf := newUnionFind(10)

	edges := [][2]int{{0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {7, 8}}
	for _, e := range edges {
		uf.Union(e[0], e[1])
	}

	fmt.Println("Connected(0, 2):", uf.Connected(0, 2))
	fmt.Println("Connected(0, 3):", uf.Connected(0, 3))
	fmt.Println("Connected(5, 8):", uf.Connected(5, 8))
	fmt.Println("Connected(4, 9):", uf.Connected(4, 9))
	fmt.Println("distinct sets before merging 2-3:", uf.count)

	uf.Union(2, 3)
	fmt.Println("Connected(0, 4) after union(2,3):", uf.Connected(0, 4))
	fmt.Println("distinct sets after merging 2-3:", uf.count)
}

package main

import (
	"fmt"
	"math"
)

type tnode struct {
	val         int
	left, right *tnode
}

// isValidBST checks the BST invariant by threading a valid (min, max)
// range down through the recursion instead of just comparing children.
func isValidBST(n *tnode, min, max int) bool {
	if n == nil {
		return true
	}
	if n.val <= min || n.val >= max {
		return false
	}
	// Left child inherits the same floor but its ceiling tightens to
	// n.val; the right child inherits the same ceiling but its floor
	// rises to n.val. That's how every deeper node stays constrained
	// by every ancestor above it, not just its direct parent.
	return isValidBST(n.left, min, n.val) && isValidBST(n.right, n.val, max)
}

func validate(root *tnode) bool {
	// Root has no ancestors yet, so seed the range with the widest
	// possible bounds instead of a sentinel like 0 that could collide
	// with a real node value.
	return isValidBST(root, math.MinInt, math.MaxInt)
}

func main() {
	// Valid BST:
	//        5
	//       / \
	//      3   8
	//     / \   \
	//    1   4   9
	valid := &tnode{5,
		&tnode{3, &tnode{val: 1}, &tnode{val: 4}},
		&tnode{8, nil, &tnode{val: 9}},
	}

	// Invalid: right subtree's left child (3) satisfies "< its parent 8"
	// but violates the ancestor rule (must be > root 5), so a naive
	// "compare with immediate parent only" check would miss it.
	invalid := &tnode{5,
		&tnode{3, &tnode{val: 1}, &tnode{val: 4}},
		&tnode{8, &tnode{val: 3}, &tnode{val: 9}},
	}

	// Invalid: duplicate value equal to an ancestor.
	dup := &tnode{5,
		&tnode{val: 5},
		&tnode{val: 8},
	}

	fmt.Println("valid tree isValidBST:", validate(valid))
	fmt.Println("invalid tree isValidBST:", validate(invalid))
	fmt.Println("duplicate-value tree isValidBST:", validate(dup))
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	const n = 10
	// unbuffered: a send only completes once the other goroutine is ready to
	// receive, so this channel works as a synchronous "baton" rather than a
	// data pipe -- struct{}{} carries no payload because only the handoff
	// itself matters
	ch := make(chan struct{})
	var wg sync.WaitGroup
	wg.Add(2)

	go func() { // prints odd numbers; holds the baton first since i starts at 1
		defer wg.Done()
		for i := 1; i <= n; i += 2 {
			fmt.Println(i)
			// hand the baton to the even goroutine -- this blocks until it's
			// received, which is what pins "odd printed" before "even printed"
			ch <- struct{}{}
			if i+2 <= n {
				// only wait for the baton back if another odd number remains --
				// on the last iteration the even goroutine has already sent its
				// final number and exits without sending again, so receiving
				// unconditionally here would deadlock
				<-ch
			}
		}
	}()

	go func() { // prints even numbers; always waits for the baton before printing
		defer wg.Done()
		for i := 2; i <= n; i += 2 {
			<-ch
			fmt.Println(i)
			if i+2 <= n {
				// same guard as the odd side: don't send the baton back once
				// there's no odd number left to receive it
				ch <- struct{}{}
			}
		}
	}()

	wg.Wait()
}

package main

import "fmt"

func main() {
	const n = 10
	// two dedicated, unbuffered channels instead of one shared channel --
	// each direction of the handoff gets its own name, so which goroutine's
	// turn it is can never be ambiguous the way it would be if both sides
	// sent and received on the same channel
	oddTurn := make(chan struct{})
	evenTurn := make(chan struct{})
	// a separate completion signal is needed because main isn't one of the
	// two ping-ponging goroutines -- it has no turn channel of its own to
	// block on once the last number has been printed
	done := make(chan struct{})

	go func() { // waits for oddTurn, prints, signals evenTurn
		for i := 1; i <= n; i += 2 {
			<-oddTurn
			fmt.Println(i)
			evenTurn <- struct{}{}
		}
	}()

	go func() { // waits for evenTurn, prints, signals oddTurn (or done)
		for i := 2; i <= n; i += 2 {
			<-evenTurn
			fmt.Println(i)
			if i < n {
				oddTurn <- struct{}{}
			} else {
				// last number printed -- signal done instead of oddTurn, since
				// sending on oddTurn here would have no receiver left (the odd
				// goroutine's loop has already ended) and would block forever
				done <- struct{}{}
			}
		}
	}()

	// neither goroutine can proceed until someone sends the first token, so
	// main primes the sequence itself before waiting on the finish line
	oddTurn <- struct{}{} // kick off the first turn
	<-done
}

package main

import "fmt"

func main() {
	const items = 6
	// buffered: producer can run ahead of consumer, filling up to 3 slots
	// before it has to block on a send -- with items=6 > capacity=3 the
	// producer still catches up to the consumer partway through, so the
	// buffer smooths bursts but doesn't remove backpressure entirely
	buf := make(chan int, 3)

	go func() { // producer: only sends, never prints (avoids racing consumer's prints)
		for i := 1; i <= items; i++ {
			buf <- i
		}
		// closing tells the consumer's range loop there's nothing more coming --
		// without this close, range over buf would block forever after the
		// last value instead of exiting
		close(buf)
	}()

	for v := range buf { // consumer: sole printer, drains in FIFO order
		// a channel delivers values in the order they were sent and there's
		// exactly one goroutine printing them, so "consumed: 1..6" in order is
		// guaranteed -- there's no second reader that could steal an item out
		// of sequence
		fmt.Println("consumed:", v)
	}
	fmt.Println("done")
}

package main

import (
	"fmt"
	"sync"
)

// jobs is receive-only and results is send-only from the worker's point of
// view -- the compiler then rejects any attempt to send on jobs or read from
// results here, so a worker can only ever consume work and produce output
func worker(id int, jobs <-chan int, results chan<- [2]int, wg *sync.WaitGroup) {
	defer wg.Done()
	for j := range jobs { // exits once jobs is closed and drained, letting wg.Done fire
		results <- [2]int{j, j * j} // [job, result] pair, no printing here
	}
}

func main() {
	const numJobs = 9
	const numWorkers = 3

	// both channels sized to hold every job/result up front, so the sending
	// side (main filling jobs, workers filling results) never has to block
	// waiting on the other side to drain -- that keeps the handoff logic
	// below simple regardless of how fast workers happen to run
	jobs := make(chan int, numJobs)
	results := make(chan [2]int, numJobs)
	var wg sync.WaitGroup

	for w := 1; w <= numWorkers; w++ {
		wg.Add(1)
		// all workers read from the same jobs channel, so which worker handles
		// which job is nondeterministic (first one free grabs the next job) --
		// that's fine since nothing here depends on processing order, only on
		// the final printed order (restored below)
		go worker(w, jobs, results, &wg)
	}

	for j := 1; j <= numJobs; j++ {
		jobs <- j
	}
	close(jobs) // no more jobs -- lets each worker's range loop end once drained

	go func() {
		// closing results must wait until every worker is done sending, but
		// that can't happen on main's goroutine: main still needs to range
		// over results below, and blocking main here on wg.Wait() first would
		// make the two steps run in the wrong order relative to draining --
		// running it in its own goroutine lets results be closed the moment
		// workers finish, concurrently with main already consuming
		wg.Wait()
		close(results)
	}()

	out := make([]int, numJobs+1) // index by job number
	for r := range results { // drains in whatever order workers finished, not job order
		out[r[0]] = r[1] // stash by job number so completion order can't leak into the output
	}

	for j := 1; j <= numJobs; j++ { // single printer, strict order
		// iterating 1..numJobs here (instead of printing as results arrive)
		// is what makes the output deterministic despite the nondeterministic
		// worker scheduling above
		fmt.Printf("job %d -> %d\n", j, out[j])
	}
}

package main

import (
	"fmt"
	"sort"
	"sync"
)

// returns a receive-only channel so callers can't accidentally send on (or
// close) a channel they don't own the sending side of
func source(base int) <-chan int {
	out := make(chan int)
	go func() {
		// closing once this goroutine is done producing is what lets a
		// downstream "for range" over this channel terminate instead of
		// blocking forever after the last value
		defer close(out)
		for i := 1; i <= 3; i++ {
			out <- base + i
		}
	}()
	return out
}

func fanIn(chans ...<-chan int) <-chan int {
	merged := make(chan int)
	var wg sync.WaitGroup
	wg.Add(len(chans)) // set the full count before any forwarder starts, so Wait can't return early
	for _, c := range chans {
		// one independent forwarder goroutine per input channel -- they all
		// send to the same merged channel with no coordination between them,
		// which is exactly why the interleaving of a/b/c values is a race and
		// not reproducible run to run
		go func(c <-chan int) {
			defer wg.Done()
			for v := range c {
				merged <- v
			}
		}(c)
	}
	go func() {
		// runs in its own goroutine because it has to block on wg.Wait() until
		// every forwarder finishes -- doing that inline in fanIn would block
		// the function itself and it could never return merged to the caller
		// for draining, which the forwarders need in order to unblock their
		// sends and finish in the first place
		wg.Wait()
		close(merged) // safe: guaranteed no forwarder is still sending once wg.Wait() returns
	}()
	return merged
}

func main() {
	a := source(0)
	b := source(10)
	c := source(20)

	var all []int
	for v := range fanIn(a, b, c) { // arrival order is non-deterministic
		all = append(all, v)
	}

	sort.Ints(all) // sort before printing so output is stable every run
	fmt.Println("merged (sorted):", all)
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	const numWorkers = 5
	var wg sync.WaitGroup
	done := make([]bool, numWorkers)
	var mu sync.Mutex

	for i := 0; i < numWorkers; i++ {
		// Add(1) happens before the goroutine is started (not inside it), so
		// the counter is guaranteed to already reflect every worker by the
		// time wg.Wait() below runs, no matter how the scheduler interleaves
		// startup
		wg.Add(1)
		// i is passed in as id rather than captured from the enclosing scope --
		// each goroutine then has its own private copy of the loop value, so it
		// can't observe i having already moved on to a later iteration
		go func(id int) {
			defer wg.Done()
			// mu guards the shared done slice; each goroutine only ever writes
			// its own index so this particular write can't collide with another
			// goroutine's, but locking is the habit that keeps this code correct
			// by default rather than by coincidence of which index each worker
			// happens to touch
			mu.Lock()
			done[id] = true
			mu.Unlock()
		}(i)
	}

	wg.Wait() // blocks until all workers call Done(); also the point after which their writes to done are guaranteed visible here

	count := 0
	for _, d := range done {
		if d {
			count++
		}
	}
	fmt.Printf("%d/%d workers finished\n", count, numWorkers)
	fmt.Println("done")
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	const numGoroutines = 5
	var once sync.Once // guarantees initialize runs exactly once, even with 5 racing callers - no mutex/bool bookkeeping needed
	var wg sync.WaitGroup
	ran := make([]bool, numGoroutines) // per-goroutine slot, no shared write races

	initialize := func() {
		fmt.Println("initializing shared resource...")
	}

	for i := 0; i < numGoroutines; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			once.Do(initialize) // only the first caller actually runs initialize; the other 4 block here until it finishes, then return without re-running it
			ran[id] = true // safe to run after once.Do returns - initialization is guaranteed complete for every goroutine, not just the winner
		}(i)
	}

	wg.Wait() // without this, main could read ran before the goroutines finish writing to it

	for i, r := range ran { // single printer, strict order - main is the only reader here, so ran needs no locking of its own
		fmt.Printf("goroutine %d saw initialization complete: %v\n", i, r)
	}
}

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

func main() {
	const goroutines = 50
	const incrementsEach = 1000

	// Mutex-protected counter: mutexCounter++ is a read-modify-write, so without a lock two goroutines
	// could read the same value and both write back the same increment, losing an update
	var mu sync.Mutex
	mutexCounter := 0
	var wg1 sync.WaitGroup
	for i := 0; i < goroutines; i++ {
		wg1.Add(1)
		go func() {
			defer wg1.Done()
			for j := 0; j < incrementsEach; j++ {
				mu.Lock() // serializes access so the increment below is never split across two goroutines
				mutexCounter++
				mu.Unlock()
			}
		}()
	}
	wg1.Wait() // must finish before printing, otherwise mutexCounter could still be mid-update

	// atomic counter: same workload, but using a lock-free CPU instruction instead of a mutex -
	// cheaper than locking for a single int64 since there's no goroutine to block/wake
	var atomicCounter int64
	var wg2 sync.WaitGroup
	for i := 0; i < goroutines; i++ {
		wg2.Add(1)
		go func() {
			defer wg2.Done()
			for j := 0; j < incrementsEach; j++ {
				atomic.AddInt64(&atomicCounter, 1) // hardware-level fetch-and-add, so the increment can't be interleaved with another goroutine's
			}
		}()
	}
	wg2.Wait()

	// both print 50000 (50 goroutines * 1000 increments) - proof neither approach dropped an update
	fmt.Println("mutex counter:", mutexCounter)
	fmt.Println("atomic counter:", atomicCounter)
}

package main

import "fmt"

// generate returns immediately with an unbuffered channel; the values are produced by a goroutine
// running concurrently with whatever reads from the channel, so production and consumption overlap
func generate(n int) <-chan int {
	out := make(chan int) // unbuffered: each send blocks until square's goroutine is ready to receive it
	go func() {
		defer close(out) // closing signals "no more values" so downstream range loops terminate instead of blocking forever
		for i := 1; i <= n; i++ {
			out <- i
		}
	}()
	return out // return the receive-only end before the goroutine finishes - caller consumes as values arrive
}

// square is the middle pipeline stage: it fans values through unchanged in shape (int -> int),
// only transforming each one, so stages can chain without knowing about their neighbors' internals
func square(in <-chan int) <-chan int {
	out := make(chan int)
	go func() {
		defer close(out)
		for v := range in { // range over a channel exits automatically once in is closed and drained
			out <- v * v
		}
	}()
	return out
}

// sum is the terminal stage: it collapses the stream into a single value, sent only once the
// upstream channel is closed and every value has been accumulated
func sum(in <-chan int) <-chan int {
	out := make(chan int) // still a channel (not a plain return value) so main can block-receive the final result
	go func() {
		defer close(out)
		total := 0
		for v := range in {
			total += v
		}
		out <- total // only reached after the range loop above sees in closed, i.e. after square/generate are done
	}()
	return out
}

func main() {
	const n = 5
	// pipeline: generate 1..n -> square each -> sum all; three goroutines run concurrently, linked by
	// unbuffered channels, so values flow through the moment each stage is ready rather than in batches
	result := <-sum(square(generate(n))) // blocks until the sum goroutine sends its single final value
	fmt.Printf("sum of squares 1..%d = %d\n", n, result)
}

package main

import (
	"context"
	"fmt"
)

// worker only accepts the receive-only Done() channel via ctx - it has no way to cancel itself,
// keeping the "who can cancel" decision entirely with whoever holds the cancel function
func worker(ctx context.Context, stopped chan<- string) {
	<-ctx.Done() // Done() is closed (not sent to) on cancellation, so every waiting goroutine wakes up, not just one
	stopped <- fmt.Sprintf("worker stopped: %v", ctx.Err()) // ctx.Err() reports why it was cancelled, e.g. "context canceled" vs a deadline timeout
}

func main() {
	ctx, cancel := context.WithCancel(context.Background()) // cancel is the only handle that can close ctx.Done() - the worker never sees it
	stopped := make(chan string) // unbuffered handshake channel: lets main block until the worker has actually observed the cancellation

	go worker(ctx, stopped)

	fmt.Println("worker started")
	cancel() // cancel the context, signalling the worker to stop; safe to call more than once and from any goroutine
	fmt.Println(<-stopped) // blocks here until worker's <-ctx.Done() unblocks and it sends its message - proves the signal was received, not just sent
}

package main

import "fmt"

// a select with only one case would block until ch has a value; adding default makes the receive
// non-blocking - if no value is ready right now, default runs instead of waiting
func tryRecv(ch <-chan int, label string) {
	select {
	case v := <-ch: // only taken if a value is immediately available to receive
		fmt.Printf("%s: got value %d\n", label, v)
	default: // runs immediately when ch is empty, so the caller never stalls waiting for a sender
		fmt.Printf("%s: channel empty, moving on\n", label)
	}
}

func main() {
	ch := make(chan int, 1) // buffered so a send can complete without a receiver already waiting

	tryRecv(ch, "check 1") // channel is empty, so this hits default rather than blocking

	ch <- 42 // buffer has room, so this send returns immediately instead of waiting for a receiver
	tryRecv(ch, "check 2") // channel now has a value; the receive case fires and also drains it

	tryRecv(ch, "check 3") // value was drained by check 2, empty again - proves select/default doesn't accidentally leave the value behind
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	const n = 8
	// n+1 unbuffered channels form a chain: batons[i-1] wakes goroutine i, which then wakes i+1 via
	// batons[i] - each channel is a one-shot baton passed exactly once, never reused
	batons := make([]chan struct{}, n+1)
	for i := range batons {
		batons[i] = make(chan struct{}) // struct{}{} carries no data - the channel is used purely as a signal, not to transfer a value
	}

	var wg sync.WaitGroup
	wg.Add(n) // registered up front so main's wg.Wait() below always has the right count to wait for

	for i := 1; i <= n; i++ {
		go func(id int) {
			defer wg.Done()
			<-batons[id-1]  // blocks here - all n goroutines start immediately but only one is unblocked at a time, so they can't race each other to print
			fmt.Println(id) // this goroutine's exclusive turn to print
			if id < n {
				batons[id] <- struct{}{} // pass the baton to the next goroutine; the last goroutine (id == n) has no successor to unblock
			}
		}(i)
	}

	batons[0] <- struct{}{} // kick off goroutine 1; without this nothing would ever unblock and the program would deadlock
	wg.Wait() // blocks until all n goroutines have printed and returned, guaranteeing the full 1..n sequence lands before main exits
}

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	const numJobs = 6
	const maxConcurrent = 2

	// a buffered channel used purely for its capacity: the buffer size caps how many
	// goroutines can hold a "token" at once, so it works as a counting semaphore
	sem := make(chan struct{}, maxConcurrent)
	// pre-sized and written by index (not appended) so each goroutine can write its
	// own slot without racing with the others, no locking needed for this part
	results := make([]string, numJobs)
	var wg sync.WaitGroup

	for i := 1; i <= numJobs; i++ {
		wg.Add(1)
		// i is passed in as job (not captured directly) so each goroutine gets
		// its own private copy of the loop value to write into results with
		go func(job int) {
			defer wg.Done()
			sem <- struct{}{}        // acquire a slot in the semaphore
			// deferred (not a plain call at the end) so the slot is freed even if the
			// goroutine panics after this point, otherwise a panic would leak a token
			// and permanently shrink the effective concurrency limit
			defer func() { <-sem }() // release the slot when done

			time.Sleep(20 * time.Millisecond) // simulate work
			// writing to results[job-1] instead of appending means the final printed
			// order is job 1..N regardless of which goroutine actually finishes first
			results[job-1] = fmt.Sprintf("job %d: done (ran with at most %d jobs active)", job, maxConcurrent)
		}(i)
	}

	// blocks until every goroutine has called wg.Done(); this also establishes a
	// happens-before edge so all the writes into results above are visible here
	wg.Wait()
	fmt.Printf("semaphore capacity: %d concurrent job(s) allowed\n", maxConcurrent)
	for _, r := range results {
		fmt.Println(r)
	}
	fmt.Println("all jobs completed")
}

package main

import (
	"fmt"
	"time"
)

// fetch simulates work that takes `delay` before it has a result ready.
func fetch(delay time.Duration) <-chan string {
	// buffered with capacity 1 so the send below never blocks: if the caller
	// times out and stops listening, this goroutine can still deliver its
	// value into the buffer and exit instead of leaking forever
	out := make(chan string, 1)
	go func() {
		time.Sleep(delay)
		out <- "result ready"
	}()
	return out
}

// fetchWithTimeout waits for the fetch to finish, but gives up after `timeout`.
func fetchWithTimeout(delay, timeout time.Duration) string {
	// select blocks on both channels at once and proceeds with whichever fires
	// first, so the "fetch finished" and "timeout" cases race fairly instead
	// of one being checked before the other
	select {
	case res := <-fetch(delay):
		return res
	case <-time.After(timeout):
		// time.After starts a fresh timer each call and returns its channel;
		// no cleanup is needed here since fetchWithTimeout returns right after --
		// as of Go 1.23+ an unstopped, undrained timer is still garbage collected
		// once unreachable, so this doesn't leak the way it would have in older Go
		return "timed out waiting for result"
	}
}

func main() {
	const timeout = 50 * time.Millisecond

	fmt.Println("call A: work finishes in 10ms, timeout is 50ms")
	fmt.Println("  ->", fetchWithTimeout(10*time.Millisecond, timeout))

	fmt.Println("call B: work finishes in 200ms, timeout is 50ms")
	fmt.Println("  ->", fetchWithTimeout(200*time.Millisecond, timeout))
}

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	const numWorkers = 4
	// closing this broadcasts "stop" to every worker: a send on done could only
	// ever wake one waiting receiver, but a closed channel makes every pending
	// and future receive return immediately, so all N workers wake up together
	done := make(chan struct{})
	// indexed by id-1 (not appended) so printing in slice order below is the
	// same as worker id order, independent of the order workers actually exit
	results := make([]string, numWorkers)
	var wg sync.WaitGroup

	for i := 1; i <= numWorkers; i++ {
		wg.Add(1)
		// i passed in as id gives each goroutine its own copy to index results with
		go func(id int) {
			defer wg.Done()
			for {
				// the default case makes this select non-blocking: on each loop the
				// worker peeks at done without waiting, so it can keep "working" in
				// between checks instead of parking on the receive
				select {
				case <-done:
					results[id-1] = fmt.Sprintf("worker %d: stop signal received, exiting", id)
					return
				default:
					time.Sleep(5 * time.Millisecond) // stand-in for a unit of work; also throttles the loop so it polls done instead of spinning the CPU
				}
			}
		}(i)
	}

	time.Sleep(30 * time.Millisecond) // let workers tick for a bit
	fmt.Println("main: broadcasting stop to all workers")
	close(done) // every worker's <-done case unblocks at once

	wg.Wait()
	for _, r := range results {
		fmt.Println(r)
	}
	fmt.Println("main: all workers stopped")
}

package main

import (
	"fmt"
	"time"
)

func main() {
	const numRequests = 5

	// the ticker's channel receives a value every 10ms; that fixed cadence is
	// what enforces the rate limit below, not any locking or counting
	limiter := time.NewTicker(10 * time.Millisecond)
	// Stop releases the ticker's internal timer resource; without it the ticker
	// would keep firing in the background for the life of the program
	defer limiter.Stop()

	// sized to hold all requests up front and then closed, so it's just a
	// pre-filled queue for range to drain in order — there's no producer
	// goroutine here, so this isn't guarding against blocking sends
	requests := make(chan int, numRequests)
	for i := 1; i <= numRequests; i++ {
		requests <- i
	}
	close(requests)

	// Every request must wait for a tick before it is allowed through,
	// so actions never happen more often than one per tick.
	for req := range requests {
		// blocking receive: this is what actually paces the loop to one
		// iteration per tick instead of running as fast as possible
		<-limiter.C
		fmt.Printf("request %d: allowed through at tick\n", req)
	}
	fmt.Println("rate limiter: all requests processed, one per tick")
}

package main

import (
	"fmt"
	"sync"
)

type SafeConfig struct {
	mu    sync.RWMutex
	value int
}

func (c *SafeConfig) Read() int {
	// RLock lets any number of readers in at once (unlike a plain Mutex, which
	// would serialize them); it only blocks if a writer currently holds Lock
	c.mu.RLock()
	defer c.mu.RUnlock()
	return c.value
}

func (c *SafeConfig) Write(v int) {
	// the exclusive Lock (not RLock) is what makes this safe to mix with
	// Read: it waits for every current reader to RUnlock first, and blocks
	// any new RLock until this Unlock, so a write can never be torn or seen
	// half-applied by a concurrent read
	c.mu.Lock()
	defer c.mu.Unlock()
	c.value = v
}

func main() {
	cfg := &SafeConfig{}
	const numReaders = 4

	// Phase 1: a single writer sets the initial value.
	cfg.Write(100)
	fmt.Println("writer: set value to 100")

	// Phase 2: many readers may hold the RLock at the same time.
	// They all observe the same value since no writer runs concurrently with them.
	// reads is indexed by id-1 (not appended) purely so the printed order below
	// matches reader id order, regardless of which goroutine actually ran first
	reads := make([]string, numReaders)
	var wg sync.WaitGroup
	for i := 1; i <= numReaders; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			v := cfg.Read()
			reads[id-1] = fmt.Sprintf("reader %d: read value %d", id, v)
		}(i)
	}
	wg.Wait()
	for _, r := range reads {
		fmt.Println(r)
	}

	// Phase 3: the writer updates the value again; RWMutex ensures this
	// waits until all in-flight readers from phase 2 are done.
	// wg.Wait() above already guarantees phase 2's readers finished, so this
	// Lock call is uncontended here — the comment holds for the general case
	// where a writer arrives while readers are still active
	cfg.Write(200)
	fmt.Println("writer: set value to 200")
	fmt.Println("final read:", cfg.Read())
}

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	var mu sync.Mutex
	// a Cond is always paired with a Locker: Wait() needs the lock to check the
	// predicate (ready) safely, and Signal/Broadcast need it to change that
	// same state safely from the other goroutine
	cond := sync.NewCond(&mu)
	ready := false

	var wg sync.WaitGroup
	wg.Add(1)

	// closing this is how main confirms the waiter has actually started and
	// locked mu before main goes on to flip ready and Signal - without it main
	// could race ahead and signal before anyone is listening
	waitingPrinted := make(chan struct{})

	go func() {
		defer wg.Done()
		mu.Lock()
		fmt.Println("waiter: waiting for condition to become true")
		close(waitingPrinted)
		// cond.Wait() atomically unlocks mu and suspends the goroutine, then
		// re-locks mu before returning - that's what makes it safe to re-check
		// ready here without a lost-wakeup gap between unlocking and sleeping
		for !ready { // predicate loop guards against spurious/early wakeups
			cond.Wait()
		}
		fmt.Println("waiter: condition is true, proceeding")
		mu.Unlock()
	}()

	<-waitingPrinted                  // make sure the waiter has printed and is entering Wait
	// Wait() only guarantees the waiter reached Println/close above, not that it
	// has gotten past cond.Wait()'s internal unlock; this sleep buys it that
	// time. Unlike a channel send, a Signal delivered before Wait() begins
	// listening has no buffer to sit in and is simply lost forever
	time.Sleep(20 * time.Millisecond) // give it time to actually reach cond.Wait()

	// the state change must happen under the same lock the waiter checks
	// ready with, otherwise the waiter could observe a torn/partial update
	mu.Lock()
	ready = true
	fmt.Println("signaler: state changed, signaling waiter")
	mu.Unlock()
	// Signal wakes at most one goroutine parked in Wait (Broadcast would wake
	// all of them); called after Unlock here purely as a minor optimization so
	// the woken waiter isn't immediately blocked again re-acquiring mu
	cond.Signal()

	wg.Wait()
	fmt.Println("main: done")
}

package main

import (
	"context"
	"fmt"
	"sync"
	"time"
)

func main() {
	const numWorkers = 3
	const jobsPerWorker = 3
	// Each job has its own slot, and only the worker that owns that job ever
	// writes to it, so this needs no mutex despite being shared across goroutines.
	// Printing walks the slice by index afterward, so output order is fixed
	// by job number, not by whichever goroutine happens to finish first.
	status := make([]string, numWorkers*jobsPerWorker)

	// WithCancel gives every worker a shared ctx.Done() channel: calling cancel()
	// once closes it, and a closed channel is readable by any number of goroutines
	// at once, which is what makes it a cheap one-to-many broadcast.
	ctx, cancel := context.WithCancel(context.Background())
	var wg sync.WaitGroup

	for w := 0; w < numWorkers; w++ {
		wg.Add(1)
		go func(worker int) {
			defer wg.Done()
			for k := 0; k < jobsPerWorker; k++ {
				job := worker*jobsPerWorker + k + 1
				// The default case makes this a non-blocking poll: if ctx.Done() isn't
				// closed yet, fall straight through to the work instead of waiting on it.
				select {
				case <-ctx.Done():
					status[job-1] = fmt.Sprintf("job %d: skipped (context cancelled)", job)
					continue
				default:
				}
				time.Sleep(100 * time.Millisecond) // simulate work
				status[job-1] = fmt.Sprintf("job %d: completed", job)
			}
		}(w)
	}

	// Cancel while every worker is still busy with its first job (100ms).
	// Each worker only checks ctx.Done() *between* jobs, so job 1 always
	// finishes, but jobs 2 and 3 are skipped once cancellation lands.
	go func() {
		time.Sleep(50 * time.Millisecond)
		cancel()
	}()

	// Wait for every worker to finish writing its slots (completed or skipped)
	// before reading the slice back; without this the read here would race
	// with the still-running writes above.
	wg.Wait()
	for _, s := range status {
		fmt.Println(s)
	}
}

package main

import "fmt"

// squares returns a channel that lazily produces the squares of 1, 2, 3, ...
// It only computes and sends the next value once the consumer asks for it.
func squares(done <-chan struct{}) <-chan int {
	// Unbuffered: the goroutine below can only get one value ahead of the
	// consumer, since a send blocks until something receives it. That's what
	// makes generation "lazy" instead of racing ahead to produce every value.
	out := make(chan int)
	go func() {
		defer close(out)
		for n := 1; ; n++ {
			// Without the done case, this send would block forever once main stops
			// reading from gen, leaking this goroutine for the rest of the program.
			select {
			case out <- n * n:
				// value delivered, generator waits for next request
			case <-done:
				// A closed channel is always immediately ready to receive from, so once
				// close(done) runs, this case wins the select and the generator exits.
				return // consumer stopped listening; stop generating
			}
		}
	}()
	return out
}

func main() {
	done := make(chan struct{})
	gen := squares(done)

	// Only pull the first 5 values on demand; the generator produces them
	// one at a time and would keep going forever if we kept asking.
	for i := 0; i < 5; i++ {
		v := <-gen
		fmt.Printf("requested value %d: %d\n", i+1, v)
	}

	close(done) // tell the generator to stop producing further values
	fmt.Println("consumer: done pulling values, generator signaled to stop")
}

package main

import (
	"fmt"
	"time"
)

func source(name string, delays []time.Duration) <-chan string {
	out := make(chan string)
	go func() {
		defer close(out)
		for i, d := range delays {
			time.Sleep(d)
			out <- fmt.Sprintf("%s-%d", name, i+1)
		}
	}()
	return out
}

// mergeTwo reads from both a and b until both are closed, preserving
// whichever one becomes ready at each step.
func mergeTwo(a, b <-chan string) <-chan string {
	// A single goroutine drives this merge, so values only ever go into out
	// one at a time, in the same order select picked them up in below.
	out := make(chan string)
	go func() {
		defer close(out)
		// Loop until both source channels are nilled out below; a nil channel
		// in a select case blocks forever, so once one source is drained the
		// loop naturally keeps selecting only the other one.
		for a != nil || b != nil {
			select {
			case v, ok := <-a:
				if !ok {
					// Receiving from a closed channel never blocks and always succeeds,
					// so without nilling a out here, this case would fire on every loop
					// iteration going forward and spam zero-value strings into out.
					a = nil // stop selecting a closed channel
					continue
				}
				out <- v
			case v, ok := <-b:
				if !ok {
					b = nil // same trick: remove b from consideration once it's drained
					continue
				}
				out <- v
			}
		}
	}()
	return out
}

func main() {
	// Delays are staggered so each value becomes ready at a distinct,
	// well-separated moment, giving a deterministic merge order.
	a := source("A", []time.Duration{20 * time.Millisecond, 40 * time.Millisecond, 40 * time.Millisecond})
	b := source("B", []time.Duration{40 * time.Millisecond, 40 * time.Millisecond})

	for v := range mergeTwo(a, b) {
		fmt.Println("received:", v)
	}
	fmt.Println("both channels closed, merge complete")
}

package main

import (
	"fmt"
	"sync"
)

type Account struct {
	id      int
	mu      sync.Mutex
	balance int
}

// transfer moves amount from one account to another. If two goroutines ran
// transfers in opposite directions (A->B and B->A) and each locked "from"
// then "to", they could deadlock (each holding one lock, waiting on the
// other). The fix: always acquire the two locks in a fixed global order
// (lowest account id first), regardless of transfer direction.
func transfer(from, to *Account, amount int) {
	// Reorder by id so a transfer A->B and a concurrent transfer B->A both
	// lock the same account first. Whichever goroutine gets there first fully
	// acquires both locks before the other can grab even one, so no goroutine
	// ever waits on a lock held by something that is itself waiting on it.
	first, second := from, to
	if first.id > second.id {
		first, second = second, first
	}
	first.mu.Lock()
	defer first.mu.Unlock()
	second.mu.Lock()
	defer second.mu.Unlock()

	from.balance -= amount
	to.balance += amount
}

func main() {
	a := &Account{id: 1, balance: 500}
	b := &Account{id: 2, balance: 500}

	var wg sync.WaitGroup
	transfers := []struct {
		from, to *Account
		amount   int
	}{
		{a, b, 100}, // A -> B
		{b, a, 50},  // B -> A
		{a, b, 30},  // A -> B
		{b, a, 80},  // B -> A
	}

	for _, t := range transfers {
		wg.Add(1)
		go func(from, to *Account, amount int) {
			defer wg.Done()
			transfer(from, to, amount)
		}(t.from, t.to, t.amount)
	}

	// If transfer didn't reorder its locks, this mix of A->B and B->A transfers
	// running concurrently would be exactly the pattern that can deadlock.
	wg.Wait()
	fmt.Println("all transfers completed without deadlock (locks always acquired lowest-id first)")
	// the four transfers can run in any order relative to each other, but +=
	// and -= are commutative, so the final balances come out the same
	// regardless of that order -- it's only the deadlock risk, not the result,
	// that depends on lock ordering here
	fmt.Printf("account %d balance: %d\n", a.id, a.balance)
	fmt.Printf("account %d balance: %d\n", b.id, b.balance)
}

package main

import (
	"fmt"
	"time"
)

func main() {
	const bucketSize = 3
	const numRequests = 5

	// A buffered channel doubles as the token bucket itself: its capacity is
	// the max number of tokens that can ever be outstanding at once, and
	// sends/receives on it are already safe across goroutines with no extra
	// locking needed.
	bucket := make(chan struct{}, bucketSize)
	for i := 0; i < bucketSize; i++ {
		bucket <- struct{}{} // start with a full bucket
	}

	stopRefill := make(chan struct{})
	go func() {
		// A ticker fires on a fixed 10ms schedule, and pairing it with select lets
		// this goroutine keep listening for the stop signal between ticks instead
		// of being stuck inside a blocking time.Sleep with no way to exit early.
		ticker := time.NewTicker(10 * time.Millisecond)
		defer ticker.Stop()
		for {
			select {
			case <-ticker.C:
				// The inner select's default case makes this a non-blocking send: if the
				// bucket is already at bucketSize tokens, this refill is simply dropped
				// instead of the whole goroutine stalling on a full channel. That's what
				// actually caps the bucket at bucketSize rather than letting tokens pile
				// up unbounded.
				select {
				case bucket <- struct{}{}: // add a token if there's room
				default: // bucket full, drop the token
				}
			case <-stopRefill:
				return // closing stopRefill below lets this goroutine exit instead of leaking
			}
		}
	}()

	for i := 1; i <= numRequests; i++ {
		// Because bucket is buffered, this only blocks once it's genuinely empty:
		// requests 1-3 drain the initial fill instantly, but requests 4 and 5 each
		// have to wait for the ticker to deposit another token - that wait is the
		// rate limiting.
		<-bucket // blocks until a token is available
		fmt.Printf("request %d: granted a token\n", i)
	}

	close(stopRefill)
	fmt.Println("token bucket: all requests served, first 3 used the initial fill, the rest waited for refills")
}

package main

import (
	"fmt"
	"time"
)

// query simulates asking one of several redundant sources for the same
// answer. Each has a buffered result channel so a "losing" goroutine can
// still send its value without blocking forever (and leaking).
func query(name string, delay time.Duration) <-chan string {
	result := make(chan string, 1)
	go func() {
		time.Sleep(delay)
		result <- fmt.Sprintf("%s: answer ready", name)
	}()
	return result
}

func main() {
	// Query three redundant sources at once; take whichever answers first.
	mirrorA := query("mirror-A", 10*time.Millisecond)
	mirrorB := query("mirror-B", 50*time.Millisecond)
	mirrorC := query("mirror-C", 90*time.Millisecond)

	// select would pick fairly among cases that are ready at the same instant,
	// but the delays above are staggered widely enough that mirrorA is reliably
	// the only one ready when this runs, making the winner deterministic here
	var winner string
	select {
	case winner = <-mirrorA:
	case winner = <-mirrorB:
	case winner = <-mirrorC:
	}

	fmt.Println("first result wins:", winner)
	// mirrorB and mirrorC's goroutines are still running at this point and will
	// eventually send too, but because their result channels are buffered with
	// room for that one value, those sends complete immediately instead of
	// blocking forever with no receiver - the goroutines simply exit and their
	// unread values are garbage collected along with the channels.
	fmt.Println("the other two responses are discarded once a winner is chosen")
}

package main

import "fmt"

// twoSum returns the indices of the two numbers in nums that add up to target.
// It uses a map to record each value's index, giving O(n) time instead of O(n^2).
func twoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int) // value -> index
	for i, n := range nums {
		complement := target - n
		// check before inserting the current number: this guarantees j < i and
		// prevents pairing an element with itself when target is exactly 2*n
		if j, ok := seen[complement]; ok {
			return j, i, true
		}
		seen[n] = i
	}
	return 0, 0, false
}

func main() {
	nums := []int{2, 7, 11, 15}
	target := 9
	i, j, ok := twoSum(nums, target)
	fmt.Printf("nums=%v target=%d\n", nums, target)
	if ok {
		fmt.Printf("indices: [%d, %d] -> values %d + %d = %d\n", i, j, nums[i], nums[j], target)
	}

	nums2 := []int{3, 2, 4}
	target2 := 6
	i2, j2, ok2 := twoSum(nums2, target2)
	fmt.Printf("\nnums=%v target=%d\n", nums2, target2)
	if ok2 {
		fmt.Printf("indices: [%d, %d] -> values %d + %d = %d\n", i2, j2, nums2[i2], nums2[j2], target2)
	}

	nums3 := []int{1, 2, 3}
	target3 := 100
	_, _, ok3 := twoSum(nums3, target3)
	fmt.Printf("\nnums=%v target=%d\n", nums3, target3)
	fmt.Printf("found pair: %v\n", ok3)
}

package main

import "fmt"

// reverseString reverses a string rune by rune so multi-byte UTF-8
// characters (like accented letters or emoji) are not corrupted.
func reverseString(s string) string {
	runes := []rune(s)
	// walk from both ends toward the middle; stopping at i < j means an odd-length
	// string's middle rune is left in place instead of being swapped with itself
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func main() {
	inputs := []string{"Hello, Go!", "Golang", "héllo wörld", "日本語"}
	for _, s := range inputs {
		fmt.Printf("input:  %q\n", s)
		fmt.Printf("output: %q\n\n", reverseString(s))
	}
}

package main

import (
	"fmt"
	"unicode"
)

// isPalindrome reports whether s reads the same forwards and backwards,
// ignoring case and skipping any character that isn't a letter or digit.
func isPalindrome(s string) bool {
	runes := []rune(s)
	i, j := 0, len(runes)-1
	for i < j {
		// advance i past punctuation/spaces on its own; a continue here re-checks
		// i < j without touching j, so the two sides skip independently
		if !unicode.IsLetter(runes[i]) && !unicode.IsDigit(runes[i]) {
			i++
			continue
		}
		// same skip, mirrored for j, so unequal amounts of punctuation on each
		// side (e.g. "a," vs "a") don't throw off the alignment of the comparison
		if !unicode.IsLetter(runes[j]) && !unicode.IsDigit(runes[j]) {
			j--
			continue
		}
		if unicode.ToLower(runes[i]) != unicode.ToLower(runes[j]) {
			return false
		}
		i++
		j--
	}
	return true
}

func main() {
	inputs := []string{
		"A man, a plan, a canal: Panama",
		"race a car",
		"Was it a car or a cat I saw?",
		"12321",
	}
	for _, s := range inputs {
		fmt.Printf("input: %q -> palindrome: %v\n", s, isPalindrome(s))
	}
}

package main

import (
	"fmt"
	"unicode"
)

// isAnagram reports whether a and b contain exactly the same letters
// (case-insensitive), just rearranged, by counting rune frequencies.
func isAnagram(a, b string) bool {
	counts := make(map[rune]int)
	for _, r := range a {
		if unicode.IsSpace(r) {
			continue
		}
		counts[unicode.ToLower(r)]++
	}
	// reuse the same map and decrement for b instead of building a second map:
	// if a and b are anagrams, every letter's count nets back to exactly zero
	for _, r := range b {
		if unicode.IsSpace(r) {
			continue
		}
		counts[unicode.ToLower(r)]--
	}
	// any surviving nonzero count means that letter appeared a different
	// number of times in a than in b
	for _, c := range counts {
		if c != 0 {
			return false
		}
	}
	return true
}

func main() {
	pairs := [][2]string{
		{"listen", "silent"},
		{"Astronomer", "Moon starer"},
		{"hello", "world"},
	}
	for _, p := range pairs {
		fmt.Printf("%q vs %q -> anagram: %v\n", p[0], p[1], isAnagram(p[0], p[1]))
	}
}

package main

import "fmt"

// fizzBuzz returns the classic FizzBuzz label for n:
// "Fizz" for multiples of 3, "Buzz" for multiples of 5,
// "FizzBuzz" for multiples of both, otherwise the number itself.
func fizzBuzz(n int) string {
	switch {
	// the multiple-of-15 case must be checked first: every multiple of 15 is
	// also a multiple of 3 and 5, so checking those individually first would
	// always return early with just "Fizz" or "Buzz" and never "FizzBuzz"
	case n%15 == 0:
		return "FizzBuzz"
	case n%3 == 0:
		return "Fizz"
	case n%5 == 0:
		return "Buzz"
	default:
		return fmt.Sprintf("%d", n)
	}
}

func main() {
	for i := 1; i <= 20; i++ {
		fmt.Println(fizzBuzz(i))
	}
}

package main

import "fmt"

// binarySearch returns the index of target in a sorted slice, or -1 if
// it isn't present. It halves the search range each step: O(log n).
func binarySearch(sorted []int, target int) int {
	lo, hi := 0, len(sorted)-1
	for lo <= hi {
		// lo + (hi-lo)/2 instead of (lo+hi)/2: the latter can overflow int when
		// lo and hi are both large, even though neither alone is out of range
		mid := lo + (hi-lo)/2
		switch {
		case sorted[mid] == target:
			return mid
		case sorted[mid] < target:
			// target is to the right; mid is excluded since it's already ruled out
			lo = mid + 1
		default:
			// target is to the left; same reasoning, mid is excluded going down
			hi = mid - 1
		}
	}
	return -1
}

func main() {
	sorted := []int{1, 3, 5, 7, 9, 11, 13, 17, 19}
	targets := []int{7, 19, 1, 4}

	for _, t := range targets {
		idx := binarySearch(sorted, t)
		fmt.Printf("searching for %d in %v -> index %d\n", t, sorted, idx)
	}
}

package main

import "fmt"

// firstDuplicate scans nums left to right and returns the first value
// that has already been seen earlier in the slice, using a set for O(n).
func firstDuplicate(nums []int) (int, bool) {
	// empty struct{} as the value costs no extra memory; the map is used purely as a set
	seen := make(map[int]struct{})
	for _, n := range nums {
		// check membership before recording n, so a value doesn't count as its own duplicate
		if _, ok := seen[n]; ok {
			return n, true
		}
		seen[n] = struct{}{}
	}
	// reached the end with every value unique
	return 0, false
}

func main() {
	cases := [][]int{
		{2, 1, 3, 5, 3, 2},
		{1, 2, 3, 4},
		{7, 7, 1, 2},
	}
	for _, nums := range cases {
		dup, ok := firstDuplicate(nums)
		fmt.Printf("nums=%v -> ", nums)
		if ok {
			fmt.Printf("first duplicate: %d\n", dup)
		} else {
			fmt.Println("no duplicate found")
		}
	}
}

package main

import "fmt"

// mergeSorted merges two already-sorted slices into one sorted slice
// in O(n+m) time by walking both with two pointers.
func mergeSorted(a, b []int) []int {
	// pre-size the backing array to the combined length so append never reallocates
	merged := make([]int, 0, len(a)+len(b))
	i, j := 0, 0
	// advance whichever pointer holds the smaller front element, so merged stays sorted
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			merged = append(merged, a[i])
			i++
		} else {
			merged = append(merged, b[j])
			j++
		}
	}
	// one slice is exhausted by now; the other's remaining tail is already sorted,
	// so append it wholesale instead of comparing element by element
	merged = append(merged, a[i:]...)
	merged = append(merged, b[j:]...)
	return merged
}

func main() {
	a := []int{1, 3, 5, 7}
	b := []int{2, 4, 6, 8, 10}
	fmt.Printf("a=%v\nb=%v\nmerged=%v\n\n", a, b, mergeSorted(a, b))

	c := []int{}
	d := []int{-3, -1, 0, 2}
	fmt.Printf("a=%v\nb=%v\nmerged=%v\n", c, d, mergeSorted(c, d))
}

package main

import "fmt"

// longestUniqueSubstring returns the length and text of the longest run
// of characters in s with no repeats, using a sliding window plus a map
// of each rune's most recent index to jump the window start forward.
func longestUniqueSubstring(s string) (int, string) {
	runes := []rune(s)
	lastSeen := make(map[rune]int)
	best, bestStart := 0, 0
	start := 0
	for i, r := range runes {
		// idx >= start matters: a stale sighting of r from before the current window
		// started is irrelevant and must not push start forward again
		if idx, ok := lastSeen[r]; ok && idx >= start {
			start = idx + 1
		}
		// record/overwrite the most recent index of r regardless, so future repeats see it
		lastSeen[r] = i
		// current window [start, i] is unique by construction; keep it if it's the longest so far
		if length := i - start + 1; length > best {
			best = length
			bestStart = start
		}
	}
	return best, string(runes[bestStart : bestStart+best])
}

func main() {
	inputs := []string{"abcabcbb", "bbbbb", "pwwkew", "go gopher"}
	for _, s := range inputs {
		n, sub := longestUniqueSubstring(s)
		fmt.Printf("input: %q -> longest unique substring: %q (length %d)\n", s, sub, n)
	}
}

package main

import "fmt"

// isBalanced reports whether every bracket in s is properly opened and
// closed in the right order, using a stack to track open brackets.
func isBalanced(s string) bool {
	// maps each closing bracket to the opener it must match
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	// the most recently opened, still-unclosed bracket is always on top,
	// which is exactly what a stack gives us in O(1) per operation
	var stack []rune
	for _, r := range s {
		switch r {
		case '(', '[', '{':
			stack = append(stack, r)
		case ')', ']', '}':
			// invalid if there's nothing open to close, or the top of the stack
			// isn't the matching opener (wrong type or wrong order)
			if len(stack) == 0 || stack[len(stack)-1] != pairs[r] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	// a leftover open bracket with nothing closing it is also unbalanced
	return len(stack) == 0
}

func main() {
	inputs := []string{"()[]{}", "([{}])", "(]", "([)]", "{[()()]}"}
	for _, s := range inputs {
		fmt.Printf("input: %-10q -> balanced: %v\n", s, isBalanced(s))
	}
}

package main

import "fmt"

// fibRecursive computes the n-th Fibonacci number the naive way, recursing
// on both smaller subproblems. It recomputes the same values many times,
// so it's exponential time: O(2^n).
func fibRecursive(n int) int {
	// base cases fib(0)=0 and fib(1)=1 stop the recursion
	if n < 2 {
		return n
	}
	// each call branches into two more calls with no memory of work already done,
	// so the same smaller subproblems (e.g. fib(3)) get recomputed many times over
	return fibRecursive(n-1) + fibRecursive(n-2)
}

// fibMemo computes the n-th Fibonacci number using a cache of already
// solved subproblems, so each value is computed only once: O(n) time.
func fibMemo(n int, cache map[int]int) int {
	if n < 2 {
		return n
	}
	// if this subproblem was already solved on an earlier branch, reuse it
	// instead of paying for the recursion again
	if v, ok := cache[n]; ok {
		return v
	}
	result := fibMemo(n-1, cache) + fibMemo(n-2, cache)
	// save the result before returning so every future call for n is O(1)
	cache[n] = result
	return result
}

func main() {
	fmt.Println("naive recursive fibonacci:")
	for i := 0; i <= 10; i++ {
		fmt.Printf("fib(%d) = %d\n", i, fibRecursive(i))
	}

	fmt.Println("\nmemoized fibonacci:")
	// one cache shared across every call in this loop, so it keeps growing instead
	// of being rebuilt from scratch each time
	cache := make(map[int]int)
	for i := 0; i <= 10; i++ {
		fmt.Printf("fib(%d) = %d\n", i, fibMemo(i, cache))
	}

	fmt.Println("\nmemoization makes larger values practical, e.g.:")
	// fib(40) would take billions of calls with fibRecursive; reusing the
	// already-populated cache makes it near-instant here
	fmt.Printf("fib(40) = %d\n", fibMemo(40, cache))
}

package main

import "fmt"

// quicksort sorts nums in place by picking a pivot, partitioning the
// slice around it, then recursively sorting each side: average O(n log n).
func quicksort(nums []int) {
	// 0 or 1 elements are trivially sorted; this also ends the recursion
	if len(nums) < 2 {
		return
	}
	// the middle element avoids the worst-case O(n^2) behavior that picking
	// the first or last element would cause on already-sorted input
	pivot := nums[len(nums)/2]
	left, right := 0, len(nums)-1
	// Hoare partition: walk left up and right down past elements already on
	// the correct side of the pivot, swapping the ones that are out of place
	for left <= right {
		for nums[left] < pivot {
			left++
		}
		for nums[right] > pivot {
			right--
		}
		if left <= right {
			nums[left], nums[right] = nums[right], nums[left]
			// move past the pair just swapped so it isn't re-examined
			left++
			right--
		}
	}
	// right and left have crossed, splitting nums into two partitions around
	// the pivot's final resting place; recursively sort each independently
	quicksort(nums[:right+1])
	quicksort(nums[left:])
}

func main() {
	nums := []int{8, 3, 1, 7, 0, 10, 2}
	fmt.Printf("before: %v\n", nums)
	quicksort(nums)
	fmt.Printf("after:  %v\n", nums)

	nums2 := []int{5, 5, 5, -1, 3}
	fmt.Printf("\nbefore: %v\n", nums2)
	quicksort(nums2)
	fmt.Printf("after:  %v\n", nums2)
}

package main

import "fmt"

// maxSubArray returns the largest sum of any contiguous, non-empty subarray
// of nums, using Kadane's algorithm in O(n) time and O(1) extra space.
func maxSubArray(nums []int) int {
	best := nums[0]
	cur := nums[0]
	for i := 1; i < len(nums); i++ {
		n := nums[i]
		// a negative running sum can only drag down any future subarray,
		// so it's never worth carrying forward - start fresh from n instead
		if cur < 0 {
			cur = n
		} else {
			cur += n
		}
		// best tracks the max cur seen at any point, since the optimal
		// subarray must end at some index i and cur is the best sum ending there
		if cur > best {
			best = cur
		}
	}
	return best
}

func main() {
	inputs := [][]int{
		{-2, 1, -3, 4, -1, 2, 1, -5, 4},
		{5, 4, -1, 7, 8},
		{-3, -1, -8, -2},
	}

	for _, nums := range inputs {
		fmt.Printf("nums=%v -> max subarray sum=%d\n", nums, maxSubArray(nums))
	}
}

package main

import (
	"fmt"
	"sort"
)

// groupAnagrams clusters strings that are anagrams of each other by sorting
// each word's runes into a canonical key and bucketing on that key.
func groupAnagrams(words []string) [][]string {
	groups := make(map[string][]string)
	var order []string

	for _, w := range words {
		// any two anagrams produce the same sorted rune sequence, so that
		// sorted form is a canonical key every member of the group shares
		runes := []rune(w)
		sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
		key := string(runes)
		// record each key only the first time it's seen, so groups come
		// out in first-appearance order even though map iteration isn't ordered
		if _, ok := groups[key]; !ok {
			order = append(order, key)
		}
		groups[key] = append(groups[key], w)
	}

	result := make([][]string, 0, len(order))
	for _, key := range order {
		result = append(result, groups[key])
	}
	return result
}

func main() {
	words := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Printf("words=%v\n", words)
	for _, group := range groupAnagrams(words) {
		fmt.Printf("group: %v\n", group)
	}
}

package main

import "fmt"

// longestCommonPrefix returns the longest prefix shared by every string in
// strs, comparing column by column across all words at once.
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	// start assuming the whole first word is the prefix, then shrink it
	// down as each subsequent word disagrees with it
	prefix := strs[0]
	for _, s := range strs[1:] {
		i := 0
		// walk both strings together and stop at the first mismatching
		// column (or the end of the shorter one) - everything before that
		// point is still common to every word seen so far
		for i < len(prefix) && i < len(s) && prefix[i] == s[i] {
			i++
		}
		prefix = prefix[:i]
		// once the prefix is empty it can't shrink any further, so there's
		// no point checking the remaining words
		if prefix == "" {
			break
		}
	}
	return prefix
}

func main() {
	cases := [][]string{
		{"flower", "flow", "flight"},
		{"dog", "racecar", "car"},
		{"interspecies", "interstellar", "interstate"},
	}

	for _, strs := range cases {
		fmt.Printf("strs=%v -> longest common prefix=%q\n", strs, longestCommonPrefix(strs))
	}
}

package main

import (
	"container/heap"
	"fmt"
)

// minHeap is an int min-heap; we keep it capped at size k so its root is
// always the k-th largest value seen so far.
type minHeap []int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {
	old := *h
	n := len(old)
	v := old[n-1]
	*h = old[:n-1]
	return v
}

// kthLargest returns the k-th largest element of nums using a bounded
// min-heap of size k, giving O(n log k) time.
func kthLargest(nums []int, k int) int {
	h := &minHeap{}
	heap.Init(h)
	for _, n := range nums {
		heap.Push(h, n)
		// once the heap holds more than k elements, the smallest of them
		// can no longer be among the k largest overall, so evict it
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	// after processing every element, the heap holds exactly the k
	// largest values, and its root is the smallest of those - i.e. the k-th largest
	return (*h)[0]
}

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	for _, k := range []int{2, 4} {
		fmt.Printf("nums=%v, k=%d -> %d-th largest=%d\n", nums, k, k, kthLargest(nums, k))
	}

	nums2 := []int{3, 2, 3, 1, 2, 4, 5, 5, 6}
	k := 4
	fmt.Printf("nums=%v, k=%d -> %d-th largest=%d\n", nums2, k, k, kthLargest(nums2, k))
}

package main

import "fmt"

// reverse flips the elements of s in place between indices lo and hi.
func reverse(s []int, lo, hi int) {
	for lo < hi {
		s[lo], s[hi] = s[hi], s[lo]
		lo++
		hi--
	}
}

// rotate shifts nums to the right by k positions in place, using the
// reverse-three-times trick: reverse the whole slice, then reverse each part.
func rotate(nums []int, k int) {
	n := len(nums)
	if n == 0 {
		return
	}
	// k can exceed n (rotating by n is a no-op), so reduce it to its
	// effective value in [0, n) before using it as an index
	k %= n
	// reversing the whole slice puts every element in its final half but
	// backwards within each half; reversing the two halves individually
	// then un-reverses each one back into the correct order
	reverse(nums, 0, n-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, n-1)
}

func main() {
	nums := []int{1, 2, 3, 4, 5, 6, 7}
	k := 3
	fmt.Printf("before=%v, k=%d\n", nums, k)
	rotate(nums, k)
	fmt.Printf("after=%v\n", nums)

	nums2 := []int{-1, -100, 3, 99}
	k2 := 2
	fmt.Printf("before=%v, k=%d\n", nums2, k2)
	rotate(nums2, k2)
	fmt.Printf("after=%v\n", nums2)

	nums3 := []int{1, 2, 3}
	k3 := 10
	fmt.Printf("before=%v, k=%d\n", nums3, k3)
	rotate(nums3, k3)
	fmt.Printf("after=%v\n", nums3)
}

package main

import "fmt"

// maxArea finds the two lines in height that, together with the x-axis,
// form the container holding the most water, using the two-pointer method.
func maxArea(height []int) int {
	// start with the widest possible container and narrow it, since width
	// only shrinks from here - any better area has to come from a taller side
	lo, hi := 0, len(height)-1
	best := 0
	for lo < hi {
		// the container's height is capped by its shorter wall
		h := height[lo]
		if height[hi] < h {
			h = height[hi]
		}
		area := h * (hi - lo)
		if area > best {
			best = area
		}
		// move whichever side is shorter: keeping it in place can never beat
		// the current area (width shrinks, height stays capped by the same wall),
		// so moving it is the only way to possibly find a taller pair
		if height[lo] < height[hi] {
			lo++
		} else {
			hi--
		}
	}
	return best
}

func main() {
	cases := [][]int{
		{1, 8, 6, 2, 5, 4, 8, 3, 7},
		{1, 1},
		{4, 3, 2, 1, 4},
	}

	for _, height := range cases {
		fmt.Printf("height=%v -> max water area=%d\n", height, maxArea(height))
	}
}

package main

import "fmt"

// moveZeroes shifts every zero in nums to the end, in place, while keeping
// the relative order of the non-zero elements, using a single write pointer.
func moveZeroes(nums []int) {
	// write marks the boundary: everything before it is the non-zero
	// elements packed so far, in their original relative order.
	write := 0
	for read := 0; read < len(nums); read++ {
		if nums[read] != 0 {
			// swapping (rather than just assigning) puts whatever was at
			// write - a zero already accounted for, or nums[write] itself
			// when read==write - into read's old slot, so no extra buffer
			// or second pass is needed to shift the zeros down.
			nums[write], nums[read] = nums[read], nums[write]
			write++
		}
	}
}

func main() {
	nums := []int{0, 1, 0, 3, 12}
	fmt.Printf("before=%v\n", nums)
	moveZeroes(nums)
	fmt.Printf("after=%v\n", nums)

	nums2 := []int{0, 0, 1}
	fmt.Printf("before=%v\n", nums2)
	moveZeroes(nums2)
	fmt.Printf("after=%v\n", nums2)

	nums3 := []int{4, 2, 4, 0, 0, 3, 0, 5, 1, 0}
	fmt.Printf("before=%v\n", nums3)
	moveZeroes(nums3)
	fmt.Printf("after=%v\n", nums3)
}

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// compress run-length-encodes s, replacing each run of a repeated character
// with the character followed by its run length (e.g. "aaabbc" -> "a3b2c1").
func compress(s string) string {
	if s == "" {
		return ""
	}
	var b strings.Builder
	// decode to runes first so multi-byte characters count as one character
	// each, not as however many UTF-8 bytes they occupy.
	runeStr := []rune(s)
	count := 1
	// i runs one past the last index on purpose: that out-of-range step is
	// what forces the final run to be flushed, since otherwise the loop
	// would end mid-run with count never written out.
	for i := 1; i <= len(runeStr); i++ {
		if i < len(runeStr) && runeStr[i] == runeStr[i-1] {
			count++
			continue
		}
		// runeStr[i-1] is the last character of the run that just ended
		// (or the run-end sentinel step at i==len(runeStr)); flush it with
		// its accumulated count before starting the next run.
		b.WriteRune(runeStr[i-1])
		b.WriteString(strconv.Itoa(count))
		count = 1
	}
	return b.String()
}

func main() {
	inputs := []string{"aaabbc", "abcd", "aabbccddeeee", "wwwwwwwwwwwwx"}
	for _, s := range inputs {
		fmt.Printf("input=%q -> compressed=%q\n", s, compress(s))
	}
}

package main

import (
	"fmt"
	"strings"
)

// isRotation reports whether s2 is a rotation of s1 (e.g. "erbottlewat" is a
// rotation of "waterbottle"). The trick: any rotation of s1 is a substring
// of s1+s1.
func isRotation(s1, s2 string) bool {
	// a rotation must have exactly the same length; without this check a
	// shorter s2 could false-positive as "contained" in s1+s1.
	if len(s1) != len(s2) {
		return false
	}
	// concatenating s1 with itself lines up every possible rotation point
	// as a contiguous substring, so a single Contains check covers all of
	// them without trying each rotation offset individually.
	return strings.Contains(s1+s1, s2)
}

func main() {
	cases := []struct{ a, b string }{
		{"waterbottle", "erbottlewat"},
		{"hello", "llohe"},
		{"hello", "helol"},
		{"abc", "abcd"},
	}

	for _, c := range cases {
		fmt.Printf("s1=%q, s2=%q -> is rotation=%t\n", c.a, c.b, isRotation(c.a, c.b))
	}
}

package main

import (
	"fmt"
	"sort"
)

// merge sorts intervals by start and merges any that overlap, returning the
// minimal set of non-overlapping intervals that covers the same ranges.
func merge(intervals [][2]int) [][2]int {
	if len(intervals) == 0 {
		return nil
	}
	// copy first so the caller's slice isn't reordered as a side effect of
	// sorting it in place.
	sorted := make([][2]int, len(intervals))
	copy(sorted, intervals)
	// sorting by start turns "do any two intervals overlap" into "does each
	// interval overlap only its immediate neighbor", since once ordered by
	// start, an overlap can only ever involve the most recently merged one.
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][0] < sorted[j][0] })

	result := [][2]int{sorted[0]}
	for _, cur := range sorted[1:] {
		// take the address of the slice element so extending it in place
		// (below) updates result directly, without a separate lookup/write.
		last := &result[len(result)-1]
		if cur[0] <= last[1] {
			// cur starts inside (or right at) last's range, so they overlap;
			// only grow the end if cur reaches further, since cur could be
			// fully contained within last (e.g. [1,4] then [2,3]).
			if cur[1] > last[1] {
				last[1] = cur[1]
			}
		} else {
			// cur starts after last ends, so it can't overlap anything seen
			// so far (thanks to the sort) - it becomes its own interval.
			result = append(result, cur)
		}
	}
	return result
}

func main() {
	cases := [][][2]int{
		{{1, 3}, {2, 6}, {8, 10}, {15, 18}},
		{{1, 4}, {4, 5}},
		{{1, 4}, {0, 4}},
		{{1, 4}, {2, 3}},
	}

	for _, intervals := range cases {
		fmt.Printf("intervals=%v -> merged=%v\n", intervals, merge(intervals))
	}
}

package main

import (
	"fmt"
	"sort"
	"strings"
	"unicode"
)

// wordFrequency splits text into lowercase words (stripping punctuation) and
// counts how many times each word appears.
func wordFrequency(text string) map[string]int {
	// treat any rune that's neither a letter nor a digit as a separator, so
	// FieldsFunc splits on punctuation and whitespace alike in one pass
	// without a separate strip-punctuation step.
	fields := strings.FieldsFunc(strings.ToLower(text), func(r rune) bool {
		return !unicode.IsLetter(r) && !unicode.IsDigit(r)
	})
	// a map gives O(1) increment per word instead of a linear scan for each
	// occurrence to find its existing count.
	counts := make(map[string]int)
	for _, w := range fields {
		counts[w]++
	}
	return counts
}

// sortedByCount returns words ordered by descending count, then alphabetically
// to keep output deterministic.
func sortedByCount(counts map[string]int) []string {
	// Go's map iteration order is randomized, so the keys must be collected
	// and explicitly sorted to get any stable, repeatable output.
	words := make([]string, 0, len(counts))
	for w := range counts {
		words = append(words, w)
	}
	// primary key: count descending. Ties fall back to alphabetical order
	// so words with equal counts still print in a fixed, reproducible order.
	sort.Slice(words, func(i, j int) bool {
		if counts[words[i]] != counts[words[j]] {
			return counts[words[i]] > counts[words[j]]
		}
		return words[i] < words[j]
	})
	return words
}

func main() {
	text := "The quick brown fox jumps over the lazy dog. The dog barks, but the fox runs away!"
	fmt.Printf("text=%q\n", text)

	counts := wordFrequency(text)
	for _, w := range sortedByCount(counts) {
		fmt.Printf("%s: %d\n", w, counts[w])
	}
}

package main

import "fmt"

// numIslands counts the connected regions of '1' (land) in grid, where a
// region is any set of land cells connected horizontally or vertically.
// It flood-fills each newly found island with BFS so it is never re-counted.
func numIslands(grid [][]byte) int {
	if len(grid) == 0 {
		return 0
	}
	rows, cols := len(grid), len(grid[0])
	// visited is a parallel grid, separate from the input, marking every
	// land cell already assigned to an island; without it the outer scan
	// below would walk into the same island repeatedly and over-count it,
	// and the BFS itself could revisit a cell and loop forever.
	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	type point struct{ r, c int }
	// bfs claims every land cell reachable from (sr, sc) by 4-directional
	// steps, marking each one visited the moment it's enqueued (not when
	// it's dequeued) so the same cell can never be added to the queue twice.
	bfs := func(sr, sc int) {
		queue := []point{{sr, sc}}
		visited[sr][sc] = true
		for len(queue) > 0 {
			// pop from the front - this is what makes it a breadth-first
			// (layer-by-layer) search rather than depth-first; either order
			// finds the same island, but BFS avoids deep recursion on large
			// islands.
			p := queue[0]
			queue = queue[1:]
			// the four orthogonal neighbors; islands are defined by
			// horizontal/vertical adjacency only, so diagonals are excluded.
			dirs := []point{{p.r - 1, p.c}, {p.r + 1, p.c}, {p.r, p.c - 1}, {p.r, p.c + 1}}
			for _, d := range dirs {
				// skip neighbors that would fall outside the grid before
				// indexing into it, to avoid a panic at the edges/corners.
				if d.r < 0 || d.r >= rows || d.c < 0 || d.c >= cols {
					continue
				}
				// skip water, and skip land already claimed by this (or an
				// earlier) BFS - both cases mean there's nothing new to add.
				if visited[d.r][d.c] || grid[d.r][d.c] != '1' {
					continue
				}
				visited[d.r][d.c] = true
				queue = append(queue, d)
			}
		}
	}

	count := 0
	// scanning every cell guarantees no island is missed regardless of its
	// shape or position; the !visited check is what makes each island only
	// ever trigger one bfs call - once flood-filled, its cells are skipped
	// for the rest of the scan.
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == '1' && !visited[r][c] {
				count++
				bfs(r, c)
			}
		}
	}
	return count
}

func printGrid(grid [][]byte) {
	for _, row := range grid {
		fmt.Println(string(row))
	}
}

func main() {
	grid1 := [][]byte{
		[]byte("11110"),
		[]byte("11010"),
		[]byte("11000"),
		[]byte("00000"),
	}
	fmt.Println("grid 1:")
	printGrid(grid1)
	fmt.Printf("islands=%d\n\n", numIslands(grid1))

	grid2 := [][]byte{
		[]byte("11000"),
		[]byte("11000"),
		[]byte("00100"),
		[]byte("00011"),
	}
	fmt.Println("grid 2:")
	printGrid(grid2)
	fmt.Printf("islands=%d\n", numIslands(grid2))
}