数据砖 电面表演

经典三大面经中的一题 KV store， 所有操作要求常数时间复杂度很友善的韩国小哥面试，很多提示
我用了ringbuffer


看地里没有直接的python答案， 就在这里附上一份代码分享给大家， 可以拿来直接准备
希望加米 准备面试




# import heapq


# def say_hello():
#     print('Hello, World')
#     lt = [1,2]
#     heapq.heapify(lt)
#     print(lt)

# for i in range(5):
#     say_hello()
import time

class KeyValueStore(object):
  def __init__(self):
    self.key_value = {}
    self.last_time_put = 0
    self.last_time_get = 0
    self.last_idx_put = 0
    self.last_idx_get = 0
    self.ring_buffer_put = [0] * 300
    self.ring_buffer_get = [0] * 300

  # Writes the given key-value pair to the map
  def put(self, key, val):
    self.key_value[key] = val

    cur_time = time.time()
    dif = int(min(300, (cur_time - sel

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

    if dif > 300:
      return 0

    res = 0
    if dif == 0:
        res += self.ring_buffer_put[self.last_idx_get]
    for i in range(dif - 1):
      idx = (self.last_idx_get + i) % 300
      res += self.ring_buffer_get[idx]

    return res

obj = KeyValueStore()
obj.put(2,'a')
obj.put(3,'b')
obj.put(4,'b')

print(obj.get(2))
print(obj.measure_put_load())

lz过了吗

过了zszs

这个和queue比好在哪里？

黄色战神 发表于 2022-7-25 23:39
这个和queue比好在哪里？

同问。。请问你想出来了吗，感觉用queue记录(timestamp, count) pair也差不多啊

请问楼主ring buffer相比用queue记录(timestamp, count)好在哪里？

我看了这么多答案这题，还是不能理解， 为什么buffer 里面不能就存一个（timestamp, count) ,然后每次forloop 300 次不就行了？