Go Built-In Time Complexity: The Interview Cheat Sheet

Go is a deliberately minimal language. "Deliberately" is doing a lot of work in that sentence.

No priority queue. No deque. No ordered map. No set. Coming from Java or Python you feel that gap immediately, usually around the moment you type new and realize there's nothing to new. What Go does include works well and carries predictable complexity. But not knowing the cost of slice append, or discovering mid-interview that map iteration is randomized, can cost you real points when an interviewer asks you to narrate your choices out loud.

This is the Go built-in time complexity reference you want open before any coding interview.

Slice: Three Words, Two Costs

A Go slice is a three-word struct under the hood: a pointer to an underlying array, a length, and a capacity. Almost every slice complexity question in an interview traces back to whether that pointer is shared.

Operation	Time
Index read/write `s[i]`	O(1)
`len(s)`, `cap(s)`	O(1)
Append within capacity	O(1)
Append past capacity	O(n) worst, O(1) amortized
`copy(dst, src)`	O(min(len(dst), len(src)))
Delete by index (order preserved)	O(n)
Delete by index (swap with last)	O(1)
Slice expression `s[lo:hi]`	O(1)

The amortized cost of append is O(1), but individual appends that trigger a resize are O(n). Go doubles capacity for slices under 256 elements and then grows at roughly 1.25x above that. If you know the final size, pre-allocate with make([]T, 0, n) and every single append stays O(1). Interviewers love hearing this optimization stated unprompted.

s1 := []int{}              // len=0, cap=0; first append allocates
s2 := make([]int, 0, 100)  // len=0, cap=100; first 100 appends are O(1)

For a deeper look at why the amortized argument holds, see the amortized analysis guide.

The Aliasing Trap (The One That Gets Everyone)

A slice expression s[lo:hi] creates a new header but shares the same underlying array. Mutations through the subslice are visible in the original. This is not a bug. This is a feature. A feature that will absolutely ruin your backtracking solution at 11pm.

original := []int{1, 2, 3, 4}
sub := original[1:3]  // shares the array
sub[0] = 99
fmt.Println(original) // [1 99 3 4]

You mutate the subslice. The original array watches in horror. When you want a true snapshot in backtracking, use copy or append to a nil slice. Not a subslice expression. Never a subslice expression.

snapshot := append([]int(nil), path...) // always a fresh copy

Nil Slice vs Empty Slice

A nil slice (var s []int) and an empty slice (s := []int{}) both have length zero and both work with append. The distinction matters in exactly one place in interviews: JSON encoding. A nil slice marshals to null. An empty slice marshals to []. Know which one your problem expects, because "it works on my machine" is not a valid API contract.

Map: O(1) Average, Several Hidden Rules

Go maps are hash tables. Reads, writes, and deletes all run in O(1) average time and O(n) worst case. Go 1.24 replaced the internal bucket-based implementation with a Swiss Table design, bringing 20 to 50 percent performance improvements for large maps while keeping the same API. You probably will not need to mention this in an interview. Mention it anyway.

Operation	Time
Read `m[k]`	O(1) avg
Write `m[k] = v`	O(1) avg
Delete `delete(m, k)`	O(1) avg
`len(m)`	O(1)
Iterate `for k, v := range m`	O(n)
Comma-ok check `v, ok := m[k]`	O(1) avg

For the full treatment of how the hash table achieves O(1) and when it degrades, see hash map time complexity.

Writing to a nil map panics at runtime. Reading from a nil map returns the zero value safely. This asymmetry trips up every Go newcomer at least once. In an interview it trips you up exactly once, at the worst possible moment.

var m map[string]int
_ = m["x"]  // safe, returns 0
m["x"] = 1  // panic: assignment to entry in nil map

Always initialize with make or a map literal. Always. This is not optional advice.

m := make(map[string]int)

Iteration Order Is Randomized

Go randomizes map iteration order intentionally, starting from Go 1. This was a deliberate design decision to prevent developers from accidentally depending on a specific order that just happened to work. If your solution requires sorted output from a map, extract keys, sort them, then iterate.

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
    fmt.Println(k, m[k])
}

This adds O(n log n) for the sort on top of O(n) for the extraction. Say that complexity out loud when you do it.

The Comma-Ok Pattern

Accessing a missing key returns the zero value. To tell "not present" from "present with a zero value," use the two-return form. Interviewers treat this as table-stakes idiomatic Go. Use it any time your logic depends on key existence, which is most of the time.

v, ok := m["missing"]
if !ok {
    // key does not exist at all
}

The Set Idiom

Go has no built-in set. The standard pattern is map[T]struct{}. The empty struct takes zero bytes, so the map stores only keys with no memory overhead per entry. It looks weird the first time. It looks correct after that.

seen := make(map[int]struct{})
seen[42] = struct{}{}
if _, ok := seen[42]; ok {
    fmt.Println("found")
}

String Concatenation Will Silently Destroy You

Go strings are immutable byte slices. Concatenating with + in a loop allocates and copies on every step: O(n²) total time. This is the same trap as Python's str +=. It runs fine on small inputs during development and melts down on anything real.

// O(n²): don't do this
result := ""
for _, s := range parts {
    result += s
}

// O(n): use strings.Builder
var b strings.Builder
for _, s := range parts {
    b.WriteString(s)
}
result := b.String()

strings.Builder amortizes allocations the same way a dynamic array does, doubling capacity on overflow. b.WriteByte(c) and b.WriteRune(r) are O(1) amortized and the right choice when building character by character.

The sort Package: O(n log n) Worst Case, No Excuses

Go's sort package uses PDQSort (Pattern-Defeating QuickSort), which guarantees O(n log n) in the worst case. Classic quicksort could degrade to O(n²) on adversarial inputs. PDQSort does not, which means you can sort with confidence and no defensive pivoting.

Function	Time	Notes
`sort.Ints(s)`	O(n log n)	Convenience wrapper
`sort.Strings(s)`	O(n log n)	Convenience wrapper
`sort.Slice(s, less)`	O(n log n)	Unstable
`sort.SliceStable(s, less)`	O(n log n)	Stable
`sort.Search(n, f)`	O(log n)	Binary search

sort.Slice is the workhorse for custom comparators. It is not stable. If two elements compare equal and their original order must be preserved, use sort.SliceStable. Saying this distinction unprompted makes you sound like someone who has been burned by this before. Which is exactly the right impression.

// Sort by length, then lexicographically on ties
sort.Slice(words, func(i, j int) bool {
    if len(words[i]) != len(words[j]) {
        return len(words[i]) < len(words[j])
    }
    return words[i] < words[j]
})

Go 1.21 added the slices package with generic variants (slices.Sort, slices.SortFunc, slices.BinarySearch). If the judge supports Go 1.21 or later, these are type-safe alternatives worth using.

sort.Search Is Binary Search

sort.Search finds the smallest index i in [0, n) at which a monotone predicate becomes true. It is Go's standard binary search primitive and it is slightly weird looking until it isn't.

// First index where s[i] >= target
idx := sort.Search(len(s), func(i int) bool {
    return s[i] >= target
})
// idx == len(s) means target is not present

O(log n). Say that. Every time.

container/heap: Other Languages Give You a Priority Queue. Go Gives You Lumber.

Go has no built-in priority queue. container/heap turns any type implementing five methods into a heap. Five methods. Not one. Five.

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 any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

Operation	Time
`heap.Init(h)`	O(n)
`heap.Push(h, x)`	O(log n)
`heap.Pop(h)`	O(log n)
Peek minimum `(*h)[0]`	O(1)

heap.Init builds the heap bottom-up in O(n), not O(n log n). This is Floyd's build algorithm and it matters for problems where you initialize once from an existing slice before querying. Mentioning this earns a small complexity bonus point.

To flip to a max-heap, reverse the Less predicate: return h[i] > h[j]. For the underlying theory, see the heap data structure guide.

The boilerplate is real. Under interview pressure, have the five-method skeleton memorized cold. Not almost memorized. Cold.

The Gaps and the Workarounds

Go does not have everything. Here is what it expects you to build yourself:

Structure	Go's workaround
Set	`map[T]struct{}`
Priority queue	`container/heap` with interface
Deque	Slice with head index
Stack	Slice (`append` and reslice)
Ordered map	Extract keys, sort, iterate
Linked list	`container/list` (rarely worth the interface cost)

The BFS queue pattern that matters most in interviews is a slice with a head pointer, not q = q[1:]. The reslice looks clean. It shifts all elements left in O(n). Over a full BFS that adds up quietly until it doesn't. The head-pointer version keeps every dequeue at O(1).

q := []int{start}
head := 0
for head < len(q) {
    node := q[head]
    head++
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            visited[neighbor] = true
            q = append(q, neighbor)
        }
    }
}

Five Traps That Show Up in Go Interviews

1. Nil map write panics. Initialize with make before writing. Reads are safe on a nil map. Writes are a runtime panic. The compiler will not warn you.

2. Subslice aliasing. s[lo:hi] shares the backing array. Use append([]T(nil), s[lo:hi]...) when you need a real copy. In backtracking especially.

3. Map iteration order is random. Sort keys explicitly if output order matters. Do not trust a consistent order that happens to appear in testing.

4. String concatenation in a loop is O(n²). Use strings.Builder instead of +=. The difference will not show up on small test cases and will destroy performance on large ones.

5. sort.Slice is unstable. Use sort.SliceStable when equal-element order matters. Knowing which one to reach for, and why, is the kind of thing that earns a "strong hire" note.

Knowing the complexity is half the battle. The other half is explaining it under pressure while also writing the code. SpaceComplexity runs voice-based mock interviews where you narrate your data structure choices in real time and get rubric-based feedback on what lands and what gets you a "can you clarify that?"