Time Based Key-Value Store - Practice Coding Problems

Time Based Key-Value Store - 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 "".

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["TimeMap", "set", "get", "get", "set", "get", "get"], parameters = [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

› Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

💡 Note: TimeMap created → set foo=bar at t=1 → get foo at t=1 returns "bar" → get foo at t=3 returns "bar" (t=1 ≤ 3) → set foo=bar2 at t=4 → get foo at t=4 returns "bar2" → get foo at t=5 returns "bar2" (t=4 ≤ 5)

Example 2 — No Valid Timestamp

$ Input: operations = ["TimeMap", "set", "get"], parameters = [[], ["love", "high", 10], ["love", 5]]

› Output: [null, null, ""]

💡 Note: TimeMap created → set love=high at t=10 → get love at t=5 returns "" because no timestamp ≤ 5 exists

Example 3 — Multiple Values Same Key

$ Input: operations = ["TimeMap", "set", "set", "get"], parameters = [[], ["key", "val1", 1], ["key", "val2", 3], ["key", 2]]

› Output: [null, null, null, "val1"]

💡 Note: TimeMap created → set key=val1 at t=1 → set key=val2 at t=3 → get key at t=2 returns "val1" (largest timestamp ≤ 2 is 1)

Constraints

1 ≤ key.length, value.length ≤ 100
key and value consist of lowercase English letters and digits.
1 ≤ timestamp ≤ 10⁷
All the timestamps of set are strictly increasing.
At most 2 × 10⁵ calls will be made to set and get.

Visualization

Tap to expand

Understanding the Visualization

Input

Operations: set("foo", "bar", 1), get("foo", 3)

Process

Store values with timestamps, find largest timestamp ≤ query

Output

Return corresponding value: "bar"

Key Takeaway

🎯 Key Insight: Combine HashMap for key lookup with sorted arrays and binary search for timestamp queries

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is combining hash tables for O(1) key access with binary search for O(log n) timestamp lookup. The optimal approach uses a HashMap where each key maps to a sorted list of (timestamp, value) pairs, enabling efficient queries through binary search.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search - Optimal Solution	O(log n)	O(n)	HashMap + sorted timestamps with binary search for efficient lookups
Brute Force - Linear Search	O(n)	O(n)	Store all values and search linearly for the largest valid timestamp

Binary Search - Optimal Solution — Algorithm Steps

Store (timestamp, value) pairs sorted by timestamp per key
For get(), use binary search to find rightmost valid timestamp
Return the corresponding value in O(log n) time

Visualization

Tap to expand

Step-by-Step Walkthrough

Sorted Storage

Store entries sorted by timestamp for each key

Binary Search

Use binary search to find rightmost timestamp ≤ target

Fast Result

Return corresponding value in O(log n) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ENTRIES 1000
#define MAX_KEYS 100
#define MAX_KEY_LEN 100
#define MAX_VALUE_LEN 100

typedef struct {
    int timestamp;
    char value[MAX_VALUE_LEN];
} Entry;

typedef struct {
    char key[MAX_KEY_LEN];
    Entry entries[MAX_ENTRIES];
    int count;
} KeyData;

typedef struct {
    KeyData keys[MAX_KEYS];
    int keyCount;
} TimeMap;

TimeMap* timeMapCreate() {
    TimeMap* obj = (TimeMap*)malloc(sizeof(TimeMap));
    obj->keyCount = 0;
    return obj;
}

void timeMapSet(TimeMap* obj, char* key, char* value, int timestamp) {
    for (int i = 0; i < obj->keyCount; i++) {
        if (strcmp(obj->keys[i].key, key) == 0) {
            Entry* entry = &obj->keys[i].entries[obj->keys[i].count];
            entry->timestamp = timestamp;
            strcpy(entry->value, value);
            obj->keys[i].count++;
            return;
        }
    }
    
    strcpy(obj->keys[obj->keyCount].key, key);
    Entry* entry = &obj->keys[obj->keyCount].entries[0];
    entry->timestamp = timestamp;
    strcpy(entry->value, value);
    obj->keys[obj->keyCount].count = 1;
    obj->keyCount++;
}

char* timeMapGet(TimeMap* obj, char* key, int timestamp) {
    static char result[MAX_VALUE_LEN];
    result[0] = '\0';
    
    for (int i = 0; i < obj->keyCount; i++) {
        if (strcmp(obj->keys[i].key, key) == 0) {
            int left = 0, right = obj->keys[i].count - 1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (obj->keys[i].entries[mid].timestamp <= timestamp) {
                    strcpy(result, obj->keys[i].entries[mid].value);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            break;
        }
    }
    
    return result;
}

int main() {
    printf("[null,null,null,\"bar\",null,\"bar\"]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search through sorted timestamps for each get() operation

⚡ Linearithmic

Space Complexity

O(n)

HashMap stores all key-value-timestamp entries

⚡ Linearithmic Space

185.0K Views

High Frequency

~25 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler