求问一道hash key 是整数范围的 hashmap的存储和查询问题
5091
最近面试某厂码农,遇到如下面试题目,想听听大家的解法建议。 多谢。
Given a data base like the following
1000~1234: A
2345~3267: B
3459~6000: A
7147~9899: C
...
Question 1:
Given the data base, you are required to return to the mapping value by inquery ineger.
For example,
if input is: 1156, the expected output is: A
if input is: 3460, the expected output is: A
if input is: 3262, the expected output is: B
Please write a function to implement the data base saving and query.
And what is the time / space complexity?
Question 2:
If the data base is very huge and has billions of entries, how should you modify your solution?
And what is the time / space complexity?
我的回答:
Answer 1:
首先数据库存储:
对记录按照 每个记录 记录成 一个长度为3的数组。3个元素依次对应,起点,终点,字符。 然后按照 数值的起点,终点排序。
Time Complexity: O(N)
Space Complexity: O(N)
其次: 查询。
按照binary serach 的方法查找input integer对应的三元组的位置,然后返回改位置所记录的字符。
Time Complexity: O(logN)
Space Complexity: O(1)
欢迎大家的建议。
Given a data base like the following
1000~1234: A
2345~3267: B
3459~6000: A
7147~9899: C
...
Question 1:
Given the data base, you are required to return to the mapping value by inquery ineger.
For example,
if input is: 1156, the expected output is: A
if input is: 3460, the expected output is: A
if input is: 3262, the expected output is: B
Please write a function to implement the data base saving and query.
And what is the time / space complexity?
Question 2:
If the data base is very huge and has billions of entries, how should you modify your solution?
And what is the time / space complexity?
我的回答:
Answer 1:
首先数据库存储:
对记录按照 每个记录 记录成 一个长度为3的数组。3个元素依次对应,起点,终点,字符。 然后按照 数值的起点,终点排序。
Time Complexity: O(N)
Space Complexity: O(N)
其次: 查询。
按照binary serach 的方法查找input integer对应的三元组的位置,然后返回改位置所记录的字符。
Time Complexity: O(logN)
Space Complexity: O(1)
欢迎大家的建议。
- 1
1条回复