Design a key-value store with getLast

Design and implement an in-memory key–value store with this API: add(key, value), get(key), remove(key), and getLast(). The operation getLast() must return the most recently added entry that still exists in the store. Calling get(key) must not change which element is considered "last." Specify behavior for edge cases: adding an existing key (overwrite vs. reject), removing the current last element (the next most recent becomes last), and calling getLast() on an empty store (return sentinel or throw). Target O(1) average time for all operations; justify your data structures, provide pseudocode for each method, and analyze time and space complexity. Discuss how you would test correctness for concurrent adds/removes and outline any locking strategy if concurrency is required.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Design a Key-Value Store with getLast

Implement an in-memory key-value store that supports four operations, each O(1) average time:

• add(key, value) - insert key with value. If key already exists, overwrite its value AND treat it as the most recently added entry (refreshes recency).
• get(key) - return the value for key, or a null/None sentinel if absent. Calling get must NOT change which entry is considered "last".
• remove(key) - delete key from the store (no-op if absent). If you remove the current last entry, the next most recently added entry that still exists becomes the new last.
• getLast() - return the most recently added entry that still exists, as a [key, value] pair, or null/None if the store is empty.

Write a function processOperations(operations) that replays a list of operations and returns the list of outputs produced by the query operations (get and getLast), in order.

Each operation is a list whose first element is the op name:

• ["add", key, value]
• ["get", key] -> appends the value (or null) to the result list
• ["remove", key]
• ["getLast"] -> appends [key, value] (or null) to the result list

Keys are strings and values are integers.

Example:

Input: [["add","a",1],["add","b",2],["getLast"],["get","a"],["getLast"]]
Output: [["b",2], 1, ["b",2]]

(getLast is b after the two adds; get("a") returns 1 without changing the last; getLast is still b.)

Constraints

• Keys are strings; values are integers.
• add on an existing key overwrites the value and refreshes its recency (becomes last).
• get returns null/None for a missing key and never changes which entry is last.
• remove is a no-op on a missing key; removing the last entry promotes the next most recent live entry to last.
• getLast on an empty store returns null/None.
• All operations must be O(1) average time.

Hints

1. A hash map alone gives O(1) add/get/remove but cannot answer getLast efficiently after the most-recent entry is removed.
2. Pair the hash map with a doubly linked list ordered by insertion recency; the tail is always 'last'. Store node pointers in the map so any key can be detached in O(1).
3. On add of an existing key, detach its node first, then re-append at the tail so recency is refreshed. On remove, detach and let the previous node become the new tail automatically.
4. get must read the value without touching the linked list, so recency is preserved.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Design and implement an in-memory key–value store with this API: add(key, value), get(key), remove(key), and getLast(). The operation getLast() must return the most recently added entry that still exists in the store. Calling get(key) must not change which element is considered "last." Specify behavior for edge cases: adding an existing key (overwrite vs. reject), removing the current last element (the next most recent becomes last), and calling getLast() on an empty store (return sentinel or throw). Target O(1) average time for all operations; justify your data structures, provide pseudocode for each method, and analyze time and space complexity. Discuss how you would test correctness for ...

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.