What is the time complexity of Time Based Key-Value Store?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Time Based Key-Value Store?

This problem uses Hash Table, String, Binary Search, Design. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Time Based Key-Value Store?

Insight 1: Using a hash map (or dictionary) is efficient for storing the key-timestamp-value data because it provides fast average-case lookup by key. Insight 2: For each key, storing the timestamps and values as a sorted list enables the use of binary search to efficiently find the appropriate value for a given timestamp, fulfilling the requirement to return the value with the largest timestamp less than or equal to the input timestamp.

Which companies ask LeetCode 981. Time Based Key-Value Store in interviews?

This problem is frequently asked at Airbnb, Anduril, Axon, CARS24, Coinbase and 16 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Time Based Key-Value Store - LeetCode 981 Solution

Q: How to solve Time Based Key-Value Store?

The solution uses a hash map (`store`) where keys are strings and values are lists of timestamp-value pairs. Each timestamp-value pair is stored as a tuple (Python), a custom `Pair` class (Java), or a pair (C++, C). The `set` operation simply appends a new timestamp-value pair to the list associated with the given key. The `get` operation uses binary search on the timestamp list for the given key to find the value associated with the largest timestamp less than or equal to the input timestamp.

Time Based Key-Value Store - Complete Solution Guide

Time Based Key-Value Store is LeetCode problem 981, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem requires designing a data structure, `TimeMap`, that stores key-value pairs with timestamps. The `set` operation allows associating a key with a value at a specific timestamp. The `get` operation retrieves the value associated with a given key and timestamp. If an exact match for the timestamp doesn't exist, the `get` operation should return the value associated with the largest timestamp that is less than or equal to the given timestamp. If no such value exists (e.g., the timestamp is earlier than any timestamps for the key), an empty string should be returned. Timestamps for a given key are guaranteed to be strictly increasing.

Solution Approach

The solution uses a hash map (`store`) where keys are strings and values are lists of timestamp-value pairs. Each timestamp-value pair is stored as a tuple (Python), a custom `Pair` class (Java), or a pair (C++, C). The `set` operation simply appends a new timestamp-value pair to the list associated with the given key. The `get` operation uses binary search on the timestamp list for the given key to find the value associated with the largest timestamp less than or equal to the input timestamp.

Step-by-Step Algorithm

Step 1: **Initialize the TimeMap:** Create a hash map (`store`) to store the key-value pairs. The key is a string, and the value is a list of (timestamp, value) tuples (or Pair objects).
Step 2: **Set Operation (set(key, value, timestamp)):** Append the (timestamp, value) tuple to the list associated with the given key in the hash map.
Step 3: **Get Operation (get(key, timestamp)):**
Step 3a: Check if the key exists in the hash map. If not, return an empty string.
Step 3b: Retrieve the list of (timestamp, value) tuples associated with the key.
Step 3c: Perform binary search on the list of timestamps to find the largest timestamp less than or equal to the given timestamp.
Step 3d: If a timestamp is found that is less than or equal to the input timestamp, store the corresponding value as the result.
Step 3e: If no such timestamp is found (meaning the input timestamp is smaller than all timestamps in the list), return an empty string.
Step 3f: Return the stored result value.

Key Insights

Insight 1: Using a hash map (or dictionary) is efficient for storing the key-timestamp-value data because it provides fast average-case lookup by key.
Insight 2: For each key, storing the timestamps and values as a sorted list enables the use of binary search to efficiently find the appropriate value for a given timestamp, fulfilling the requirement to return the value with the largest timestamp less than or equal to the input timestamp.
Insight 3: Handling the edge case where no timestamp exists that's less than or equal to the target timestamp is crucial. The algorithm must return an empty string in this situation.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(n)

Topics

This problem involves: Hash Table, String, Binary Search, Design.

Companies

Asked at: Airbnb, Anduril, Axon, CARS24, Coinbase, Compass, Confluent, CrowdStrike, Databricks, Flexport, Gusto, Instacart, Lyft, Netflix, Nextdoor, Notion, OpenAI, Snowflake, VMware, Verkada, eBay.

Time Based Key-Value Store | LeetCode 981

Medium

Hash Table String Binary Search Design

Time: O(log n)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {

    private Map<String, List<Pair>> store;

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!store.containsKey(key)) {
            store.put(key, new ArrayList<>());
        }
        store.get(key).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<Pair> values = store.get(key);
        if (values == null) {
            return "";
        }

        String res = "";
        int left = 0;
        int right = values.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (values.get(mid).timestamp <= timestamp) {
                res = values.get(mid).value;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }

    private static class Pair {
        int timestamp;
        String value;

        public Pair(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 981: Time Based Key-Value Store - Detailed explanation and solution approaches.

Topics

Hash Table String Binary Search Design

Companies

AirbnbAndurilAxonCARS24CoinbaseCompassConfluentCrowdStrike

Stats

Difficulty:Medium

Languages:4

Companies:21

Problem #:981

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: **Initialize the TimeMap:** Create a hash map (`store`) to store the key-value pairs. The key is a string, and the value is a list of (timestamp, value) tuples (or Pair objects).
2
Step 2: **Set Operation (set(key, value, timestamp)):** Append the (timestamp, value) tuple to the list associated with the given key in the hash map.
3
Step 3: **Get Operation (get(key, timestamp)):**
4
Step 3a: Check if the key exists in the hash map. If not, return an empty string.
5
Step 3b: Retrieve the list of (timestamp, value) tuples associated with the key.
6
Step 3c: Perform binary search on the list of timestamps to find the largest timestamp less than or equal to the given timestamp.
7
Step 3d: If a timestamp is found that is less than or equal to the input timestamp, store the corresponding value as the result.
8
Step 3e: If no such timestamp is found (meaning the input timestamp is smaller than all timestamps in the list), return an empty string.
9
Step 3f: Return the stored result value.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The `get` operation utilizes binary search on a list of timestamps. Binary search has a time complexity of O(log n). The `set` operation uses a hash map, which offers an average time complexity of O(1) for insertion. The space complexity is O(n) because the hash map stores all the (key, value, timestamp) triplets.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Instead of binary search in the `get` operation, a linear search could be used to iterate through the timestamps and find the largest timestamp that is less than or equal to the given timestamp.

Time: O(n), where n is the number of timestamps associated with a given key.Space: O(n), where n is the total number of (key, value, timestamp) triplets stored in the TimeMap.

Trade-offs: Linear search is simpler to implement, but it is less efficient than binary search for large numbers of timestamps. This approach would be acceptable if the number of timestamps associated with a single key is expected to be small.

Using a TreeMap (Java) or similar ordered data structure

In Java, you could use a TreeMap for each key, mapping timestamps directly to values. This automatically keeps the timestamps sorted and provides methods like `floorKey()` which directly returns the greatest key less than or equal to the given key. This simplifies the get operation.

Time: O(log n) for both set and get operations, due to the TreeMap's ordered nature.Space: O(n)

Trade-offs: Can simplify the code, especially in languages with built-in ordered map data structures. The tradeoffs are that TreeMap operations can have slightly higher overhead than HashMap operations and potential increased memory usage in some implementations.

✨

Key Insights

1Insight 1: Using a hash map (or dictionary) is efficient for storing the key-timestamp-value data because it provides fast average-case lookup by key.
2Insight 2: For each key, storing the timestamps and values as a sorted list enables the use of binary search to efficiently find the appropriate value for a given timestamp, fulfilling the requirement to return the value with the largest timestamp less than or equal to the input timestamp.
3Insight 3: Handling the edge case where no timestamp exists that's less than or equal to the target timestamp is crucial. The algorithm must return an empty string in this situation.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Key not present in the TimeMap: The `get` operation checks if the key exists in the hash map. If the key is not present, an empty string is returned, as specified in the problem description.
Edge case 2: Timestamp is smaller than all existing timestamps for a key: The binary search in the `get` operation will not find any timestamp that satisfies the condition (timestamp_prev <= timestamp). The loop will terminate with `res` initialized as "", and this empty string will be returned.
Edge case 3: Empty TimeMap: The `get` method should handle an empty Timemap correctly by returning an empty string, as no keys would be present.
Edge case 4: Multiple values exist at the same timestamp. Although the problem states timestamps are strictly increasing, in a variation of the problem, this would need handling. The provided solution implicitly handles it correctly, returning the last value set for that timestamp, due to the binary search continuing to the right.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the key is not present in the TimeMap. This will lead to a `NullPointerException` or similar error if the code tries to access the list of timestamps for a non-existent key.

✗Common mistake 2: Incorrect binary search implementation, leading to an infinite loop or an incorrect result. It's essential to carefully check the conditions for updating the `left` and `right` pointers in the binary search loop.

✗Common mistake 3: Not handling the edge case where the timestamp is smaller than all existing timestamps for the key. In this case, an empty string should be returned, but the code might return an incorrect value or throw an exception if this case is not handled explicitly.

✗Common mistake 4: Inefficient string copying in C. Using `strcpy` without bounds checking can lead to buffer overflows. `strncpy` with null termination is much safer.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Storing stock prices over time. The key is the stock symbol, the value is the price, and the timestamp is the time the price was recorded. This TimeMap could be used to retrieve the price of a stock at a specific time or the most recent price before a specific time.

🏦Real-world scenario 2: Caching data with expiration times. The key is the data identifier, the value is the cached data, and the timestamp is the expiration time. The TimeMap can be used to retrieve the cached data if it's still valid (expiration time is in the future) or to retrieve the most recently valid version of the data before a given time.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Time Based Key-Value Store"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?