Long-ID Store Without Hashing
Problem statement
Objects are identified by numeric IDs that can be up to 40 digits long, too long for any built-in integer type, so IDs are given as strings of digits. Build a store that starts empty and supports:
insert(id, value): storevalueunderid, replacing any value already there.get(id): return the value stored underid, or-1if there is none.delete(id): removeidand its value; do nothing if it is not stored.
Two IDs are the same only if their digit strings are equal. Call i is operations[i] on ids[i], and values[i] is the value for an insert (0 otherwise). Return the results of the get calls in order.
Goal (not judged): do not use a hash table, and make each call take time proportional to the length of its ID, no matter how many IDs are stored.
Function
runIdStore(operations: String[], ids: String[], values: int[]) → int[]Examples
Example 1
operations = ["insert","insert","get","delete","get","get"]ids = ["98765432109876543210","98765432109876543211","98765432109876543210","98765432109876543210","98765432109876543210","98765432109876543211"]values = [5,6,0,0,0,0]return = [5,-1,6]The two IDs differ only in the last digit, and both are too long for a 64-bit integer. After the first is deleted, getting it returns -1, while the second still returns 6.
Example 2
operations = ["insert","insert","get","get"]ids = ["42","42","42","4"]values = [1,7,0,0]return = [7,-1]Inserting an ID that is already stored replaces its value, so get 42 returns 7. ID 4 was never inserted: -1.
Example 3
operations = ["delete","get","insert","get"]ids = ["5","5","0","0"]values = [0,0,0,0]return = [-1,0]Deleting a missing ID does nothing. The ID 0 with value 0 is a real entry, so the last get returns 0.
Constraints
1 <= operations.length <= 1000, andids.length == values.length == operations.length- Each
operations[i]is"insert","get"or"delete", and at least one is"get". - Each
ids[i]is a decimal number of 1 to 40 digits without leading zeros (the single digit"0"is allowed). 0 <= values[i] <= 10^9for an insert, andvalues[i] == 0otherwise.