Solution: Snapshot Array

Let's solve the Snapshot Array problem using the Custom Data Structures pattern.

We'll cover the following

Statement

In this challenge, you have to implement a Snapshot Array with the following properties:

  • Constructor (length): This is the constructor and it initializes the data structure to hold the specified number of indexes.

  • Set Value (idx, val): This property sets the value at a given index idx to value val.

  • Snapshot(): This method takes no parameters and returns the Snap ID. Snap ID is the number of times that the snapshot function was called, less 11, as we start the count at 00. The first time this function is called, it saves a snapshot and returns 00. The nthn^{th} time it is called, after saving the snapshot, it returns n−1n-1.

  • Get Value (idx, Snap ID) method returns the value at the index in the snapshot with the given Snap ID.

Suppose that we have three nodes whose values we wish to track in the snapshot array. Initially, the value of all the nodes will be 00. After calling the Set Value (1, 4) function, the value of node 1 will change to 44. If we take a snapshot at this point, the current values of all the nodes will be saved with Snap ID 00. Now, if we call Set Value (1, 7), the current value for node 1 will change to 77. Now, if we call the Get Value (1, 0) function, we will get the value of node 1 from snapshot 00, that is, 44.

Constraints:

  • 1≤1 \leq length ≤1000\leq 1000
  • 0≤0 \leq idx << length
  • 0≤0 \leq val ≤109\leq 10^9
  • 0≤0 \leq snapid << (the total number of times we call Snapshot)
  • At most 5×1035 \times 10^3 calls will be made to Set Value, Snapshot, and Get Value.

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to create an array-like data structure that supports snapping its values ​​at different times would be to create a list to store the array values ​​in each snapshot. We will increment the counter to keep track of the current snapshot ID. To take a snapshot, we will copy the current list and add it to the list of snapshots. To get the value on a given index and the snapshot ID, we access the given snapshot ID and the corresponding element in the snapshot list for the index.

For example, we want to create an array of length 5 and take three snapshots of its values at different times. We will create a list to store the values of the array at each snapshot, as well as a counter to keep track of the current snapshot ID:

arr = [0, 0, 0, 0, 0]

To set a value at a given index, we can update the corresponding element in the list:

arr[2] = 4

To take a snapshot, we will create a copy of the current list and add it to the list of snapshots. After taking three snapshots, the snapshots list will contain the following:

snapshots = [[0, 0, 0, 0, 0], [0, 0, 4, 0, 0], [0, 0, 4, 0, 0], [0, 0, 4, 0, 0]]

This naive approach will work for small arrays and a small number of snapshots. When the size of the array and the number of snapshots increases, this approach can become inefficient, since it requires copying the entire list for each snapshot. Let’s see if we can use the Custom Data Structures pattern to reduce the complexity of our solution.

Optimized approach using nested dictionaries

To solve this problem, we will start by creating a dictionary named Node Value. The node value will hold all the values, along with the nodes, at different times in further subdictionaries. The keys to the Node Value dictionary are the Snapshot IDs. For a given key, the values are also dictionaries. These inner dictionaries have node IDs as keys and the node’s value as values.

The Node Value dictionary keeps track of values that are set until the latest snapshot, rather than storing the entire array for each snapshot, as in the naive approach. This allows for more efficient memory usage and faster performance, especially for large arrays and a large number of snapshots.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

As an optimization, we will not initialize all the nodes. Instead, we will initialize a node when we set its value for the first time. We will use the Set Value (idx, val) function to set the node at the specified idx to val.

import java.util.*;
class SnapshotArray {
    public static HashMap<Integer, Integer> nodeValue;
    public static int nCount;
    // Constructor
    public SnapshotArray(int length) {
        nodeValue = new HashMap<Integer, Integer>();
        nCount = length;
    }
    // Function setValue sets the value at a given index idx to val.
    public void setValue(int idx, int val) {
        if (idx < nCount) {
            nodeValue.put(idx, val);
        }
    }
    public static void main(String[] args) {
        // Driver code
        List<Integer> numNodes = Arrays.asList(3, 5, 5, 3, 2);
        List<List<List<Integer>>> nodesValue = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 5), Arrays.asList(0, 1), Arrays.asList(2, 3), Arrays.asList(1, 10)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 21)),
                Arrays.asList(Arrays.asList(4, 12), Arrays.asList(2, 61)),
                Arrays.asList(Arrays.asList(0, 15), Arrays.asList(0, 5), Arrays.asList(2, 13), Arrays.asList(1, 100)),
                Arrays.asList(Arrays.asList(0, 32), Arrays.asList(0, 6), Arrays.asList(1, 2))
        );
        for (int i = 0; i < numNodes.size(); i++) {
            System.out.println(i + 1 + ".\tInitializing a data structure with " + numNodes.get(i) + " nodes");
            SnapshotArray snapshotArr = new SnapshotArray(numNodes.get(i));
            for (int j = 0; j < nodesValue.get(i).size(); j++) {
                for (int k = 0; k < nodesValue.get(i).get(j).size(); k++) {
                    System.out.println("\t\tSetting the value of node " + nodesValue.get(i).get(j).get(0) + " to " + nodesValue.get(i).get(j).get(1));
                    snapshotArr.setValue(nodesValue.get(i).get(j).get(0), nodesValue.get(i).get(j).get(1));
                    System.out.println("\t\tContents of snapshot array:" + snapshotArr.nodeValue);
                    break;
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Snapshot Array

The dictionary will contain a copy of the current state of the nodes. All the nodes with their values will be added to this dictionary against the same Snap ID. We can easily verify that there is no error in the copy by printing and comparing it with the contents of the dictionary.

import java.util.*;
class SnapshotArray {
    public static Map<Integer, Integer> nodeValue;
    public static int nCount;
    // Constructor
    public SnapshotArray(int length) {
        nodeValue = new HashMap<Integer, Integer>();
        nCount = length;
    }
    // Function setValue sets the value at a given index idx to val.
    public void setValue(int idx, int val) {
        if (idx < nCount) {
            nodeValue.put(idx, val);
        }
    }
    // This function takes no parameters and returns the snapid.
    // snapid is the number of times that the snapshot() function was called minus 1.
    public int snapshot() {
        // Create a deep copy of the map nodeState[snap_id -1]
        Map<Integer, Integer> newMap = new HashMap<Integer, Integer>(nodeValue);
        System.out.println("\t\tCopied state of dictionary: " + newMap);
        return -1;
    }
    public static void main(String[] args) {
        // Driver code
        List<Integer> numNodes = Arrays.asList(3, 5, 5, 3, 2);
        List<List<List<Integer>>> nodesValue = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 5), Arrays.asList(0, 1), Arrays.asList(2, 3), Arrays.asList(1, 10)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 21)),
                Arrays.asList(Arrays.asList(4, 12), Arrays.asList(2, 61)),
                Arrays.asList(Arrays.asList(0, 15), Arrays.asList(0, 5), Arrays.asList(2, 13), Arrays.asList(1, 100)),
                Arrays.asList(Arrays.asList(0, 32), Arrays.asList(0, 6), Arrays.asList(1, 2))
        );
        for (int i = 0; i < numNodes.size(); i++) {
            System.out.println(i + 1 + ".\tInitializing a data structure with " + numNodes.get(i) + " nodes");
            SnapshotArray snapshotArr = new SnapshotArray(numNodes.get(i));
            for (int j = 0; j < nodesValue.get(i).size(); j++) {
                for (int k = 0; k < nodesValue.get(i).get(j).size(); k++) {
                    System.out.println("\t\tSnapshot before setting value: " + snapshotArr.nodeValue);
                    snapshotArr.snapshot();
                    System.out.println("\t\tSetting the value of node " + nodesValue.get(i).get(j).get(0) +
                            " to " + nodesValue.get(i).get(j).get(1));
                    snapshotArr.setValue(nodesValue.get(i).get(j).get(0), nodesValue.get(i).get(j).get(1));
                    System.out.println("\t\tSnapshot after setting value: " + snapshotArr.nodeValue);
                    System.out.println();
                    break;
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Snapshot Array

Now, even though we’ve made a copy of the current state of the dictionary, we won’t save it anywhere. As a result, every time we set a value of a node, the previous state of the nodes is lost.

We can understand the limited functionality of the code above with the help of an example. Suppose we initialize a data structure with a length of 33. We first set the value of node 00 to 11 and then to 55. Even though we had made a copy of node 00 before setting it to 55, we lost that state of the node because we did not save the state anywhere.

So, where should we save the copy of the current state of the nodes?

Since we need to save the current state of the nodes at every snapshot, we will maintain a Snap ID to identify each snapshot. We will save every copy against a new Snap ID. So, after taking a snapshot, we will increment the Snap ID.

By using a Snap ID and a nested dictionary, we can save the current state of the nodes at every snapshot and retrieve the state of any node at any given Snap ID. The Node Value dictionary with the nested dictionary structure holds the state of all nodes at each snapshot. Each snapshot corresponds to a unique Snap ID, and the state of the nodes at each snapshot is saved as a copy in the nested dictionary with the corresponding Snap ID. This ensures that the previous states of the nodes are saved and can be retrieved when required.

import java.util.*;
class SnapshotArray {
    private int snapid;
    private Map<Integer, Map<Integer, Integer>> nodeValue;
    private int ncount;
    
    // Constructor
    public SnapshotArray(int length) {
        snapid = 0;
        nodeValue = new HashMap<Integer, Map<Integer, Integer>>();
        nodeValue.put(0, new HashMap<Integer, Integer>());
        ncount = length;
    }
    
    // Function setValue sets the value at a given index idx to val.
    public void setValue(int idx, int val) {
        if (idx < ncount) {
            nodeValue.get(snapid).put(idx, val);
        }
    }
    
    // This function takes no parameters and returns the snapid.
    // snapid is the number of times that the snapshot() function was called minus 1.
    public int snapshot() {
        nodeValue.put(snapid + 1, new HashMap<Integer, Integer>(nodeValue.get(snapid)));
        snapid++;
        return snapid - 1;
    }
    public static void main(String[] args) {
        // Driver code
        List<Integer> numNodes = Arrays.asList(3, 5, 5, 3, 2);
        List<List<List<Integer>>> nodesValue = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 5), Arrays.asList(0, 1), Arrays.asList(2, 3), Arrays.asList(1, 10)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 21)),
                Arrays.asList(Arrays.asList(4, 12), Arrays.asList(2, 61)),
                Arrays.asList(Arrays.asList(0, 15), Arrays.asList(0, 5), Arrays.asList(2, 13), Arrays.asList(1, 100)),
                Arrays.asList(Arrays.asList(0, 32), Arrays.asList(0, 6), Arrays.asList(1, 2)));
        List<List<List<Integer>>> valueToGet = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 0), Arrays.asList(0, 1), Arrays.asList(1, 0)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(0, 1), Arrays.asList(1, 1)),
                Arrays.asList(Arrays.asList(0, 0)));
        for (int i = 0; i < numNodes.size(); i++) {
            System.out.println(i + 1 + ".\tInitializing a data structure with " + numNodes.get(i) + " nodes");
            SnapshotArray snapshotArr = new SnapshotArray(numNodes.get(i));
            for (int j = 0; j < nodesValue.get(i).size(); j++) {
                for (int k = 0; k < nodesValue.get(i).get(j).size(); k++) {
                    System.out.println("\t\tSetting the value of node " + nodesValue.get(i).get(j).get(0) + " to " + nodesValue.get(i).get(j).get(1));
                    snapshotArr.setValue(nodesValue.get(i).get(j).get(0), nodesValue.get(i).get(j).get(1));
                    System.out.println("\t\tDictionary: " + snapshotArr.nodeValue);
                    System.out.println("\t\tSnap id:" + snapshotArr.snapshot() + "\n");
                    break;
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Snapshot Array

In the Get Value function, we first check if the input Snap ID is less than the total number of snapshots taken so far and if it is greater than or equal to zero. This is done to ensure that the input Snap ID is valid and corresponds to an actual snapshot.

If the input Snap ID is valid, we check if the input index idx is less than the total length of the array. If it is, then we check if the input index exists in the nested dictionary with the corresponding Snap ID. If it does, we return the value of the node at that index and Snap ID. If it does not, we return 0 as the node value.

If the input Snap ID is not valid, we return NULL.

import java.util.*;
class SnapshotArray {
    private int snapid;
    private Map<Integer, Map<Integer, Integer>> nodeValue;
    private int ncount;
    
    // Constructor
    public SnapshotArray(int length) {
        snapid = 0;
        nodeValue = new HashMap<Integer, Map<Integer, Integer>>();
        nodeValue.put(0, new HashMap<Integer, Integer>());
        ncount = length;
    }
    
    // Function setValue sets the value at a given index idx to val.
    public void setValue(int idx, int val) {
        if (idx < ncount) {
            nodeValue.get(snapid).put(idx, val);
        }
    }
    
    // This function takes no parameters and returns the snapid.
    // snapid is the number of times that the snapshot() function was called minus 1.
    public int snapshot() {
        nodeValue.put(snapid + 1, new HashMap<Integer, Integer>(nodeValue.get(snapid)));
        snapid++;
        return snapid - 1;
    }
    // Function getValue returns the value at the index idx with the given snapid.
    public int getValue(int idx, int snapshotId1) {
        if (snapshotId1 < snapid && snapshotId1 >= 0) {
            if (nodeValue.get(snapshotId1).containsKey(idx)) {
                return nodeValue.get(snapshotId1).get(idx);
            } else {
                return 0;
            }
        } else {
            return -1;
        }
    }
    public static void main(String[] args) {
        // Driver code
        List<Integer> numNodes = Arrays.asList(3, 5, 5, 3, 2);
        List<List<List<Integer>>> nodesValue = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 5), Arrays.asList(0, 1), Arrays.asList(2, 3), Arrays.asList(1, 10)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 21)),
                Arrays.asList(Arrays.asList(4, 12), Arrays.asList(2, 61)),
                Arrays.asList(Arrays.asList(0, 15), Arrays.asList(0, 5), Arrays.asList(2, 13), Arrays.asList(1, 100)),
                Arrays.asList(Arrays.asList(0, 32), Arrays.asList(0, 6), Arrays.asList(1, 2)));
        List<List<List<Integer>>> valueToGet = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 0), Arrays.asList(0, 1), Arrays.asList(1, 0)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(0, 1), Arrays.asList(1, 1)),
                Arrays.asList(Arrays.asList(0, 0)));
        for (int i = 0; i < numNodes.size(); i++) {
            System.out.println(i + 1 + ".\tInitializing a data structure with " + numNodes.get(i) + " nodes");
            SnapshotArray snapshotArr = new SnapshotArray(numNodes.get(i));
            for (int j = 0; j < nodesValue.get(i).size(); j++) {
                for (int k = 0; k < nodesValue.get(i).get(j).size(); k++) {
                    System.out.println("\t\tSetting the value of node " + nodesValue.get(i).get(j).get(0) +
                            " to " + nodesValue.get(i).get(j).get(1));
                    snapshotArr.setValue(nodesValue.get(i).get(j).get(0), nodesValue.get(i).get(j).get(1));
                    System.out.println("\t\tDictionary: " + snapshotArr.nodeValue);
                    System.out.println("\t\tSnap id: " + snapshotArr.snapshot() + "\n");
                    break;
                }
            }
            for (int x = 0; x < valueToGet.get(i).size(); x++) {
                for (int y = 0; y < valueToGet.get(i).get(x).size(); y++) {
                    System.out.println("\t\tNode value at index " + valueToGet.get(i).get(x).get(0) +
                            " with snapID: " + valueToGet.get(i).get(x).get(1) +
                            " is: " + snapshotArr.getValue(valueToGet.get(i).get(x).get(0), valueToGet.get(i).get(x).get(1)));
                    break;
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Snapshot Array

Just the code

Here’s the complete solution to this problem:

import java.util.*;
class SnapshotArray {
    private int snapid;
    private Map<Integer, Map<Integer, Integer>> nodeValue;
    private int ncount;
    
    // Constructor
    public SnapshotArray(int length) {
        snapid = 0;
        nodeValue = new HashMap<Integer, Map<Integer, Integer>>();
        nodeValue.put(0, new HashMap<Integer, Integer>());
        ncount = length;
    }
    
    // Function setValue sets the value at a given index idx to val.
    public void setValue(int idx, int val) {
        if (idx < ncount) {
            nodeValue.get(snapid).put(idx, val);
        }
    }
    
    // This function takes no parameters and returns the snapid.
    // snapid is the number of times that the snapshot() function was called minus 1.
    public int snapshot() {
        nodeValue.put(snapid + 1, new HashMap<Integer, Integer>(nodeValue.get(snapid)));
        snapid++;
        return snapid - 1;
    }
    // Function getValue returns the value at the index idx with the given snapid.
    public int getValue(int idx, int snapshotId1) {
        if (snapshotId1 < snapid && snapshotId1 >= 0) {
            if (nodeValue.get(snapshotId1).containsKey(idx)) {
                return nodeValue.get(snapshotId1).get(idx);
            } else {
                return 0;
            }
        } else {
            return -1;
        }
    }
    public static void main(String[] args) {
        // Driver code
        List<Integer> numNodes = Arrays.asList(3, 5, 5, 3, 2);
        List<List<List<Integer>>> nodesValue = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 5), Arrays.asList(0, 1), Arrays.asList(2, 3), Arrays.asList(1, 10)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 21)),
                Arrays.asList(Arrays.asList(4, 12), Arrays.asList(2, 61)),
                Arrays.asList(Arrays.asList(0, 15), Arrays.asList(0, 5), Arrays.asList(2, 13), Arrays.asList(1, 100)),
                Arrays.asList(Arrays.asList(0, 32), Arrays.asList(0, 6), Arrays.asList(1, 2)));
        List<List<List<Integer>>> valueToGet = Arrays.asList(
                Arrays.asList(Arrays.asList(0, 0), Arrays.asList(0, 1), Arrays.asList(1, 0)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(4, 1), Arrays.asList(2, 1), Arrays.asList(3, 1)),
                Arrays.asList(Arrays.asList(0, 1), Arrays.asList(1, 1)),
                Arrays.asList(Arrays.asList(0, 0)));
        for (int i = 0; i < numNodes.size(); i++) {
            System.out.println(i + 1 + ".\tInitializing a data structure with " + numNodes.get(i) + " nodes");
            SnapshotArray snapshotArr = new SnapshotArray(numNodes.get(i));
            for (int j = 0; j < nodesValue.get(i).size(); j++) {
                for (int k = 0; k < nodesValue.get(i).get(j).size(); k++) {
                    System.out.println("\t\tSetting the value of node " + nodesValue.get(i).get(j).get(0) + " to " + nodesValue.get(i).get(j).get(1));
                    snapshotArr.setValue(nodesValue.get(i).get(j).get(0), nodesValue.get(i).get(j).get(1));
                    System.out.println("\t\tSnap id:" + snapshotArr.snapshot() + "\n");
                    break;
                }
            }
            for (int x = 0; x < valueToGet.get(i).size(); x++) {
                for (int y = 0; y < valueToGet.get(i).get(x).size(); y++) {
                    System.out.println("\t\tNode value at index " + valueToGet.get(i).get(x).get(0) + " with snapID: " + valueToGet.get(i).get(x).get(1) + " is: " + snapshotArr.getValue(valueToGet.get(i).get(x).get(0), valueToGet.get(i).get(x).get(1)));
                    break;
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Snapshot Array

Solution summary

  1. Create a constructor that initializes the data structure to hold the specified number of indexes.

  2. Create a function, Set Value (idx, val), that sets the value at a given index to value.

  3. Create a function, Snapshot(), that makes a copy of all the key-value pairs in the snapshot array and stores it as the latest snapshot, returning the count of snapshots taken so far.

  4. Create a function, Get Value (idx, Snap ID), that returns the value at the index in the snap with the given Snap ID.

Time complexity

Let nn be the number of nodes and mm be the number of snapshots.

  • Constructor: The time complexity of the constructor is O(1)O(1).
  • Get Value (idx, Snap ID): The time complexity for this function is O(1)O(1).
  • Set Value(idx, val): The time complexity for this function is O(1)O(1).
  • Snapshot(): The time complexity for this function is O(n)O(n), as we are creating the deep copy of the dictionary.

Space complexity

To solve the problem given above, we will use O(n∗m)O(n * m) space, where nn will be the number of nodes and mm will be the number of snapshots taken.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.