The code comprehension round

How do you find what's wrong in code you've never seen, in under an hour?

Real work mostly means changing code someone else wrote. A round built around that makes sense, and it suits the AI era too, since reading code now matters more than typing it. Google's reported pilot is this kind of round.

The trap is to start changing things straight away. First get a picture: what's this meant to do, what are the main pieces, and what does it promise? A bug is simply a gap between a promise and what happens.

  • LRU: Least recently used. When a cache is full, it removes the item unused for the longest.
  • TTL: Time to live. How long an item stays valid.
  • Invariant: Something that must always be true, such as: size never exceeds max.

Steps:

  1. Read the names and the shape first. Types, public methods and comments tell you the promises.
  2. Write the promises down. Each promise is something you can test.
  3. Trace one normal call by hand. Follow the data through it.
  4. Test each promise. Start with a small script. Each failure is a lead.
  5. Fix the cause. Then rerun everything.
  6. Ask AI to explain, then check. It's good at summaries, but it can describe what code should do rather than what it does.

Good questions for the assistant: Ask it to summarise a function, to list what a file assumes about its inputs, or to explain an unfamiliar API. Then verify it against the code. If it says a cache is LRU because the file's comment says so, you've learned nothing.

Prompt, List the promises:

Read this code. Don't assume the comments are correct.
[code]
List: 1) what it promises to callers, 2) what it assumes about its inputs, 3) any state it changes. Then, for each promise, write one short test that would fail if the promise were broken. Don't fix anything.

Code, The file you're handed. Meant to be an LRU cache with expiry. Find three bugs before reading the notes. Nothing crashes, which is what makes them hard.

/** Meant to be an LRU cache with expiry. It has three bugs, and no test here fails yet. */
export class TtlCacheInherited<V> {
  private items = new Map<string, Item<V>>();
  private max: number;
  private ttlMs: number;
  private now: Clock;
  constructor(max: number, ttlMs: number, now: Clock) {
    this.max = max;
    this.ttlMs = ttlMs;
    this.now = now;
  }
  get(key: string): V | undefined {
    const item = this.items.get(key);
    if (!item || item.expires <= this.now()) return undefined;
    return item.value;
  }
  set(key: string, value: V): void {
    if (this.items.size >= this.max) {
      const oldest = this.items.keys().next().value as string;
      this.items.delete(oldest);
    }
    this.items.set(key, { value, expires: this.now() + this.ttlMs });
  }
  get size(): number {
    return this.items.size;
  }
}
  • item.expires <= this.now(): Returns undefined, but leaves the dead item in the map, where it keeps taking space.
  • return item.value: Doesn't mark the key as recently used, so this is really first-in, first-out.
  • this.items.size >= this.max: Also runs when overwriting an existing key, evicting an innocent key though the size wouldn't grow.

Code, The fixed version. All three fixes come from one fact: a Map remembers insertion order.

/** Map keeps insertion order, so delete-then-set moves a key to the "most recent" end. */
export class TtlCache<V> {
  private items = new Map<string, Item<V>>();
  private max: number;
  private ttlMs: number;
  private now: Clock;
  constructor(max: number, ttlMs: number, now: Clock) {
    this.max = max;
    this.ttlMs = ttlMs;
    this.now = now;
  }
  get(key: string): V | undefined {
    const item = this.items.get(key);
    if (!item) return undefined;
    this.items.delete(key);
    if (item.expires <= this.now()) return undefined;
    this.items.set(key, item);
    return item.value;
  }
  set(key: string, value: V): void {
    this.items.delete(key);
    if (this.items.size >= this.max) {
      const oldest = this.items.keys().next().value as string;
      this.items.delete(oldest);
    }
    this.items.set(key, { value, expires: this.now() + this.ttlMs });
  }
  get size(): number {
    return this.items.size;
  }
}
  • this.items.delete(key): Delete then set moves a key to the newest position. It also handles expired items and overwrites.

  • this.items.keys().next().value: The first key in the Map is the least recently used one.

  • Failure, Rewriting it: You were asked to understand and improve it. A rewrite throws away what you could have shown, and burns the time.

  • Failure, Trusting the comments: The file says LRU. It isn't. Comments are claims, not facts.

  • Failure, Fixing the symptom: Three bugs here share one fix once you know how a Map orders its keys.

What are the three bugs in the inherited cache?
Reading a key doesn't mark it as used, overwriting a key can evict a different one, and expired items stay and take up space.
Why are these hard to find?
None of them crash. The cache just returns misses at the wrong times, so you only find them by testing what it promises.
Why does delete-then-set make it LRU?
A Map iterates in insertion order. Reinserting moves a key to the end, so the first key is always the least recently used.

Sources: