Coding Interview Questions | Time-Based Key-Value Store

January 27th, 2024

Time-Based Key-Value Store Problem Introduction:

This summary will talk about my solution to the time-based key-value store problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps
and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.

void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.

String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the value associated with the largest timestamp_prev.
If there are no values, it returns "".

How do you solve the Time Based Key-Value Store Problem?

Solution:

class TimeMap {
  // key time map has a key of `key_time`
  private keyTimeMap: Map<string, string>;
  private keyTimeStackMap: Map<string, number[]>;

  constructor() {
    this.keyTimeMap = new Map();
    this.keyTimeStackMap = new Map();
  }

  set(key: string, value: string, timestamp: number): void {
    this.keyTimeMap.set(`${key}_${timestamp}`, value);
    const currentTimeStack = this.keyTimeStackMap.get(key);

    if (!currentTimeStack) {
      this.keyTimeStackMap.set(key, [timestamp]);
      return;
    }

    currentTimeStack.push(timestamp);
    this.keyTimeStackMap.set(key, currentTimeStack);
  }

  get(key: string, timestamp: number): string {
    const potentialKeyTimes = this.keyTimeStackMap.get(key);
    if (!potentialKeyTimes) {
      return "";
    }

    // If this is defined, it is guaranteed to have a length.
    // If first time on the stack is greater than the timestamp requested,
    // no keys are a match for this call.
    if (potentialKeyTimes[0] > timestamp) {
      return "";
    }

    // If most recent key time is less than or equal to requested time,
    // return that key
    const mostRecentKeyTime = potentialKeyTimes[potentialKeyTimes.length - 1];
    if (mostRecentKeyTime <= timestamp) {
      return this.keyTimeMap.get(`${key}_${mostRecentKeyTime}`)!;
    }

    // Iterate until finding a key with a timestamp
    // that is matching the criteria
    let currentKeyTimeIdx = potentialKeyTimes.length - 1;
    while (potentialKeyTimes[currentKeyTimeIdx] > timestamp) {
      currentKeyTimeIdx--;
    }

    return this.keyTimeMap.get(
      `${key}_${potentialKeyTimes[currentKeyTimeIdx]}`
    )!;
  }
}

Time-Based Key-Value Store Solution Summary:

Below is a breakdown of the key aspects of the provided solution for the time-based key-value store problem seen above:

1. Key-Value Storage: The keyTimeMap maintains a mapping of keys appended with timestamps to corresponding values. The key for the keyTimeMap data structure is a concatenation of the key and timestamp for the associated set operation.

2. Timestamp Stack: The keyTimeStackMap keeps track of timestamps associated with each key in the form of a stack. New timestamps are pushed onto the stack when a new value is set for a key.

3. Set Operation: The set method adds a new entry to keyTimeMap and updates the corresponding timestamp stack. If the key doesn’t have an existing stack, a new stack is created.

4. Get Operation: The get method retrieves the value for a key at a specified timestamp. It considers various scenarios:

   • If no timestamps are associated with the key, it returns an empty string.
   • If the first timestamp on the stack is greater than the requested timestamp, no matching key is found.
   • If the most recent timestamp is less than or equal to the requested timestamp, it returns the corresponding value.
   • Otherwise, it iterates through the stack to find the key with a timestamp matching the criteria.

Complexities

1. Time Complexity: Both set and get operations have an average time complexity of O(1), as they involve basic map operations and stack manipulations.

2. Space Complexity: The space complexity is O(n), where n is the total number of timestamps stored, as it involves maintaining two maps and associated stacks.