Key-value store with prefix search

Build an in-memory key-value store whose values can also be looked up by key prefix. Keys are strings and values are integers.

Implement the KVStore class:

• KVStore() creates an empty store.
• set(key, value) adds a new pair. Raise an error if key is already stored.
• get(key) -> int returns the value for key, or -1 if key is not stored.
• update(key, value) replaces the value of a stored key. Raise an error if key is not stored.
• delete_key(key) removes key. Do nothing if it is not stored.
• search(prefix) -> List[int] returns the values of all stored keys that start with prefix, ordered by key (lexicographic). An empty prefix matches every key. Return an empty list when nothing matches.

Prefix queries are frequent, so search should not scan the whole store. Its cost should depend on the prefix length and the size of the result, not on the total number of keys.

Constraints

• Up to 10^5 operations in total.
• Keys are 0 to 50 characters long; the empty string is a valid key.
• Values fit in a 32-bit signed integer.

Example

store = KVStore()
store.set("pen", 4)
store.set("pencil", 2)
store.set("pet", 8)
store.set("map", 6)

store.search("pe")     -> [4, 2, 8]   # pen, pencil, pet
store.search("pen")    -> [4, 2]
store.get("pet")       -> 8
store.update("pen", 5)
store.delete_key("pencil")
store.search("pen")    -> [5]
store.get("pencil")    -> -1
store.search("z")      -> []
store.set("map", 1)    -> error: key exists

Interviewers often add parts one at a time, such as the sum of values under a prefix, returning only the first k matches, nested transactions with rollback, or making the store safe for concurrent use.

Reconstructed from the reported question; details may differ from what interviewers ask.