Implement a Simplified DNS Resolver

Problem Description

Implement an in-memory DNS resolver that manages resource records and handles recursive lookup semantics for domain queries.

Your resolver must support two record types:

• "A": Maps a domain name to an IPv4 address string (e.g., "192.0.2.1"). Multiple A records can exist for the same domain.
• "CNAME": Maps an alias domain name to a canonical domain name (e.g., "target.example.com"). A domain can have at most one valid CNAME record.

Requirements

1. Domain Normalization: Domain names are case-insensitive and may optionally end with a trailing dot (.). For example, "example.COM." and "example.com" refer to the same domain.
2. TTL Expiration: Records are inserted with a ttl (Time To Live, in seconds) at a specified current_time. A record is valid for queries where current_time < insertion_time + ttl. If a record has expired by current_time, it must be ignored during resolution.
3. CNAME Resolution: When querying for record type "A" on a domain that has a valid CNAME record pointing to another domain, the resolver must follow the CNAME chain until it finds valid A record(s) for the target domain.
4. Cycle & Hop Detection: If a CNAME resolution encounters a cycle (e.g., a.com -> b.com -> a.com) or exceeds 10 hops, resolution must fail immediately and return an empty list [].
5. Record Conflicts: If a domain already has a valid CNAME record, adding an A record should overwrite/invalidate the CNAME record, and vice versa.

Class Interface

class DNSResolver:
    def __init__(self):
        pass

    def add_record(self, name: str, record_type: str, value: str, ttl: int, current_time: int) -> None:
        """
        Stores a DNS record.
        """
        pass

    def resolve(self, name: str, record_type: str, current_time: int) -> list[str]:
        """
        Resolves the query at current_time.
        Returns a sorted list of unique values (e.g., IP addresses), or an empty list if not found or on cycle/exceeded hops.
        """
        pass

Examples

resolver = DNSResolver()
resolver.add_record("example.com", "A", "93.184.216.34", ttl=60, current_time=100)
resolver.add_record("www.example.com.", "CNAME", "example.com", ttl=60, current_time=100)

# Direct lookup
resolver.resolve("EXAMPLE.COM.", "A", current_time=120)
# Returns: ["93.184.216.34"]

# CNAME resolution
resolver.resolve("www.example.com", "A", current_time=150)
# Returns: ["93.184.216.34"]

# Expired TTL
resolver.resolve("www.example.com", "A", current_time=170)
# Returns: []

Constraints

• Number of operations (add_record + resolve) = 1.
• current_time is non-decreasing across consecutive queries.
• Max hops for CNAME resolution: 10.