Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Time Based Key-Value Store

Explore implementing a time-based key value store that can set and retrieve values at various timestamps. Understand how to manage multiple values per key and return the most recent valid entry for any given timestamp, using custom data structures for efficient lookup and storage.

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 isn’t recorded, return the value corresponding to the most recent timestamp before the query’s timestamp. If there are no timestamps before the query’s timestamp, return an empty string.

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

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.

“”

1 / 3

Figure it out!

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

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > TimeStamp.java
import java.util.*;
class TimeStamp {
	
	public TimeStamp() {
		// Write your code here
	}
	// Set TimeStamp data variables
	public boolean setValue(String key, String value, int timestamp) {
		// Replace this placeholder return statement with your code
		return false;
	}
	// Get the value for the given key and timestamp
	public String getValue(String key, int timeStamp) {
		// Replace this placeholder return statement with your code
		return "";
	}
}
Time Based Key-Value Store