Cache With Time Limit

Medium Design Data Structures Hash Map + Heap Original on LeetCode

Reported atNetflix

Cache With Time Limit is a medium design data structures problem solved with the hash map + heap pattern. The best approach, optimal (hash map + min-heap of expiries), runs in O(log n) amortized per call time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan on count) up.

Problem

Design a key-value cache where every entry has its own lifetime. The class TimeLimitedCache supports three operations, and each call carries the current clock value time (the clock never goes backwards between calls):

  • set(time, key, value, duration) stores value under the integer key and makes it valid for duration time units, so it expires at time + duration. Return true if key already held a live (not yet expired) entry, in which case both its value and its timer are replaced; otherwise return false.
  • get(time, key) returns the value of key if it is still live, or -1 if it was never set or has expired.
  • count(time) returns how many keys are live right now.

An entry that expires at e is live at every time t < e and gone from t = e onward.

Examples

Example 1

Input
TimeLimitedCache(), set(0, 7, 40, 100), get(50, 7), count(60), get(100, 7), count(100)
Output
false, 40, 1, -1, 0
Why
Key 7 is stored at time 0 for 100 units, so it lives while the clock is below 100. At time 100 it has expired.

Example 2

Input
TimeLimitedCache(), set(5, 1, 10, 50), set(20, 1, 99, 10), get(25, 1), get(30, 1), set(31, 2, 3, 5), count(33)
Output
false, true, 99, -1, false, 1
Why
The second set finds key 1 still alive, so it returns true and replaces both the value and the timer: the key now expires at 30, not at 55.

Example 3

Input
TimeLimitedCache(), set(1, 4, 8, 3), set(2, 5, 9, 10), count(3), count(4), get(4, 4), set(4, 4, 6, 2), count(5)
Output
false, false, 2, 1, -1, false, 2
Why
Key 4 expires at time 4, so setting it again at time 4 counts as a fresh insert and returns false.

Constraints

  • 0 <= time <= 10^9, and the time arguments never decrease from one call to the next.
  • 0 <= key, value <= 10^9
  • 1 <= duration <= 10^6
  • At most 3 * 10^4 calls in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan on count)O(1) for get/set, O(k) for countO(k)
Optimal (hash map + min-heap of expiries)O(log n) amortized per callO(n)

1Brute force (scan on count)

TimeO(1) for get/set, O(k) for countEvery `count` visits all k keys ever stored, including long-dead ones.
SpaceO(k)Expired entries are never removed, so the map holds every key seen.

Keep a hash map from key to {value, expiresAt}. get and set check a single entry; count walks the whole map and counts the entries whose expiry is still in the future.

  1. set(t, key, value, d): look up key; remember whether it exists with expiresAt > t; store {value, t + d}; return that flag.
  2. get(t, key): if the entry exists and t < expiresAt return its value, else -1.
  3. count(t): loop over all entries and count those with t < expiresAt.
class TimeLimitedCache {
    private final Map<Integer, int[]> map = new HashMap<>(); // key -> {value, expiresAt}

    public TimeLimitedCache() {}

    public boolean set(int time, int key, int value, int duration) {
        int[] e = map.get(key);
        boolean alive = e != null && time < e[1];
        map.put(key, new int[] { value, time + duration });
        return alive;
    }

    public int get(int time, int key) {
        int[] e = map.get(key);
        return (e != null && time < e[1]) ? e[0] : -1;
    }

    public int count(int time) {
        int c = 0;
        for (int[] e : map.values()) {
            if (time < e[1]) c++;
        }
        return c;
    }
}

2Optimal (hash map + min-heap of expiries)

TimeO(log n) amortized per callEach `set` pushes one heap entry, and every entry is popped at most once over the whole run.
SpaceO(n)The heap holds at most one entry per `set` call; the map holds only live keys.

Because the clock never goes backwards, an entry that has expired stays expired. Push {expiresAt, key} into a min-heap on every set. Before any operation, pop heap entries whose expiry is <= time and delete the key from the map, but only if the map still holds that same expiry (otherwise the heap entry is stale: the key was overwritten later). After this cleanup the map contains exactly the live keys, so count is just its size.

  1. purge(t): while the heap top has expiresAt <= t, pop it; if map[key].expiresAt equals that value, remove key from the map.
  2. set(t, key, value, d): purge(t); alive = key in map; store {value, t + d}; push {t + d, key}; return alive.
  3. get(t, key): purge(t); return map[key].value if present, else -1.
  4. count(t): purge(t); return map size.
class TimeLimitedCache {
    private final Map<Integer, int[]> map = new HashMap<>(); // key -> {value, expiresAt}
    private final PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {expiresAt, key}

    public TimeLimitedCache() {}

    private void purge(int time) {
        while (!heap.isEmpty() && heap.peek()[0] <= time) {
            int[] top = heap.poll();
            int[] e = map.get(top[1]);
            if (e != null && e[1] == top[0]) map.remove(top[1]);
        }
    }

    public boolean set(int time, int key, int value, int duration) {
        purge(time);
        boolean alive = map.containsKey(key);
        int exp = time + duration;
        map.put(key, new int[] { value, exp });
        heap.offer(new int[] { exp, key });
        return alive;
    }

    public int get(int time, int key) {
        purge(time);
        int[] e = map.get(key);
        return e == null ? -1 : e[0];
    }

    public int count(int time) {
        purge(time);
        return map.size();
    }
}

Edge cases to test

  • Calling get exactly at the expiry time: the key is already gone
  • Overwriting a live key resets its timer to the new duration, which may be shorter than before
  • Setting a key again right after it expired returns false
  • count on an empty cache returns 0

Hints

Hint 1

Store, for each key, its value together with the absolute time it stops being valid: time + duration.

Hint 2

A key is alive at time t exactly when t < expiresAt. get and set only need that one check.

Hint 3

For a fast count, keep the expiry times in a min-heap and throw away expired entries from the top before answering. Watch out for heap entries that belong to an older version of a key.

FAQ

What is the best time complexity for Cache With Time Limit?

Optimal (hash map + min-heap of expiries) runs in O(log n) amortized per call time and O(n) extra space. Each `set` pushes one heap entry, and every entry is popped at most once over the whole run.

Which pattern does Cache With Time Limit use?

It is a design data structures problem that uses the hash map + heap pattern.

Is there a brute force solution for Cache With Time Limit?

Yes. Brute force (scan on count) takes O(1) for get/set, O(k) for count time and O(k) space. Keep a hash map from key to {value, expiresAt}.

Which edge cases should I test for Cache With Time Limit?

Calling get exactly at the expiry time: the key is already gone; Overwriting a live key resets its timer to the new duration, which may be shorter than before; Setting a key again right after it expired returns false; count on an empty cache returns 0.