Free Handbook · Every example compiled & verified

Data Structures & Algorithms

Build core data structures by hand in Go, then use the standard library: slices, maps, stacks, queues, trees, heaps, graphs, search, sort and DP.

0 / 134 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Estimate the cost of common Go operations in Big-O and pick the right structure for a job
Use slices as stacks and queues, maps as sets, and container/list and container/heap when a slice is not enough
Build a linked list and a binary search tree by hand with pointers, and write recursive functions with a clear base case
Traverse a graph with BFS and DFS, and search sorted data with slices.BinarySearch and sort.Search
Sort with slices.Sort, slices.SortFunc and sort.Slice, and solve dynamic programming problems with memoisation and tables

Big-O and what Go operations cost

Big-O describes how the work grows as the input grows, ignoring constant factors. O(1) takes the same time for 10 items or 10 million; O(n) doubles when the input doubles; O(log n) barely grows (a million items is about 20 steps); O(n²) quadruples. For interviews and for real code, the question is always: what happens when n is 1,000,000?

Memorise the shape, not the table: slices are fast at the end and slow in the middle; maps are fast for lookups but unordered; anything sorted gives you O(log n) search.
Operation	Go code	Cost
Index a slice	`s[i]`	O(1)
Append to a slice	`s = append(s, x)`	O(1) amortised (occasionally copies)
Pop from the end	`s = s[:len(s)-1]`	O(1)
Insert / delete in the middle	`slices.Insert`, `slices.Delete`	O(n) — shifts the tail
Find in an unsorted slice	`slices.Index(s, x)`	O(n)
Find in a sorted slice	`slices.BinarySearch(s, x)`	O(log n)
Map get / set / delete	`m[k]`, `delete(m, k)`	O(1) average
Sort	`slices.Sort(s)`	O(n log n)
Heap push / pop	`heap.Push`, `heap.Pop`	O(log n)
Linked list insert at a known element	`l.InsertAfter(v, e)`	O(1)
String concatenation in a loop	`s += x`	O(n²) total — use `strings.Builder`

Counting steps makes the difference concrete. Both functions answer "does the list contain a duplicate?":

gomain.go

package main

import "fmt"

func dupNested(xs []int) (bool, int) {
	steps := 0
	for i := range xs {
		for j := i + 1; j < len(xs); j++ {
			steps++
			if xs[i] == xs[j] {
				return true, steps
			}
		}
	}
	return false, steps
}

func dupMap(xs []int) (bool, int) {
	seen := make(map[int]bool, len(xs))
	steps := 0
	for _, x := range xs {
		steps++
		if seen[x] {
			return true, steps
		}
		seen[x] = true
	}
	return false, steps
}

func main() {
	xs := make([]int, 1000)
	for i := range xs {
		xs[i] = i // no duplicates: the worst case
	}
	fmt.Println(dupNested(xs))
	fmt.Println(dupMap(xs))
}

Outputcompiled & run with real Go

false 499500
false 1000

O(n²) vs O(n): 499,500 comparisons against 1,000 map lookups. At a million items the nested loop does about 500 billion.

Your turn

Make the list 2,000 long. Roughly how much do the two step counts grow?

Slices: Go's dynamic array

A slice is a view of a backing array with a length and a capacity (Module 04). When append runs out of capacity it allocates a bigger array — roughly double for small slices — and copies, which is why appending is O(1) on average. If you know the final size, make([]T, 0, n) avoids every copy. The slices package has the everyday algorithms.

gomain.go

package main

import (
	"fmt"
	"slices"
)

func main() {
	s := make([]int, 0, 8) // room for 8 without reallocating
	for i := 1; i <= 5; i++ {
		s = append(s, i*10)
	}
	fmt.Println(s, len(s), cap(s))

	s = slices.Insert(s, 1, 15) // O(n): shifts the tail right
	s = slices.Delete(s, 3, 4)  // O(n): removes s[3], shifts left
	fmt.Println(s)

	fmt.Println(slices.Index(s, 40), slices.Contains(s, 99))
	fmt.Println(slices.Max(s), slices.Min(s))

	slices.Reverse(s)
	fmt.Println(s)

	// two-pointer reverse by hand: the same thing slices.Reverse does
	t := []string{"a", "b", "c", "d"}
	for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
		t[i], t[j] = t[j], t[i]
	}
	fmt.Println(t)
}

Outputcompiled & run with real Go

[10 20 30 40 50] 5 8
[10 15 20 40 50]
3 false
50 10
[50 40 20 15 10]
[d c b a]

Your turn

Remove every even number from s in place with slices.DeleteFunc.

Maps and sets

A Go map is a hash table: average O(1) get, set and delete. Go has no set type; the idiom is map[T]struct{} — the empty struct takes zero bytes, so only the keys cost memory. (map[T]bool also works and reads more easily; pick one per codebase.) Map iteration order is deliberately random, so whenever output order matters, collect the keys and sort them.

gomain.go

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

type Set map[string]struct{}

func (s Set) Add(v string)      { s[v] = struct{}{} }
func (s Set) Has(v string) bool { _, ok := s[v]; return ok }
func (s Set) Sorted() []string  { return slices.Sorted(maps.Keys(s)) }

func main() {
	// frequency count: the most common map job in interviews
	counts := map[string]int{}
	for _, w := range strings.Fields("go is fun and go is fast") {
		counts[w]++
	}
	for _, k := range slices.Sorted(maps.Keys(counts)) {
		fmt.Print(k, "=", counts[k], " ")
	}
	fmt.Println()

	a, b := Set{}, Set{}
	for _, v := range []string{"go", "rust", "java"} {
		a.Add(v)
	}
	for _, v := range []string{"go", "python"} {
		b.Add(v)
	}
	inter := Set{}
	for k := range a {
		if b.Has(k) {
			inter.Add(k)
		}
	}
	fmt.Println(a.Sorted(), inter.Sorted(), a.Has("rust"), b.Has("rust"))
}

Outputcompiled & run with real Go

and=1 fast=1 fun=1 go=2 is=2 
[go java rust] [go] true false

slices.Sorted(maps.Keys(m)) (Go 1.23+) is the one-liner for "the keys in a fixed order". Without it, the for k := range counts loop would print in a different order on each run.

Your turn

Add a Union method that returns a new Set with the keys of both sets.

Stacks, queues and container/list

A stack is last-in, first-out: push and pop at the same end. A slice is a perfect stack — append to push, s[len(s)-1] and s = s[:len(s)-1] to pop, both O(1). The classic stack problem is checking brackets: every closer must match the most recent unmatched opener.

gomain.go

package main

import "fmt"

func balanced(s string) bool {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var stack []rune
	for _, c := range s {
		switch c {
		case '(', '[', '{':
			stack = append(stack, c) // push
		case ')', ']', '}':
			if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
				return false
			}
			stack = stack[:len(stack)-1] // pop
		}
	}
	return len(stack) == 0
}

func main() {
	for _, s := range []string{"([]{})", "([)]", "((", "f(a[1])"} {
		fmt.Println(s, balanced(s))
	}
}

Outputcompiled & run with real Go

([]{}) true
([)] false
(( false
f(a[1]) true

Your turn

Return the index of the first problem instead of false, or -1 when balanced.

Visualizebalanced("([)]")Step 1 / 4

1for _, c := range s {
2	switch c {
3	case '(', '[', '{':
4		stack = append(stack, c)
5	case ')', ']', '}':
6		if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
7			return false
8		}
9		stack = stack[:len(stack)-1]
10	}
11}

Line 4

( is an opener: push it.

Variables now

`c`	`'('`
`stack`	`(`

All 4 steps as a table

Step	Line	What happened	Variables now
1	4	`(` is an opener: push it.	`c = '('` `stack = (`
2	4	`[` is an opener: push it on top.	`c = '['` `stack = ( [`
3	6	`)` is a closer. The top of the stack is `[`, but `)` needs `(`.	`c = ')'` `top = '['` `pairs[c] = '('`
4	7	Mismatch: the brackets cross instead of nesting, so the answer is false without looking further.

A queue is first-in, first-out. On a slice, append to the back and take from the front with q = q[1:] — O(1), but the backing array only shrinks when append reallocates, which is fine for a short-lived queue (like one BFS). For a long-running deque (add and remove at both ends) the standard library has container/list, a doubly linked list.

gomain.go

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// queue on a slice
	q := []string{"a", "b"}
	q = append(q, "c") // enqueue
	front := q[0]      // peek
	q = q[1:]          // dequeue
	fmt.Println(front, q)

	// deque on container/list
	d := list.New()
	d.PushBack(2)
	d.PushBack(3)
	d.PushFront(1)
	last := d.Remove(d.Back()).(int) // elements hold 'any': assert the type
	fmt.Print("popped ", last, ": ")
	for e := d.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println("len", d.Len())
}

Outputcompiled & run with real Go

a [b c]
popped 3: 1 2 len 2

container/list predates generics, so values come back as any. In practice a slice beats it for most jobs because it is cache-friendly; reach for the list when you need O(1) removal of an element you already hold a pointer to, as in an LRU cache.

A linked list by hand

A singly linked list is a chain of nodes, each holding a value and a pointer to the next. It is rarely the right choice in Go (slices are faster in practice), but it is the standard way interviews test whether you understand pointers. With generics the node works for any type.

gomain.go

package main

import (
	"fmt"
	"strings"
)

type Node[T any] struct {
	Val  T
	Next *Node[T]
}

type List[T any] struct {
	head *Node[T]
	size int
}

func (l *List[T]) PushFront(v T) {
	l.head = &Node[T]{Val: v, Next: l.head}
	l.size++
}

// Reverse flips the pointers in place: O(n) time, O(1) extra memory.
func (l *List[T]) Reverse() {
	var prev *Node[T]
	cur := l.head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev, cur = cur, next
	}
	l.head = prev
}

func (l *List[T]) String() string {
	var b strings.Builder
	for n := l.head; n != nil; n = n.Next {
		fmt.Fprintf(&b, "%v -> ", n.Val)
	}
	b.WriteString("nil")
	return b.String()
}

func main() {
	var l List[int]
	for _, v := range []int{3, 2, 1} {
		l.PushFront(v)
	}
	fmt.Println(l.String(), "size", l.size)
	l.Reverse()
	fmt.Println(l.String())
}

Outputcompiled & run with real Go

1 -> 2 -> 3 -> nil size 3
3 -> 2 -> 1 -> nil

Your turn

Add a PushBack method. To make it O(1) instead of walking the whole list, keep a tail pointer.

VisualizeReverse on 1 -> 2 -> 3Step 1 / 7

1var prev *Node[T]
2cur := l.head
3for cur != nil {
4	next := cur.Next
5	cur.Next = prev
6	prev, cur = cur, next
7}
8l.head = prev

Line 2

Start with nothing reversed yet.

Variables now

`prev`	`nil`
`cur`	`1`

All 7 steps as a table

Step	Line	What happened	Variables now
1	2	Start with nothing reversed yet.	`prev = nil` `cur = 1`
2	5	Save 2 in `next`, then point 1 back at `prev` (nil). 1 is now the tail.	`next = 2` `1.Next = nil`
3	6	Step forward: the reversed part is `1`.	`prev = 1` `cur = 2`
4	5	Point 2 back at 1.	`next = 3` `2.Next = 1`
5	6	Reversed part is `2 -> 1`.	`prev = 2` `cur = 3`
6	6	Point 3 back at 2, step forward: `cur` is nil, so the loop ends.	`prev = 3` `cur = nil`
7	8	The old tail is the new head.	`l.head = 3`

Recursion

A recursive function solves a problem by calling itself on a smaller piece of it. Every one needs a base case that stops the recursion, and every call must move toward it. Go has no tail-call optimisation, but goroutine stacks grow on demand (up to 1 GB by default), so depth is rarely a problem before you run out of patience — an infinite recursion ends with fatal error: stack overflow. Recursion shines on problems that are naturally trees: nested folders, JSON, expression parsing, generating combinations.

gomain.go

package main

import "fmt"

// subsets returns every subset of items: the core of backtracking.
func subsets(items []string) [][]string {
	if len(items) == 0 {
		return [][]string{{}} // base case: one subset, the empty one
	}
	rest := subsets(items[1:])
	out := make([][]string, 0, 2*len(rest))
	for _, s := range rest {
		out = append(out, s) // without items[0]
		with := append([]string{items[0]}, s...)
		out = append(out, with) // with items[0]
	}
	return out
}

func sumDigits(n int) int {
	if n < 10 {
		return n
	}
	return n%10 + sumDigits(n/10)
}

func main() {
	fmt.Println(sumDigits(9045))
	for _, s := range subsets([]string{"a", "b", "c"}) {
		fmt.Print(s, " ")
	}
	fmt.Println()
}

Outputcompiled & run with real Go

18
[] [a] [b] [a b] [c] [a c] [b c] [a b c]

append([]string{items[0]}, s...) builds a new slice. Appending to s directly could share a backing array between subsets and corrupt them — the Module 04 aliasing trap.

Your turn

A set of n items has 2ⁿ subsets. Print len(subsets(...)) for 10 letters and check it is 1024.

More recursion

Factorial, Fibonacci and the call stack are covered step by step in Module 03. The dynamic programming lesson below shows how to stop a recursive function from recomputing the same answers.

A binary search tree

A binary search tree (BST) keeps, at every node, smaller values in the left subtree and larger ones in the right. Search, insert and delete follow one path from the root, so they cost O(height): O(log n) when the tree is balanced, O(n) when it degenerates into a line (insert sorted data and see). An in-order traversal (left, node, right) visits the values sorted. Production code uses a balanced tree or just a sorted slice; the hand-built BST is how interviews test recursion on pointers.

gomain.go

package main

import (
	"cmp"
	"fmt"
)

type Tree[T cmp.Ordered] struct {
	Val         T
	Left, Right *Tree[T]
}

// Insert returns the (possibly new) root, so an empty tree works too.
func Insert[T cmp.Ordered](t *Tree[T], v T) *Tree[T] {
	if t == nil {
		return &Tree[T]{Val: v}
	}
	if v < t.Val {
		t.Left = Insert(t.Left, v)
	} else if v > t.Val {
		t.Right = Insert(t.Right, v)
	} // equal: ignore duplicates
	return t
}

func Contains[T cmp.Ordered](t *Tree[T], v T) bool {
	for t != nil {
		switch {
		case v < t.Val:
			t = t.Left
		case v > t.Val:
			t = t.Right
		default:
			return true
		}
	}
	return false
}

func InOrder[T cmp.Ordered](t *Tree[T], visit func(T)) {
	if t == nil {
		return
	}
	InOrder(t.Left, visit)
	visit(t.Val)
	InOrder(t.Right, visit)
}

func Height[T cmp.Ordered](t *Tree[T]) int {
	if t == nil {
		return 0
	}
	return 1 + max(Height(t.Left), Height(t.Right))
}

func main() {
	var root *Tree[int]
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80} {
		root = Insert(root, v)
	}
	InOrder(root, func(v int) { fmt.Print(v, " ") })
	fmt.Println()
	fmt.Println(Contains(root, 60), Contains(root, 65), "height", Height(root))
}

Outputcompiled & run with real Go

20 30 40 50 60 70 80 
true false height 3

Your turn

Insert 1 to 7 in sorted order into a fresh tree and print its height. Why is it 7, and what does that do to Contains?

Heaps and priority queues with container/heap

A heap is a tree stored in a slice where every parent is smaller than its children (a min-heap), so the smallest item is always at index 0. Push and pop cost O(log n). It is the structure behind priority queues, "top k" problems, schedulers and Dijkstra's shortest path. Go's container/heap supplies the algorithms; you supply a type that implements heap.Interface: Len, Less, Swap (from sort.Interface) plus Push and Pop.

gomain.go

package main

import (
	"container/heap"
	"fmt"
)

type Task struct {
	Name     string
	Priority int // lower = more urgent
}

type PQ []Task

func (q PQ) Len() int           { return len(q) }
func (q PQ) Less(i, j int) bool { return q[i].Priority < q[j].Priority }
func (q PQ) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q *PQ) Push(x any)        { *q = append(*q, x.(Task)) }
func (q *PQ) Pop() any {
	old := *q
	n := len(old)
	t := old[n-1]
	*q = old[:n-1]
	return t
}

func main() {
	q := &PQ{{"write docs", 3}, {"fix prod bug", 1}}
	heap.Init(q)
	heap.Push(q, Task{"review PR", 2})
	heap.Push(q, Task{"lunch", 4})

	fmt.Println("next up:", (*q)[0].Name) // peek: index 0 is the minimum
	for q.Len() > 0 {
		t := heap.Pop(q).(Task)
		fmt.Println(t.Priority, t.Name)
	}
}

Outputcompiled & run with real Go

next up: fix prod bug
1 fix prod bug
2 review PR
3 write docs
4 lunch

Call heap.Push / heap.Pop (the package functions), never q.Push directly — your methods only append and remove at the end; the package does the sifting that keeps the heap ordered.

Your turn

Turn it into a max-heap by changing one character in Less.

gomain.go

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap is a min-heap of ints.
type IntHeap []int

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

// topK keeps a min-heap of size k: the root is the smallest of the k largest.
func topK(nums []int, k int) []int {
	h := &IntHeap{}
	for _, n := range nums {
		heap.Push(h, n)
		if h.Len() > k {
			heap.Pop(h) // drop the smallest
		}
	}
	out := make([]int, h.Len())
	for i := len(out) - 1; i >= 0; i-- {
		out[i] = heap.Pop(h).(int)
	}
	return out
}

func main() {
	fmt.Println(topK([]int{5, 1, 9, 3, 7, 8, 2}, 3))
}

Outputcompiled & run with real Go

[9 8 7]

Top-k in O(n log k) and O(k) memory — far better than sorting a huge stream when k is small.

Graphs: BFS and DFS

A graph is nodes connected by edges. In Go the usual representation is an adjacency list: map[string][]string from each node to its neighbours. Breadth-first search (BFS) explores in rings using a queue, so the first time it reaches a node is along a shortest path (counting edges). Depth-first search (DFS) goes as deep as it can before backtracking, using recursion or a stack — the tool for "is it connected", cycle detection and topological order. Both need a visited set, and both are O(V + E).

gomain.go

package main

import (
	"fmt"
	"slices"
)

var graph = map[string][]string{
	"A": {"B", "C"},
	"B": {"A", "D"},
	"C": {"A", "D", "E"},
	"D": {"B", "C", "F"},
	"E": {"C", "F"},
	"F": {"D", "E"},
}

// bfs returns the shortest path from start to goal (fewest edges).
func bfs(start, goal string) []string {
	prev := map[string]string{start: ""}
	queue := []string{start}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == goal {
			var path []string
			for n := goal; n != ""; n = prev[n] {
				path = append(path, n)
			}
			slices.Reverse(path)
			return path
		}
		for _, next := range graph[node] {
			if _, seen := prev[next]; !seen {
				prev[next] = node
				queue = append(queue, next)
			}
		}
	}
	return nil
}

func dfs(node string, visited map[string]bool, order *[]string) {
	visited[node] = true
	*order = append(*order, node)
	for _, next := range graph[node] {
		if !visited[next] {
			dfs(next, visited, order)
		}
	}
}

func main() {
	fmt.Println("BFS path A->F:", bfs("A", "F"))
	var order []string
	dfs("A", map[string]bool{}, &order)
	fmt.Println("DFS order:", order)
}

Outputcompiled & run with real Go

BFS path A->F: [A B D F]
DFS order: [A B D C E F]

The output is deterministic because the code never ranges over the map itself: it only looks up graph[node], and each neighbour list is a slice in a fixed order.

Your turn

Add a function that counts connected components: run dfs from every unvisited node (iterate over slices.Sorted(maps.Keys(graph)) to keep it deterministic).

VisualizeBFS from A to FStep 1 / 6

1queue := []string{start}
2for len(queue) > 0 {
3	node := queue[0]
4	queue = queue[1:]
5	if node == goal { /* rebuild path */ }
6	for _, next := range graph[node] {
7		if _, seen := prev[next]; !seen {
8			prev[next] = node
9			queue = append(queue, next)
10		}
11	}
12}

Line 1

Start with only A in the queue; A is marked seen.

Variables now

queue [A]

All 6 steps as a table

Step	Line	What happened	Variables now
1	1	Start with only A in the queue; A is marked seen.	`queue = [A]`
2	9	Take A. Its neighbours B and C are new: record A as their parent and enqueue them.	`node = A` `queue = [B C]`
3	9	Take B. A is already seen; D is new (parent B).	`node = B` `queue = [C D]`
4	9	Take C. A and D are seen; E is new (parent C).	`node = C` `queue = [D E]`
5	9	Take D. F is new (parent D). E will find F already seen.	`node = D` `queue = [E F]`
6	5	Take E (nothing new), then F — the goal. Follow parents back: F ← D ← B ← A.	`node = F`

Binary search

On sorted data, binary search halves the search range at every step: look at the middle, then throw away the half that cannot contain the target. A million items take at most 20 comparisons. Writing it by hand is an interview favourite because the boundaries are easy to get wrong; in real code use slices.BinarySearch, or sort.Search when you need "the first index where a condition becomes true".

gomain.go

package main

import (
	"fmt"
	"slices"
	"sort"
)

// search returns the index of target in sorted xs, or -1.
func search(xs []int, target int) int {
	lo, hi := 0, len(xs)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2 // avoids overflow of lo+hi
		switch {
		case xs[mid] == target:
			return mid
		case xs[mid] < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1
}

func main() {
	xs := []int{3, 8, 15, 23, 42, 57, 91}
	fmt.Println(search(xs, 42), search(xs, 5))

	i, found := slices.BinarySearch(xs, 23)
	fmt.Println(i, found)
	i, found = slices.BinarySearch(xs, 50) // where it would be inserted
	fmt.Println(i, found)

	// sort.Search: first index where the predicate is true
	first := sort.Search(len(xs), func(i int) bool { return xs[i] >= 20 })
	fmt.Println("first >= 20 at", first, "=", xs[first])
}

Outputcompiled & run with real Go

4 -1
3 true
5 false
first >= 20 at 3 = 23

Your turn

Use slices.BinarySearch's insertion index with slices.Insert to add 50 while keeping xs sorted.

Visualizesearch(xs, 42) on [3 8 15 23 42 57 91]Step 1 / 6

1lo, hi := 0, len(xs)-1
2for lo <= hi {
3	mid := lo + (hi-lo)/2
4	switch {
5	case xs[mid] == target:
6		return mid
7	case xs[mid] < target:
8		lo = mid + 1
9	default:
10		hi = mid - 1
11	}
12}

Line 1

The whole slice is in range.

Variables now

`lo`	`0`
`hi`	`6`

All 6 steps as a table

Step	Line	What happened	Variables now
1	1	The whole slice is in range.	`lo = 0` `hi = 6`
2	3	Middle is index 3, value 23.	`mid = 3` `xs[mid] = 23`
3	8	23 < 42, so the target can only be to the right. Discard indexes 0–3.	`lo = 4` `hi = 6`
4	3	New middle is index 5, value 57.	`mid = 5` `xs[mid] = 57`
5	10	57 > 42: discard the right half.	`lo = 4` `hi = 4`
6	6	Middle is index 4, value 42 — found in 3 comparisons instead of 5.	`mid = 4`

Sorting

For built-in ordered types use slices.Sort. For structs use slices.SortFunc with a comparison that returns negative, zero or positive — cmp.Compare builds it, and cmp.Or chains tie-breakers. slices.SortStableFunc keeps equal elements in their original order. You will still see the older sort.Slice(s, func(i, j int) bool {…}) everywhere in existing code. All of them are O(n log n) (Go uses pattern-defeating quicksort).

gomain.go

package main

import (
	"cmp"
	"fmt"
	"slices"
	"sort"
)

type Dev struct {
	Name string
	Lang string
	Yrs  int
}

func main() {
	nums := []int{42, 7, 19, 3}
	slices.Sort(nums)
	fmt.Println(nums)

	devs := []Dev{
		{"Kim", "Go", 4}, {"Ada", "Rust", 6}, {"Lee", "Go", 6}, {"Bo", "Rust", 2},
	}
	// by language A-Z, then most experienced first
	slices.SortFunc(devs, func(a, b Dev) int {
		return cmp.Or(
			cmp.Compare(a.Lang, b.Lang),
			cmp.Compare(b.Yrs, a.Yrs), // b before a: descending
		)
	})
	for _, d := range devs {
		fmt.Print(d.Name, "/", d.Lang, "/", d.Yrs, " ")
	}
	fmt.Println()

	// the older API, still common
	words := []string{"banana", "fig", "apple"}
	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
	fmt.Println(words)
}

Outputcompiled & run with real Go

[3 7 19 42]
Lee/Go/6 Kim/Go/4 Ada/Rust/6 Bo/Rust/2 
[fig apple banana]

Your turn

Sort devs by name length, and use slices.SortStableFunc so equal lengths keep their current order.

You should also be able to write one O(n log n) sort by hand. Merge sort splits the slice in half, sorts each half recursively, and merges the two sorted halves — stable, and always O(n log n):

gomain.go

package main

import "fmt"

func mergeSort(xs []int) []int {
	if len(xs) <= 1 {
		return xs
	}
	mid := len(xs) / 2
	left := mergeSort(xs[:mid])
	right := mergeSort(xs[mid:])

	out := make([]int, 0, len(xs))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] { // <= keeps it stable
			out = append(out, left[i])
			i++
		} else {
			out = append(out, right[j])
			j++
		}
	}
	out = append(out, left[i:]...)
	return append(out, right[j:]...)
}

func main() {
	fmt.Println(mergeSort([]int{38, 27, 43, 3, 9, 82, 10}))
}

Outputcompiled & run with real Go

[3 9 10 27 38 43 82]

Uses O(n) extra memory for the merged slices. Quicksort sorts in place but has an O(n²) worst case; insertion sort is O(n²) but fastest for tiny inputs, which is why real libraries mix all three.

Dynamic programming

Dynamic programming (DP) is recursion that remembers. It applies when a problem breaks into overlapping sub-problems — the same smaller question gets asked many times. Two styles: top-down memoisation (write the recursion, cache each answer in a map) and bottom-up tabulation (fill a slice from the smallest case upward). Both turn exponential time into polynomial.

gomain.go

package main

import "fmt"

var calls int

func fibMemo(n int, memo map[int]int) int {
	calls++
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v
	}
	memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
	return memo[n]
}

// minCoins: fewest coins that sum to amount, or -1. Bottom-up table.
func minCoins(coins []int, amount int) int {
	dp := make([]int, amount+1) // dp[a] = fewest coins for amount a
	for a := 1; a <= amount; a++ {
		dp[a] = amount + 1 // "infinity"
		for _, c := range coins {
			if c <= a && dp[a-c]+1 < dp[a] {
				dp[a] = dp[a-c] + 1
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func main() {
	fmt.Println(fibMemo(50, map[int]int{}), "in", calls, "calls")
	fmt.Println(minCoins([]int{1, 5, 10, 25}, 63))
	fmt.Println(minCoins([]int{4, 7}, 5))
}

Outputcompiled & run with real Go

12586269025 in 99 calls
6
-1

Plain recursive fib(50) makes about 40 billion calls; the memoised version makes 99. 63 cents = 25 + 25 + 10 + 1 + 1 + 1.

Your turn

Change minCoins to also return which coins it used: keep a second slice pick[a] recording the coin chosen for each amount, then walk back from amount.

1
Define the state
Say in words what one table cell means: "dp[a] = fewest coins that make amount a".
2
Write the transition
How a cell is built from smaller ones: dp[a] = min(dp[a-c] + 1) over every coin c.
3
Set the base case
dp[0] = 0: zero coins make zero.
4
Pick the order
Fill so every cell you read is already computed — here, small amounts first.

Cheat sheet: which structure for which job

You need to…	Use in Go	Cost
Keep items in order, add at the end	`[]T` + `append`	O(1) amortised
Look up by key	`map[K]V`	O(1) average
Test membership / remove duplicates	`map[T]struct{}`	O(1) average
Iterate a map in a stable order	`slices.Sorted(maps.Keys(m))`	O(n log n)
Last in, first out	Slice as a stack	O(1) push / pop
First in, first out	Slice queue (`q[1:]`) or `container/list`	O(1)
Always take the smallest / largest next	`container/heap`	O(log n) push / pop
Search sorted data	`slices.BinarySearch`, `sort.Search`	O(log n)
Sort	`slices.Sort`, `slices.SortFunc` + `cmp.Compare`	O(n log n)
Shortest path by edge count	BFS with a slice queue	O(V + E)
Explore everything reachable, detect cycles	DFS (recursion or stack)	O(V + E)
Overlapping sub-problems	Memo map or DP slice	Usually O(n·k)
Build a long string	`strings.Builder`	O(n)

Big-O: How the cost of an algorithm grows with the input size, ignoring constant factors.
Amortised O(1): Occasionally slow (a slice regrowing), but constant time on average over many operations.
Stack / queue: Last-in-first-out and first-in-first-out collections; both are usually a slice in Go.
Binary search tree: A tree with smaller values to the left and larger to the right at every node; O(height) search.
Heap: A tree in a slice where each parent is at most its children; the minimum is always at index 0.
BFS / DFS: Graph traversals: breadth-first by rings with a queue, depth-first by recursion or a stack.
Memoisation: Caching the result of a function call so the same input is never computed twice.
Tabulation: Bottom-up DP: filling a table from the smallest sub-problem to the full one.

Quick check

You print the result of for k, v := range counts in a test and it passes sometimes and fails other times. Why?

Map iteration order is unspecified and deliberately randomised. Sort the keys first, for example with slices.Sorted(maps.Keys(counts)).

Quick check

Which is the right way to take the highest-priority item from a container/heap?

heap.Pop swaps the root to the end, restores the heap order, and then calls your Pop method to remove the last element. Calling your method directly removes the wrong item and breaks the heap.

Next: Module 14 puts these structures to work on eight classic interview patterns. For graded practice on the same ideas, try the Python practice problems — the algorithms carry over line for line.

← Module 12Go + Tools Module 14 →Problem Solving

Frequently asked questions

How do I make a set in Go?

Go has no built-in set type. Use a map with an empty struct value, map[T]struct{}, add with s[v] = struct{}{}, and test membership with _, ok := s[v]. map[T]bool also works and is a little easier to read.

Does Go have a priority queue?

Yes, through the container/heap package. You define a slice type with Len, Less, Swap, Push and Pop methods, then call heap.Init, heap.Push and heap.Pop, which keep the smallest item (by your Less) at index 0.

Should I use sort.Slice or slices.Sort in Go?

Prefer the generic slices package: slices.Sort for ordered types and slices.SortFunc with cmp.Compare for structs. sort.Slice is the older reflection-based API; it still works and is common in existing code.

Finish the Go handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.