LeetCode //C - 981. Time Based Key-Value Store

981. Time Based Key-Value Store

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 “”.
   

Example 1:

Input:
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output:
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]
Explanation:
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2”

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• $1<=timestamp<=10^7$
• All the timestamps timestamp of set are strictly increasing.
• At most $2\ast 10^5$ calls will be made to set and get.

From: LeetCode
Link: 981. Time Based Key-Value Store

Solution:

Ideas:

Core Concepts:

• Hash Map for Key Management: The implementation uses a hash map to efficiently map keys to their associated data. This allows for fast lookup, insertion, and deletion operations based on keys.

• Chaining for Collision Resolution: The hash map employs chaining as a collision resolution technique. Each bucket in the hash table can store a linked list of nodes, where each node represents a unique key and its list of timestamp-value pairs. Chaining ensures that even if multiple keys hash to the same index, they can be stored and retrieved without conflict.

• Dynamically Resizable Arrays for Timestamp-Value Pairs: For each key, the values and their associated timestamps are stored in a dynamically resizable array. This structure supports efficient append operations at the end of the array and enables binary search for quick retrieval based on timestamps.

• Binary Search for Retrieval: To find the most recent value for a key as of a given timestamp, the code performs a binary search on the array of timestamp-value pairs. This allows for logarithmic time complexity in the retrieval operation, making it much faster than linear search, especially for a large number of timestamp-value pairs.

Key Operations:

• Set Operation (timeMapSet): This operation stores or updates the value associated with a specific key at a given timestamp. It involves hashing the key to find the appropriate bucket, then appending the timestamp-value pair to the dynamic array associated with the key. If the key does not already exist in the map, a new entry is created.

• Get Operation (timeMapGet): This operation retrieves the value associated with a key for the most recent timestamp not later than the specified timestamp. It uses binary search to efficiently find the closest timestamp less than or equal to the given timestamp in the dynamic array of timestamp-value pairs for the key.

• Free Operation (timeMapFree): This operation cleans up and frees all dynamically allocated memory used by the time-based key-value store, preventing memory leaks. It iterates through the hash map, freeing the linked lists (chaining), dynamic arrays, and their contents.

Design Choices:

• The choice of chaining for collision resolution and binary search for timestamp lookup are crucial for achieving efficient performance in terms of both time and space. Chaining allows the hash map to handle an arbitrary number of collisions gracefully, while binary search minimizes the time needed to find the correct value for a given timestamp.

• Dynamically resizable arrays for timestamp-value pairs ensure that the data structure can adapt to the number of entries for each key, providing flexibility and efficient use of memory.

Code:

#define HASH_MAP_SIZE 10007 // Use a prime number for better distribution

typedef struct {
    int timestamp;
    char* value;
} TimeValuePair;

typedef struct KeyValueNode {
    char* key;
    TimeValuePair* pairs;
    int size;
    int capacity;
    struct KeyValueNode* next;
} KeyValueNode;

typedef struct {
    KeyValueNode* buckets[HASH_MAP_SIZE];
} TimeMap;

unsigned int hash(char* key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    return hash % HASH_MAP_SIZE;
}

TimeMap* timeMapCreate() {
    return calloc(1, sizeof(TimeMap)); // Automatically initializes to zero
}

void ensureCapacity(TimeValuePair** array, int* capacity) {
    if (*capacity == 0) {
        *capacity = 4;
        *array = malloc(sizeof(TimeValuePair) * (*capacity));
    } else {
        *capacity *= 2;
        *array = realloc(*array, sizeof(TimeValuePair) * (*capacity));
    }
}

void timeMapSet(TimeMap* map, char* key, char* value, int timestamp) {
    unsigned int index = hash(key);
    KeyValueNode* node = map->buckets[index];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) break;
        node = node->next;
    }
    if (!node) {
        node = malloc(sizeof(KeyValueNode));
        node->key = strdup(key);
        node->pairs = NULL;
        node->size = 0;
        node->capacity = 0;
        node->next = map->buckets[index];
        map->buckets[index] = node;
    }
    if (node->size == node->capacity) {
        ensureCapacity(&node->pairs, &node->capacity);
    }
    node->pairs[node->size].timestamp = timestamp;
    node->pairs[node->size].value = strdup(value);
    node->size++;
}

char* timeMapGet(TimeMap* map, char* key, int timestamp) {
    unsigned int index = hash(key);
    KeyValueNode* node = map->buckets[index];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    if (node == NULL) return "";

    // Binary search for the highest timestamp <= given timestamp
    int left = 0, right = node->size - 1;
    char* result = "";
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (node->pairs[mid].timestamp <= timestamp) {
            result = node->pairs[mid].value;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

void timeMapFree(TimeMap* map) {
    for (int i = 0; i < HASH_MAP_SIZE; i++) {
        KeyValueNode* node = map->buckets[i];
        while (node) {
            KeyValueNode* temp = node;
            node = node->next;
            free(temp->key);
            for (int j = 0; j < temp->size; j++) {
                free(temp->pairs[j].value);
            }
            free(temp->pairs);
            free(temp);
        }
    }
    free(map);
}