Key-Value Store with getLast

Requirements

• Build a key-value store with support for get, add, remove, and getLast.
• A lookup through get(key) must leave the result of getLast() unchanged.
• Combine a hashmap with linked-list-style ordering metadata so key lookup and retrieval of the last item remain efficient.
• Follow-up: explain how you would distribute the store across several servers, including approaches such as partitioning or consistent hashing.

API

Use the following language-neutral interface:

get(key) -> value | null
add(key, value) -> void
remove(key) -> void
getLast() -> key | null

Examples

For the examples below, interpret getLast() as returning the most recently inserted key that is still present. Confirm this interpretation with the interviewer, since the desired meaning may differ.

Example 1

add("red", 14)
add("blue", 27)
get("red")      -> 14
getLast()       -> "blue"

The lookup returns the value for "red" but does not alter insertion order, so "blue" remains the last key.

Example 2

add("oak", 5)
add("pine", 9)
remove("pine")
getLast()       -> "oak"

After "pine" is removed, "oak" is the newest key left in the store.

Example 3

add("cat", 3)
add("dog", 8)
get("dog")      -> 8
getLast()       -> "dog"

Reading "dog" does not promote it or otherwise change the last-key result.

Constraints

• Hashmap operations should be expected to run in constant time.
• Linked-list bookkeeping should allow insertion-order updates and removals without scanning every stored key.
• The store may be empty, in which case get and getLast return null for missing results.