Practice problem · Databricks · Medium

KV Store Hit Counter

A key-value store that also reports its own load: how many get calls and how many put calls a second it has served lately. 2 stages in Python with an AI assistant. Pro.

Stage 1 of 2: Gets and puts per second

Background. A key-value store that also reports its own load: how many get calls and how many put calls a second it has served lately.

Implement MeteredStore(clock) with put(key, value), get(key) and rates() in store.py.

  • clock is a function with no arguments that returns the current time as a whole number of seconds, from 0 to 10^12. It never goes back; two readings in a row may be equal. The store learns the time only from clock: the tests pass a FakeClock from test_helpers.py and move it themselves.
  • The store's start is the clock's reading when the store is created.
  • put(key, value) stores value under key, replacing any earlier value, and returns None. get(key) returns the value stored under key, the very object put there and not a copy, or None when there is none. A key is any hashable value, and equal keys are the same key: 1 and 1.0, or frozenset({1, 2}) and frozenset({2, 1}).
  • Every put and every get is one call of its kind, made at the clock's reading during the call, whether or not the key was there. rates() is not a call.
  • rates() reads the clock (now) and returns a dict with exactly the keys "get" and "put". Each value is the number of calls of that kind made at times now - 299 to now, divided by min(300, now - start + 1): the seconds the store has been running, the current one included, capped at 300. A call made exactly 300 seconds ago no longer counts, and in its first second a store divides by 1.
  • The clock may jump forward by any amount between calls. Every call must return within a second, however far it jumped.

Example

clock = FakeClock(7_200_045)
store = MeteredStore(clock)   # starts at 7,200,045
store.put("a", 1)
store.get("a")                # 1
store.get("b")                # None, and still a get
clock.advance(9)              # 7,200,054: the store has run 10 seconds
store.rates()                 # {"get": 0.2, "put": 0.1}
clock.advance(300)
store.put("b", 2)
store.rates()                 # {"get": 0.0, "put": 0.0033333333333333335}: one put in the last 300 seconds

Notes

  • Each store has its own data, calls and start; several live in one process.
  • Rates are checked to a relative tolerance of 1e-9.
  • On the starter, all 12 tests in tests/test_part1.py fail.

Done when Submit goes green.

Constraints

  • Python 3.12 standard library only
  • Editable: store.py
  • Read-only: test_helpers.py and all tests/test_*.py files
  • The clock reads whole seconds from 0 to 10^12 and never goes back

What comes after stage 1

The next stage opens once the tests for the one before it pass. Each raises the bar, the way an interviewer does in the room.

  1. Stage 2: An hour, a day, a week. The same figures for the last hour, day and week, while the store's memory stays flat however busy it gets.

The files you get

  • Yours to edit: store.py.
  • Read-only: test_helpers.py.
  • Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: an agent in the editor

The assistant here works like the one in the interview IDE. It reads your files, runs code and proposes changes, and you accept or reject each one. It doesn't volunteer ideas, so what gets built is what you asked for. Along the way the interviewer asks about your decisions, and at the end the report says what you checked and what you accepted unread.

Frequently asked, briefly answered

Is KV Store Hit Counter 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?

Databricks. Based on candidates' reports of Databricks interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The assistant is in the editor, same as in the interview IDEs at Meta, Stripe and Amazon. What you choose at Begin is the format: an agent that proposes changes you accept or reject, or an answer-only assistant that can't write code.

What does the interviewer ask?

5 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, how Databricks runs its AI round, the AI coding interview guide.