The coding interview playbook

package main
 
import (
	"fmt"
	"math/rand/v2"
)
 
// brute checks every substring: O(n² · 26). Slow, obviously correct: the reference.
func brute(s string, k int) int {
	best := 0
	for i := range len(s) {
		var count [26]int
		maxFreq := 0
		for j := i; j < len(s); j++ {
			count[s[j]-'A']++
			maxFreq = max(maxFreq, count[s[j]-'A'])
			if j-i+1-maxFreq <= k {
				best = max(best, j-i+1)
			}
		}
	}
	return best
}
 
// characterReplacement keeps a window where length - (count of its most common letter) <= k.
func characterReplacement(s string, k int) int {
	var count [26]int
	best, maxFreq, left := 0, 0, 0
	for right := range len(s) {
		count[s[right]-'A']++
		maxFreq = max(maxFreq, count[s[right]-'A'])
		for right-left+1-maxFreq > k {
			count[s[left]-'A']--
			left++
		}
		best = max(best, right-left+1)
	}
	return best
}
 
func main() {
	examples := []struct {
		s string
		k int
	}{{"ABAB", 2}, {"AABABBA", 1}, {"A", 0}, {"ABCDE", 1}, {"AAAA", 0}}
	for _, e := range examples {
		fmt.Printf("%-8s k=%d -> %d\n", e.s, e.k, characterReplacement(e.s, e.k))
	}
 
	// Randomized check against the brute force.
	r := rand.New(rand.NewPCG(1, 2))
	for range 2000 {
		b := make([]byte, 1+r.IntN(12))
		for i := range b {
			b[i] = "ABC"[r.IntN(3)]
		}
		s, k := string(b), r.IntN(4)
		if got, want := characterReplacement(s, k), brute(s, k); got != want {
			fmt.Println("MISMATCH", s, k, got, want)
			return
		}
	}
	fmt.Println("2000 random cases agree with the brute force")
}

ABAB     k=2 -> 4
AABABBA  k=1 -> 4
A        k=0 -> 1
ABCDE    k=1 -> 2
AAAA     k=0 -> 4
2000 random cases agree with the brute force

package main
 
import (
	"cmp"
	"container/heap"
	"fmt"
	"slices"
	"sort"
	"strings"
)
 
// Heap is a generic binary heap for container/heap: pass any "less" function.
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}
 
func (h *Heap[T]) Len() int           { return len(h.data) }
func (h *Heap[T]) Less(i, j int) bool { return h.less(h.data[i], h.data[j]) }
func (h *Heap[T]) Swap(i, j int)      { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *Heap[T]) Push(x any)         { h.data = append(h.data, x.(T)) }
func (h *Heap[T]) Pop() any {
	n := len(h.data)
	x := h.data[n-1]
	h.data = h.data[:n-1]
	return x
}
 
// DSU is union-find with path halving and union by size.
type DSU struct{ parent, size []int }
 
func NewDSU(n int) *DSU {
	d := &DSU{make([]int, n), make([]int, n)}
	for i := range n {
		d.parent[i], d.size[i] = i, 1
	}
	return d
}
 
func (d *DSU) Find(x int) int {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]]
		x = d.parent[x]
	}
	return x
}
 
func (d *DSU) Union(a, b int) bool {
	a, b = d.Find(a), d.Find(b)
	if a == b {
		return false
	}
	if d.size[a] < d.size[b] {
		a, b = b, a
	}
	d.parent[b] = a
	d.size[a] += d.size[b]
	return true
}
 
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
 
// shortestPath is BFS on a grid: '#' is a wall. Returns -1 if unreachable.
func shortestPath(grid []string, sr, sc, tr, tc int) int {
	dist := make([][]int, len(grid))
	for i := range dist {
		dist[i] = slices.Repeat([]int{-1}, len(grid[0]))
	}
	dist[sr][sc] = 0
	queue := [][2]int{{sr, sc}}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, d := range dirs {
			r, c := cur[0]+d[0], cur[1]+d[1]
			if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) || grid[r][c] == '#' || dist[r][c] != -1 {
				continue
			}
			dist[r][c] = dist[cur[0]][cur[1]] + 1
			queue = append(queue, [2]int{r, c})
		}
	}
	return dist[tr][tc]
}
 
func main() {
	// Top 3 largest with a min-heap of size 3: O(n log k).
	h := &Heap[int]{less: func(a, b int) bool { return a < b }}
	for _, x := range []int{5, 1, 9, 3, 7, 8, 2} {
		heap.Push(h, x)
		if h.Len() > 3 {
			heap.Pop(h)
		}
	}
	top := slices.Clone(h.data)
	slices.SortFunc(top, func(a, b int) int { return cmp.Compare(b, a) })
	fmt.Println("top 3:", top)
 
	// Priority queue of structs: earliest deadline first.
	type task struct {
		name     string
		deadline int
	}
	pq := &Heap[task]{less: func(a, b task) bool { return a.deadline < b.deadline }}
	for _, t := range []task{{"deploy", 3}, {"review", 1}, {"email", 2}} {
		heap.Push(pq, t)
	}
	var order []string
	for pq.Len() > 0 {
		order = append(order, heap.Pop(pq).(task).name)
	}
	fmt.Println("by deadline:", order)
 
	// Union-find: count connected components.
	d := NewDSU(6)
	for _, e := range [][2]int{{0, 1}, {1, 2}, {3, 4}} {
		d.Union(e[0], e[1])
	}
	roots := map[int]struct{}{} // a set
	for i := range 6 {
		roots[d.Find(i)] = struct{}{}
	}
	fmt.Println("components:", len(roots))
 
	// BFS on a grid.
	grid := []string{
		"..#.",
		"..#.",
		"....",
	}
	fmt.Println("grid steps:", shortestPath(grid, 0, 0, 0, 3))
 
	// Binary search on the answer: smallest x with x*x >= 50.
	fmt.Println("smallest x with x*x >= 50:", sort.Search(100, func(x int) bool { return x*x >= 50 }))
 
	// Sort intervals by end, then by start.
	iv := [][2]int{{1, 4}, {2, 3}, {0, 3}}
	slices.SortFunc(iv, func(a, b [2]int) int { return cmp.Or(cmp.Compare(a[1], b[1]), cmp.Compare(a[0], b[0])) })
	fmt.Println("by end:", iv)
 
	// Counting letters: an anagram key that is comparable, so it works as a map key.
	key := func(s string) [26]byte {
		var k [26]byte
		for i := range len(s) {
			k[s[i]-'a']++
		}
		return k
	}
	fmt.Println("anagrams:", key("listen") == key("silent"))
 
	// Building strings: strings.Builder, never += in a loop.
	var sb strings.Builder
	for i := range 3 {
		fmt.Fprintf(&sb, "[%d]", i)
	}
	fmt.Println("built:", sb.String())
}

top 3: [9 8 7]
by deadline: [review email deploy]
components: 3
grid steps: 7
smallest x with x*x >= 50: 8
by end: [[0 3] [2 3] [1 4]]
anagrams: true
built: [0][1][2]