Practice/Microsoft/Design a DNS caching system

Design a DNS caching system

Object Oriented DesignMust

Problem

Design and implement a URL caching system that stores mappings between domain names and their resolved IP addresses. This system should minimize redundant network lookups by caching results locally, while efficiently managing memory through eviction policies and time-based expiration.

Your cache must handle scenarios such as limited memory capacity, entry expiration based on time-to-live (TTL), and frequent access patterns where popular URLs should remain cached longer than rarely accessed ones.

The system should be optimized for:

• Fast lookups (O(1) average case)
• Efficient eviction when capacity is reached
• Automatic expiration of stale entries
• Thread-safe operations (conceptually, though implementation can be single-threaded)

Requirements

1. Implement a URLCache class with configurable maximum size and TTL
2. Support put(url, ip_address) to store URL-to-IP mappings
3. Support get(url) to retrieve cached IP addresses, returning None for expired or missing entries
4. Implement LRU (Least Recently Used) eviction when cache reaches maximum capacity
5. Automatically expire entries after their TTL has elapsed
6. Provide invalidate(url) to manually remove specific entries
7. Provide clear() to remove all cached entries
8. Handle edge cases: empty cache, single-entry cache, expired entries, duplicate URLs

Constraints

• Cache size: 1 ≤ max_size ≤ 10,000
• TTL: 1 ≤ ttl_seconds ≤ 86,400 (1 day)
• URL length: 1 ≤ length ≤ 2,048 characters
• Expected time complexity: O(1) for get and put operations
• Expected space complexity: O(n) where n is the number of cached entries

Examples

Example 1: Basic cache operations

cache = URLCache(max_size=3, ttl_seconds=3600) cache.put("api.example.com", "192.168.1.1") cache.get("api.example.com") # Returns "192.168.1.1" cache.put("cdn.example.com", "10.0.0.1") cache.get("cdn.example.com") # Returns "10.0.0.1" cache.get("unknown.com") # Returns None

Example 2: LRU eviction

cache = URLCache(max_size=2, ttl_seconds=3600) cache.put("a.com", "1.1.1.1") cache.put("b.com", "2.2.2.2") cache.put("c.com", "3.3.3.3") # Evicts "a.com" (least recently used) cache.get("a.com") # Returns None (was evicted) cache.get("b.com") # Returns "2.2.2.2" cache.get("c.com") # Returns "3.3.3.3"

Example 3: TTL expiration

` cache = URLCache(max_size=10, ttl_seconds=2) cache.put("service.com", "5.5.5.5") cache.get("service.com") # Returns "5.5.5.5" immediately

Wait 3 seconds

cache.get("service.com") # Returns None (expired) `

Example 4: Update existing entry

cache = URLCache(max_size=5, ttl_seconds=3600) cache.put("app.com", "7.7.7.7") cache.put("app.com", "8.8.8.8") # Update with new IP cache.get("app.com") # Returns "8.8.8.8"