2622. Cache With Time Limit
Problem Description
In this problem, we are tasked with designing a class TimeLimitedCache
that supports setting and getting key-value pairs with an expiration time. When you set a key with a value, you also specify how long (in milliseconds) that key should be valid. After this duration has elapsed, the key should be considered expired and should not be accessible.
There are three public methods we need to implement:
-
set(key, value, duration)
: Saves a key with associated value and an expiration time in milliseconds. If this key already exists and has not yet expired, update the value and duration, returningtrue
; if the key is new or has expired, returnfalse
. Afterduration
milliseconds, the key should expire and no longer be accessible. -
get(key)
: Retrieves the value associated with a key if the key is unexpired. If the key does not exist or has expired, it should return-1
. -
count()
: Returns the number of keys that are currently unexpired in the cache.
Every time we interact with the cache (through set
, get
, or count
), we must also ensure that any expired keys are removed.
Intuition
The solution requires us to keep track of the expiration time for each key, in addition to the value associated with it. The simplest approach is to use a data structure that provides efficient access to the keys, values, and their respective expiration times. A Map
is a suitable data structure for this, which in TypeScript can be used to map a key to a tuple containing the value and the expiration time (calculated as the current time plus the duration).
Here is the thought process behind the solution:
-
Storing Key-Value Pairs with Expiration: A
Map
object is used to store the key paired with a tuple of value and the expiration timestamp. -
Handling Expiration: Every time the
set
,get
, orcount
method is called, we first remove expired keys. This is done by iterating over the map entries and checking the current time against the expiration time of each key. If the current time is greater than or equal to the expiration time, the key is deleted. -
Set Method: For the
set
method, we first remove expired keys, then we check if the key already exists in the cache. If it does exist, we overwrite its value and expiration time and returntrue
. If it doesn't exist or has expired and was removed, we set the new value and expiration time and returnfalse
. -
Get Method: For the
get
method, we first remove expired keys. Then we attempt to retrieve the value associated with the key. If the key is found and isn't expired, we return the value; if not, we return-1
. -
Count Method: For the
count
method, we first remove expired keys, then simply return the number of keys currently in the cache (which doesn't include expired keys as they have been removed).
The solution is straightforward, ensuring that at each operation, the cache automatically cleans up expired keys. This keeps the cache's size in check and ensures that all the accessible keys are valid according to the duration that was specified when they were set.
Solution Approach
In our solution, we've crafted a TimeLimitedCache
class that employs algorithmic patterns and data structures to achieve the desired functionality. Let's walk through the implementation step by step.
-
Using a Map Data Structure: We use a
Map
to store the keys and their associated values and expiration times. The Map's key is the integerkey
provided by the user, and the value is a tuple consisting of thevalue
given by the user and the calculated expiration timestamp. This makes retrieval, updating, and deletion operations efficient. -
Timestamp Calculation: To determine when a key should expire, we compute an expiration timestamp by adding the current time (
new Date().getTime()
) to theduration
(in milliseconds). -
Automatic Expiration Handling: Each public method (
set
,get
, andcount
) starts by invoking theremoveExpire
method. This method iterates through all entries in the map, compares the current time with the stored expiration timestamp, and removes any entry that has expired. -
set Method:
- Invoke
removeExpire
to ensure we're working with a fresh, unexpired set of keys. - Check if the key exists with the method
this.cache.has(key)
. - Update the map with the new value and expiration timestamp.
- Return the result of the has check which indicates if the key already existed.
set(key: number, value: number, duration: number): boolean { this.removeExpire(); const ans = this.cache.has(key); this.cache.set(key, [value, this.now() + duration]); return ans; }
- Invoke
-
get Method:
- Invoke
removeExpire
to clear expired keys. - Retrieve the value associated with
key
if it exists and return it. - If the key does not exist or has expired, return
-1
.
get(key: number): number { this.removeExpire(); return this.cache.get(key)?.[0] ?? -1; }
- Invoke
-
count Method:
- Call
removeExpire
to remove expired keys. - Return the count of the entries in the map, which now only includes unexpired keys.
count(): number { this.removeExpire(); return this.cache.size; }
- Call
-
Private Helper Methods:
now()
: Returns the current time in milliseconds since the Unix epoch.removeExpire()
: Removes expired keys from the map by iterating over the entries and deleting those with an expiration date that has passed.
Overall, this implementation is efficient because it performs cleanup lazily, only when necessary. By leveraging the Map
data structure and calculating the expiration dynamically, this approach keeps the usage straightforward while managing the time-sensitive aspect of the key-value store.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach by walking through a small example step by step.
-
Instantiate TimeLimitedCache: First, we create an instance of the
TimeLimitedCache
class.const cache = new TimeLimitedCache();
-
Setting a Value with Expiration: We save a key-value pair with a specific expiration duration in the cache. For instance, we set the key
1
to the value10
with an expiration of 3000 milliseconds (or 3 seconds).cache.set(1, 10, 3000); // returns false as the key is new and therefore not already existing
At this point, the cache will contain one key,
1
, which will expire after 3 seconds. -
Setting an Existing Key Before Expiry: Suppose we quickly set another value to the same key before it expires, let's say after 1 second with a new duration.
setTimeout(() => cache.set(1, 15, 4000), 1000); // returns true as the key existed before and was updated
The key
1
now has a new value,15
, and its expiration is extended by another 4 seconds from the point of this set operation. -
Getting a Value Before Expiry: We attempt to get the value of key
1
while it is still unexpired.setTimeout(() => console.log(cache.get(1)), 1500); // outputs 15, since the key is still valid
Since the key is still valid, it returns the value
15
. -
Count Unexpired Keys: If we want to know how many unexpired keys are in our cache, we could call
count
.console.log(cache.count()); // outputs 1 as there is only one unexpired key
-
Attempting to Get Value After Expiry: If we wait for longer than the expiration duration and then try to get the value of key
1
, it should be expired and hence return-1
.setTimeout(() => console.log(cache.get(1)), 5000); // outputs -1, since the key has expired
-
Count After Expiry: After key
1
has expired and we check the count of unexpired keys, it should now be 0.setTimeout(() => console.log(cache.count()), 5000); // outputs 0 since key `1` has expired
This example demonstrates how the TimeLimitedCache
works in practice. Keys are set with a value and an expiration duration, and they can be updated as long as they haven't expired. The get
method will retrieve the value for a key if it is still within its validity period, and the count
method will return the number of unexpired keys. The cache is cleaned up automatically on any interaction, ensuring that expired keys don't linger in the system.
Solution Implementation
1import time
2from typing import Dict, Tuple
3
4# Define a type alias for the tuple used to store cache values and their expiration timestamps.
5CacheValue = Tuple[int, float]
6
7# This dictionary will act as the cache storage.
8cache: Dict[int, CacheValue] = {}
9
10# A function to obtain the current time in seconds.
11def now() -> float:
12 return time.time()
13
14# A function to remove expired keys and their associated values from the cache.
15def remove_expired_keys() -> None:
16 # Get the current time for comparison.
17 current_time = now()
18 # List of keys to delete after iteration to avoid runtime error.
19 keys_to_delete = []
20 # Iterate over the items in the cache dictionary.
21 for key, (_, expire) in cache.items():
22 # If the expiration time is less or equal than the current time, mark for deletion.
23 if expire <= current_time:
24 keys_to_delete.append(key)
25 # Delete the marked keys.
26 for key in keys_to_delete:
27 del cache[key]
28
29# A function to set a value in the cache with a specific duration before it expires.
30# Returns True if the key was already present in the cache; otherwise, False.
31def set_value(key: int, value: int, duration: float) -> bool:
32 # Remove expired cache entries first.
33 remove_expired_keys()
34 # Check if the key is already present in the cache.
35 was_present = key in cache
36 # Set the key with its value and expiration time.
37 cache[key] = (value, now() + duration)
38 # Return whether the key was present.
39 return was_present
40
41# A function to get a value from the cache by its key.
42# Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
43def get_value(key: int) -> int:
44 # Remove expired cache entries first.
45 remove_expired_keys()
46 # Return the value if the key exists and is not expired, otherwise return -1.
47 return cache[key][0] if key in cache else -1
48
49# A function to count the number of non-expired entries currently in the cache.
50def count_cache_entries() -> int:
51 # Cleanup expired cache entries first.
52 remove_expired_keys()
53 # Return the size of the cache dictionary, representing non-expired entries.
54 return len(cache)
55
56# Usage Example:
57# Note: This is a simple usage example.
58
59# Set a key-value pair in the cache with an expiry duration (should return False initially).
60set_value(1, 42, 5) # Example: Store the value '42' with the key '1' for '5' seconds.
61# Get the value for a given key (should return 42 if not expired).
62get_value(1)
63# Count the number of non-expired cache entries (initially expected to be 1).
64count_cache_entries()
65
1import java.util.Iterator;
2import java.util.Map;
3import java.util.concurrent.ConcurrentHashMap;
4
5// Class CacheValue to store the cache value along with its expiration timestamp
6class CacheValue {
7 int value;
8 long expire;
9
10 CacheValue(int value, long expire) {
11 this.value = value;
12 this.expire = expire;
13 }
14}
15
16public class Cache {
17 // ConcurrentHashMap to act as the cache storage
18 private Map<Integer, CacheValue> cache = new ConcurrentHashMap<>();
19
20 // Method to obtain the current time in milliseconds
21 private long now() {
22 return System.currentTimeMillis();
23 }
24
25 // Method to remove the expired keys and their associated values from the cache
26 private void removeExpiredKeys() {
27 long currentTime = now();
28 Iterator<Map.Entry<Integer, CacheValue>> iterator = cache.entrySet().iterator();
29
30 while (iterator.hasNext()) {
31 Map.Entry<Integer, CacheValue> entry = iterator.next();
32 if (entry.getValue().expire <= currentTime) {
33 iterator.remove();
34 }
35 }
36 }
37
38 // Method to set a value in the cache with a certain duration before it expires
39 // Returns true if the key was already present in the cache; otherwise, returns false
40 public boolean setValue(int key, int value, int duration) {
41 removeExpiredKeys();
42 boolean wasPresent = cache.containsKey(key);
43 cache.put(key, new CacheValue(value, now() + duration));
44 return wasPresent;
45 }
46
47 // Method to get a value from the cache by its key
48 // Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1
49 public int getValue(int key) {
50 removeExpiredKeys();
51 CacheValue cacheValue = cache.get(key);
52 if (cacheValue != null) {
53 return cacheValue.value;
54 }
55 return -1;
56 }
57
58 // Method to count the number of non-expired entries currently in the cache
59 public int countCacheEntries() {
60 removeExpiredKeys();
61 return cache.size();
62 }
63
64 // Usage example (not for production use)
65 public static void main(String[] args) {
66 Cache myCache = new Cache();
67
68 boolean isPresent = myCache.setValue(1, 42, 1000); // Sets the key with a value and expiry duration, expected to return false initially
69 System.out.println(isPresent); // Expected to print `false`
70
71 int value = myCache.getValue(1); // Should return 42 if not expired
72 System.out.println(value); // Expected to print `42`
73
74 int count = myCache.countCacheEntries(); // Should return the count of non-expired cache entries, expected to be 1 initially
75 System.out.println(count); // Expected to print `1`
76 }
77}
78
1#include <iostream>
2#include <map>
3#include <chrono>
4
5// We are defining a type alias for the pair that will be used to store the cache values along with their expiration timestamps
6using CacheValue = std::pair<int, long long>;
7
8// This map will act as the cache storage
9std::map<int, CacheValue> cache;
10
11// A function to obtain the current time in milliseconds
12long long now() {
13 return std::chrono::duration_cast<std::chrono::milliseconds>(
14 std::chrono::system_clock::now().time_since_epoch()
15 ).count();
16}
17
18// A function to remove the expired keys and their associated values from the cache
19void removeExpiredKeys() {
20 auto currentTime = now();
21 for (auto it = cache.begin(); it != cache.end(); ) {
22 if (it->second.second <= currentTime) {
23 it = cache.erase(it); // Erase and advance the iterator in one step
24 } else {
25 ++it; // Only advance the iterator
26 }
27 }
28}
29
30// A function to set a value in the cache with a certain duration before it expires.
31// Returns true if the key was already present in the cache; otherwise, returns false.
32bool setValue(int key, int value, int duration) {
33 removeExpiredKeys();
34 bool wasPresent = cache.find(key) != cache.end();
35 cache[key] = {value, now() + duration};
36 return wasPresent;
37}
38
39// A function to get a value from the cache by its key.
40// Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
41int getValue(int key) {
42 removeExpiredKeys();
43 auto it = cache.find(key);
44 if (it != cache.end()) {
45 return it->second.first;
46 }
47 return -1;
48}
49
50// A function to count the number of non-expired entries currently in the cache.
51int countCacheEntries() {
52 removeExpiredKeys();
53 return cache.size();
54}
55
56// Usage example (main function)
57int main() {
58 // Sets the key with a value and an expiry duration, expected to return false initially
59 std::cout << std::boolalpha << setValue(1, 42, 1000) << std::endl;
60
61 // Should return 42 if not expired
62 std::cout << getValue(1) << std::endl;
63
64 // Should return the count of non-expired cache entries, expected to be 1 initially
65 std::cout << countCacheEntries() << std::endl;
66
67 return 0;
68}
69
1// We are defining a type alias for the tuple that will be used to store the cache values along with their expiration timestamps
2type CacheValue = [value: number, expire: number];
3
4// This map will act as the cache storage
5const cache: Map<number, CacheValue> = new Map();
6
7// A function to obtain the current time in milliseconds
8function now(): number {
9 return new Date().getTime();
10}
11
12// A function to remove the expired keys and their associated values from the cache
13function removeExpiredKeys(): void {
14 const currentTime = now();
15 for (const [key, [, expire]] of cache) {
16 if (expire <= currentTime) {
17 cache.delete(key);
18 }
19 }
20}
21
22// A function to set a value in the cache with a certain duration before it expires.
23// Returns true if the key was already present in the cache; otherwise, false.
24function setValue(key: number, value: number, duration: number): boolean {
25 removeExpiredKeys();
26 const wasPresent = cache.has(key);
27 cache.set(key, [value, now() + duration]);
28 return wasPresent;
29}
30
31// A function to get a value from the cache by its key.
32// Returns the value if the key is in the cache and hasn't expired; otherwise, returns -1.
33function getValue(key: number): number {
34 removeExpiredKeys();
35 return cache.get(key)?.[0] ?? -1;
36}
37
38// A function to count the number of non-expired entries currently in the cache.
39function countCacheEntries(): number {
40 removeExpiredKeys();
41 return cache.size;
42}
43
44// Usage
45// An example of usage is provided below.
46// Please remove this when implementing this logic in production as global state and functions
47// may collide with other parts of the system, and direct usage like this might not be recommended.
48
49setValue(1, 42, 1000); // Sets the key with a value and an expiry duration, expected to return false initially
50getValue(1); // Should return 42 if not expired
51countCacheEntries(); // Should return the count of non-expired cache entries, expected to be 1 initially
52
Time and Space Complexity
Time Complexity:
-
set
operation:- This operation involves checking the presence of a key, setting a new value for the key, and removing expired elements.
- The check and set operations on the map are
O(1)
on average (amortized time). - The
removeExpire
operation iterates over the entire cache to remove expired entries, leading to anO(n)
complexity wheren
is the number of entries. - Therefore, the overall time complexity for
set
isO(n)
.
-
get
operation:- Similar to
set
,get
first callsremoveExpire
, which isO(n)
. - Retrieving the value for a key from the map is
O(1)
. - Thus, the time complexity for
get
is alsoO(n)
.
- Similar to
-
count
operation:- This operation only calls
removeExpire
before returning the cache size. - The time complexity for
removeExpire
isO(n)
, so the same holds for thecount
operation.
- This operation only calls
-
now
operation:- Simply returns the current time, which is a constant-time operation,
O(1)
.
- Simply returns the current time, which is a constant-time operation,
-
removeExpire
operation:- This operation has to iterate through each element in the cache, checking expiration, and possibly deleting the entry.
- The worst-case complexity for this operation is
O(n)
.
Space Complexity:
- The space complexity of the TimeLimitedCache class depends on the number of key-value pairs stored in the cache map. Since each key maps to a fixed-size array of two numbers (the value and the expiration time), the space complexity is
O(n)
, wheren
is the number of unique keys that have been inserted into the cache.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!