Design a key-value store that supports insertion, lookup, deletion, and access to the first and last active entries in constant time.

Active entries are maintained in insertion order. Updating an existing key changes only its value and does not change its position.

Method Signature

void put(String key, String value)

String get(String key)

String delete(String key)

String getFirstEntry()

String getLastEntry()

Note: During interview rounds you may be asked to return any active key value pair (getAnyEntry() or getRandom()) which has the same solution as getFirstEntry() or getLastEntry().

Rules

• put inserts a new key-value pair if the key does not exist.
• put updates the value if the key already exists.
• get returns the value for the given key.
• delete removes the given key and returns its value.
• getFirstEntry returns the earliest inserted active entry in the format "key-value".
• getLastEntry returns the latest inserted active entry in the format "key-value".
• Keys and values contain only lowercase English letters.
• Return an empty string if get, delete, getFirstEntry, or getLastEntry cannot find a valid result.
• Active entries must keep their relative insertion order.
• If a deleted key is inserted again later, it is treated as a new key and becomes the latest inserted active entry.

Constraints

• 1 <= key.length, value.length <= 100
• At most 105 method calls will be made.
• All operations should run in average O(1) time.

Example 1

KeyValueStore store = new KeyValueStore()

store.put(key = "a", value = "apple")

store.put(key = "b", value = "banana")

store.get(key = "a") returns "apple"

store.getFirstEntry() returns "a-apple"

store.getLastEntry() returns "b-banana"

Example 2

KeyValueStore store = new KeyValueStore()

store.put(key = "x", value = "one")

store.put(key = "y", value = "two")

store.put(key = "x", value = "three")

store.get(key = "x") returns "three"

store.getFirstEntry() returns "x-three"

store.getLastEntry() returns "y-two"

store.delete(key = "x") returns "three"

store.get(key = "x") returns ""

store.getFirstEntry() returns "y-two"

store.getLastEntry() returns "y-two"

Example 3

KeyValueStore store = new KeyValueStore()

store.getFirstEntry() returns ""

store.getLastEntry() returns ""

store.put(key = "a", value = "apple")

store.put(key = "b", value = "banana")

store.put(key = "c", value = "cherry")

store.delete(key = "b") returns "banana"

store.getFirstEntry() returns "a-apple"

store.getLastEntry() returns "c-cherry"