#include <stdlib.h>
#include <string.h>
typedef struct {
int timestamp;
char *value;
} Entry;
typedef struct {
char *key;
Entry *entries;
int size;
int capacity;
} Bucket;
typedef struct {
Bucket *buckets;
int size;
int capacity;
} TimeMap;
TimeMap *timeMapCreate() {
TimeMap *obj = malloc(sizeof(TimeMap));
obj->size = 0;
obj->capacity = 16;
obj->buckets = malloc(sizeof(Bucket) * obj->capacity);
return obj;
}
static Bucket *findOrCreateBucket(TimeMap *obj, char *key) {
for (int i = 0; i < obj->size; i++) {
if (strcmp(obj->buckets[i].key, key) == 0)
return &obj->buckets[i];
}
if (obj->size == obj->capacity) {
obj->capacity *= 2;
obj->buckets = realloc(obj->buckets, sizeof(Bucket) * obj->capacity);
}
Bucket *b = &obj->buckets[obj->size++];
b->key = strdup(key);
b->size = 0;
b->capacity = 4;
b->entries = malloc(sizeof(Entry) * b->capacity);
return b;
}
static Bucket *findBucket(TimeMap *obj, char *key) {
for (int i = 0; i < obj->size; i++) {
if (strcmp(obj->buckets[i].key, key) == 0)
return &obj->buckets[i];
}
return NULL;
}
void timeMapSet(TimeMap *obj, char *key, char *value, int timestamp) {
Bucket *b = findOrCreateBucket(obj, key);
if (b->size == b->capacity) {
b->capacity *= 2;
b->entries = realloc(b->entries, sizeof(Entry) * b->capacity);
}
b->entries[b->size].timestamp = timestamp;
b->entries[b->size].value = strdup(value);
b->size++;
}
char *timeMapGet(TimeMap *obj, char *key, int timestamp) {
Bucket *b = findBucket(obj, key);
if (!b)
return "";
int left = 0, right = b->size - 1, resIdx = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (b->entries[mid].timestamp == timestamp)
return b->entries[mid].value;
if (b->entries[mid].timestamp > timestamp)
right = mid - 1;
else {
resIdx = mid;
left = mid + 1;
}
}
return resIdx == -1 ? "" : b->entries[resIdx].value;
}
void timeMapFree(TimeMap *obj) {
for (int i = 0; i < obj->size; i++) {
free(obj->buckets[i].key);
for (int j = 0; j < obj->buckets[i].size; j++)
free(obj->buckets[i].entries[j].value);
free(obj->buckets[i].entries);
}
free(obj->buckets);
free(obj);
}
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
class TimeMap {
private:
unordered_map<string, vector<pair<int, string>>> kv;
public:
TimeMap() {}
void set(string key, string value, int timestamp) {
kv[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
if (!kv.count(key))
return "";
auto &arr = kv[key];
int left = 0, right = arr.size() - 1, resIdx = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid].first == timestamp)
return arr[mid].second;
if (arr[mid].first > timestamp)
right = mid - 1;
else {
resIdx = mid;
left = mid + 1;
}
}
return resIdx == -1 ? "" : arr[resIdx].second;
}
};
package main
type entry struct {
timestamp int
value string
}
type TimeMap struct {
kv map[string][]entry
}
func Constructor() TimeMap {
return TimeMap{kv: make(map[string][]entry)}
}
func (t *TimeMap) Set(key string, value string, timestamp int) {
t.kv[key] = append(t.kv[key], entry{timestamp, value})
}
func (t *TimeMap) Get(key string, timestamp int) string {
arr, ok := t.kv[key]
if !ok {
return ""
}
left, right, resIdx := 0, len(arr)-1, -1
for left <= right {
mid := left + (right-left)/2
if arr[mid].timestamp == timestamp {
return arr[mid].value
}
if arr[mid].timestamp > timestamp {
right = mid - 1
} else {
resIdx = mid
left = mid + 1
}
}
if resIdx == -1 {
return ""
}
return arr[resIdx].value
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class TimeMap {
private Map<String, List<int[]>> kv;
private Map<String, List<String>> values;
public TimeMap() {
kv = new HashMap<>();
values = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
kv.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[] { timestamp });
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
if (!kv.containsKey(key))
return "";
List<int[]> times = kv.get(key);
List<String> vals = values.get(key);
int left = 0, right = times.size() - 1, resIdx = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
int t = times.get(mid)[0];
if (t == timestamp)
return vals.get(mid);
if (t > timestamp)
right = mid - 1;
else {
resIdx = mid;
left = mid + 1;
}
}
return resIdx == -1 ? "" : vals.get(resIdx);
}
}
class TimeMap {
constructor() {
this.kv = new Map();
}
set(key, value, timestamp) {
if (!this.kv.has(key)) this.kv.set(key, []);
this.kv.get(key).push([timestamp, value]);
}
get(key, timestamp) {
const arr = this.kv.get(key);
if (!arr) return "";
let left = 0, right = arr.length - 1, resIdx = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
const [t, value] = arr[mid];
if (t === timestamp) return value;
if (t > timestamp) right = mid - 1;
else {
resIdx = mid;
left = mid + 1;
}
}
return resIdx === -1 ? "" : arr[resIdx][1];
}
}
class TimeMap:
def __init__(self):
self.kv: dict[str, list[tuple[int, str]]] = {}
def set(self, key: str, value: str, timestamp: int) -> None:
self.kv.setdefault(key, []).append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
arr = self.kv.get(key)
if not arr:
return ""
left, right, resIdx = 0, len(arr) - 1, -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid][0] == timestamp:
return arr[mid][1]
if arr[mid][0] > timestamp:
right = mid - 1
else:
resIdx = mid
left = mid + 1
return "" if resIdx == -1 else arr[resIdx][1]
use std::collections::HashMap;
struct TimeMap {
kv: HashMap<String, Vec<(i32, String)>>,
}
impl TimeMap {
fn new() -> Self {
TimeMap { kv: HashMap::new() }
}
fn set(&mut self, key: String, value: String, timestamp: i32) {
self.kv.entry(key).or_insert_with(Vec::new).push((timestamp, value));
}
fn get(&self, key: String, timestamp: i32) -> String {
let arr = match self.kv.get(&key) {
Some(arr) => arr,
None => return String::new(),
};
let (mut left, mut right) = (0i32, arr.len() as i32 - 1);
let mut res_idx: i32 = -1;
while left <= right {
let mid = left + (right - left) / 2;
let (t, _) = &arr[mid as usize];
if *t == timestamp {
return arr[mid as usize].1.clone();
}
if *t > timestamp {
right = mid - 1;
} else {
res_idx = mid;
left = mid + 1;
}
}
if res_idx == -1 {
String::new()
} else {
arr[res_idx as usize].1.clone()
}
}
}