NeetCodeのSolutionを書いていく

#

Time Based Key-Value Store

#

問題

#

時刻を基準にしたkey-valueのデータ構造を作りましょう。以下をサポートする必要があります。

• 指定した時刻の同じキーに対して複数の値を保持できる
• 特定の時刻の値をのキーの値を取得できる

仕様は以下

• TimeMap()はobjectを初期化する
• void set(String key, String value, int timestamp)でtimestampのvalueとkeyを保存します
• String get(String key, int timestamp)で与えられたtimestampより前のkeyがあれば返却します。ない場合は"“を返します。
• 全てのsetでtimestampsは必ず昇順で使われます

制約

#

• key, valueの長さは1以上100以下です
• key, valueは数字と小文字のアルファベットのみ含みます
• timestampは1以上1000以下です

計算時間：setはO(1)、getはO(logn) メモリ：O(m*n) nはkeyに紐づく値の数、mはkeyの数

例

#

Input: [“TimeMap”, “set”, [“alice”, “happy”, 1], “get”, [“alice”, 1], “get”, [“alice”, 2], “set”, [“alice”, “sad”, 3], “get”, [“alice”, 3]]

Output: [null, null, “happy”, “happy”, null, “sad”]

Explanation: TimeMap timeMap = new TimeMap(); timeMap.set(“alice”, “happy”, 1); // store the key “alice” and value “happy” along with timestamp = 1. timeMap.get(“alice”, 1); // return “happy” timeMap.get(“alice”, 2); // return “happy”, there is no value stored for timestamp 2, thus we return the value at timestamp 1. timeMap.set(“alice”, “sad”, 3); // store the key “alice” and value “sad” along with timestamp = 3. timeMap.get(“alice”, 3); // return “sad”

メモ

#

Binary Sortの問題なので、get時にBinary Sortを使うはず。 setは必ず昇順で指定される。メモリはm*n許容されているから、全データ保持してよい。 データ全体はkeyをkeyとしたdictで保持、更にtimestampをkey、valueをvalueとしたdictをbinary searchできるlistで保持すれば良い？

意外と簡単にできた。 from sortedcontainers import SortedDict というのがあってこれを使えば、idx = timestamps.bisect_right(timestamp) - 1のように簡単にbinary searchができるみたい。

class TimeMap:
    data: dict

    def __init__(self):
        self.data = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if self.data.get(key):
            self.data[key].append({timestamp: value})
        else:
            self.data[key] = [{timestamp: value}]

    def get(self, key: str, timestamp: int) -> str:
        # keyを探す
        values = self.data.get(key)
        if not values:
            return ""
        return self.find(values, timestamp)

    def find(self, values: list[dict[int, str]], timestamp: int):
        l = 0
        r = len(values) - 1
        retval = ""
        while l <= r:
            m = (r + l) // 2
            ts = list(values[m].keys())[0]
            value = values[m][ts]
            if ts <= timestamp:
                l = m + 1
                retval = value
            else:
                r = m - 1
        return retval