Implement a Simplified DNS Resolver
Company: Anthropic
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
Implement a simplified DNS resolver in Python. You are given an in-memory DNS zone and must complete a small resolver step by step. The goal is not to build a real network DNS server, but to correctly handle name normalization, aliases, fallback behavior, errors, cycles, caching, and safe concurrent access.
### Data model
A DNS zone is represented as a dictionary from domain name to a record object:
```python
zone = {
"example.com": {"A": ["93.184.216.34"]},
"www.example.com": {"CNAME": "example.com"},
"api.example.com": {"A": ["10.0.0.5", "10.0.0.6"]},
}
```
Each record may contain:
- `A`: a list of IPv4 address strings.
- `CNAME`: a single alias target domain.
Assume a record will not intentionally contain both `A` and `CNAME`, but your code should handle malformed records gracefully.
### Required API
Implement:
```python
class DNSResolver:
def __init__(self, zone: dict, fallback=None):
pass
def resolve(self, domain: str) -> list[str]:
pass
```
`fallback`, if provided, is another object with a compatible `resolve(domain: str) -> list[str]` method.
### Requirements
1. **Normalize domain names**
- Domain lookup should be case-insensitive.
- Ignore leading and trailing whitespace.
- Treat a trailing dot as optional.
- For example, `" WWW.Example.COM. "` should resolve the same way as `"www.example.com"`.
2. **Resolve direct A records**
- If a domain has an `A` record, return its list of IP addresses in stored order.
- Return a new list so callers cannot mutate internal resolver state.
3. **Resolve aliases**
- If a domain has a `CNAME`, follow the alias chain until an `A` record is found.
- For example, if `www.example.com -> example.com` and `example.com` has an `A` record, resolving `www.example.com` should return the IPs for `example.com`.
4. **Handle missing records**
- If the domain is not found locally and no fallback resolver exists, raise `LookupError`.
- If a fallback resolver exists, delegate to it.
5. **Handle invalid records**
- If a record has neither `A` nor `CNAME`, raise `ValueError`.
- If a record has a malformed `A` value, such as a string instead of a list, raise `ValueError`.
- If a record has a malformed `CNAME` value, raise `ValueError`.
6. **Detect alias cycles**
- If aliases form a cycle, raise `RuntimeError`.
- Example: `a.com -> b.com -> c.com -> a.com`.
7. **Add caching**
- Cache successful local resolutions so repeated calls avoid recomputing the same alias chain.
- The cache key should use the normalized domain name.
- Do not cache failures unless explicitly documented.
- Returned cached lists must still be safe from caller mutation.
8. **Support concurrent calls**
- Multiple threads may call `resolve` at the same time.
- Ensure the cache and other mutable internal state remain consistent.
- Avoid holding locks while calling the fallback resolver if possible.
### Examples
```python
zone = {
"example.com": {"A": ["93.184.216.34"]},
"www.example.com": {"CNAME": "example.com"},
"loop1.com": {"CNAME": "loop2.com"},
"loop2.com": {"CNAME": "loop1.com"},
}
resolver = DNSResolver(zone)
resolver.resolve(" example.COM. ")
# returns ["93.184.216.34"]
resolver.resolve("www.example.com")
# returns ["93.184.216.34"]
resolver.resolve("missing.com")
# raises LookupError
resolver.resolve("loop1.com")
# raises RuntimeError
```
Design the implementation so that it can be tested incrementally with unit tests for each requirement.
Quick Answer: This question evaluates understanding of DNS semantics (name normalization, A and CNAME records, alias chains and cycle detection), robust error handling, cache design, and safe concurrent access when implementing a simplified resolver.
Implement the resolver rules described below. For grading, write a function `solution(zone, queries, fallback_zone=None)` that internally creates a resolver and processes the domains in `queries` from left to right.
Each DNS record is stored in a dictionary:
- `A`: a list of IPv4 address strings.
- `CNAME`: a single alias target domain.
Rules your resolver must follow:
1. Normalize domain names for lookups: trim whitespace, make lowercase, and ignore a trailing dot.
2. If a normalized domain has an `A` record, return its IP list in stored order.
3. If it has a `CNAME`, follow aliases until an `A` record is found.
4. If a domain is missing locally, use `fallback_zone` if provided; otherwise it is a lookup failure.
5. Invalid records must raise a value error:
- record has neither `A` nor `CNAME`
- record has both `A` and `CNAME`
- `A` is not a list of strings
- `CNAME` is not a string or normalizes to an empty name
6. Alias cycles must raise a runtime error.
7. Cache successful local resolutions by normalized name so repeated queries avoid recomputing the alias chain.
8. Returned lists must be safe from caller mutation.
Because online judges compare return values, your `solution` function should return one result per query:
- the resolved list of IPs on success
- the string `"LookupError"`, `"ValueError"`, or `"RuntimeError"` if that query would raise that exception
Notes:
- Only validate record shape, not the exact IPv4 syntax.
- If a local alias eventually points to a name that only exists in the fallback zone, delegation to the fallback is allowed.
- Tests are sequential, but your internal resolver design should keep its cache thread-safe.
Constraints
- 0 <= len(queries) <= 10^4
- 0 <= len(zone) + len(fallback_zone or {}) <= 10^4
- Total length of all domain strings is at most 2 * 10^5
- A valid uncached resolution should run in O(length of alias chain), and repeated cached lookups should be O(1)
Examples
Input: ({"example.com": {"A": ["93.184.216.34"]}, "www.example.com": {"CNAME": "example.com"}}, [" example.COM. ", "WWW.example.com", "www.example.com"], None)
Expected Output: [["93.184.216.34"], ["93.184.216.34"], ["93.184.216.34"]]
Explanation: The first query resolves directly after normalization. The second follows a CNAME to `example.com`. The third has the same normalized name as the second and can be served from cache.
Input: ({"api.example.com": {"A": ["10.0.0.5", "10.0.0.6"]}}, ["api.example.com"], None)
Expected Output: [["10.0.0.5", "10.0.0.6"]]
Explanation: Direct A records should be returned in stored order.
Input: ({"local.com": {"A": ["1.1.1.1"]}}, [" WWW.OTHER.com. "], {"other.com": {"A": ["8.8.8.8"]}, "www.other.com": {"CNAME": "other.com"}})
Expected Output: [["8.8.8.8"]]
Explanation: The name is missing locally, so resolution is delegated to the fallback zone, which follows `www.other.com -> other.com`.
Input: ({}, ["missing.com"], None)
Expected Output: ["LookupError"]
Explanation: The domain does not exist locally and there is no fallback resolver.
Input: ({"a.com": {"CNAME": "b.com"}, "b.com": {"CNAME": "c.com"}, "c.com": {"CNAME": "a.com"}}, ["a.com"], None)
Expected Output: ["RuntimeError"]
Explanation: The alias chain loops back to `a.com`, so this is a cycle.
Input: ({"bad.com": {"A": "1.2.3.4"}, "empty.com": {}}, ["bad.com", "empty.com"], None)
Expected Output: ["ValueError", "ValueError"]
Explanation: `bad.com` has an invalid A value because it is a string instead of a list. `empty.com` has neither `A` nor `CNAME`.
Input: ({"example.com": {"A": ["1.2.3.4"]}}, [], None)
Expected Output: []
Explanation: With no queries, the result is an empty list.
Input: ({"alias.com": {"CNAME": 123}}, ["alias.com"], None)
Expected Output: ["ValueError"]
Explanation: A CNAME target must be a string.
Hints
- Create one helper to normalize names, and use it for zone keys, queries, cache keys, and CNAME targets.
- Following CNAMEs is like walking pointers in a graph: use a `seen` set to detect cycles, and store cached answers as immutable data so callers cannot mutate internal state.