Note: In actual interview multi-threading discussion may also happen with this question.

Class

Ranged Key Value Storage

RangedKeyValueStorage()

• Creates an empty ranged key-value storage system.

Methods

Set

void set(String key, String value)

• Stores value for key.
• If key already exists, its old value is replaced.

Get

String get(String key)

• Returns the value currently stored for key.
• If key does not exist, return an empty string "".

Get Range

List<String> getRange(String startKey, String endKey)

• Returns all key-value pairs where startKey ≤ key ≤ endKey.
• Each returned string must be in the format "key,value".
• The result must be sorted by key in lexicographically increasing order.
• startKey and endKey do not need to exist in the storage.
• If no keys exist in the range, return an empty list.

Constraints

• 1 ≤ key.length() ≤ 100
• 1 ≤ value.length() ≤ 1,000
• 1 ≤ total number of method calls ≤ 100,000
• startKey ≤ endKey
• Keys and values contain only lowercase English letters, uppercase English letters, digits, hyphen, and underscore.
• No method parameter will be null.

Examples

Example 1

RangedKeyValueStorage store = new RangedKeyValueStorage()
store.set(key = "b", value = "banana")
store.set(key = "a", value = "apple")
store.get(key = "a")

• Output: "apple"
• The key "a" exists with value "apple".

Example 2

RangedKeyValueStorage store = new RangedKeyValueStorage()
store.set(key = "d", value = "dog")
store.set(key = "b", value = "ball")
store.set(key = "f", value = "fish")
store.getRange(startKey = "b", endKey = "e")

• Output: ["b,ball", "d,dog"]
• Keys "b" and "d" are inside the range, and the output is sorted by key.

Example 3

RangedKeyValueStorage store = new RangedKeyValueStorage()
store.set(key = "k1", value = "old")
store.set(key = "k1", value = "new")
store.get(key = "k1")

• Output: "new"
• The second set call replaces the previous value.

Example 4

RangedKeyValueStorage store = new RangedKeyValueStorage()
store.set(key = "m", value = "moon")
store.get(key = "x")
store.getRange(startKey = "a", endKey = "c")

• Output of get: ""
• Output of getRange: []
• The key "x" does not exist, and no stored key lies between "a" and "c".