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.