Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/time-based-key-value-store/description/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán yêu cầu ta thiết kế một cấu trúc dữ liệu dạng key-value dựa trên yếu tố thời gian timestamp. CTDL này có thể lưu nhiều giá trị với cùng 1 key tại nhiều thời điểm timestamp khác nhau, và cho phép lấy ra giá trị dựa vào từng key cùng với 1 thời điểm timestamp cụ thể.
Cho trước lớp TimeMap đại diện cho CTDL đó, và ta cần phải implement các phương thức sau:
- TimeMap(): Constructor để khởi tạo object
- void set(String key, String value, int timestamp) Lưu key với value tại thời điểm timestamp
- String get(String key, int timestamp): Trả về value tương ứng với key và các timestamp cũ - tạm gọi là timestamp_prev với điều kiện: timestamp_prev <= timestamp. Nếu có nhiều value cùng 1 key, nó sẽ trả về value được liên kết với timestamp_prev lớn nhất. Nếu không tìm thấy giá trị nào, nó sẽ trả về "".
Explain:
- Thời gian là không ngừng thay đổi, nên giá trị timestamp trong phương thức set sẽ không ngừng được tăng lên, dẫn đến các value và key nếu có cùng giá trị sẽ chắc chắn khác timestamp, và timestamp sẽ được sắp xếp tăng dần.
- Còn với phương thức get, timestamp có thể là bất kỳ giá trị nào, và yêu cầu cần tìm chính xác value được map với key sao cho timestamp của key-value đó phải <= timestamp của phương thức get.
Đối với những bài toán implementation giống như vậy, điều đầu tiên ta cần phải xác định CTDL chính dùng để lưu trữ dữ liệu là gì. Dễ thấy có key - value, và cùng key-value có thể có nhiều timestamp nên ta có thể dùng Map với key là key, còn value chính là 1 list các giá trị kết hợp giữa value và timestamp.
- Nếu chưa có key: khởi tạo record với key và list chứa phần tử <value,timestamp> từ input.
- Nếu đã có key rồi: lấy ra list các phần tử hiện tại và thêm <value,timestamp> từ input vào trong list đã có đó.
Nhưng đối với phương thức get, cho ta 2 giá trị là key và timestamp, từ key ta có thể get ra được 1 list bao gồm các <value,timestamp>, và từ argument timestamp đã cho của phương thức get, nhiệm vụ của chúng ta là tìm trong list này, cặp <value,timestamp> nào có timestamp nhỏ hơn hoặc bằng timestamp của phương thức get và trả về value.
List get ra được từ key sẽ có tính chất: với các index tăng dần từ 0 đến n thì timestamp cũng sẽ đảm bảo tăng dần. Hay nói cách khác, các giá trị timestamp sẽ đồng biến tăng dần theo index -> nghe quen quen đúng không? 😆 Và các bạn biết phải dùng giải thuật gì rồi đấy - Binary-Search.
2. Solution & Phân Tích
Cụ thể hơn, ta cần tìm cặp giá trị <value, timestamp> lớn nhất -> Ta sẽ áp dụng template tìm cực đại và biên trái left sẽ giữ vị trí của giá trị cực đại này.
Đầu tiên ta cần xác định khoảng vị trí chứa giá trị cần tìm, tạm gọi là [a, b] với mọi x thuộc khoảng này thì ta luôn có a <= x <= b. Dễ thấy [a, b] = [0, size của list các <value,timestamp> thuộc key - 1]
Với template tìm cực đại:
- left = a = 0
- right = b + 1 = size của list các <value,timestamp> thuộc key (+1 để tránh edge case right chính là vị trí cần tìm)
Điều kiện của vòng lặp while sẽ là (left + 1 < right) hay khi left và right liền kề thì ta sẽ dừng lại, left lúc này sẽ giữ vị trí mà ta cần tìm. Ta sẽ tính giá trị mid như bình thường và tiến hành so sánh timestamp tại vị trí mid với timestamp của phương thức get():
- Nếu nhỏ hơn hoặc bằng (thỏa điều kiện của đề bài): gán left = mid;
- Ngược lại nếu lớn hơn thì: gán right = mid; lý do gán right = mid chứ không phải mid - 1 là để tránh case mid - 1 chính là giá trị tìm kiếm, vì nếu gán right = mid - 1 thì không thể gán left = mid - 1 được nữa, giá trị mid sau khi chia đôi sẽ có xu hướng tiến sát về left hơn.
Cùng xét ví dụ với get("foo", 5), với list các giá trị của "foo" là [<"bar1"; 2>, <"bar2"; 4>, <"bar3"; 6>, <"bar"; 8>]
Time-Complexity: O(1) for set and O(logk) for get
Space-Complexity: O(n)
n: số lượng key-value-timestamp được set vào map ở tất cả các key.
k: số lượng value-timestamp của 1 key cụ thể.
3. Code
Lưu ý cần kiểm tra xem giá trị timestamp cần tìm kiếm của phương thức get có thật sự phù hợp hay không, nếu giá trị này nhỏ hơn tất cả giá trị timestamp trong mảng liên kết với key thì có thể trả về empty string ngay lập tức.
