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$

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

Solution:

Ideas:

• Core idea:

  • For each key, store a list of (timestamp, value) pairs.
  • Timestamps for the same key are strictly increasing, so the list is always sorted.

• Data structure:

  • A hash table maps each key → dynamic array of entries.
  • Each entry contains { timestamp, value }.

• set(key, value, timestamp):

  • Find (or create) the bucket for key in the hash table.
  • Append (timestamp, value) to the array (no sorting needed).

• get(key, timestamp):

  • Look up the array for key.
  • Use binary search to find the largest timestamp ≤ given timestamp.
  • Return the corresponding value, or “” if none exists.

• Why it’s efficient:

  • set → O(1) average (append).
  • get → O(log n) per key (binary search).
  • Works within the constraint of up to 2 * 10^5 operations.

• Memory management:

  • Strings are duplicated and stored safely.
  • All allocated memory is freed in timeMapFree.

Code:

typedef struct {
int ts;
char *val;
} Entry;

typedef struct {
char *key;
Entry *arr;
int size;
int cap;
int used; // 0 empty, 1 used
} Bucket;

typedef struct {
Bucket *table;
int cap;
int size;
} TimeMap;

static char *dupstr(const char *s) {
size_t n = strlen(s) + 1;
char *p = (char*)malloc(n);
if (p) memcpy(p, s, n);
return p;
}

// FNV-1a hash for strings
static unsigned long long hashStr(const char *s) {
unsigned long long h = 1469598103934665603ULL;
while (*s) {
h ^= (unsigned char)(*s++);
h *= 1099511628211ULL;
}
return h;
}

static void entriesEnsureCap(Bucket *b, int need) {
if (b->cap >= need) return;
int ncap = (b->cap == 0) ? 4 : b->cap;
while (ncap < need) ncap *= 2;
Entry *na = (Entry*)realloc(b->arr, (size_t)ncap * sizeof(Entry));
if (!na) return; // OOM: best effort
b->arr = na;
b->cap = ncap;
}

static void timeMapRehash(TimeMap *m);

static Bucket* findBucket(TimeMap *m, const char *key, int create) {
if (create && (m->size + 1) * 10 >= m->cap * 7) { // load factor > 0.7
timeMapRehash(m);
}

unsigned long long h = hashStr(key);
int mask = m->cap – 1;
int idx = (int)(h & (unsigned long long)mask);

for (;;) {
Bucket *b = &m->table[idx];
if (!b->used) {
if (!create) return NULL;
b->used = 1;
b->key = dupstr(key);
b->arr = NULL;
b->size = 0;
b->cap = 0;
m->size++;
return b;
}
if (strcmp(b->key, key) == 0) return b;
idx = (idx + 1) & mask;
}
}

static void timeMapRehash(TimeMap *m) {
int oldCap = m->cap;
Bucket *old = m->table;

int newCap = oldCap * 2;
Bucket *nt = (Bucket*)calloc((size_t)newCap, sizeof(Bucket));
if (!nt) return; // OOM: keep old table

m->table = nt;
m->cap = newCap;
m->size = 0;

for (int i = 0; i < oldCap; i++) {
if (!old[i].used) continue;
Bucket *dst = findBucket(m, old[i].key, 1);
// Move ownership (no deep copy)
free(dst->key);
dst->key = old[i].key;
dst->arr = old[i].arr;
dst->size = old[i].size;
dst->cap = old[i].cap;

old[i].key = NULL;
old[i].arr = NULL;
old[i].size = old[i].cap = 0;
}
free(old);
}

TimeMap* timeMapCreate() {
TimeMap *m = (TimeMap*)malloc(sizeof(TimeMap));
if (!m) return NULL;
m->cap = 1024; // must be power of 2
m->size = 0;
m->table = (Bucket*)calloc((size_t)m->cap, sizeof(Bucket));
if (!m->table) { free(m); return NULL; }
return m;
}

void timeMapSet(TimeMap* obj, char* key, char* value, int timestamp) {
if (!obj || !key || !value) return;
Bucket *b = findBucket(obj, key, 1);
if (!b) return;

entriesEnsureCap(b, b->size + 1);
if (b->cap < b->size + 1) return; // OOM

b->arr[b->size].ts = timestamp;
b->arr[b->size].val = dupstr(value);
if (!b->arr[b->size].val) return; // OOM
b->size++;
}

static int upperBoundTs(const Entry *a, int n, int ts) {
// first index with a[i].ts > ts
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi – lo) / 2;
if (a[mid].ts <= ts) lo = mid + 1;
else hi = mid;
}
return lo;
}

char* timeMapGet(TimeMap* obj, char* key, int timestamp) {
static char empty[] = "";
if (!obj || !key) return empty;

Bucket *b = findBucket(obj, key, 0);
if (!b || b->size == 0) return empty;

int ub = upperBoundTs(b->arr, b->size, timestamp);
if (ub == 0) return empty;
return b->arr[ub – 1].val;
}

void timeMapFree(TimeMap* obj) {
if (!obj) return;
for (int i = 0; i < obj->cap; i++) {
Bucket *b = &obj->table[i];
if (!b->used) continue;
free(b->key);
for (int j = 0; j < b->size; j++) free(b->arr[j].val);
free(b->arr);
}
free(obj->table);
free(obj);
}

/**
* Your TimeMap struct will be instantiated and called as such:
* TimeMap* obj = timeMapCreate();
* timeMapSet(obj, key, value, timestamp);
* char* param_2 = timeMapGet(obj, key, timestamp);
* timeMapFree(obj);
*/