Introduction to Data Structures & Algorithms — Middle Level¶

Table of Contents¶

1. Introduction
2. Why DSA Matters Beyond Performance
3. The Engineer's Decision Framework
4. Reading the Access Pattern
5. Trade-Off Axes Every Structure Sits On
6. How Algorithmic Strategies Map to Problems
7. Asymptotic vs Real-World Cost
8. Choosing a Structure — Worked Examples
9. Composing Data Structures
10. When DSA Goes Wrong in Production
11. Standard Library vs Hand-Rolled
12. Code Examples — Same Problem, Stronger Solutions
13. How to Practice at the Middle Level
14. Summary

Introduction¶

Focus: "Why does the choice matter?" and "When do I reach for which tool?"

The junior file answered what is DSA. The middle level is about judgement: given a vague requirement and a real codebase, how do you pick the right data structure and algorithm, justify the choice, and recognize the trade-offs you accepted? Middle engineers do not memorize structures — they read access patterns and derive the structure.

This document covers the decision framework, the axes you trade along, the gap between asymptotic and wall-clock performance, common composite structures, and the production failure modes that come from a wrong choice.

Why DSA Matters Beyond Performance¶

Performance is the obvious reason. But once you are past the junior stage, three more reasons start to dominate:

1. Data structure choice constrains future evolution¶

Once a hot path uses a particular structure, everything around it inherits that structure's assumptions. Choose a list when you need a set, and every caller has to defensively deduplicate forever. Choose a synchronous queue when you needed a pub/sub, and every new feature has to bolt on filtering. The right structure pays you back for years; the wrong one taxes every future change.

2. The structure encodes the invariant¶

A set "cannot contain duplicates" is a guarantee enforced by the structure itself — no caller can violate it. A min-heap "always returns the smallest pending item" is enforced by the structure. Picking the right structure means the invariant is unbreakable, instead of being a comment that some future commit will silently invalidate.

3. Communication and design vocabulary¶

"This is a write-behind cache with LRU eviction on top of an LSM-tree-backed store" is unambiguous and takes five seconds to say. The same sentence in code-level terms ("a buffer that flushes asynchronously...") takes a paragraph and is ambiguous. DSA is the shared dialect of system design.

The Engineer's Decision Framework¶

A middle engineer applies the same checklist on every non-trivial design:

1. Characterize the data.
2. Size (10? 10⁶? 10¹²?)
3. Mutability (read-only? frequent updates?)
4. Distribution (uniform? skewed? streaming?)

5. Domain (integers in a small range? arbitrary strings?)

6. Characterize the operations.

7. What is the ratio of reads to writes?
8. Which operations must be O(1) or O(log n)?
9. Which can be amortized? Which can be batched?
10. Are queries point queries, range queries, or aggregates?

11. Do you need stable ordering, or is "some order" acceptable?

12. Characterize the constraints.

13. Memory budget — RAM, cache, disk?
14. Latency SLA — p50, p99, p99.9?
15. Concurrency — readers/writers, single-threaded, distributed?
16. Persistence — in-memory only, write-through, write-back?

17. Failure model — must we survive crash mid-update?

18. Match the structure to the answers. This is mechanical once steps 1–3 are honest.

19. Estimate the resulting Big-O and back-of-envelope cost. Verify the operation budget fits the latency SLA before writing code.

The mistake of a junior engineer is to skip directly to step 4. The mistake of a senior who skipped this discipline is to skip steps 1–3 and pick the structure they used last week.

Reading the Access Pattern¶

The "access pattern" is the most useful concept at the middle level. It is the answer to: "Across all operations my code will perform, what are the dominant ones, and what shape do they have?"

Common access patterns¶

A single application usually has more than one access pattern, which is why structures are routinely composed (see Composing Data Structures).

Trade-Off Axes Every Structure Sits On¶

Every data structure can be described as a point on a small number of axes. There is no free lunch: gaining on one axis costs on another.

A middle engineer can articulate which axis they prioritized and which they sacrificed for any design choice.

How Algorithmic Strategies Map to Problems¶

Algorithms group into a small number of families. Each family has a question that selects it.

Middle-level practice is partly about training your pattern recognition so that the right family announces itself when you read the problem.

Asymptotic vs Real-World Cost¶

Big-O is necessary, but it is not sufficient. At the middle level you start caring about the constants.

1. Cache locality matters more than asymptotics for small n¶

For arrays of fewer than ~10⁴ elements, a linear scan over a contiguous slice beats a binary tree lookup, because the array fits in L1/L2 cache and the tree does not.

Hardware reality: a single L1 cache hit is ~1 ns; an L3 miss to RAM is ~100 ns; an SSD read is ~100 µs. A "fast" algorithm that pointer-chases through RAM is 100× slower than an "asymptotically worse" one that walks contiguous memory.

2. Hidden constants in language libraries¶

The middle engineer asks: "What is the actual cost, not the textbook cost?"

3. Worst case vs typical case¶

A hash table is O(1) average but O(n) worst case under adversarial input. For an internal cache that does not see attacker-controlled keys, the average case is what you ship. For a public API that accepts user-controlled keys, you must consider the worst case — which is why many languages (Python, Go, Java) randomize hash seeds at startup.

4. Amortized cost¶

A dynamic array's push is O(1) amortized but each individual push may be O(n) when it grows the backing buffer. For batch work this is fine. For a real-time system with strict per-operation latency, "amortized O(1)" can still violate the SLA on a single bad operation. The right tool there is a structure with worst-case bounds, e.g. a deque with fixed-size chunks.

Choosing a Structure — Worked Examples¶

Example 1: Rate limiter — last 60 seconds of request timestamps¶

Operations:

• record(now): append a timestamp.
• count(): how many timestamps are within the last 60 s?

Access pattern: append-on-one-end + expire-from-the-other-end + count. This is a sliding window.

Wrong: a plain list (O(n) to drop stale entries). Right: a deque. Append on the right; pop from the left while the left entry is older than now - 60. Then len(deque) is the answer. Each operation is O(1) amortized.

Example 2: Spell checker¶

Operations:

• is_word(s): is s in the dictionary?
• suggestions(prefix): list all words starting with prefix.

Access pattern: membership + prefix lookup.

Wrong: a hash set (no prefix support). Right: a trie. Membership is O(|s|). Prefix lookup walks down the trie to the prefix node and DFS-collects the subtree.

Example 3: Job scheduler¶

Operations:

• submit(job, priority).
• nextJob(): returns the highest-priority pending job.

Access pattern: insert anywhere + extract maximum.

Wrong: a sorted list (O(n) insert). Right: a max-heap. Both ops are O(log n).

Example 4: Online median (data arrives one at a time, query median anytime)¶

Wrong: re-sort the whole list every time you want the median (O(n log n) per query). Right: two heaps — a max-heap for the lower half, a min-heap for the upper half, kept balanced. Insert O(log n), query O(1).

Example 5: Detect duplicate URLs in a 100 GB log on a 16 GB machine¶

Constraint: the full set cannot fit in RAM.

Wrong: a hash set (will OOM). Right: a Bloom filter for the membership check, accepting some false positives, with a slower exact check on the suspicious subset. If you must be exact, an external-memory hash or sort-merge dedup.

These five examples illustrate the entire middle-level skill: read the access pattern, list the constraints, pick the structure whose strengths match.

Composing Data Structures¶

Real systems almost never use one structure in isolation. The middle level introduces composite structures.

LRU cache = hash map + doubly linked list¶

• Hash map gives O(1) key lookup.
• Doubly linked list gives O(1) move-to-front and evict-from-back.
• Together: O(1) get and put, with bounded size and least-recently-used eviction.

Median data stream = max-heap + min-heap¶

Already shown above. Two heaps cover two access patterns the language's standard heap cannot do alone.

Index on a database = B+ tree + bloom filter (often)¶

• B+ tree provides ordered, paged on-disk access.
• An optional Bloom filter per page short-circuits the "definitely not here" case without a disk read.

Inverted index = hash map + posting list¶

• Hash map: term → posting list of document IDs.
• Posting list: usually a sorted array, sometimes compressed (variable-byte, Roaring bitmaps).
• Together: full-text search.

Counter with top-K = hash map + heap¶

• Hash map for counts.
• Heap (size K) for the running top-K.

The lesson: when no single structure satisfies all your access patterns, layer them.

When DSA Goes Wrong in Production¶

Middle engineers learn DSA partly from the literature and partly from the production incidents listed here. These failures recur.

Each is a DSA problem in disguise.

Standard Library vs Hand-Rolled¶

A general rule for middle engineers:

Use the standard library by default. Hand-roll a structure only when (a) the standard library does not provide it, (b) you have measured and the standard library version is the bottleneck, or (c) the educational value is the point.

Library choices by language¶

Knowing what your standard library provides is itself a DSA skill.

Code Examples — Same Problem, Stronger Solutions¶

A classic middle-level problem: longest substring without repeating characters. Three solutions illustrate the progression of thinking.

Naïve — try every substring (O(n³))¶

Go¶

package main

import "fmt"

func longestUnique(s string) int {
    best := 0
    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            seen := map[byte]bool{}
            ok := true
            for k := i; k < j; k++ {
                if seen[s[k]] {
                    ok = false
                    break
                }
                seen[s[k]] = true
            }
            if ok && j-i > best {
                best = j - i
            }
        }
    }
    return best
}

func main() { fmt.Println(longestUnique("abcabcbb")) }

Java¶

public class LongestUniqueNaive {
    public static int longestUnique(String s) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                boolean[] seen = new boolean[128];
                boolean ok = true;
                for (int k = i; k < j; k++) {
                    if (seen[s.charAt(k)]) { ok = false; break; }
                    seen[s.charAt(k)] = true;
                }
                if (ok) best = Math.max(best, j - i);
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb"));
    }
}

Python¶

def longest_unique_naive(s):
    best = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            if len(set(s[i:j])) == j - i:
                best = max(best, j - i)
    return best

if __name__ == "__main__":
    print(longest_unique_naive("abcabcbb"))

Better — sliding window with a hash set (O(n))¶

Go¶

package main

import "fmt"

func longestUniqueWindow(s string) int {
    seen := map[byte]bool{}
    left, best := 0, 0
    for right := 0; right < len(s); right++ {
        for seen[s[right]] {
            delete(seen, s[left])
            left++
        }
        seen[s[right]] = true
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

func main() { fmt.Println(longestUniqueWindow("abcabcbb")) }

Java¶

import java.util.HashSet;

public class LongestUniqueWindow {
    public static int longestUnique(String s) {
        HashSet<Character> seen = new HashSet<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            while (seen.contains(s.charAt(right))) {
                seen.remove(s.charAt(left++));
            }
            seen.add(s.charAt(right));
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb"));
    }
}

Python¶

def longest_unique_window(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

if __name__ == "__main__":
    print(longest_unique_window("abcabcbb"))

Strongest — sliding window with a lastSeen map (still O(n), fewer rewinds)¶

Go¶

package main

import "fmt"

func longestUniqueFast(s string) int {
    last := make(map[byte]int)
    left, best := 0, 0
    for right := 0; right < len(s); right++ {
        if idx, ok := last[s[right]]; ok && idx >= left {
            left = idx + 1
        }
        last[s[right]] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

func main() { fmt.Println(longestUniqueFast("abcabcbb")) }

Java¶

import java.util.HashMap;

public class LongestUniqueFast {
    public static int longestUnique(String s) {
        HashMap<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c) && last.get(c) >= left) {
                left = last.get(c) + 1;
            }
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb"));
    }
}

Python¶

def longest_unique_fast(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

if __name__ == "__main__":
    print(longest_unique_fast("abcabcbb"))

The improvement from version 2 to version 3 is a middle-level move: same Big-O, smaller constant, achieved by storing more useful information.

How to Practice at the Middle Level¶

The junior file said "implement, do not just read". The middle file extends that:

1. Implement, then optimize. Solve a problem with the obvious approach; then re-solve it asking "where is the wasted work?". The second pass is where you learn pattern recognition.

2. State invariants before writing code. What property of the data structure must always hold? If you cannot state it, your loop conditions will be wrong.

3. Practice naming the access pattern. Before solving any problem, write one sentence describing its access pattern. "This is a range-sum problem with point updates." If the sentence is sharp, the structure follows.

4. Read production source code. The Java HashMap, Go runtime/map.go, Python dictobject.c, Redis dict.c — each one is a master class in DSA in the wild. Reading these teaches you what real hash tables look like, not the textbook diagram.

5. Time your solutions. Add a microbenchmark to every non-trivial implementation. The gap between your model of "fast" and the measured truth is where you learn the most.

6. Reproduce failures. When a colleague reports "the cache is slow", write the smallest reproduction. Half the time the bug is a DSA mistake (unbounded growth, accidental quadratic, lock contention).

7. Vary the inputs. Every solution should be tested on: empty, single element, all-duplicates, already-sorted, reverse-sorted, large random, adversarially-crafted. This is what hardens your code beyond toy examples.

Summary¶

At the middle level, DSA is no longer about memorizing structures — it is about reading the access pattern of a problem and deriving the structure from it. You learn to articulate trade-offs (read vs write, time vs space, worst vs average, exact vs approximate), to spot when a single structure does not suffice and structures must be composed (LRU cache, median-of-stream), and to recognize the production failure modes that come from a wrong choice.

Asymptotic complexity is necessary but not sufficient: at this level you also reason about cache locality, hidden constants, amortized vs worst-case bounds, and adversarial inputs. The standard library is your default — hand-rolling is reserved for the rare case where it is justified.

The next file, senior.md, takes the same problems and embeds them in distributed systems, concurrency, and observability. The level after that, professional.md, proves the bounds formally.