1
\$\begingroup\$

I'm posting my C++ code for LeetCode's Snapshot Array. If you have time and would like to review, please do so. Thank you!

Problem

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

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

Constraints:

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

LeetCode Template

class SnapshotArray {
public:
    SnapshotArray(int length) {
        
    }
    
    void set(int index, int val) {
        
    }
    
    int snap() {
        
    }
    
    int get(int index, int snap_id) {
        
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

Accepted C++

class SnapshotArray {
public:
    SnapshotArray(const int array_length) {}
    int curr_shot_id = 0;
    std::unordered_map<int, std::vector<pair<int, int>>> id_map;

    // Returns current snapshot O(1)
    const int snap() {
        return curr_shot_id++;
    }

    // Setter with unordered_map
    const void set(const int key, const int shot_id) {
        if (id_map[key].empty() || id_map[key].back().first != curr_shot_id) {
            id_map[key].push_back({curr_shot_id, shot_id});

        } else {
            id_map[key].back().second = shot_id;
        }
    }

    // Getter with binary searching -> O(1) memory O(log N) time
    const int get(const int key, const int shot_id) {
        const auto iter = std::upper_bound(id_map[key].begin(), id_map[key].end(), std::pair<int, int>(shot_id, INT_MAX));
        return iter == std::begin(id_map[key]) ? 0 : std::prev(iter)->second;
    }
};

Reference

LeetCode is a platform only for interviewing and competitive programming. On LeetCode, there is a class usually named Solution (for this post is SnapshotArray) with one or more public functions which we are not allowed to rename.

\$\endgroup\$
2
\$\begingroup\$

The class template provided provides the necessary public interface, anything else should be private rather than public. Therefore the variable int curr_shot_id and the variable std::unordered_map<int, std::vector<pair<int, int>>> id_map; should be declared after private:.

The variable curr_shot_id should be initialized by the constructor SnapshotArray(int length).

    SnapshotArray(int length)
    : curr_shot_id{0}
    { }

It's not clear that you need a binary search of the map since a map is a direct access memory structure which means that the key will be hashed and that provides a direct reference to the object stored.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The protected classification is if there are classes that will inherit from the SnapshotArray class and need access to those fields. In this case there will be no inheritance so they can be private. \$\endgroup\$ – pacmaninbw Jun 19 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.