Data Structures, Algorithms and Programming Patterns · Part 9 of 9

Data Structures and Algorithms, Part 9: Study Path and Quicksheet

You now know the main data structures and the main ways to solve problems with them. This last part is the one to bookmark: a recap, a Big-O quicksheet, a table for choosing a structure, a practice routine, testing habits, real systems that use these ideas, and projects to build next.

1. The series on one page

You have come a long way. This part is a map you can come back to: what each part gave you, a quicksheet of costs, and a plan for what to do next. Keep it open in a tab while you practise.

2. Big-O, Theta and Omega

Part 1 used Big-O for everything. There are really three symbols, and together they say how a cost sits against a growth rate. Think of a speed limit sign.

The definition, in words

Say f(n) is the number of steps. We write f(n) = O(g(n)) when, for large enough n, f(n) is never more than some constant times g(n). We write f(n) = Ω(g(n)) when it is never less than some (smaller) constant times g(n). We write f(n) = Θ(g(n)) when both are true.

Example: f(n) = 3n + 10. It is O(n) because 3n + 10 ≤ 4n once n ≥ 10. It is Ω(n) because 3n + 10 ≥ 3n. So it is Θ(n). It is also true, but loose, that it is O(n²). Always give the tightest bound you can.

fun f(n: Int): Long = 3L * n + 10        // the real cost, in steps

fun main() {
    println("n         f(n)        f/n     f/n^2")
    for (n in listOf(10, 100, 1000, 10_000, 100_000)) {
        val steps = f(n)
        println("%-9d %-11d %-7.2f %.6f".format(n, steps, steps.toDouble() / n, steps.toDouble() / n / n))
    }
    // f/n settles near 3: f is Theta(n). f/n^2 keeps shrinking: f is O(n^2) but not Omega(n^2).
}

Best case and worst case are not the same thing as O and Ω

This trips up almost everyone. Best, average and worst describe which input you feed the code. O, Ω and Θ describe how you bound a growth rate. You can use any symbol on any case: “the worst case is Θ(n)” and “the best case is O(1)” are both fine sentences.

Quicksheets squeeze this into one convention, and so do we below: Ω = best case, Θ = average (typical) case, O = worst case. It is a handy shortcut, not a law. Where an algorithm costs the same for every input, one Θ covers all three.

// Linear search: how many items do we look at?
fun stepsToFind(list: List<Int>, target: Int): Int {
    var steps = 0
    for (x in list) { steps++; if (x == target) return steps }
    return steps                       // not found: we looked at everything
}

fun main() {
    println("n        best (first)   typical (middle)   worst (last or missing)")
    for (n in listOf(10, 1000, 100_000)) {
        val list = List(n) { it }
        val best = stepsToFind(list, 0)
        val middle = stepsToFind(list, n / 2)
        val worst = stepsToFind(list, -1)
        println("%-8d %-14d %-18d %d".format(n, best, middle, worst))
    }
    // best is Omega(1) (always 1), typical is Theta(n) (about n/2), worst is O(n).
}

Growth rates, ranked

Learn this ladder by heart. Each rung eventually beats every rung below it, however large the constants.

1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ

Rules for simplifying

• Drop constants: 5n is Θ(n).
• Keep the biggest term: n² + 100n + 7 is Θ(n²).
• Steps in a row add: O(n) + O(n²) = O(n²).
• Steps inside steps multiply: a loop of n around a body of O(log n) is O(n log n).
• Different inputs, different letters: looping over lists of sizes m and n is O(m · n), not O(n²).
• The base of a logarithm does not matter: log₂ n and log₁₀ n differ by a constant.

Common recurrences

Recursive code is analysed with a recurrence: the cost of size n in terms of smaller sizes. These four cover most of what you will meet.

fun insertionSortSteps(input: List<Int>): Int {
    TODO("sort a copy and count how many times you compare two items")
}

fun insertionSortSteps(input: List<Int>): Int {
    val a = input.toMutableList()
    var comparisons = 0
    for (i in 1 until a.size) {
        val key = a[i]
        var j = i - 1
        while (j >= 0) {
            comparisons++
            if (a[j] > key) { a[j + 1] = a[j]; j-- } else break
        }
        a[j + 1] = key
    }
    return comparisons
}

3. Complete quicksheet: best, average and worst

Columns follow the convention above: Ω best, Θ average or typical, O worst. When one value is shown, all three agree. Variables: n items, V vertices, E edges, k key or word length, m a value range.

Data structures: average and worst case

Graph representations

Sorting algorithms

No sort that works only by comparing items can beat Ω(n log n) in the worst case (Part 6 shows why). Counting, radix and bucket sort escape that limit by not comparing.

Searching, graph and other algorithms

Dynamic programming and backtracking

Space complexity in one glance

• O(1): a few variables (iterative loops, two pointers, in-place swaps).
• O(log n): recursion that halves the input (binary search, quicksort’s call stack).
• O(n): one extra copy or table (hash set, merge sort buffer, memo array).
• O(n²): a table over pairs (adjacency matrix, LCS table).
• Recursion depth counts as space: a recursion n calls deep uses O(n) stack, even if it allocates nothing else.

4. Big-O quicksheet

Costs below are for the usual implementation and for the worst case unless the note says otherwise. n is the number of items, V and E are vertices and edges of a graph, and k is the length of a word or key.

Data structures

Algorithms

Standard-library names to remember: sorted() and sortedBy are O(n log n), HashMap is the hash map, TreeMap is the balanced tree map, PriorityQueue is the heap, and ArrayDeque is both stack and queue.

5. Which structure should I use?

Start from what you need to do, not from the structure. Ask which operation will run most often, then pick the structure that makes it cheap.

6. How to study this material

Reading is the easy part and the weakest. You learn algorithms the way you learn an instrument: by playing, making mistakes and repeating. Here is a routine that works for one session of about an hour.

1. Read one short section. Do not take notes yet.
2. Predict. Before you run a demo, write down what you think it prints. Being wrong here is useful; it shows where your mental model is off.
3. Run. Compare the output with your prediction.
4. Break it. Change a line on purpose: an off-by-one, a wrong comparison, an empty input. See what fails and how it fails.
5. Rewrite from memory. Close the page and write the code again. Peek only when you are truly stuck.
6. Explain aloud. Tell a friend, a rubber duck or an empty room how it works and what it costs. Gaps in your explanation are gaps in your understanding.

Habits that make it stick

• Spaced repetition. Revisit a topic after 1 day, 3 days, 1 week and 3 weeks. Rewrite the key code each time. Short and often beats long and once.
• Keep a mistakes log. A simple file with the date, the problem, what went wrong and the fix. Read it every week. You will notice you make the same three or four mistakes.
• Time-box being stuck. Give yourself 20 to 30 minutes of honest struggle. Then read a hint, then more of the solution. After that, close it and solve it yourself the next day. Struggling a little builds skill; struggling for hours just drains you.
• Trace by hand with a table. Take a tiny input and write one row per loop step with the variables as columns. The next demo does this in code.
• Change one thing at a time. When you modify code, run it after each small change.

An 8-week example schedule

About 4 to 6 hours a week works well. Adjust to your timetable; finishing slowly is better than rushing.

7. Debugging and testing algorithms

Algorithm bugs are sneaky: the code runs, the answer is just wrong for one input. A few habits catch most of them.

• Write the small tests first. Before the code, list inputs and expected outputs: empty, one item, two items, all equal, already sorted, reversed, duplicates, negative numbers.
• Keep the brute force. The slow, obviously correct version is your answer key for the fast one.
• Print the state. Print the variables at the top of each loop step, the same columns as your hand trace. Remove the prints when it works.
• Name the invariant. An invariant is a sentence that is true at the start of every loop step, such as "if the target exists, it is inside a[lo..hi]". If you can say it, you can check it with check(...).
• Shrink the failing case. Once a test fails, try to make the input smaller while it still fails. A bug on three numbers is much easier to see than a bug on three thousand.

Off-by-one checklist

• Does the range include or exclude the last index? (0 until n versus 0..n.)
• Is the loop < or <=? Try a list with one element.
• In binary search, does lo or hi move past mid, or can it get stuck?
• Is mid computed as lo + (hi - lo) / 2, which cannot overflow?
• Do you handle the empty input before touching a[0]?
• Is a "length" confused with a "last index"? Length is one more.

Watching an invariant at work

fun binarySearch(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size - 1
    var step = 1
    while (lo <= hi) {
        // Invariant: everything left of lo is smaller than target,
        // everything right of hi is bigger than target.
        if (lo > 0) check(a[lo - 1] < target) { "invariant broken on the left" }
        if (hi < a.size - 1) check(a[hi + 1] > target) { "invariant broken on the right" }

        val mid = lo + (hi - lo) / 2
        println("step $step: lo=$lo hi=$hi mid=$mid a[mid]=${a[mid]}")
        step++
        when {
            a[mid] == target -> return mid
            a[mid] < target -> lo = mid + 1
            else -> hi = mid - 1
        }
    }
    return -1
}

fun main() {
    val a = intArrayOf(1, 3, 5, 7, 9, 11)
    println("found at ${binarySearch(a, 7)}")
    println("found at ${binarySearch(a, 4)}")
}

A tiny property-style test

Hand-written tests only cover the cases you thought of. A randomized test generates hundreds of small inputs and compares the fast solution with the brute force. Using a fixed seed means the "random" inputs are the same on every run, so a failure can be repeated.

Below, the maximum sum of a contiguous slice. maxSumBuggy looks right but starts its best at 0, so it is wrong when every number is negative. Watch the test find that.

import kotlin.random.Random

// Slow but obviously correct: try every slice. O(n^2)
fun maxSumBrute(a: List<Int>): Int {
    var best = a[0]
    for (i in a.indices) {
        var sum = 0
        for (j in i until a.size) {
            sum += a[j]
            if (sum > best) best = sum
        }
    }
    return best
}

// Fast and correct: best slice that ends here. O(n)
fun maxSumFast(a: List<Int>): Int {
    var current = a[0]
    var best = a[0]
    for (i in 1 until a.size) {
        current = maxOf(a[i], current + a[i])
        best = maxOf(best, current)
    }
    return best
}

// Fast but wrong: starting at 0 means "take nothing" is allowed.
fun maxSumBuggy(a: List<Int>): Int {
    var current = 0
    var best = 0
    for (x in a) {
        current = maxOf(0, current + x)
        best = maxOf(best, current)
    }
    return best
}

fun compare(name: String, fast: (List<Int>) -> Int) {
    val random = Random(12345)               // fixed seed: same inputs every run
    repeat(1000) { trial ->
        val size = random.nextInt(1, 8)       // small inputs are easy to read
        val a = List(size) { random.nextInt(-5, 6) }
        val expected = maxSumBrute(a)
        val actual = fast(a)
        if (actual != expected) {
            println("$name FAILED on trial $trial: input=$a expected=$expected got=$actual")
            return
        }
    }
    println("$name passed 1000 random trials")
}

fun main() {
    compare("maxSumFast ", ::maxSumFast)
    compare("maxSumBuggy", ::maxSumBuggy)
}

Now try the idea yourself. The function below is slow. Write the fast version so that it matches the brute force and also handles a large input.

fun countPairsBrute(nums: List<Int>, target: Int): Long {
    var count = 0L
    for (i in nums.indices) for (j in i + 1 until nums.size) {
        if (nums[i] + nums[j] == target) count++
    }
    return count
}

fun countPairsFast(nums: List<Int>, target: Int): Long {
    TODO("walk once; keep a map of how many times each value has appeared")
}

fun countPairsBrute(nums: List<Int>, target: Int): Long {
    var count = 0L
    for (i in nums.indices) for (j in i + 1 until nums.size) {
        if (nums[i] + nums[j] == target) count++
    }
    return count
}

fun countPairsFast(nums: List<Int>, target: Int): Long {
    val seen = HashMap<Int, Int>()
    var count = 0L
    for (x in nums) {
        count += seen[target - x] ?: 0
        seen[x] = (seen[x] ?: 0) + 1
    }
    return count
}

8. Where this shows up in real systems

None of this is only for exercises. The same ideas sit under software you use every day.

Example: an LRU cache

LRU stands for least recently used. A cache is a small, fast store in front of something slow. When it is full and a new item arrives, it throws out the item that has gone unused the longest. To do that in O(1) you need two things: a hash map for fast lookup, and a list that remembers the usage order. Java and Kotlin's LinkedHashMap is exactly that pair in one class. With accessOrder = true, every get moves the entry to the back, and the oldest entry is at the front.

class LruCache<K, V>(private val capacity: Int) :
    LinkedHashMap<K, V>(16, 0.75f, true) {          // true = order by access

    // Called after every put. Returning true removes the oldest entry.
    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
        return size > capacity
    }
}

fun main() {
    val cache = LruCache<String, Int>(3)
    cache["a"] = 1
    cache["b"] = 2
    cache["c"] = 3
    println("start:        ${cache.keys}")      // [a, b, c]

    cache["a"]                                  // read a: it becomes the newest
    println("after get a: ${cache.keys}")      // [b, c, a]

    cache["d"] = 4                              // full, so the oldest (b) is evicted
    println("after put d: ${cache.keys}")      // [c, a, d]
    println("b present? ${cache.containsKey("b")}")
}

Your turn.

class LRUCache(private val capacity: Int) {
    private val map = LinkedHashMap<Int, Int>()

    fun get(key: Int): Int {
        TODO("return -1 if missing, otherwise move the key to the end and return the value")
    }

    fun put(key: Int, value: Int) {
        TODO("insert or update as most recent; evict the first key when over capacity")
    }
}

class LRUCache(private val capacity: Int) {
    private val map = LinkedHashMap<Int, Int>()

    fun get(key: Int): Int {
        val value = map.remove(key) ?: return -1
        map[key] = value
        return value
    }

    fun put(key: Int, value: Int) {
        map.remove(key)
        map[key] = value
        if (map.size > capacity) {
            val oldest = map.keys.first()
            map.remove(oldest)
        }
    }
}

9. Capstone mini-projects

The best way to make all of this yours is to build something. Each project below is small, uses one or two structures, and can be finished in a weekend. Pick one, write a few tests first, and use the randomized comparison trick from earlier where you can.

For each project, write down before you start: what the input is, what the output is, which structure fits each need (use the table in section 3) and what the cost should be. Afterwards, compare your plan with what you built.

10. Further reading

These are well-known books and tools. Several have free versions or free course material; search for the title to find the official source.

• Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. The standard university textbook. Thorough and mathematical; read it slowly, one chapter at a time.
• The Algorithm Design Manual by Steven Skiena. Friendly and practical, with a catalogue of problems and the structure that fits each.
• Algorithms by Robert Sedgewick and Kevin Wayne. Clear explanations with pictures; the companion website has code and slides.
• Grokking Algorithms by Aditya Bhargava. A very gentle, illustrated introduction. Good as a second look at Parts 1 to 5.
• Algorithms by Dasgupta, Papadimitriou and Vazirani. A short, well-written book with a free draft available from its authors.
• visualgo.net. Animated visualisations of sorting, trees, heaps, graphs and more. Step through an algorithm and watch the data change.
• The Kotlin documentation at kotlinlang.org. Look at the pages on collections, especially the lists, sets, maps and sequences, so you know what the standard library already gives you.
• The source of your language's standard collections. Reading how ArrayList, HashMap and PriorityQueue are written is a great second pass once you know the basics.

11. Takeaways

• Pick the structure from the operation, then check the cost in the table.
• Brute force is the answer key for your fast solution.
• Seeded random tests find bugs your hand-written tests miss, and can be repeated.
• Practise a little, often, and rewrite code from memory.
• Real systems use the same structures you have just built: trees, heaps, tries, graphs and hash maps.
• Keep building. A small project teaches more than another chapter.