Timestamped Parcel Attribute Store With Compare-and-Set, Prefix Listing and TTL

Implement an in-memory store of parcels. Each parcel is identified by a parcel ID and can hold many attributes with different names, each attribute being a name with a value. Every operation is called with a timestamp. The exercise is a timed, level-based coding assessment checked by automated tests, with four levels in 90 minutes, and each level extends the same class. The three reported levels are below. ### Constraints and Clarifications - An attribute holds exactly one value. Writing it again replaces the value; no history of earlier values is kept. - Every method takes a timestamp, including at the first two levels, where the timestamp affects no result. - The method names and argument orders below are one consistent reconstruction of the reported operations; return values for missing data are to be confirmed (see the questions). - Correctness is what is scored: a straightforward, brute-force implementation that passes the tests is acceptable. ### Clarifying Questions - What does `get` return for an unknown parcel or attribute: `None`, an empty string, or something else? What do `set` and the conditional update return? - Are values strings, and is a "match" exact, case-sensitive equality? - Can the conditional update create an attribute that does not exist yet? - Do timestamps increase from call to call? ### Part 1 — Set, get and conditional update Implement: - `set(timestamp, parcel_id, attribute, value)`: store `value` under `attribute` for the parcel, overwriting any existing value. - `get(timestamp, parcel_id, attribute)`: return the attribute's current value. - `update_if_match(timestamp, parcel_id, attribute, expected, new_value)`: set the attribute to `new_value` only if its current value equals `expected` exactly; otherwise change nothing. ```hint Shape of the store A parcel ID leads to a set of named attributes with one value each. Choose the nesting that makes "does this parcel have this attribute" a single lookup. ``` ```hint Match means exact Decide what the conditional update does when the attribute is missing, and make sure a failed match leaves the store untouched. ``` #### What This Part Should Cover - A nested store keyed by parcel ID and attribute name - Overwrite semantics, without unnecessary history or time ordering - Compare-then-write behavior that changes nothing on a mismatch or a missing attribute ### Part 2 — Listing attributes Add: - `list_attributes(timestamp, parcel_id)`: return every attribute of the parcel formatted as `name(value)`, ordered lexicographically by attribute name. - `list_attributes_with_prefix(timestamp, parcel_id, prefix)`: the same, restricted to attributes whose names start with `prefix`. ```hint One listing, two callers The two operations differ only in a filter on the name. Share the filtering, sorting and formatting so they can never disagree. ``` #### Clarifying Questions for this Part - Is the result a list of strings or a single joined string, and with what separator? - What is returned for an unknown parcel, or for a parcel with no matching attributes? - Is the order plain, case-sensitive string comparison of the names? #### What This Part Should Cover - Ordering by attribute name and the exact `name(value)` output format - A prefix filter on the attribute name that reuses the unfiltered listing's logic - Empty and unknown-parcel results ### Part 3 — Time-to-live Each attribute now has a time-to-live. `set` and `update_if_match` gain a `ttl` argument. A `ttl` of 0 means the attribute never expires; otherwise it expires `ttl` time units after it is written. `get` and both listing operations must ignore expired attributes. `update_if_match` must not update an expired attribute, but it can update an unexpired one, including setting its `ttl` to 0 so that it never expires. ```hint What a stored value must carry Expiry should be decidable from the stored entry and the query timestamp alone. Work out what the entry must record at write time for that to hold. ``` ```hint One liveness test The get, both listings and the conditional update all need the same "is this attribute alive at this timestamp" check. Put it in one place. ``` #### Clarifying Questions for this Part - Is an attribute written at time `w` with ttl `d` still visible at exactly `w + d`? - Does a successful write restart the lifetime from its own timestamp, using the ttl passed in that call? - What ttl applies when a call omits it, for example the level 1 calls that existing tests still make? #### What This Part Should Cover - What each stored value records so that expiry can be decided - One liveness rule (ttl 0, the boundary, restart on write) applied to `get`, both listings and the conditional update - Whether expired entries are hidden or removed ### What a Strong Answer Covers - A store layout that makes per-attribute lookups and per-parcel listings simple - Precise semantics for missing data, failed matches, ordering and prefix filtering - A single expiry rule applied consistently to every read and to the conditional update - Incremental code in which each level is a small extension, without overbuilding for the timestamp the first two levels ignore ### Follow-up Questions - How would you reclaim the memory held by expired attributes without slowing down reads? - How would you support reading an attribute's value as of a past timestamp? - If parcels have many attributes and prefix listings are frequent, what structure avoids sorting on every call? - How would you keep `update_if_match` correct if several threads used the store at once?