求问一道hash key 是整数范围的 hashmap的存储和查询问题

avatar 137980
codedayday
509
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条回复