DNS Cache
MediumFreeEvery request starts with a DNS lookup, so browsers and servers keep recent answers in a cache instead of asking DNS each time. Each answer comes with a **time to live** (TTL): how many seconds it can be trusted before it must be looked up again.
Design a class, DnsCache. Creating one with DnsCache(ttl) gives an empty cache where every answer stays fresh for ttl seconds. It has three methods, and each one gets the current time, now, in whole seconds.
put(name, ip, now) stores ip as the answer for name, stored at time now. If name already has an answer, the new one replaces it.
get(name, now) returns the IP stored for name if it's still fresh: now is less than the time it was stored plus ttl. Otherwise it returns None (null in JavaScript). An answer that has expired should also be removed.
size(now) returns how many names have a fresh answer at time now.
Time never goes backward from one call to the next. Try to make every method take O(1) time on average.
Each example is a list of calls, in order: the first creates the cache, and the rest call its methods. The output lists what each call returned. Creating the cache and put return nothing, shown as None in Python and null in JavaScript.
Example 1
- Input
- DnsCache(60), put('example.com', '203.0.113.7', 0), get('example.com', 30), get('example.com', 60), size(60)
- Output
- [None, None, '203.0.113.7', None, 0]
The answer was stored at second 0 with a TTL of 60. It's fresh up to second 59, and expired at second 60.
Example 2
- Input
- DnsCache(10), put('shop.example.com', '198.51.100.1', 0), put('shop.example.com', '198.51.100.2', 5), get('shop.example.com', 12), size(12), get('shop.example.com', 15)
- Output
- [None, None, None, '198.51.100.2', 1, None]
The second put replaces the first, so the name has one answer, stored at second 5. It stays fresh until second 15.
Example 3
- Input
- DnsCache(5), put('a.example.com', '192.0.2.1', 0), put('b.example.com', '192.0.2.2', 3), size(4), size(5), get('b.example.com', 7), size(8)
- Output
- [None, None, None, 2, 1, '192.0.2.2', 0]
Both are fresh at second 4. The first expires at second 5, and the second at second 8.
Constraints
- 1 <= ttl <= 1,000,000,000
- 0 <= now <= 1,000,000,000, and now never goes down from one call to the next
- Names are host names like example.com, and IPs are written like 203.0.113.7
- At most 100,000 calls to put, get and size
Build it in your browser
Write it in Python or JavaScript, run it on the examples, then submit it against hidden tests, with hints and worked solutions when you need them.