DNS Resolver Exercise

In this exercise, you'll build your own version of a Domain Name System (DNS) resolver, the system your computer uses to translate a domain name into an IP address. You aren't expected to know anything about DNS — everything is explained in the directions.

Implement each step in order so the provided unit tests pass. It's normal to not complete all the steps.

Step 0 - Normalize

In DNS, names are case insensitive, and by convention always end in a trailing dot. For example, "Anthropic.COM" normalizes to "anthropic.com.".

Implement normalize() in dns_exercise.py. You can run all Step 0 tests with:

./test.sh 0

You can read the tests in tests/test_dns.py and you can run an individual test with pytest -k test_function_name. For example:

pytest -k test_normalize_trailing_dot

Step 1 - Annotated Example

For concreteness, we'll start with an annotated example and show the actual responses to help you get a feel for how DNS works.

Suppose you type "Anthropic.COM" into your web browser. With your normalize() function, the normalized name is anthropic.com..

We've provided a function send_query(normalized_name, server_ip) that simulates the network call to server_ip, and the IP address of a “root server” which is the starting point of any DNS query.

send_query("anthropic.com.", ROOT_SERVER)

returns:

DNSResponse(
    status="NOERROR",
    answer=None,
    authority=[DNSRecord(name="com.", rdtype="NS",
                         rdata="a.gtld-servers.net.")],
    additional=[DNSRecord(name="a.gtld-servers.net.", rdtype="AAAA",
                          rdata="2001:db8::1"),
                DNSRecord(name="a.gtld-servers.net.", rdtype="A",
                          rdata="192.5.6.30")]
)

The root server query succeeded with NOERROR, but answer is None — it doesn't know the IP address. But it does know another server who can help us. The NS type record says that the server named a.gtld-servers.net. knows more about com. names.

Finally, our long journey is over. The answer field holds a type A record, and we return its rdata.

Now implement resolve() in dns_exercise.py so that the provided unit tests pass for Step 1. Test Step 1 from Terminal with:

./test.sh 1

Don't worry about handling any cases not covered by the tests yet; we'll get to those in future steps. For now, assume every query returns status="NOERROR".

If you get a status of NXDOMAIN, this means “the name you asked for definitely doesn't exist”. Check your normalization.

Step 2 - CNAME records

Sometimes, instead of containing an A record, the answer section will contain a CNAME record.

For example, when resolving www.example.com, the authoritative server returns:

DNSResponse(
    status="NOERROR",
    answer=DNSRecord(name="www.example.com.", rdtype="CNAME",
                     rdata="example.com."),
    authority=[],
    additional=[],
)

This means we have to start the process over from the root server, but instead of looking for www.example.com., we're now looking for a different name stored in this rdata field: example.com.

CNAME chains can be longer than one hop. For example, store.example.com aliases to shop.fastcdn.net., which itself aliases to cdn.fastcdn.net., which finally has an A record.

Add handling for this case to resolve() and test your code with:

./test.sh 2

Step 3 - Missing glue records

Sometimes we are directed to a nameserver whose IP isn't in the additional section. When there is no matching glue record, you must resolve the nameserver's IP address before continuing.

For example, when we try to resolve api.anthropic.com:

DNSResponse(
    status="NOERROR",
    answer=None,
    authority=[DNSRecord(name="api.anthropic.com.", rdtype="NS",
                         rdata="gemma.ns.cloudflare.com.")],
    additional=[],
)

The authority says to ask gemma.ns.cloudflare.com., but additional is empty — this server doesn’t know the IP for gemma.ns.cloudflare.com.. So we need to resolve gemma.ns.cloudflare.com. first, starting from the root server, just like any other resolution, to get its IP, then continue resolving api.anthropic.com.

For this step, still assume there is exactly one NS record in authority.

./test.sh 3

Step 4 - Error handling and NS fallback

Now, in the authority section: there can be multiple NS records, and each NS record may or may not have a matching glue record. We will try each nameserver in order until one succeeds.

So far every query has returned status="NOERROR", but there are two other statuses we'll handle.

NXDOMAIN means you're asking the right server, but the name definitely doesn't exist in this zone. In this case, there's no point trying another NS — we can just return None.
REFUSED means for whatever reason, the server can't help you and does not know about this name. In this case we need to try the next nameserver if available.

For example, resolving deadns.com, the .com TLD returns two NS records with glue:

DNSResponse(
    status="NOERROR",
    answer=None,
    authority=[DNSRecord(name="deadns.com.", rdtype="NS",
                         rdata="ns1.deadns.com."),
               DNSRecord(name="deadns.com.", rdtype="NS",
                         rdata="ns2.deadns.com.")],
    additional=[DNSRecord(name="ns1.deadns.com.", rdtype="AAAA",
                          rdata="2001:db8::1"),
                DNSRecord(name="ns1.deadns.com.", rdtype="A",
                          rdata="192.0.2.1"),
                DNSRecord(name="ns2.deadns.com.", rdtype="A",
                          rdata="192.0.2.2")]
)

Querying the first nameserver at 192.0.2.1 returns status="REFUSED" — so we fall back to the second NS at 192.0.2.2, which succeeds.

Edge cases: if a nameserver has no glue and we fail to resolve its IP, skip it and try the next NS. If all the nameservers fail to help us, we return None.

./test.sh 4

Step 5 - Cycle Handling

Properly configured DNS should not contain cycles, but in practice these can happen by accident in two ways:

CNAME chains: A aliases to B, which aliases back to A.
Glue lookups: zone A's NS is in zone B, and zone B's NS is in zone A.

Implement a basic form of cycle detection: if we haven't succeeded after max_queries calls to send_query, assume we're caught in a cycle and return None.

./test.sh 5

Step 6 - Cached batch resolution

Implement resolve_all(). Given a list of domains, resolve each one and return a mapping from each input domain, note that inputs are not necessarily normalized, to its resolved IP, or None if it couldn't be resolved.

The key requirement: cache the result of every send_query call so that no (name, server) pair is queried twice across the batch. Many domains share the same delegation path, for example they all query ROOT, then the .com TLD, so caching eliminates redundant work.

NXDOMAIN and REFUSED responses should also be cached.
max_queries is the limit per domain. A cache hit does not call send_query, but still counts against the limit for that domain.
The cache must be scoped to each resolve_all() call — not persisted globally.

./test.sh 6

Step 7 - Parallel resolution

Make resolve_all() resolve domains concurrently to complete faster in wall-clock time.

At most max_workers, default 5, calls to send_query may be in-flight at any time.
If a query is already in-flight from another domain's resolution, wait for it rather than sending a duplicate.

./test.sh 7

Limits

[execution time limit] 30 seconds
[memory limit] 4g

我们长期稳定承接各大科技公司如Capital One、TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.