Practice problem · OpenAI · Hard

KV Store Persistence

kvstore.py holds KVStore, a map from string keys to string values kept in memory; write, read, remove and len(store) already work. 3 stages in Python written by you, with an assistant that only answers. Pro.

Stage 1 of 3: Dump and load

kvstore.py holds KVStore, a map from string keys to string values kept in memory; write, read, remove and len(store) already work. Now the store has to survive being turned into bytes and back.

Implement KVStore.dump() and KVStore.load(data) in kvstore.py.

  • dump() returns the whole store as bytes and leaves the store unchanged.
  • load(data) takes bytes that dump() returned, on this store or another one, and replaces this store's contents with that store's: afterwards read and len(store) give exactly its entries, and keys this store held that the dump does not hold are gone. The store keeps working after a load.
  • A key or value can be any string UTF-8 can encode, up to 100,000 characters: empty, full of punctuation, whitespace or control characters such as "\0", "\n" and "\r", or non-ASCII text.
  • load raises ValueError and leaves the store exactly as it was when data is a dump with bytes missing from its end (any number of them, down to b"") or a dump followed by more bytes.
  • kvstore.py uses no serialization module, such as json, pickle, marshal, shelve or plistlib, and no eval, exec or ast.literal_eval. struct, int.to_bytes, bytearray, io and codecs are fine.

Example

store = KVStore()
store.write("path|a,b", "line\nbreak")
store.write("", "café")
data = store.dump()

copy = KVStore()
copy.write("old", "gone after the load")
copy.load(data)
copy.read("path|a,b")   # "line\nbreak"
copy.read("")           # "café"
copy.read("old")        # None
len(copy)               # 2
copy.load(data[:-1])    # ValueError, and copy still holds the same two entries

Notes

  • The layout of the bytes is yours to choose. The tests read a dump only through your own load.
  • Several stores can be alive at once, each with its own entries.
  • On the starter, all 10 tests in tests/test_part1.py fail.

Done when Submit goes green.

Constraints

  • Python 3.12 standard library only
  • Editable: kvstore.py
  • Read-only: all tests/test_*.py files
  • Keys and values are strings UTF-8 can encode, up to 100,000 characters each

What comes after stage 1

The next stages open once the tests for the one before them pass. Each raises the bar, the way an interviewer does in the room.

  1. Stage 2: Files under a size limit. The store goes to disk as files that never pass a size limit, each one readable on its own.
  2. Stage 3: Changes without a rewrite. A large store is too slow to rewrite at every shutdown, and a crash must not lose a change already made.

The files you get

  • Yours to edit: kvstore.py.
  • Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: no AI, an assistant that only answers

OpenAI runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.

Frequently asked, briefly answered

Is KV Store Persistence free?

It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.

Which company asks something like this?

OpenAI. It is modelled on OpenAI's coding round, which runs without AI. Based on candidates' reports of OpenAI interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.

What does the interviewer ask?

6 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.

Start the problem

Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.

Start this problem → Sign in

More like it: every practice problem, OpenAI's interviews, the AI coding interview guide.