登录
  • #Google
  • #求职(非面经)

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

codedayday
126
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条回复
热度排序

发表回复