mediumHashingPattern: Hashing
Hash Table Key Mapping Solution
Problem Statement
You are given two lists of strings, `keys` and `values`. The `keys` list contains unique identifiers, and the `values` list contains corresponding numerical mappings. Each key is a string of fixed length `K`. Implement a data structure that can store these key-value pairs and efficiently retrieve the numerical value associated with a given key string.
Examples
Example 1:
Input:keys = ["abcdefghijklmn", "opqrstuvwxyz12"], values = [10, 20]
Output:10
Explanation: When looking up the key "abcdefghijklmn", the data structure should return its corresponding value, which is 10. Both keys are 14 characters long.
Example 2:
Input:keys = ["a1b2c3d4e5f6g7", "h8i9j0k1l2m3n4"], values = [100, 200]
Output:200
Explanation: When looking up the key "h8i9j0k1l2m3n4", the data structure should return its corresponding value, which is 200. Both keys are 14 characters long.
Example 3:
Input:keys = ["key1234567890a", "keycdef1234567"], values = [5, 15]
Output:15
Explanation: When looking up the key "keycdef1234567", the data structure should return its corresponding value, which is 15. Both keys are 14 characters long.
Constraints
- 1 <= keys.length <= 10^5
- 1 <= values.length <= 10^5
- keys.length == values.length
- Each key is a string of length K, where 10 <= K <= 20.
- All keys in the 'keys' list are unique.
- Values are integers between 0 and 10^9.
Time: Insertion: O(N*K) on average, O(N*K) worst case. Lookup: O(K) on average, O(N*K) worst case. Where N is the number of key-value pairs and K is the length of each key. Space: O(N*K) to store the keys and values in the hash map.
Utilize a hash map (or dictionary) data structure. Iterate through the `keys` and `values` lists once to populate the hash map, where each key maps to its respective value. Subsequent lookups for a given key can then be performed in average O(1) time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def lookup_value(keys, values, lookup_key):
if not keys:
return None
hash_map = {}
for i in range(len(keys)):
hash_map[keys[i]] = values[i]
return hash_map.get(lookup_key)