Query a Versioned Array

Question

The question asks the candidate to implement a function that queries a versioned array, allowing retrieval of elements based on their version history.

Codemia · Accepted Answer

To solve the problem of querying a versioned array, I will maintain a list of versions where each version corresponds to a snapshot of the array. Each time an update is made, a new version of the array will be created, preserving the previous versions. This allows us to query any version of the array efficiently.

The algorithm involves creating a class `VersionedArray` that stores the array and a list of versions. The main operations will be `update(index, value)` to modify an element and `query(version)` to retrieve the element from a specific version. Here is a simple implementation:

```python
class VersionedArray:
    def __init__(self, arr):
        self.versions = [arr.copy()]

def update(self, index, value):
        current_version = self.versions[-1].copy()
        current_version[index] = value
        self.versions.append(current_version)

def query(self, version):
        if version < 0 or version >= len(self.versions):
            raise IndexError('Version out of range')
        return self.versions[version]
```

The time complexity for the `update` operation is O(n) because we need to copy the current version of the array. The `query` operation runs in O(1) time since it accesses a specific index in the list of versions. The space complexity is O(n * k), where n is the number of updates and k is the size of the array, as we store each version of the array.

It is important to handle edge cases, such as attempting to query a version that does not exist. In the provided code, I raise an `IndexError` if the requested version is out of bounds. Additionally, I would ensure that the `update` method does not allow negative indices.

In summary, this approach effectively manages a versioned array by creating snapshots upon updates. It allows for quick retrieval of any version while maintaining a clear structure. If further optimizations are needed, I could explore more advanced data structures like segment trees or versioned data structures.

Query a Versioned Array

Truefoundry

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Truefoundry Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string