AI Careers

The Progressive Coding Interview: Build an In-Memory Database in Four Levels

One problem, four levels, ninety minutes, and the requirements change every twenty. A full worked solution to the in-memory database problem family that candidates report from AI-lab assessments - and the three design choices in level one that decide whether you finish.

Why this format exists

A classic coding interview hands you a self-contained puzzle. A progressive one hands you a small system and then changes the requirements three times. Candidates report this format from AI-lab online assessments - most often an in-memory key-value database that grows scans, then expiry, then backup and restore - and it is spreading because it measures something puzzles do not: whether your first design can absorb change.

This post works the problem end to end. The exact wording of any company's assessment is confidential and changes; the version here is a representative practice problem built from the commonly reported levels. What transfers is the method, not the spec.

Three decisions in level one decide whether level four is a twenty-minute extension or a rewrite. Store records, not bare values, so that metadata has somewhere to live. Take the current time as an argument on every operation instead of reading a clock, so that expiry and history are deterministic and testable. And keep one small method per operation, so each new level is an addition rather than an edit across the file.

Levels one and two: records and scans

Level one is set, get and delete on a key and a field within it. Level two adds scans: return all fields of a key, sorted, and the same filtered by a prefix. Both are easy, which is the point - the time you save here is the time you need later, but only if the structure is right.

Notice that scan already filters through alive(), even though nothing can expire yet. That is the dividend of the level-one record design: when expiry arrives, every read path already respects it.

from dataclasses import dataclass

@dataclass
class Rec:
    value: str
    expires_at: int | None = None

    def alive(self, now: int) -> bool:
        return self.expires_at is None or now < self.expires_at

class DB:
    def __init__(self):
        self.d: dict[str, dict[str, Rec]] = {}
        self.backups: list[tuple[int, dict]] = []

    # ---- level 1
    def set(self, now, key, field, value):
        self.d.setdefault(key, {})[field] = Rec(value)

    def get(self, now, key, field):
        r = self.d.get(key, {}).get(field)
        return r.value if r and r.alive(now) else None

    def delete(self, now, key, field) -> bool:
        fields = self.d.get(key, {})
        r = fields.get(field)
        if not r or not r.alive(now):
            return False
        del fields[field]
        return True

    # ---- level 2
    def scan(self, now, key, prefix=""):
        fields = self.d.get(key, {})
        return [f"{f}({r.value})" for f, r in sorted(fields.items())
                if f.startswith(prefix) and r.alive(now)]

Level three: time to live

Level three adds set_with_ttl: a field that disappears ttl units after it was written. If time had been read from a global clock, this level would mean threading a clock through everything and writing tests that sleep. Because time is already an argument, it is three lines - compute the expiry and store it on the record.

A common extension at this level is a method returning the remaining time to live, and the edge cases are where points are lost. Is a field alive at exactly now == expires_at? The usual specification says no, which is why alive() uses a strict less-than. Does overwriting a field with a plain set clear its TTL? It should, and with records it does automatically, because set creates a fresh record with no expiry.

    # ---- level 3
    def set_with_ttl(self, now, key, field, value, ttl):
        self.d.setdefault(key, {})[field] = Rec(value, now + ttl)

    def ttl(self, now, key, field):
        r = self.d.get(key, {}).get(field)
        if not r or not r.alive(now):
            return None
        return None if r.expires_at is None else r.expires_at - now

Level four: backup and restore

Level four is where unstructured solutions collapse. Backup stores a snapshot of the live data; restore brings back the state as of a given backup - and, in the variant that catches people, the remaining TTL of each field must be preserved relative to the restore time, not the original write time.

The clean way is to snapshot remaining lifetimes rather than absolute expiry times. At backup, convert each live record's expiry into time left. At restore, convert back by adding the restore time. Expired records are dropped at backup, so they cannot come back to life. Restore picks the latest backup taken at or before the requested timestamp.

    # ---- level 4
    def backup(self, now) -> int:
        snap = {k: {f: (r.value, None if r.expires_at is None else r.expires_at - now)
                    for f, r in fields.items() if r.alive(now)}
                for k, fields in self.d.items()}
        snap = {k: v for k, v in snap.items() if v}
        self.backups.append((now, snap))
        return len(snap)

    def restore(self, now, at):
        candidates = [s for t, s in self.backups if t <= at]
        if not candidates:
            return
        snap = candidates[-1]
        self.d = {k: {f: Rec(v, None if left is None else now + left)
                      for f, (v, left) in fields.items()}
                  for k, fields in snap.items()}

def test_restore_keeps_remaining_ttl():
    db = DB()
    db.set_with_ttl(0, "u", "token", "abc", ttl=10)
    db.backup(4)                     # 6 units left at backup time
    db.restore(100, at=5)            # restore much later
    assert db.ttl(100, "u", "token") == 6
    assert db.get(105, "u", "token") == "abc"
    assert db.get(106, "u", "token") is None

How to spend the ninety minutes

Spend the first five minutes reading the level-one spec and sketching the record and method signatures. Do not try to guess the later levels exactly, but design so that metadata and time have a home. Run the provided tests after every method, not at the end of the level.

Write one test of your own per level for the edge the spec mentions in passing - boundary times, overwriting, deleting something already expired. Those are the cases hidden tests probe. When you move to a new level, add methods rather than editing old ones wherever possible; every edit to working code is a chance to break a level you already passed.

Finally, remember that some candidates report the assessment is reviewed beyond the score. Readable names, short functions and no special-casing of test inputs are part of the result, not decoration.

Keep reading

Related articles