981.time-based-key-value-store.md

981. Time Based Key-Value Store

• To store key-value pair, we can use hash table.
• To support storing multiple values for the same key, we can use list or set. To support searching the value by timestamp, we have to store the list in sorted order. Here we can use TreeMap to store the timestamp as key in sorted order, and the value as value.

Sorted List/Map

class TimeMap() {

    // (key -> (timestamp -> value))
    // Space Complexity: O(n)
    private val map = HashMap<String, TreeMap<Int, String>>()

    // Time Complexity: O(1)
    fun set(key: String, value: String, timestamp: Int) {
        if (!map.containsKey(key)) {
            map[key] = TreeMap<Int, String>()
        }
        map[key]!!.put(timestamp, value)
    }

    // Time Complexity: O(lg n)
    fun get(key: String, timestamp: Int): String {
        if (map.containsKey(key)) {
            // We search the timestamp or the greatest timestamp less than the given timestamp.
            val timestampPrev = map[key]!!.floorKey(timestamp)
            if (timestampPrev != null) {
                return map[key]!!.get(timestampPrev)!!
            }
        }
        return ""
    }
}

Binary Search

Or we can just use a list to store the timestamp and value pair since the all timestamps are guaranteed to be stictly increasing, that is already sorted. And then use binary search to search the timestamp.

class TimeMap() {

    // (key -> (timestamp -> value))
    private val map = HashMap<String, MutableList<Pair<Int, String>>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!map.containsKey(key)) {
            map[key] = mutableListOf<Pair<Int, String>>()
        }
        map[key]!!.add(timestamp to value)
    }

    fun get(key: String, timestamp: Int): String {
        if (map.containsKey(key)) {
            val timestampPrev = binarySearch(map[key]!!, timestamp)
            if (timestampPrev != -1) {
                return map[key]!!.get(timestampPrev)!!.second
            }
        }
        return ""
    }

    // Search the last number <= target
    private fun binarySearch(list: List<Pair<Int, String>>, target: Int): Int {
        var left = 0
        var right = list.size - 1
        while (left <= right) {
            val middle = left + (right - left) / 2
            val middleTimestamp = list[middle].first
            if (target < middleTimestamp) {
                right = middle - 1
            } else if (middleTimestamp < target) {
                left = middle + 1
            } else if (middleTimestamp == target) {
                left = middle + 1
            }
        }
        return if (right in 0 until list.size) right else -1
    }

    // Or equivalently, we can search the last number that satisfies the condition.
    private fun binarySearch(list: List<Pair<Int, String>>, target: Int): Int {
        var left = 0
        var right = list.size - 1
        
        while (left <= right) {
            val middle = left + (right - left) / 2
            val value = list[middle].first
            
            // Looking for the last element that satisfies the condition.
            if (meetCondition(target, value)) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return if (right in 0 until list.size) right else -1
    }

    // Condition: num <= target
    private fun meetCondition(target: Int, num: Int): Boolean {
        return num <= target
    }
}