Problem Description

Design and implement an in-memory key-value store that supports the following API operations:

• add(key, value): Adds a new key-value pair or updates an existing one.
• get(key): Retrieves the value associated with a given key.
• remove(key): Deletes a key-value pair from the store.
• getLast(): Returns the most recently added entry that still exists in the store.

Constraints and Requirements

• The getLast() operation must return the most recently added entry that has not yet been removed.
• Calling get(key) must not alter which element is considered "last."
• All operations (add, get, remove, getLast) should target an average time complexity of O(1).
• Justify your chosen data structures.
• Provide pseudocode for each method.
• Analyze the time and space complexity for all operations.

Edge Case Handling

The design must explicitly address the behavior for the following edge cases:

• Adding an existing key: Should it overwrite the existing value or reject the operation?
• Removing the current "last" element: What becomes the new "last" element? (Hint: the next most recent element that still exists).
• Calling getLast() on an empty store: Should it return a sentinel value (e.g., null, None) or throw an exception?

Concurrency Considerations

• Discuss how you would test the correctness of your implementation under concurrent add and remove operations.
• Outline any locking strategy you would employ if concurrency is a requirement for the store.