Untitled
unknown
plain_text
15 days ago
2.0 kB
2
Indexable
Never
class TimeMap { private static final int N = 5; // Number of recent values to keep per key private Map<String, TimestampedValue[]> map; private static class TimestampedValue { int timestamp; String value; TimestampedValue(int timestamp, String value) { this.timestamp = timestamp; this.value = value; } } public TimeMap() { map = new HashMap<>(); } public void set(String key, String value, int timestamp) { TimestampedValue[] values = map.computeIfAbsent(key, k -> new TimestampedValue[N]); int index = findInsertionIndex(values, timestamp); if (index < N) { // Shift elements if necessary System.arraycopy(values, index, values, index + 1, Math.min(N - index - 1, values.length - index - 1)); values[index] = new TimestampedValue(timestamp, value); } } public String get(String key, int timestamp) { TimestampedValue[] values = map.get(key); if (values == null) return ""; int index = findFloorIndex(values, timestamp); return index >= 0 ? values[index].value : ""; } private int findInsertionIndex(TimestampedValue[] values, int timestamp) { int left = 0, right = N - 1; while (left <= right) { int mid = left + (right - left) / 2; if (values[mid] == null || values[mid].timestamp < timestamp) { left = mid + 1; } else { right = mid - 1; } } return left; } private int findFloorIndex(TimestampedValue[] values, int timestamp) { int left = 0, right = N - 1; while (left <= right) { int mid = left + (right - left) / 2; if (values[mid] == null || values[mid].timestamp > timestamp) { right = mid - 1; } else { left = mid + 1; } } return right; } }
Leave a Comment