NeetCode 150: Time Based Key-Value Store

Table of contents

The Problem

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 "".

A Visual Example

Image taken from LeetCode.

The Approach

The overall structure is to use a Map to that stores the keys & its respective value, another Map where the key-value pairs are the timestamp & the value. We utilise the TreeMap to take advantage of its floorKey method which (as per the Java docs);

“Returns the greatest key less than or equal to the given key or null if there is no such key.”

to locate the respective timestamp of a key to get its value.

My Solution

class TimeMap {
    HashMap<String, TreeMap> driverMap;

    public TimeMap() {
        driverMap = new HashMap<String, TreeMap>();
    }
    
    // Checks if the key-value pair is present, updating the TreeMap if required.
    public void set(String key, String value, int timestamp) {
        if (driverMap.containsKey(key)) {
            TreeMap<Integer, String> timestampMap = driverMap.get(key);
            timestampMap.put(timestamp, value);
        } else {
            TreeMap<Integer, String> timestampMap =  new TreeMap<Integer, String>();
            timestampMap.put(timestamp, value);
            driverMap.put(key, timestampMap);
        }
    }
    
    // Utilises the TreeMap's floorKey() method to obtain the key that:
    // "Returns the greatest key less than or equal to the given key,
    // or null if there is no such key."
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> timestampMap = driverMap.get(key);
        
        // Returns "" if there no value map for this key.
        if (timestampMap == null) {
            return "";
        }

        Integer floorKey = timestampMap.floorKey(timestamp);

        // Returns "" if there no valid key. Else, returns the value.
        if (floorKey == null) {
            return "";
        } else {
            return timestampMap.get(floorKey);
        }

    }
}

The respective explanations is commented at the top of each method.