Time-Based Key-Value Store

Try to solve the Time-Based Key-Value Store problem.

We'll cover the following

Statement#

Implement a data structure that can store multiple values of the same key at different timestamps and retrieve the key’s value at a certain timestamp.

You’ll need to implement the TimeStamp class. This class has the following functions:

  • Init(): This function initializes the values dictionary and timestamp dictionary.

  • Set Value(key, value, timestamp): This function stores the key and value at any given timestamp.

  • Get Value(key, timestamp): This function returns the value set for this key at the specified timestamp.

Note: When a query requests the value of a key at a timestamp that is more recent than the most recent entry for that key, our data structure should return the value corresponding to the most recent timestamp.

Constraints:

  • 1≤1 \leq key.length, value.length ≤20\leq 20
  • key and value consist of lowercase English letters and digits.
  • 1≤1 \leq timestamp ≤103\leq 10^3
  • At most 1×1031 \times 10^3 calls will be made to Set Value and Get Value.
  • All the timestamps, timestamp, of Set Value are strictly increasing.

Examples#

Created with Fabric.js 3.6.6 Sample example 1 key = "Courses", value = "DSA", timestamp = 3 key = "Courses", timestamp = 3 "DSA"

1 of 2

Created with Fabric.js 3.6.6 Sample example 2 key = "Courses", value = "OOP", timestamp = 5 key = "Courses", timestamp = 7 "OOP"

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check that you’re solving the correct problem:

Time-Based Key-Value Store

1

Given this series of commands, what is the output of the last command?

Init()

Set Value(“prediction”, “winning”, 3)

Get Value(“prediction”, 2)

A)

“winning”

B)

“losing”

C)

“”

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks required to implement Get Value().

Drag and drop the cards to rearrange them in the correct sequence.

In order to get a value, verify if the given key exists.

Verify if the timestamp we’re passing to get a value is greater than the previous timestamp.

Return an empty string if the required timestamp is less than the timestamps that were set previously.

Otherwise, return the value for the respective key and timestamp.

Try it yourself#

Implement your solution in time_stamp.py in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.

Python
time_stamp.py
binary_search.py
Input #1
Input #2
Time-Based Key-Value Store

Solution: Implement LRU Cache

Solution: Time-Based Key-Value Store