Snapshot Array

Published: Jan 22, 2023

Medium Hash Table Binary Search Design

Problem Description

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
  • void set(index, val) sets the element at the given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Constraints:

  • 1 <= length <= 5 * 10**4
  • 0 <= index < length
  • 0 <= val <= 10**9
  • 0 <= snap_id < (the total number of times we call snap())
  • At most 5 * 10**4 calls will be made to set, snap, and get.

Examples

Example 1
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

How to Solve

The key design for this problem is how to save or not to save each snapshot array. One approach is to save snapshot array when the snap method is called. The snapshot may or may not use by later get method calls. However, it is easier to implement the get method. Another approach is to use the binary search. In this approach, the snap method just counts up the id. When the get method is called, do binary search using ids of the given index. The snap_id of get method call may or may not exist. Find the upper (right) insertion point among ids of the specific index. If it is 0, the ids array is empty. So, return 0. If it is not 0, return the value of one index left of the insertion point.

Solution

class SnapshotArray {
private:
    vector<map<int, int>> values;
    int _id = 0;
public:
    SnapshotArray(int length) {
        values.resize(length);
    }

    void set(int index, int val) {
        values[index][_id] = val;
    }

    int snap() {
        return _id++;
    }

    int get(int index, int snap_id) {
        auto it = values[index].upper_bound(snap_id);
        return it == values[index].begin() ? 0 : prev(it)->second;
    }
};



/**
 * @param {number} length
 */
var SnapshotArray = function(length) {
    this.values = Array.from({ length }).map((_) => new Object())
    this._id = 0
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function(index, val) {
    this.values[index][this._id] = val
}

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function() {
    this._id++
    return this._id - 1
}

/**
 * @param {number} index
 * @param {number} snap_id
 * @return {number}
 */
SnapshotArray.prototype.get = function(index, snap_id) {
    const search = (ary, value) => {
        let left = 0, right = ary.length - 1
        while (left <= right) {
            let mid = Math.floor((left + right) / 2)
            if (ary[mid] > value) {
                right = mid - 1
            } else if (ary[mid] < value) {
                left = mid + 1
            } else {
                return mid + 1
            }
        }
        return left
    }

    if (this.values[index][snap_id]) return this.values[index][snap_id]
    const ids = Object.keys(this.values[index]).toSorted((a, b) => a - b)
    const idx = search(ids, snap_id)
    return idx === 0 ? 0 : this.values[index][ids[idx - 1]]
}

class SnapshotArray:

    def __init__(self, length: int):
        self.values = [{} for _ in range(length)]
        self._id = 0

    def set(self, index: int, val: int) -> None:
        self.values[index][self._id] = val

    def snap(self) -> int:
        self._id += 1
        return self._id - 1

    def get(self, index: int, snap_id: int) -> int:
        if snap_id in self.values[index]:
            return self.values[index][snap_id]
        ids = sorted([k for k, _ in self.values[index].items()])
        idx = bisect.bisect_right(ids, snap_id)
        return 0 if idx == 0 else self.values[index][ids[idx - 1]]

class SnapshotArray

=begin
    :type length: Integer
=end
    def initialize(length)
        @values = Array.new(length).map {|e| Hash.new }
        @_id = 0
    end


=begin
    :type index: Integer
    :type val: Integer
    :rtype: Void
=end
    def set(index, val)
        @values[index][@_id] = val
        nil
    end


=begin
    :rtype: Integer
=end
    def snap()
        @_id += 1
        @_id - 1
    end


=begin
    :type index: Integer
    :type snap_id: Integer
    :rtype: Integer
=end
    def get(index, snap_id)
        return @values[index][snap_id] if @values[index][snap_id]
        ids = @values[index].keys.sort
        idx = search(ids, snap_id)
        idx == 0 ? 0 : @values[index][ids[idx - 1]]
    end

    private

    def search(ary, value)
        left, right = 0, ary.length - 1
        while left <= right
            mid = (left + right) / 2
            if ary[mid] > value
                right = mid - 1
            elsif ary[mid] < value
                left = mid + 1
            else
                return mid + 1
            end
        end
        left
    end
end

Complexities

  • Time: set: O(1), snap: O(1), get: O(n * log(n)) – n: number of snap ids in values’ items
  • Space: O(m * n) – m: given length, n: number of snap ids