Go for Interviews

// SliceBasics shows the everyday slice operations.
func SliceBasics() []int {
	a := make([]int, 0, 4) // len 0, cap 4
	a = append(a, 1, 2, 3) // ALWAYS reassign the result of append
	a = append(a, []int{4, 5}...)
	return a[1:4] // half-open: indexes 1,2,3 -> [2 3 4]
}

// AliasDemo shows that sub-slices share memory with the original.
func AliasDemo() (orig, sub []int) {
	orig = []int{1, 2, 3, 4}
	sub = orig[:2]
	sub[0] = 99 // also changes orig[0]!
	return orig, sub
}

// AppendAlias: sub has spare capacity, so append overwrites orig[2].
func AppendAlias() []int {
	orig := []int{1, 2, 3, 4}
	sub := orig[:2]
	sub = append(sub, 100) // writes into orig's backing array
	_ = sub
	return orig // [1 2 100 4]
}

// CloneSlice makes an independent copy (use before mutating or saving a path).
func CloneSlice(src []int) []int {
	dst := make([]int, len(src))
	copy(dst, src) // copy(dst, src) copies min(len(dst), len(src)) elements
	return dst
}

// Subsets collects every subset. The copy is essential: without it every
// stored subset would alias the same backing array and be overwritten.
func Subsets(nums []int) [][]int {
	var res [][]int
	var cur []int
	var dfs func(i int)
	dfs = func(i int) {
		if i == len(nums) {
			res = append(res, append([]int(nil), cur...)) // snapshot
			return
		}
		dfs(i + 1)
		cur = append(cur, nums[i])
		dfs(i + 1)
		cur = cur[:len(cur)-1] // backtrack
	}
	dfs(0)
	return res
}

// NewGrid builds a rows x cols grid. Each row must be allocated separately.
func NewGrid(rows, cols int) [][]int {
	grid := make([][]int, rows)
	for i := range grid {
		grid[i] = make([]int, cols)
	}
	return grid
}

// RemoveAt deletes index i, preserving order, in O(n).
func RemoveAt(a []int, i int) []int {
	return append(a[:i], a[i+1:]...)
}

// SwapRemove deletes index i in O(1) when order does not matter.
func SwapRemove(a []int, i int) []int {
	a[i] = a[len(a)-1]
	return a[:len(a)-1]
}

// CountFreq counts occurrences. A missing key reads as the zero value, so
// no "if exists" check is needed for counters.
func CountFreq(nums []int) map[int]int {
	freq := map[int]int{}
	for _, n := range nums {
		freq[n]++
	}
	return freq
}

// HasDuplicate uses map[T]struct{} as a set (struct{} takes zero bytes).
func HasDuplicate(nums []int) bool {
	seen := map[int]struct{}{}
	for _, n := range nums {
		if _, ok := seen[n]; ok { // comma-ok: ok is false when key is absent
			return true
		}
		seen[n] = struct{}{}
	}
	return false
}

// GroupByLen maps a key to a slice; append on a missing key works because
// a nil slice is a valid empty slice.
func GroupByLen(words []string) map[int][]string {
	g := map[int][]string{}
	for _, w := range words {
		g[len(w)] = append(g[len(w)], w)
	}
	return g
}

// AnagramKey returns a comparable key: arrays (not slices) can be map keys.
func AnagramKey(s string) [26]int {
	var k [26]int
	for _, c := range s {
		k[c-'a']++
	}
	return k
}

// ZeroValues lists what an uninitialised variable holds.
func ZeroValues() (int, string, bool, []int, map[string]int, *int) {
	var (
		i int            // 0
		s string         // ""
		b bool           // false
		a []int          // nil (len 0, safe to append/range)
		m map[string]int // nil (safe to read, PANICS on write)
		p *int           // nil
	)
	return i, s, b, a, m, p
}

// SortBasics shows the common sorting calls.
func SortBasics() ([]int, []string) {
	nums := []int{3, 1, 2}
	sort.Ints(nums) // ascending, in place
	words := []string{"pear", "fig", "apple"}
	sort.Strings(words)
	return nums, words
}

// SortIntervals sorts by start, then by end. The less func must be a strict
// ordering: return false when equal.
func SortIntervals(iv [][]int) {
	sort.Slice(iv, func(i, j int) bool {
		if iv[i][0] != iv[j][0] {
			return iv[i][0] < iv[j][0]
		}
		return iv[i][1] < iv[j][1]
	})
}

// SortDescAndSearch shows descending order and binary search.
func SortDescAndSearch(nums []int, target int) ([]int, int) {
	sort.Sort(sort.Reverse(sort.IntSlice(nums))) // descending
	slices.Sort(nums)                            // generic ascending (Go 1.21+)
	// first index with nums[i] >= target, O(log n); nums must be sorted
	idx := sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
	return nums, idx
}

// IntMinHeap is a min-heap of ints. container/heap needs five methods:
// Len, Less, Swap (from sort.Interface) plus Push and Pop.
type IntMinHeap []int

func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] } // smallest on top
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push and Pop use a POINTER receiver (they change the slice length).
// Never call them directly; use heap.Push / heap.Pop.
func (h *IntMinHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntMinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

// IntMaxHeap embeds the min-heap and inverts Less: biggest on top.
type IntMaxHeap struct{ IntMinHeap }

func (h IntMaxHeap) Less(i, j int) bool { return h.IntMinHeap[i] > h.IntMinHeap[j] }

// KthLargest keeps a min-heap of size k; the top is the kth largest. O(n log k).
func KthLargest(nums []int, k int) int {
	h := &IntMinHeap{}
	for _, n := range nums {
		heap.Push(h, n)
		if h.Len() > k {
			heap.Pop(h) // evict the smallest
		}
	}
	return (*h)[0] // peek: index 0 is the top
}

// TopDownMax pops everything from a max-heap: descending order.
func TopDownMax(nums []int) []int {
	h := &IntMaxHeap{}
	for _, n := range nums {
		heap.Push(h, n)
	}
	var out []int
	for h.Len() > 0 {
		out = append(out, heap.Pop(h).(int))
	}
	return out
}

// Item is the usual interview shape: a payload plus a priority.
type Item struct {
	Val, Pri int
}
type PQ []Item

func (p PQ) Len() int           { return len(p) }
func (p PQ) Less(i, j int) bool { return p[i].Pri < p[j].Pri }
func (p PQ) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p *PQ) Push(x any)        { *p = append(*p, x.(Item)) }
func (p *PQ) Pop() any {
	old := *p
	x := old[len(old)-1]
	*p = old[:len(old)-1]
	return x
}

// Stack is a slice used LIFO: push = append, pop = shrink by one.
type Stack []int

func (s *Stack) Push(v int) { *s = append(*s, v) }
func (s *Stack) Pop() int {
	old := *s
	v := old[len(old)-1] // panics if empty: check len first
	*s = old[:len(old)-1]
	return v
}
func (s Stack) Peek() int { return s[len(s)-1] }

// ValidParens is the classic stack problem.
func ValidParens(s string) bool {
	pair := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var st []rune
	for _, c := range s {
		switch c {
		case '(', '[', '{':
			st = append(st, c)
		default:
			if len(st) == 0 || st[len(st)-1] != pair[c] {
				return false
			}
			st = st[:len(st)-1]
		}
	}
	return len(st) == 0
}

// BFSOrder shows the queue idiom: q[0] is the front, q = q[1:] dequeues.
// Dequeue is O(1) (it only moves the slice header); memory is reclaimed
// once the slice is re-allocated by a later append.
func BFSOrder(adj map[int][]int, start int) []int {
	seen := map[int]bool{start: true}
	queue := []int{start}
	var order []int
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		order = append(order, cur)
		for _, nb := range adj[cur] {
			if !seen[nb] {
				seen[nb] = true
				queue = append(queue, nb)
			}
		}
	}
	return order
}

// Repeat builds a string in O(n) total. Plain `s += x` in a loop copies the
// whole string each time: O(n^2).
func Repeat(word string, n int) string {
	var sb strings.Builder
	for i := 0; i < n; i++ {
		sb.WriteString(word)
	}
	return sb.String()
}

// Lengths contrasts bytes and runes. len(s) counts BYTES; use []rune for
// characters when the input may be non-ASCII.
func Lengths(s string) (bytes, runes int) {
	return len(s), len([]rune(s))
}

// ReverseString reverses by rune so multi-byte characters survive.
func ReverseString(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

// LetterIndex: s[i] is a byte, so char arithmetic is cheap.
// 'c' - 'a' == 2. Strings are immutable: convert to []byte to modify.
func LetterIndex(s string, i int) int {
	return int(s[i] - 'a')
}

func ToUpperFirst(s string) string {
	b := []byte(s)
	if len(b) > 0 && b[0] >= 'a' && b[0] <= 'z' {
		b[0] -= 'a' - 'A'
	}
	return string(b)
}

// MinMax: min and max are builtins since Go 1.21 (any number of args, any
// ordered type). No more hand-written helper functions.
func MinMax(a, b, c int) (int, int) {
	return min(a, b, c), max(a, b, c)
}

// ListNode is the standard singly linked list node.
type ListNode struct {
	Val  int
	Next *ListNode // nil marks the end
}

// ReverseList flips the pointers in place: O(n) time, O(1) space.
func ReverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for head != nil {
		next := head.Next // save before overwriting
		head.Next = prev
		prev, head = head, next
	}
	return prev
}

// MergeSorted uses a dummy head so the first node needs no special case.
func MergeSorted(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

// TreeNode is the standard binary tree node. Recursion on nil is the base case.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(MaxDepth(root.Left), MaxDepth(root.Right))
}

// Structs are copied when passed by value; pointers share.
type Counter struct{ N int }

func IncByValue(c Counter)    { c.N++ } // changes a copy: caller sees nothing
func IncByPointer(c *Counter) { c.N++ } // changes the original

// SafeWrite shows that reading a nil map is fine but writing panics.
func SafeWrite() (panicked bool) {
	defer func() { panicked = recover() != nil }()
	var m map[string]int
	_ = m["x"] // OK: returns 0
	m["x"] = 1 // panic: assignment to entry in nil map
	return false
}

// ClosuresCollect: since Go 1.22 each iteration has its own loop variable,
// so closures capture what you expect. (Before 1.22 all saw the final value;
// older judges may still run old Go, so copy `i := i` if unsure.)
func ClosuresCollect() []int {
	var fs []func() int
	for i := 0; i < 3; i++ {
		fs = append(fs, func() int { return i })
	}
	var out []int
	for _, f := range fs {
		out = append(out, f())
	}
	return out // [0 1 2]
}

// RangeCopy: `v` is a COPY of the element, so modifying it changes nothing.
func RangeCopy(pts []Counter) {
	for _, p := range pts {
		p.N++ // no effect
	}
	for i := range pts {
		pts[i].N++ // modifies the slice
	}
}

// Mid computes a midpoint; int is 64-bit on judges, but the habit matters.
func Mid(lo, hi int) int {
	return lo + (hi-lo)/2
}