Retrieve the Latest Timestamped Value for Each Key

Question

The question asks the candidate to implement a data structure that retrieves the latest value associated with a key based on a given timestamp.

Codemia · Accepted Answer

The task is to create a data structure that allows storing key-value pairs along with timestamps. The main operations required are:
1. `set(key, value, timestamp)`: Store the value with the associated timestamp for the key.
2. `get(key)`: Retrieve the value associated with the key that has the latest timestamp.

To efficiently manage the timestamped values, I will use a combination of a hash map and a sorted list. The hash map will store the key and a list of pairs (timestamp, value). This allows for quick access to the values by key, while the sorted list will help retrieve the latest timestamp efficiently.

Here is a Python implementation of the proposed solution:
```python
class TimestampedCache:
    def __init__(self):
        self.cache = {}

def set(self, key, value, timestamp):
        if key not in self.cache:
            self.cache[key] = []
        self.cache[key].append((timestamp, value))

def get(self, key):
        if key not in self.cache:
            return None
        # Retrieve the latest value based on timestamp
        latest_value = max(self.cache[key], key=lambda x: x[0])[1]
        return latest_value
```
This implementation uses a list to store timestamped values, and the `get` method retrieves the latest value by finding the maximum timestamp.

The time complexity for the `set` operation is O(1) since we are appending to a list. The `get` operation has a time complexity of O(n) due to the need to find the maximum timestamp in the list. The space complexity is O(n) for storing the timestamped values.

This solution is straightforward but may not be optimal for large datasets due to the O(n) complexity in the `get` method. To improve this, we could maintain a separate sorted list of timestamps or use a more complex data structure like a balanced tree. Edge cases to consider include handling duplicate timestamps and ensuring that the `get` method returns `None` for non-existent keys.

Retrieve the Latest Timestamped Value for Each Key

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Amazon 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