Design an in-memory database with TTL and backups

Q: Design an in-memory database with TTL and backups

This question evaluates skills in designing and implementing in-memory data structures, TTL-based expiration, lexicographic prefix scans, and backup/restore snapshot semantics within the Coding & Algorithms domain.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Coinbase.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

Question

Design an in-memory database with TTL and backups

PracHub · Accepted Answer

def solution(operations):
    db = {}
    out = []

for op in operations:
        if op[0] == 'put':
            _, key, value, _ = op
            db[key] = value
        else:
            _, key, _ = op
            out.append(db.get(key))

return out

def solution(operations):
    from bisect import bisect_left

db = {}
    keys = []
    out = []

for op in operations:
        cmd = op[0]

if cmd == 'put':
            _, key, value, _ = op
            if key not in db:
                i = bisect_left(keys, key)
                keys.insert(i, key)
            db[key] = value

elif cmd == 'get':
            _, key, _ = op
            out.append(db.get(key))

else:  # scan
            _, prefix, _ = op
            i = bisect_left(keys, prefix)
            cur = []
            while i < len(keys) and keys[i].startswith(prefix):
                k = keys[i]
                cur.append([k, db[k]])
                i += 1
            out.append(cur)

return out

def solution(operations):
    from bisect import bisect_left

db = {}
    keys = []
    out = []

def alive(entry, t):
        if entry is None:
            return False
        _, expire_at = entry
        return expire_at is None or t < expire_at

for op in operations:
        cmd = op[0]

if cmd == 'put':
            if len(op) == 5:
                _, key, value, t, ttl = op
                expire_at = t + ttl
            else:
                _, key, value, t = op
                expire_at = None

if key not in db:
                i = bisect_left(keys, key)
                keys.insert(i, key)
            db[key] = (value, expire_at)

elif cmd == 'get':
            _, key, t = op
            entry = db.get(key)
            out.append(entry[0] if alive(entry, t) else None)

else:  # scan
            _, prefix, t = op
            i = bisect_left(keys, prefix)
            cur = []
            while i < len(keys) and keys[i].startswith(prefix):
                k = keys[i]
                entry = db.get(k)
                if alive(entry, t):
                    cur.append([k, entry[0]])
                i += 1
            out.append(cur)

return out

def solution(operations):
    from bisect import bisect_left

state = {}
    keys = []
    backups = {}
    next_backup_id = 1
    out = []

def alive(entry, t):
        if entry is None:
            return False
        _, expire_at = entry
        return expire_at is None or t < expire_at

for op in operations:
        cmd = op[0]

if cmd == 'put':
            if len(op) == 5:
                _, key, value, t, ttl = op
                expire_at = t + ttl
            else:
                _, key, value, t = op
                expire_at = None

if key not in state:
                i = bisect_left(keys, key)
                keys.insert(i, key)
            state[key] = (value, expire_at)

elif cmd == 'get':
            _, key, t = op
            entry = state.get(key)
            out.append(entry[0] if alive(entry, t) else None)

elif cmd == 'scan':
            _, prefix, t = op
            i = bisect_left(keys, prefix)
            cur = []
            while i < len(keys) and keys[i].startswith(prefix):
                k = keys[i]
                entry = state.get(k)
                if alive(entry, t):
                    cur.append([k, entry[0]])
                i += 1
            out.append(cur)

elif cmd == 'backup':
            _, t = op
            snapshot = {}
            snap_keys = []
            for k in keys:
                entry = state.get(k)
                if alive(entry, t):
                    value, expire_at = entry
                    remaining = None if expire_at is None else expire_at - t
                    snapshot[k] = (value, remaining)
                    snap_keys.append(k)

backup_id = next_backup_id
            next_backup_id += 1
            b

Quick Overview

Examples

Solution

Hints

Part 2: Scan by prefix

Constraints

Examples

Solution

Hints

Part 3: Expiration with TTL

Constraints

Examples

Solution

Hints

Part 4: Backup and restore with TTL preservation

Constraints

Examples

Solution

Hints

Quick Overview