Snapshot Array: อาร์เรย์รองรับ Snapshot ใน Python

โจทย์

ออกแบบ SnapshotArray รองรับ operations:

• SnapshotArray(length): สร้างอาร์เรย์ขนาด length เริ่มต้นทุกค่า = 0
• set(index, val): ตั้งค่า index = val (เวอร์ชันปัจจุบัน)
• snap(): ถ่าย snapshot คืน snap_id (เริ่มจาก 0, เพิ่มทีละ 1)
• get(index, snap_id): คืนค่าที่ index ใน snapshot snap_id

ตัวอย่าง: set(0,5), snap()→0, set(0,6), get(0,0)→5

วิธีแก้: Binary Search + Version History ต่อ Index

แทนที่จะเก็บ snapshot ทั้งอาร์เรย์ (หน่วยความจำมาก) ให้เก็บ history ต่อ index แยกกัน:

• แต่ละ index มี list ของ (snap_id, value) เรียงตาม snap_id
• set: อัปเดต/เพิ่ม entry ใน history ของ index นั้น
• get: Binary search ใน history หา snap_id ≤ target

การติดตั้ง (Python Implementation)

class SnapshotArray:
    def __init__(self, length: int):
        self.current_snap = 0
        # arr[i] = list of [snap_id, value] sorted by snap_id
        self.arr = [[[0, 0]] for _ in range(length)]
    
    def set(self, index: int, val: int) -> None:
        history = self.arr[index]
        # ถ้า snap_id ล่าสุดเท่ากับ current -> update value
        if history[-1][0] == self.current_snap:
            history[-1][1] = val
        else:
            history.append([self.current_snap, val])
    
    def snap(self) -> int:
        snap_id = self.current_snap
        self.current_snap += 1
        return snap_id
    
    def get(self, index: int, snap_id: int) -> int:
        history = self.arr[index]
        # Binary search: หา largest snap_id <= target
        left, right = 0, len(history) - 1
        while left < right:
            mid = (left + right + 1) // 2  # upper mid
            if history[mid][0] <= snap_id:
                left = mid
            else:
                right = mid - 1
        return history[left][1]

# ทดสอบ
ob = SnapshotArray(3)
ob.set(0, 5)
print(ob.snap())      # 0
ob.set(0, 6)
print(ob.get(0, 0))   # 5
print(ob.get(0, 1))   # 6 (current version)

Output

0
5
6

การทำงานภายใน (Internal State)

หลัง ob.set(0,5):     arr[0] = [[0,5]]
หลัง ob.snap():       current_snap = 1, return 0
หลัง ob.set(0,6):     arr[0] = [[0,5], [1,6]]
ob.get(0,0): binary search หา snap_id <= 0 → [0,5] → return 5
ob.get(0,1): binary search หา snap_id <= 1 → [1,6] → return 6

Complexity

• set: O(1) amortized
• snap: O(1)
• get: O(log H) โดย H = จำนวนครั้งที่ set index นั้น (≤ จำนวน snap)
• Space: O(length + total_sets) - เก็บเฉพาะการเปลี่ยนแปลง

สรุป

Snapshot Array ใช้เทคนิค Persistent Data Structure แบบ Path Copying (แต่ per-index) ใช้ Binary Search บน history ต่อ index ทำให้ memory efficient และ get() เร็ว

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ