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.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Dropbox.

What role is this question designed for?

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

Implement KV Store and Token Bucket | Dropbox Coding Question

Implement KV Store and Token Bucket

Company: Dropbox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The coding portion covered two implementation tasks: 1. Implement a simple in-memory key-value store. Support basic operations such as: - `put(key, value)`: insert or update a value - `get(key)`: return the current value or indicate that the key does not exist - `delete(key)`: remove a key Be prepared to discuss API design, edge cases, and expected time complexity. 2. Implement a concurrent token-bucket rate limiter. The bucket has: - a fixed maximum capacity - a refill rate of `r` tokens per second - an operation such as `allow(n)` that consumes `n` tokens if enough tokens are available, otherwise rejects the request Your implementation should be thread-safe under concurrent callers, refill tokens based on elapsed time, and never allow the token count to exceed capacity. Explain your synchronization strategy and complexity.

Quick Answer: This question evaluates a candidate's skills in implementing core data structures and concurrent algorithms, specifically in-memory key-value store design, API considerations, time-based token-bucket rate limiting, thread-safety, and synchronization.

In-Memory Key-Value Store

Implement a simple in-memory key-value store and replay a sequence of operations against it. You are given a list of `operations`. Each operation is itself a list whose first element is the command name: - `["put", key, value]` — insert or update `key` with `value`. Result: `None`. - `["get", key]` — return the current value for `key`, or `None` if the key does not exist. Result: the value (or `None`). - `["delete", key]` — remove `key`. Result: `True` if the key existed and was removed, `False` if it was absent. Return a list containing the result of every operation, in order. This mirrors the design of a real KV store's `put` / `get` / `delete` API. All three operations should run in expected O(1) time using a hash map. Example: ``` operations = [["put","a",1], ["get","a"], ["put","a",2], ["get","a"], ["delete","a"], ["get","a"]] -> [None, 1, None, 2, True, None] ```

Constraints

0 <= number of operations <= 10^5
Each operation is one of put / get / delete
Keys and values can be any hashable / storable type
get on a missing key returns None; delete on a missing key returns False

Examples

Input: ([['put', 'a', 1], ['get', 'a'], ['put', 'a', 2], ['get', 'a'], ['delete', 'a'], ['get', 'a']],)

Expected Output: [None, 1, None, 2, True, None]

Explanation: put a=1, read 1, overwrite a=2, read 2, delete a returns True, then get a returns None (gone).

Input: ([['get', 'missing'], ['delete', 'missing']],)

Expected Output: [None, False]

Explanation: Reading and deleting an absent key returns None and False respectively.

Input: ([],)

Expected Output: []

Explanation: No operations -> empty result list.

Input: ([['put', 'x', 'hello'], ['put', 'y', 'world'], ['get', 'x'], ['get', 'y'], ['delete', 'x'], ['get', 'x'], ['delete', 'x']],)

Expected Output: [None, None, 'hello', 'world', True, None, False]

Explanation: Two keys stored; deleting x once returns True, a second delete returns False.

Input: ([['put', 'k', 0], ['put', 'k', 9], ['get', 'k']],)

Expected Output: [None, None, 9]

Explanation: Overwriting a key keeps only the latest value (9).

Hints

A dictionary (hash map) gives expected O(1) put, get, and delete.
Distinguish 'key exists with value None' edge cases by using membership (`in`) for delete rather than truthiness.
delete should report whether the key was actually present so callers can detect no-ops.

Token-Bucket Rate Limiter

Implement a token-bucket rate limiter and simulate it against a timed sequence of requests. The bucket has a fixed maximum `capacity` and refills at `refill_rate` tokens per second. It starts **full** (tokens = capacity). Tokens accumulate continuously over time but are **capped at `capacity`** — extra refill is lost. You are given `requests`, a list of `[timestamp, n]` pairs sorted by non-decreasing `timestamp` (in seconds). For each request, in order: 1. Refill the bucket based on the time elapsed since the previous request: `tokens = min(capacity, tokens + elapsed * refill_rate)`. 2. If at least `n` tokens are available, consume `n` and the request is **allowed** (`True`). Otherwise consume nothing and **reject** it (`False`). Return a list of booleans, one per request. (In a real concurrent implementation the same refill-then-consume step is guarded by a lock or a CAS loop so simultaneous callers can't double-spend; here we evaluate the deterministic logic via explicit timestamps.) Example: ``` capacity = 10, refill_rate = 2, requests = [[0,10], [0,1], [2,4], [2,1]] -> [True, False, True, False] ```

Constraints

1 <= capacity <= 10^9
0 < refill_rate (tokens per second)
requests sorted by non-decreasing timestamp (seconds, >= 0)
Bucket starts full; tokens never exceed capacity
0 <= n <= capacity per request

Examples

Input: (10, 1, [[0, 5], [0, 5], [0, 1]])

Expected Output: [True, True, False]

Explanation: Full bucket of 10: spend 5 then 5 (now 0); the third request for 1 token is rejected since no refill time elapsed.

Input: (10, 2, [[0, 10], [0, 1], [2, 4], [2, 1]])

Expected Output: [True, False, True, False]

Explanation: Drain all 10 at t=0; next request rejected. By t=2, 2s*2/s = 4 tokens refilled, so a request for 4 succeeds; the following request for 1 fails (bucket empty).

Input: (5, 1, [[0, 5], [100, 5]])

Expected Output: [True, True]

Explanation: Drain at t=0; by t=100 the bucket has long since refilled and capped at capacity 5, so 5 is available again.

Input: (3, 1, [[0, 3], [1, 1], [1, 1]])

Expected Output: [True, True, False]

Explanation: Drain 3 at t=0; 1s later exactly 1 token refilled and consumed; a second request at the same instant has nothing left.

Input: (10, 1, [])

Expected Output: []

Explanation: No requests -> empty result.

Input: (2, 5, [[0, 2], [0, 1], [10, 2]])

Expected Output: [True, False, True]

Explanation: Capacity caps refill: even after 10s * 5/s = 50 tokens would accrue, the bucket holds at most 2, so the final request for 2 succeeds.

Input: (4, 1, [[0, 0], [0, 4], [0, 0]])

Expected Output: [True, True, True]

Explanation: Requests for 0 tokens are always allowed; the middle request drains the full bucket of 4.

Hints

Track current token count and the timestamp of the last refill; lazily refill on each request instead of on a timer.
Refill amount is elapsed_seconds * refill_rate, but clamp the total with min(capacity, ...) so the bucket never overflows.
Only deduct tokens when the request is allowed; a rejected request must leave the bucket untouched. In a real multithreaded version, wrap the refill+check+deduct in a single critical section (mutex) or a CAS retry loop.

Quick Overview

This question evaluates a candidate's skills in implementing core data structures and concurrent algorithms, specifically in-memory key-value store design, API considerations, time-based token-bucket rate limiting, thread-safety, and synchronization.