Meta Online Assessment -- Design HashMap
Implement a HashMap class that supports versioning and atomic operations:
class HashMap {
fetch(timestamp, key, field) { }
insert(timestamp, key, field, value) { }
atomicSwap(timestamp, key, field, expectedValue, newValue) { }
atomicEvict(timestamp, key, field, expectedValue) { }
enumerate(timestamp, key) { }
enumerateFiltered(timestamp, key, prefix) { }
insertWithExpiry(timestamp, key, field, value, ttl) { }
atomicSwapWithExpiry(timestamp, key, field, expectedValue, newValue, ttl) { }
fetchAt(currentTimestamp, key, field, historicalTimestamp) { }
}
fetch: Returns the value of a field at the given timestamp. Returns empty string if not found.
insert: Stores or updates a field-value pair. Returns empty string.
atomicSwap: Updates field only if current value matches expectedValue. Returns "true" or "false".
atomicEvict: Removes field only if current value matches expectedValue. Returns "true" or "false".
enumerate: Returns all fields as "field1(value1), field2(value2), ..." sorted alphabetically.
enumerateFiltered: Returns only fields starting with prefix, same format as enumerate.
insertWithExpiry: Like insert but with TTL. Value expires after timestamp + ttl.
atomicSwapWithExpiry: Like atomicSwap but sets TTL on successful update.
fetchAt: Retrieves the value as it existed at historicalTimestamp, considering TTL expiration.
const hashmap = new HashMap();
const queries = [
["insert", "1", "user1", "name", "Alice"],
["insert", "2", "user1", "age", "25"],
["insert", "3", "user1", "addr", "NYC"],
["insert", "4", "user1", "admin", "false"],
["fetch", "5", "user1", "name"],
["fetch", "5", "user1", "email"],
["atomicSwap", "6", "user1", "age", "25", "26"],
["atomicSwap", "6", "user1", "age", "25", "27"],
["atomicEvict", "7", "user1", "addr", "LA"],
["atomicEvict", "7", "user1", "addr", "NYC"],
["enumerateFiltered", "8", "user1", "a"],
["enumerateFiltered", "8", "user1", "ad"],
["enumerateFiltered", "8", "user1", "n"],
["enumerateFiltered", "8", "user1", "z"],
["enumerate", "8", "user1"],
["insertWithExpiry", "10", "user1", "token", "xyz", "5"],
["atomicSwapWithExpiry", "12", "user1", "token", "xyz", "abc", "3"],
["fetchAt", "20", "user1", "token", "13"],
["fetchAt", "20", "user1", "token", "16"]
];
/* Explanations:
t=1: hashmap state: {"user1": {"name": "Alice"}}
t=2: hashmap state: {"user1": {"name": "Alice", "age": "25"}}
t=3: hashmap state: {"user1": {"name": "Alice", "age": "25", "addr": "NYC"}}
t=4: hashmap state: {"user1": {"name": "Alice", "age": "25", "addr": "NYC", "admin": "false"}}
returns "Alice" (name exists)
returns "" (email doesn't exist)
returns "true" (age was 25, updated to 26)
returns "false" (age is now 26, not 25)
returns "false" (addr is "NYC", not "LA")
returns "true" (addr was "NYC", now deleted)
returns "admin(false), age(26)" (fields starting with "a")
returns "admin(false)" (fields starting with "ad")
returns "name(Alice)" (fields starting with "n")
returns "" (no fields start with "z")
returns "admin(false), age(26), name(Alice)" (all remaining fields)
t=10: "token" = "xyz" expires at t=15
t=12: "token" updated to "abc", expires at t=15 (new expiry)
returns "abc" (token at t=13 is "abc", not expired)
returns "" (token expired at t=15)
*/
// Expected outputs:
// ["", "", "", "", "Alice", "", "true", "false", "false", "true", "admin(false), age(26)", "admin(false)", "name(Alice)", "", "admin(false), age(26), name(Alice)", "", "true", "abc", ""]
ProxyPass "/meta-online-assessment-questions" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap/" ProxyPassReverse "/meta-online-assessment-questions" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap/"
ProxyPass "/meta-online-assessment-questions/" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap/" ProxyPassReverse "/meta-online-assessment-questions/" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap/"
ProxyPass "/meta-online-assessment-questions#" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap#" ProxyPassReverse "/meta-online-assessment-questions#" "http://localhost:3000/iq/docs/meta/online-assessment/design-hashmap#"