Build a key-value store

Should get return None or raise when the key is missing?

Pick one, say why, and then be consistent everywhere. This build raises a MissingKey that subclasses KeyError, for three reasons worth saying out loud: it matches what a dict already does, so nobody has to look the contract up; the exception carries the key, so a log line names what was missing where a None carries nothing; and an existing except KeyError around the call keeps working while a caller who cares can catch the narrower class. Returning None is defensible too, when callers mostly probe for presence and the store can never hold a null. What is not defensible is deciding it one way in get and the other way in delete.

How do I test a time to live without sleeping?

Take the clock as a constructor parameter typed as a callable that returns a float, then hand it time.monotonic in production and a fake in the tests. The fake is six lines: an object holding a number, callable, with the test assigning to the number. Every expiry test then runs in microseconds and none of them is flaky. Do this in the stage before anything needs it, because the first test you write about expiry will need it, and retro-fitting a clock means editing every call site. Monotonic rather than the wall clock, because a time sync can step the wall clock backwards and a deadline that moves backwards has no meaning.

Do I have to copy the whole store to support rollback?

No, and copying is the answer that costs you the question. A deep copy on begin is O(n) in the size of the store before the caller has written anything, and a nested begin pays it again. Keep a stack of undo logs instead, one per open transaction, where each write records what the key held before, once. A begin is then one empty dict however large the store is, a rollback costs one write per key the transaction touched, and the live data is always the current truth so reads need no special case at all.

What does commit mean when transactions are nested?

It means the inner transaction stops being separately undoable, not that its writes are permanent. The inner log folds into the log underneath it, key by key, keeping whatever the outer log already remembered for a key because the older memory is the one a rollback of the outer transaction wants. Only the outermost commit makes anything final, and even then final only means no longer undoable: nothing has been written to disk. Say that sentence in the room, because an interviewer asking about nesting is asking whether you understand it or only implemented it.

Why index value to keys rather than value to a count?

Because a counter cannot answer the next requirement and a set of keys can. Both make count O(1) in stage one, so a counter is not wrong there. Then a time to live arrives, and counting keys that are still alive means checking each key that holds the value, which you cannot do from an integer: you cannot subtract a key you cannot name. Set operations are also idempotent where counter arithmetic is not, so a discard that runs twice is harmless while a decrement that runs twice leaves a number nothing in the store can explain.