Thinking in Algorithms

What Is an Algorithm

An algorithm is a finite, precise sequence of steps that transforms an input into a desired output. Recipes, driving directions, and long division are informal algorithms; a sorting routine is a formal one. What separates engineering from trial and error is the ability to describe these steps precisely, argue that they are correct, and predict how much they cost.

Definition & Properties

Donald Knuth lists five properties every algorithm must have. They are worth keeping as a checklist whenever you design a procedure:

• Finiteness — it always stops after a finite number of steps.
• Definiteness — every step is unambiguous; two engineers would execute it identically.
• Input — it takes zero or more values from a specified set.
• Output — it produces one or more results with a specified relation to the input.
• Effectiveness — every step is basic enough to be carried out exactly.

Algorithm vs Program

An algorithm is the idea; a program is one implementation of it in a particular language, with real types, memory, and error handling. The same binary search algorithm can be written in Go, C, or Python. This separation matters: you reason about correctness and cost at the algorithm level, then deal with language details (overflow, allocation, error values) at the program level. Both levels can contain bugs.

Why Go for This Roadmap

Go is a good teaching language for data structures because it hides very little. Slices expose their length and capacity, pointers are explicit but safe, there is no hidden inheritance, and the standard library supplies only a few containers, so you build the rest yourself and understand them. Generics (Go 1.18+) let you write reusable containers once you understand the concrete version.

Install Go from go.dev/dl, then run any demo in this roadmap as a single file:

# check the installed toolchain (Go 1.23 or newer is assumed)
go version

# run one demo file directly — no module or project setup needed
go run 01_find_max.go

# static checks catch common mistakes before you run anything
go vet 01_find_max.go

The Problem-Solving Workflow

Experienced engineers rarely produce an optimal solution in one step. They follow a loop: understand the problem, try examples, write something correct, measure its cost, and improve it only if the cost is too high. The diagram shows this loop; the rest of the section explains each step.

The workflow: a correct brute-force solution comes first and becomes the oracle that every faster version is tested against. Optimization is a loop back through analysis, not a single leap.

Understand the Problem

Restate the problem in your own words and write down three things before any code: the input (types, sizes, can it be empty, can values be negative or repeated?), the output (a value, an index, a list, or an error?), and the constraints (how large can the input be, how fast must the answer be?). Most bugs in interviews and production code come from an unasked question here.

Work Examples First

Write small inputs and their expected outputs by hand. Include a typical case plus the cases that break naive code: empty input, one element, all equal, the answer at the first or last position, negative numbers. These examples become your tests, and working them by hand usually reveals the algorithm.

Start with Brute Force

The brute-force solution tries every possibility directly. It is often slow, but it is easy to get right, and it gives you something valuable: an oracle, a trusted reference against which you check faster versions on thousands of random inputs. Never skip it just because you suspect it is too slow.

Look for Repeated Work

To optimize, ask: what work does my solution repeat? The answer points to the technique. Repeatedly scanning for a value suggests a hash map. Repeatedly comparing against every element suggests sorting first. Repeatedly solving the same subproblem suggests memoization. Each later phase of this roadmap is, in effect, a catalog of ways to remove repeated work.

Reasoning About Correctness

Tests show that code works for the inputs you tried. Reasoning shows it works for all inputs. You need both: reasoning to design the code, tests to catch the gap between what you meant and what you typed.

Loop Invariants

A loop invariant is a statement that is true before the loop starts and remains true after every iteration. If it is true when the loop ends, and the loop ends, the result is correct. The example below finds a maximum; the comment states the invariant that justifies each line.

// findMax returns the largest element of nums, or an error when nums is empty.
func findMax(nums []int) (int, error) {
	if len(nums) == 0 {
		// There is no correct integer to return for "max of nothing",
		// so the empty case is an error, not a magic value like 0.
		return 0, errors.New("findMax: empty input")
	}
	best := nums[0] // invariant holds: best = max(nums[0..0])
	for i := 1; i < len(nums); i++ {
		// invariant at this point: best = max(nums[0..i-1])
		if nums[i] > best {
			best = nums[i]
		}
		// invariant restored: best = max(nums[0..i])
	}
	// loop ended with i == len(nums): best = max of the whole slice
	return best, nil
}

Full program with a table of test cases: 01_find_max.go.

Edge Cases Checklist

Run through this list for every function that takes a collection. Each item has broken real production code:

Table-Driven Tests in Go

Go's idiomatic test style stores examples as a table of structs and runs one loop over them. Put this in a file ending in _test.go next to the code and run go test. Adding a new case is one line, so edge cases are cheap to keep.

// findmax_test.go — run with: go test
package main

import "testing"

func TestFindMax(t *testing.T) {
	tests := []struct {
		name    string
		in      []int
		want    int
		wantErr bool
	}{
		{"typical", []int{3, 7, 2}, 7, false},
		{"all negative", []int{-5, -2, -8}, -2, false},
		{"empty", nil, 0, true},
	}
	for _, tt := range tests {
		// t.Run gives every case its own name in the test report
		t.Run(tt.name, func(t *testing.T) {
			got, err := findMax(tt.in)
			if (err != nil) != tt.wantErr {
				t.Fatalf("error = %v, wantErr %v", err, tt.wantErr)
			}
			if !tt.wantErr && got != tt.want {
				t.Errorf("findMax(%v) = %d, want %d", tt.in, got, tt.want)
			}
		})
	}
}

Case Study: Two Sum

Problem: given a slice of integers and a target, return the indices of two different elements that add up to the target. This small problem shows the entire workflow: a brute-force oracle, then two optimizations that each remove a different kind of repeated work.

Version 1: Every Pair

The direct approach checks every pair once. With n elements there are n(n-1)/2 pairs, so the cost grows with the square of the input.

// twoSumBrute checks all pairs: O(n^2) time, O(1) extra space.
func twoSumBrute(nums []int, target int) (int, int, bool) {
	for i := 0; i < len(nums); i++ {
		// j starts at i+1: each pair once, never an element with itself
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				return i, j, true
			}
		}
	}
	return 0, 0, false
}

Version 2: Sort and Two Pointers

Repeated work: for each element we scan all others. If the values are sorted, one comparison tells us which side to discard. Put a pointer at each end: when the sum is too small, the left value cannot pair with anything (every other right value is smaller still), so move left up; when it is too large, move right down. Each step eliminates one candidate, so the scan is linear and sorting dominates at O(n log n). The full version in the demo keeps the original indices while sorting.

Version 3: Remember What You Have Seen

Repeated work: for each element x we search for target - x. A map answers "have I seen this value?" in constant average time, so a single pass is enough.

// twoSumMap: one pass, O(n) time, O(n) extra space for the map.
func twoSumMap(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int, len(nums)) // value -> index
	for j, x := range nums {
		if i, ok := seen[target-x]; ok {
			return i, j, true
		}
		// store AFTER the lookup, so x is never paired with itself
		seen[x] = j
	}
	return 0, 0, false
}

Comparing the Three

None of the versions is "best" in every situation. The table summarizes the trade-off; the demo measures all three on the same worst-case inputs and verifies each answer against the brute-force oracle.

Full program with correctness checks and timings: 02_two_sum_three_ways.go.

Common Pitfalls

These mistakes appear in beginner and senior code alike. Each has a simple habit that prevents it.

Magic Initial Values

Starting a maximum at 0 or a minimum at 999999 silently fails on inputs outside the range you imagined. Initialize from a real element (nums[0]) or use the type's limit from the math package (math.MinInt), and handle empty input explicitly.

Off-by-One Errors

Loop bounds (< vs <=), inclusive vs exclusive ranges, and len-1 are the most common source of bugs in array code. Decide on one convention — Go slices use half-open ranges [lo, hi) — state it in a comment, and test the first and last positions.

Optimizing Too Early

An unverified fast solution is worth less than a verified slow one. Optimize only after the brute-force version works and the analysis shows it is too slow for the stated constraints — and keep the brute-force version as the test oracle.

Practice Lab

Reading is not enough; the goal is to build the habit of specifying, testing, and analyzing before coding.

Run the Demos

1. Open 01_find_max.go, change best := nums[0] to best := 0, and run it. Which case fails, and why?
2. Open 02_two_sum_three_ways.go and move seen[x] = j above the lookup in twoSumMap. Find the example that now gives a wrong answer.

Exercises

1. Second largest. Write secondMax(nums []int) (int, error). Specify first: what is the second largest of [5, 5, 3]? Write the table of cases before the code.
2. Count pairs. Change Two Sum to count all pairs that reach the target. Write the brute-force version, then a map version, and check them against each other on random inputs.
3. Invariant practice. Write the loop invariant for a function that returns the index of the first negative number, or -1 if none exists.

Next lesson: Complexity Analysis — how to predict cost before running code.