Leetcode 981 Time Based Key-Value Store

Soru

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.

void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.

String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Örnek 1

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

Çözüm

• “981. Time Based Key-Value Store” sorusu, zaman damgasıyla birlikte değerlerin saklanabileceği ve sorgulanabileceği bir veri yapısı tasarlamayı gerektirir. Bu veri yapısında, bir anahtar (key) ve değer (value) çifti belirli bir zaman damgası (timestamp) ile saklanır. Ayrıca, belirli bir anahtar için belirli bir zaman damgasına kadar olan en son değeri alabilecek bir yöntem sağlanmalıdır.
• Sorunun Detayları:
• Veri yapısı, set(key, value, timestamp) ve get(key, timestamp) olmak üzere iki fonksiyonu desteklemelidir. set işlevi, verilen anahtar için verilen değeri belirtilen zaman damgası ile saklar. get işlevi, belirtilen anahtara ve zaman damgasına (veya daha öncesine) göre en son değeri döndürür. Eğer o anahtar için o zaman damgasından önce bir değer yoksa, boş bir string ("") döndürülür.
• Bu veri yapısını Python’da defaultdict ve bisect modüllerini kullanarak etkili bir şekilde uygulayabilirsiniz. Her anahtar için bir liste saklarsınız ve bu liste zaman damgası ve değer çiftlerini içerir. Zaman damgaları sıralı olarak tutulduğu için, bisect modülü ile belirli bir zaman damgasına göre arama yapabilirsiniz.
• Çalışma Mekanizması:
• Yapıcı (Constructor): defaultdict kullanarak her anahtar için bir liste oluşturur. Bu liste, (zaman damgası, değer) çiftlerini saklar.
• Set İşlemi: Belirli bir anahtar için, değeri ve zaman damgasını liste olarak saklar.
• Get İşlemi: bisect_right kullanarak, belirtilen zaman damgası veya ondan önceki en yakın zaman damgasını bulur. Eğer bir eşleşme bulunursa, o zaman damgasının değeri döndürülür. Bulunamazsa boş bir string döndürülür.

Code

from collections import defaultdict
import bisect

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)

    def set(self, key, value, timestamp):
        self.store[key].append((timestamp, value))

    def get(self, key, timestamp):
        A = self.store[key]
        i = bisect.bisect_right(A, (timestamp, chr(255)))
        return A[i-1][1] if i else ""

# Usage
obj = TimeMap()
obj.set("key1", "value1", 1)
print(obj.get("key1", 1))  # Outputs "value1"
print(obj.get("key1", 2))  # Outputs "value1" since it's the most recent before time 2

        

Complexity

• Time complexity (Zaman Karmaşıklığı) : set işlemi O(1) zamanda gerçekleşir. get işlemi, bisect_right kullanılarak logaritmik zaman karmaşıklığında, yani O(log n), burada n belirli bir anahtar için saklanan zaman damgası sayısıdır.
• Space complexity (Alan Karmaşıklığı) : O(N), burada N toplam (zaman damgası, değer) çiftlerinin sayısıdır.