Untitled

mail@pastecode.io avatar
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