Wrong Data Structure — Find the Bug¶

Category: Performance Anti-Patterns → Wrong Data Structure — a collection whose cost model fights the access pattern.

This is critical-reading practice. Each snippet is a plausible chunk of real-world Go, Java, or Python. Read it the way a performance-aware reviewer does and answer:

What's the structure/access mismatch? What's its big-O cost? What structure fixes it, and what's the new big-O?

The "bug" is rarely a crash — it's a latent cost in the shape: an O(n) operation done in a loop, a re-sort per query, a list used as a queue. Several would sail through a casual review because each line looks cheap. One snippet is a trap: the "naive" slice is the correct choice for its small, bounded n — converting it to a map would be slower and noisier. Spot which one.

How to use this file: read each snippet and write your own answer before expanding. The skill is noticing the cost model, not recalling a name.

Table of Contents¶

1. The allowlist filter
2. The order enricher
3. The next-cheapest picker
4. The event queue
5. The reconciliation report
6. The HTTP method check
7. The leaderboard top-10

Snippet 1 — The allowlist filter¶

# Python — filter a stream of events down to allowed users
def allowed_events(events, allowlist):     # allowlist: list[int]
    return [e for e in events if e.user_id in allowlist]

What's the mismatch, its big-O, and the fix?

def allowed_events(events, allowlist):
    allowed = set(allowlist)               # O(m), once
    return [e for e in events if e.user_id in allowed]  # O(1) per check

Snippet 2 — The order enricher¶

// Go — attach a product name to each line item
func enrich(items []LineItem, products []Product) {
    for i := range items {
        for _, p := range products {        // scan all products...
            if p.SKU == items[i].SKU {      // ...to find the matching one
                items[i].Name = p.Name
                break
            }
        }
    }
}

What's the mismatch, its big-O, and the fix?

func enrich(items []LineItem, products []Product) {
    byID := make(map[string]string, len(products))
    for _, p := range products {            // build once: O(m)
        byID[p.SKU] = p.Name
    }
    for i := range items {                  // O(n)
        if name, ok := byID[items[i].SKU]; ok {   // O(1) average
            items[i].Name = name
        }
    }
}

Snippet 3 — The next-cheapest picker¶

// Java — repeatedly pull the cheapest pending task
class Scheduler {
    private List<Task> pending = new ArrayList<>();

    Task next() {
        pending.sort(Comparator.comparingInt(Task::cost)); // re-sort every call
        return pending.remove(0);                          // take the cheapest
    }
}

What's the mismatch, its big-O, and the fix?

class Scheduler {
    private final PriorityQueue<Task> pending =
        new PriorityQueue<>(Comparator.comparingInt(Task::cost));

    void add(Task t) { pending.offer(t); }   // O(log n)
    Task next()      { return pending.poll(); }  // O(log n), min at the root
}

Snippet 4 — The event queue¶

# Python — process events in FIFO order, fanning out new ones
def run(seed):
    queue = list(seed)
    while queue:
        ev = queue.pop(0)              # take from the front
        for child in handle(ev):
            queue.append(child)        # add to the back

What's the mismatch, its big-O, and the fix?

from collections import deque

def run(seed):
    queue = deque(seed)
    while queue:
        ev = queue.popleft()           # O(1)
        for child in handle(ev):
            queue.append(child)        # O(1) amortized

Snippet 5 — The reconciliation report¶

// Go — for every transaction, find duplicates by amount+date
func findDuplicates(txns []Txn) [][2]Txn {
    var dups [][2]Txn
    for i := 0; i < len(txns); i++ {
        for j := i + 1; j < len(txns); j++ {       // compare every pair
            if txns[i].Amount == txns[j].Amount &&
                txns[i].Date == txns[j].Date {
                dups = append(dups, [2]Txn{txns[i], txns[j]})
            }
        }
    }
    return dups
}

What's the mismatch, its big-O, and the fix?

func findDuplicates(txns []Txn) [][2]Txn {
    type key struct {
        Amount int
        Date   string
    }
    groups := make(map[key][]Txn)
    for _, t := range txns {                    // O(n): one pass to group
        k := key{t.Amount, t.Date}
        groups[k] = append(groups[k], t)
    }
    var dups [][2]Txn
    for _, g := range groups {                  // emit pairs within each group
        for i := 0; i < len(g); i++ {
            for j := i + 1; j < len(g); j++ {
                dups = append(dups, [2]Txn{g[i], g[j]})
            }
        }
    }
    return dups
}

Snippet 6 — The HTTP method check¶

// Go — is this an HTTP method that may carry a body?
func methodHasBody(method string) bool {
    bodyMethods := []string{"POST", "PUT", "PATCH"}
    for _, m := range bodyMethods {       // linear scan of 3 elements
        if m == method {
            return true
        }
    }
    return false
}

What's the mismatch, its big-O, and the fix?

// The only worthwhile tweak: build the literal once, not per call.
var bodyMethods = []string{"POST", "PUT", "PATCH"}

func methodHasBody(method string) bool {
    for _, m := range bodyMethods {
        if m == method {
            return true
        }
    }
    return false
}

Snippet 7 — The leaderboard top-10¶

# Python — top 10 players by score from a 5-million-row table
def top_10(players):                       # players: list of (name, score)
    ranked = sorted(players, key=lambda p: p[1], reverse=True)  # sort all 5M
    return ranked[:10]

What's the mismatch, its big-O, and the fix?

import heapq

def top_10(players):
    return heapq.nlargest(10, players, key=lambda p: p[1])  # O(n log k), O(k)

Scorecard¶

The trap (Snippet 6) is the whole point: the anti-pattern is a structure that fights the access pattern at the real n. Below the crossover, the "naive" linear scan is the right answer — and turning it into a hash structure is itself a wrong-structure choice in the opposite direction.

Related Topics¶

• tasks.md — fix these mismatches yourself, with benchmarks (Exercise 6 measures the crossover behind Snippet 6).
• optimize.md — a full before/after with profiling and numbers, including the crossover caveat.
• junior.md · middle.md · senior.md · professional.md — recognize → pick → choose-in-context → deep trade-offs.
• Premature Optimization Traps → find-bug — the opposite reviewer reflex: don't "fix" what isn't a measured hotspot.
• The big-o-analysis, hash-table-design, and profiling-techniques skills — the cost model behind every answer here.