辞書と二分探索で時刻つきの設定の履歴を設計する｜コーディング面接問題

問題

機械の設定の履歴を覚える仕組みを、クラス TimeStore として作ってください。設定の名前 key ごとに、ある時刻にどの値へ変えたかを残しておき、あとから「その時刻にはどの値だったか」を答えます。次の 2 つの操作を持ちます。

set(key, value, timestamp) は、時刻 timestamp に key の値を value にしたことを覚えます。前の値は消さずに残します
get(key, timestamp) は、key について、時刻が timestamp 以下の set のうち最も新しいものの値を返します。そういう set が無ければ、空の文字列 "" を返します

入力は、呼ぶ操作の名前の並び ops と、それぞれの引数の並び args で渡します。ops の最初はクラスの名前で、args の最初は空の並びです。出力は操作ごとの戻り値の並びで、作った所と set は null です。

set に渡す時刻は、どの key かに関わらず、呼ぶたびに必ず前より大きくなります
get に渡す時刻は自由で、前より小さくなることもあります
key と value は英小文字と数字の 1 文字以上 100 文字以下、時刻は 1 以上 10000000 以下です
操作の回数は 200000 回以下です

入力と出力の例

例 1

時刻 3 に eco、時刻 8 に fast にしています。時刻 6 に聞くと、まだ eco の頃です。

入力

ops = ["TimeStore", "set",
  "get", "get", "set", "get",
  "get"]
args = [[], ["mode", "eco", 3],
  ["mode", 2], ["mode", 5],
  ["mode", "fast", 8],
  ["mode", 8], ["mode", 6]]

出力

[null, null, "", "eco", null,
 "fast", "eco"]

例 2

設定の名前ごとに、別々の履歴を持ちます。

入力

ops = ["TimeStore", "set",
  "set", "set", "get", "get",
  "get", "get"]
args = [[], ["temp", "20", 1],
  ["fan", "low", 4],
  ["temp", "24", 7],
  ["temp", 6], ["fan", 3],
  ["fan", 100], ["temp", 7]]

出力

[null, null, null, null, "20",
 "", "low", "24"]

例 3

一度も set していない名前と、最初の set より前の時刻は、どちらも空の文字列です。

入力

ops = ["TimeStore", "get",
  "set", "get", "get"]
args = [[], ["door", 5],
  ["door", "open", 10],
  ["door", 9], ["door", 10]]

出力

[null, "", null, "", "open"]

面接での聞かれ方

テックリードの面接では、操作の形を渡したあと、データの持ち方と前提の崩れ方を聞かれます。

「時刻つきのキーと値の置き場を作ってください。ある時刻での値を引けるように」
「set の時刻が増えていく決まりが無かったらどうしますか」と、前提を外したときの持ち方を聞かれます
「履歴がどんどん増えますが、記憶はどうしますか」「古い履歴を消すならどう決めますか」と、運用まで続くこともあります
「書き込みが多い場合と読み出しが多い場合で、持ち方を変えますか」と、取り引きを話させられます

時刻が増える順に来るのか、同じ時刻の set があり得るのか、見つからないときに何を返すのかを、書き始める前に確かめます。この問題の速さは「時刻が増える順に来る」前提に支えられているので、そこを口に出して確かめること自体が評価されます。

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

素直には、set をすべて 1 本の並びに書き足し、get のたびに全部を見て、同じ名前で時刻が timestamp 以下のうち最も新しいものを探します。get が O(n) になり、20 万回の操作では遅くなります。

段 2

まず名前ごとに分けます。辞書で「名前から、その名前の履歴へ」を持てば、ほかの名前の履歴は見なくて済みます。履歴は、時刻の並びと値の並びを同じ位置で対応させて持ちます。set の時刻は必ず前より大きいので、末尾に書き足すだけで、時刻の並びは小さい順に並んだままです。並べ替えも、途中への差し込みも要りません。

段 3

get は、小さい順に並んだ時刻の並びから、「timestamp より大きい最初の位置」を二分探索で探します。その 1 つ前が、timestamp 以下で最も新しい set です。最初の位置が 0 なら、timestamp 以下の set は無いので空の文字列を返します。

段 4

前提が崩れた場合も考えておきます。時刻が増える順に来ないなら、書き足すたびに正しい位置へ差し込む必要があり、並びのままだと set が O(n) です。書き込みが多いなら、名前ごとに釣り合い木 (順序付きの木) を持ち、set も get も O(log n) にします。履歴が増え続けるのが困るなら、一定より古い時刻の項目を、時刻の並びの先頭からまとめて切り落とします。

解答

Python

from bisect import bisect_right

class TimeStore:
    def __init__(self):
        self.log = {}

    def set(self, key, val, ts):
        if key not in self.log:
            pair = ([], [])
            self.log[key] = pair
        t, v = self.log[key]
        t.append(ts)
        v.append(val)

    def get(self, key, ts):
        if key not in self.log:
            return ""
        t, v = self.log[key]
        i = bisect_right(t, ts)
        if i == 0:
            return ""
        return v[i - 1]

JavaScript

class TimeStore {
  constructor() {
    this.log = new Map();
  }

  set(key, val, ts) {
    const d = this.log;
    if (!d.has(key)) {
      d.set(key, [[], []]);
    }
    const [t, v] = d.get(key);
    t.push(ts);
    v.push(val);
  }

  get(key, ts) {
    const e = this.log.get(key);
    if (!e) return "";
    const [t, v] = e;
    let lo = 0;
    let hi = t.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (t[m] <= ts) {
        lo = m + 1;
      } else {
        hi = m;
      }
    }
    if (lo === 0) return "";
    return v[lo - 1];
  }
}

Go

import "sort"

type history struct {
	times []int
	vals  []string
}

type TimeStore struct {
	log map[string]*history
}

func newTimeStore() *TimeStore {
	return &TimeStore{
		map[string]*history{},
	}
}

func (s *TimeStore) Set(
	key, val string, ts int,
) {
	h := s.log[key]
	if h == nil {
		h = &history{}
		s.log[key] = h
	}
	h.times = append(h.times, ts)
	h.vals = append(h.vals, val)
}

func (s *TimeStore) Get(
	key string, ts int,
) string {
	h := s.log[key]
	if h == nil {
		return ""
	}
	i := sort.SearchInts(
		h.times, ts+1,
	)
	if i == 0 {
		return ""
	}
	return h.vals[i-1]
}

Python の bisect_right(t, ts) と JavaScript の二分探索は、どちらも「ts より大きい最初の位置」を返します。Go の sort.SearchInts は「渡した数以上の最初の位置」を返すので、ts+1 を渡して同じ位置を得ています。時刻は整数なので、ts+1 以上と ts より大きいは同じです。

計算量

set の時間は平均 O(1) です。辞書を引き、並びの末尾に書き足すだけです
get の時間は O(log m) です (m はその名前の set の回数)。辞書を引くのは平均 O(1) で、あとは二分探索です
使う記憶は O(n) です (n は set の回数の合計)。履歴を消さずに全部残すためです

よくある間違い

ちょうど同じ時刻を落とす。「timestamp 以上の最初の位置」を探してその 1 つ前を返すと、例 1 の get("mode", 8) で、時刻 8 の fast ではなく eco を返します。探すのは「timestamp より大きい最初の位置」です
見つからないときに番号 -1 を読む。位置が 0 のときに v[i - 1] を読むと、Python では v[-1]、つまり最も新しい値を返してしまい、エラーになりません。例 3 の get("door", 9) が open になる、気づきにくい間違いです
名前ごとに分けずに 1 本の並びで二分探索する。全部の set を 1 本にまとめると、時刻は並んでいても、見つけた項目が別の名前のことがあります。例 2 の get("fan", 3) で temp の値を返してしまいます
値を上書きして 1 つだけ持つ。名前から最新の値だけを持つ辞書にすると、過去の時刻を聞かれたときに答えられません。例 1 の get("mode", 6) は、すでに fast にした後の呼び出しでも eco を返す必要があります
前提を確かめずに並べ替えを入れる。 set のたびに並べ替えると、時刻が増える順に来る前提を使っておらず、set が O(m log m) になります。前提があるなら末尾に足すだけ、無いなら差し込みか木、と前提に合わせて選んだと説明できるようにします

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

class TimeStore: def __init__(self): # ここに持つ物を書きます pass def set(self, key, val, ts): # ここに書きます pass def get(self, key, ts): # ここに書きます pass # 「実行」を押すと、下の行が動きます obj = TimeStore() print(obj.set("mode", "eco", 3))

辞書と二分探索で時刻つきの設定の履歴を設計する

問題