Time-Based Key-Value Store: khi constraint tự trao cho bạn thuật toán

Bài toán cho bạn một key-value store mà mỗi key có thể chứa nhiều giá trị — mỗi giá trị gắn với một timestamp — và yêu cầu bạn lấy ra giá trị gần nhất tại hoặc trước một mốc thời gian cho trước. Cụm từ "gần nhất tại hoặc trước" đó chính là dấu hiệu: bài đang hỏi vị trí ngoài cùng bên phải mà một điều kiện còn thỏa, đúng bằng dạng câu hỏi của binary search. Constraint khiến điều đó thành hiện thực chỉ là một câu trong đề: "All the timestamps of set are strictly increasing." Một câu đó biến bài toán thiết kế thành bài toán binary search.

Đề bài

Thiết kế một cấu trúc dữ liệu key-value có thể lưu nhiều giá trị cho cùng một key, mỗi giá trị gắn với một timestamp, và trả về giá trị gần nhất tại hoặc trước timestamp được truy vấn. Đề gốc: LeetCode 981.

Ràng buộc:
- 1 <= key.length, value.length <= 100
- key và value chỉ gồm chữ cái thường và chữ số.
- 1 <= timestamp <= 10^7
- Tất cả timestamp của set đều tăng dần nghiêm ngặt.
- Tối đa 2 * 10^5 lần gọi set và get.

Constraints nói gì khi bạn đọc kỹ

Trước khi chọn approach, hãy đọc từng constraint và nghĩ xem nó loại bỏ điều gì.

1 <= timestamp <= 10^7 và tối đa 2 * 10^5 lần gọi set và get. Hai con số này nói lên rằng duyệt thẳng qua toàn bộ entries mỗi lần get có thể chạm tới 2 * 10^5 phần tử, và với 2 * 10^5 lần gọi get, giải pháp naive tệ nhất là O(n^2) — xấp xỉ 4 * 10^10 phép toán. Quá chậm.

key.length, value.length <= 100 nghĩa là so sánh chuỗi rẻ, nhưng timestamps mới là thứ cần tìm kiếm, không phải nội dung chuỗi.

"Timestamps of set are strictly increasing." Đây là constraint quyết định thuật toán. Bởi vì các lần gọi set đến theo thứ tự timestamp tăng dần, danh sách các cặp (value, timestamp) của bất kỳ key nào cũng luôn được sắp xếp. Bạn không cần tự sort. Bạn nhận được mảng đã sort miễn phí. Đó là tín hiệu xanh cho binary search.

Brute force: duyệt thẳng với early exit

Cách đọc đơn giản nhất: lưu mọi thứ trong hash map với key là chuỗi, value là danh sách các cặp (value, timestamp) cho key đó. Khi get được gọi, đi qua danh sách từ đầu và liên tục cập nhật biến kết quả mỗi khi gặp timestamp không vượt quá target. Dừng lại khi thấy timestamp lớn hơn target, vì danh sách đã sort.

class TimeMap:
    def __init__(self):
        self.store = {}
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((value, timestamp))
 
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        result = ""
        for value, ts in self.store[key]:
            if ts <= timestamp:
                result = value
            else:
                break  # danh sách đã sort, không cần xem thêm
        return result

public class TimeMap {
    private Dictionary<string, List<(string value, int timestamp)>> store;
 
    public TimeMap() {
        store = new Dictionary<string, List<(string, int)>>();
    }
 
    public void Set(string key, string value, int timestamp) {
        if (!store.ContainsKey(key)) {
            store[key] = new List<(string, int)>();
        }
        store[key].Add((value, timestamp));
    }
 
    public string Get(string key, int timestamp) {
        if (!store.ContainsKey(key)) return "";
        string result = "";
        foreach (var (value, ts) in store[key]) {
            if (ts <= timestamp) {
                result = value;
            } else {
                break;
            }
        }
        return result;
    }
}

break sớm không phải tối ưu thêm vào sau — nó là hệ quả trực tiếp của constraint "strictly increasing". Không có nó, bạn sẽ duyệt toàn bộ danh sách mỗi lần.

set tốn O(1) (append phân bổ). get tốn O(n) với n là số entries của key đó. Space là O(n) tổng cho toàn bộ cặp đã lưu.

Cách này gọn và đủ nhanh cho workload nhỏ. Vấn đề nằm ở O(n) mỗi lần get. Nếu một key tích lũy 10^5 entries, mỗi lần get key đó tốn 10^5 phép toán, và với 10^5 lần gọi get bạn lại rơi vào bậc hai.

Binary search: đúng công cụ cho danh sách đã sort

Cùng cấu trúc dữ liệu, chiến lược tìm kiếm hoàn toàn khác trong get. Vì danh sách đã sort theo timestamp, ta có thể binary search vị trí ngoài cùng bên phải mà ts <= timestamp.

class TimeMap:
    def __init__(self):
        self.store = {}
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((value, timestamp))
 
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        entries = self.store[key]
        left, right = 0, len(entries) - 1
        result = ""
        while left <= right:
            mid = (left + right) // 2
            if entries[mid][1] <= timestamp:
                result = entries[mid][0]  # ứng viên, nhưng có thể chưa tốt nhất
                left = mid + 1            # tìm bên phải xem có timestamp lớn hơn không
            else:
                right = mid - 1           # quá lớn, tìm bên trái
        return result

public class TimeMap {
    private Dictionary<string, List<(string value, int timestamp)>> store;
 
    public TimeMap() {
        store = new Dictionary<string, List<(string, int)>>();
    }
 
    public void Set(string key, string value, int timestamp) {
        if (!store.ContainsKey(key)) {
            store[key] = new List<(string, int)>();
        }
        store[key].Add((value, timestamp));
    }
 
    public string Get(string key, int timestamp) {
        if (!store.ContainsKey(key)) return "";
        var entries = store[key];
        int left = 0, right = entries.Count - 1;
        string result = "";
        while (left <= right) {
            int mid = (left + right) / 2;
            if (entries[mid].timestamp <= timestamp) {
                result = entries[mid].value;  // ứng viên
                left = mid + 1;               // tìm bên phải
            } else {
                right = mid - 1;              // tìm bên trái
            }
        }
        return result;
    }
}

set vẫn O(1). get giảm xuống O(log n). Space vẫn O(n).

Trace tay qua ví dụ

Chuỗi lệnh từ Example 1:

set("foo", "bar", 1)
get("foo", 1)   -> "bar"
get("foo", 3)   -> "bar"
set("foo", "bar2", 4)
get("foo", 4)   -> "bar2"
get("foo", 5)   -> "bar2"

Sau cả hai lần set, store["foo"] chứa:

index:     0             1
entries:  ("bar", 1)   ("bar2", 4)

Ta đi qua get("foo", 3):

Từng bước:

• left=0, right=1, mid=0. entries[0].ts = 1 <= 3. Ghi result = "bar". Đẩy left = 1.
• left=1, right=1, mid=1. entries[1].ts = 4 > 3. Đẩy right = 0.
• left=1 > right=0. Vòng lặp kết thúc. Trả về "bar".

Tiếp theo get("foo", 5):

• left=0, right=1, mid=0. ts=1 <= 5. Ghi result="bar". left=1.
• left=1, right=1, mid=1. ts=4 <= 5. Ghi result="bar2". left=2.
• left=2 > right=1. Vòng lặp kết thúc. Trả về "bar2".

Pattern nhất quán: mỗi khi entries[mid].ts <= timestamp, ta lưu ứng viên và đẩy con trỏ trái sang phải, đi tìm timestamp lớn hơn và vẫn đủ điều kiện.

Các edge case và điều thực sự xảy ra

Key chưa từng được set. Cả hai implementation kiểm tra sự tồn tại của key trước khi chạm vào danh sách và trả về "" ngay lập tức. Hash map lookup là O(1).

Timestamp nhỏ hơn tất cả timestamps đã lưu. Giả sử store["foo"] = [("bar", 5)] và bạn gọi get("foo", 2). Binary search chạy: mid=0, ts=5 > 2, right=-1. Vòng lặp không bao giờ ghi nhận ứng viên. result vẫn là "". Đúng.

Timestamp lớn hơn tất cả timestamps đã lưu. get("foo", 100) trên cùng danh sách: mid=0, ts=5 <= 100, result="bar", left=1. Vòng lặp kết thúc. Trả về "bar". Đúng — bạn trả về giá trị tại timestamp lớn nhất hiện có.

Timestamp khớp chính xác. get("foo", 5) trên [("bar", 5)]: mid=0, ts=5 <= 5, result="bar", left=1. Vòng lặp kết thúc. Trả về "bar". Đúng.

Chỉ có một entry cho key. Binary search xử lý danh sách độ dài một giống hệt. left=right=0, một lần duyệt, xong.

Nhiều key khác nhau. Mỗi key độc lập trong hash map. Không có tương tác giữa các key.

Tại sao early break của brute force không cứu được nó

break sớm của brute force là thực và có ý nghĩa — trong trường hợp tốt nhất, một get với timestamp rất gần đây kết thúc sau khi kiểm tra vài entries cuối. Nhưng trường hợp xấu nhất vẫn là tuyến tính: get("foo", 10^7) với 10^5 entries cho "foo" phải duyệt toàn bộ 10^5 entries trước khi dừng. Binary search không bao giờ chạm quá log2(10^5) ~ 17 entries bất kể target là gì.

Khoảng cách giữa 17 và 10^5 là lý do đáng để làm.

Cái tôi sẽ dùng, và tại sao

Tôi sẽ chọn binary search ngay lập tức. Implementation là vòng lặp left <= right chuẩn với cập nhật "vị trí ngoài cùng bên phải thỏa điều kiện" chuẩn — khoảng hai mươi dòng tổng. Không khó đọc hơn linear scan một cách đáng kể. Cải thiện complexity là hai bậc trên hot path (mỗi lần gọi get), và không có trade-off: set vẫn O(1), space vẫn O(n).

Lý do duy nhất tôi bắt đầu bằng brute force là trong phỏng vấn khi muốn thể hiện rằng tôi hiểu mình đang tối ưu cái gì trước khi tối ưu. Nêu brute force trong hai phút, gọi ra constraint khiến nó có thể cải thiện ("timestamps tăng dần, nên danh sách đã sort"), rồi chuyển ngay sang binary search.

Một điểm thiết kế đáng nhắc: bài toán nói timestamps đến theo thứ tự tăng dần. Nếu điều đó thay đổi — nếu bạn có thể set("foo", "x", 5) sau set("foo", "y", 10) — danh sách sẽ không còn được sort khi đến, và bạn cần sort nó (hoặc dùng container đã sort như balanced BST hoặc SortedList trong C#). Implementation binary search sẽ giữ nguyên; chỉ việc chèn sẽ tốn O(log n) thay vì O(1). Nhận ra assumption nào thuật toán đang dựa vào là cách tránh bất ngờ khi requirement thay đổi.

Bảng so sánh

Cả hai dùng cùng cấu trúc hash map. Sự khác biệt duy nhất là những gì xảy ra bên trong get.

Pattern cốt lõi và nơi nó xuất hiện

Tên của pattern này là "binary search trên sorted event log." Bạn có tập hợp các cặp (key, sorted-array-of-events), và các query hỏi sự kiện gần nhất tại hoặc trước một ngưỡng nào đó. Binary search tìm câu trả lời trong O(log n) mỗi query.

Đây không chỉ là construction của LeetCode. Các hệ thống thực làm đúng điều này. Version control system tra cứu trạng thái của một file tại một commit hash cho trước. Time-series database lấy sensor reading gần nhất trước một cutoff. Database MVCC layer tìm phiên bản row nào visible tại một transaction ID cho trước. Thuật toán giống hệt nhau trong tất cả.

Vị trí trong binary search series

Các bài trước trong series — Binary Search (704), Search in Rotated Sorted Array (33), Find Minimum in Rotated Sorted Array (153) — áp dụng binary search lên mảng được cho sẵn. Search a 2D Matrix (74) mở rộng ra cấu trúc hai chiều bằng cách xem matrix như mảng phẳng đã sort. Bài này thêm một lớp nữa: bạn tự xây dựng cấu trúc đã sort, bên trong một data structure được thiết kế, và lý do nó đã sort là một constraint về thứ tự input, không phải một lời gọi sort tường minh.

Ba bài lân cận có cùng hình dạng:

Snapshot Array (LeetCode 1146) là sibling gần nhất. Bạn duy trì một mảng với các snapshot, và mỗi get(index, snap_id) lấy giá trị tại index đó cho snapshot gần nhất tại hoặc trước snap_id. Cấu trúc giống hệt: per-index sorted list các cặp (value, snap_id), binary search trên snap ids. Điểm khác là bạn chỉ lưu entry mới khi giá trị thực sự thay đổi, đòi hỏi chiến lược index khác.

Design Hit Counter (LeetCode 362) yêu cầu đếm hits trong cửa sổ 5 phút rolling. Cấu trúc cơ bản là queue các timestamp, và thao tác là "bỏ mọi thứ ngoài cửa sổ" thay vì "tìm entry ngoài cùng bên phải trong ngưỡng." Biến thể binary search cho bài này sẽ tìm điểm cutoff, rồi trừ đi số lượng.

Online Stock Span (LeetCode 901) duy trì monotonic stack các cặp (price, ngày). Mỗi lần gọi next(price) hỏi có bao nhiêu ngày liên tiếp giá cổ phiếu không cao hơn giá hiện tại. Đây là dạng khác của "aggregate trên time window," giải bằng stack thay vì binary search, nhưng cấu trúc query tương tự.

My Calendar I (LeetCode 729) dùng binary search trên sorted list các khoảng để kiểm tra overlap trước khi chèn mỗi booking mới. Cơ chế "chèn và tìm kiếm trên sorted list đang tăng trưởng động" được chia sẻ với bài này.

Nếu bạn đã thoải mái với 981, bước tiếp theo tự nhiên là 1146 (Snapshot Array) — cùng data structure, lưu trữ bị ràng buộc hơn khiến bạn phải suy nghĩ cẩn thận hơn về những gì thực sự cần lưu.