Stepwise DNS resolver with aliasing

Question: Stepwise DNS resolver with aliasing

Companies: Anthropic

Difficulty: Medium

Problem statement

Build a simplified DNS resolver step by step against a fixed test harness: basic name lookup first, then alias layers on top. Later steps assume the earlier ones work.

• Level 1: add_record(name, ip), resolve(name): sorted addresses; names are case-insensitive and ignore a trailing dot.
• Level 2: add_alias(alias, target); a name is either an alias or has addresses; cycles and chains over 16 hops resolve to [].
• Level 3: ts/ttl on every call and resolve_with_ttl(name, ts) returning (addresses, ttl_left).
• Level 4: wildcard names like *.example.com; the closest enclosing wildcard answers, an exact name always wins.

class Resolver:
    def add_record(self, name, ip, ts=0, ttl=None): ...
    def add_alias(self, alias, target, ts=0, ttl=None): ...
    def resolve(self, name, ts=0): ...
    def resolve_with_ttl(self, name, ts=0): ...

Approach

The spec used here. Each level is graded by a fixed harness, and later levels assume the earlier ones are right.

Clarify first. Does adding the same address twice duplicate it (no)? Should a cycle raise or return empty (empty here; real resolvers return SERVFAIL)? Does a wildcard match several labels (yes here, as long as nothing closer exists)? What TTL does an answer reached through aliases have (the smallest along the chain, because the answer is wrong as soon as any link changes)?

One normalization helper. Lowercase and strip the trailing dot in _norm, called on every input. Most hidden-test failures in this problem are normalization, not logic.

Resolution is a loop, not recursion. Start at the name; at each step look up its entry (exact first, then wildcards). An alias moves to its target; addresses end the walk. Keep a seen set and a hop counter: the set catches cycles at once, and the counter bounds long but acyclic chains. A loop with an explicit limit also avoids Python's recursion limit.

TTL along a chain. If www → web (ttl 300) and web → 10.0.0.1 (ttl 60), the answer 10.0.0.1 is only safe to cache for 60 seconds. ttl_left is the minimum of each link's remaining time, where remaining = expires_at - t.

Expiry is a read-time check. An entry with expires_at <= t is invisible. Because the alias-versus-address exclusivity rule must also respect expiry, add_record on a name whose alias has expired succeeds.

Code

MAX_HOPS = 16


def _norm(name):
    return name.strip().lower().rstrip(".")


class Resolver:
    def __init__(self):
        self.addresses = {}  # name -> {ip: expires_at or None}
        self.aliases = {}    # name -> (target, expires_at or None)

    @staticmethod
    def _alive(expires_at, ts):
        return expires_at is None or ts < expires_at

    def _live_addresses(self, name, ts):
        return {ip: e for ip, e in self.addresses.get(name, {}).items() if self._alive(e, ts)}

    def _live_alias(self, name, ts):
        entry = self.aliases.get(name)
        return entry if entry and self._alive(entry[1], ts) else None

    def _entry(self, name, ts):
        """('alias', target, expires) | ('addresses', {ip: expires}) | None,
        trying the exact name, then the closest enclosing wildcard."""
        labels = name.split(".")
        candidates = [name] + ["*." + ".".join(labels[i:]) for i in range(1, len(labels))]
        for candidate in candidates:
            alias = self._live_alias(candidate, ts)
            if alias:
                return ("alias", alias[0], alias[1])
            found = self._live_addresses(candidate, ts)
            if found:
                return ("addresses", found)
        return None

    # -- writes --------------------------------------------------------------
    def add_record(self, name, ip, ts=0, ttl=None):
        name = _norm(name)
        if self._live_alias(name, ts):
            return False
        self.addresses.setdefault(name, {})[ip] = None if ttl is None else ts + ttl
        return True

    def add_alias(self, alias, target, ts=0, ttl=None):
        alias, target = _norm(alias), _norm(target)
        if alias == target or self._live_addresses(alias, ts):
            return False
        self.aliases[alias] = (target, None if ttl is None else ts + ttl)
        return True

    # -- reads ---------------------------------------------------------------
    def resolve(self, name, ts=0):
        return self.resolve_with_ttl(name, ts)[0]

    def resolve_with_ttl(self, name, ts=0):
        name, seen, ttl_left = _norm(name), set(), None

        def shorter(expires_at):
            if expires_at is None:
                return ttl_left
            left = expires_at - ts
            return left if ttl_left is None else min(ttl_left, left)

        for _ in range(MAX_HOPS + 1):
            if name in seen:
                return [], None  # cycle
            seen.add(name)
            entry = self._entry(name, ts)
            if entry is None:
                return [], None
            if entry[0] == "addresses":
                for expires_at in entry[1].values():
                    ttl_left = shorter(expires_at)
                return sorted(entry[1]), ttl_left
            _, name, expires_at = entry
            ttl_left = shorter(expires_at)
        return [], None  # chain too long

sorted on address strings is lexicographic (10.0.0.10 before 10.0.0.2). If the grader expects numeric order, sort with ipaddress.ip_address as the key; ask.

Complexity

Let h be the chain length (at most 16), L the labels in a name and k the addresses on the final name.

• add_*: O(k) for the liveness check on the name, else O(1).
• resolve: O(h × L × k) in the worst case: each hop tries up to L wildcard candidates. With h ≤ 16 and L under 10 this is tiny.
• Space: O(entries).

Test cases

from solution import Resolver


def test_addresses_sorted_and_deduplicated():
    r = Resolver()
    r.add_record("api.example.com", "10.0.0.2")
    r.add_record("api.example.com", "10.0.0.1")
    r.add_record("api.example.com", "10.0.0.2")
    assert r.resolve("api.example.com") == ["10.0.0.1", "10.0.0.2"]
    assert r.resolve("nope.example.com") == []


def test_names_are_normalized():
    r = Resolver()
    r.add_record("API.Example.com.", "1.1.1.1")
    assert r.resolve("api.example.COM") == ["1.1.1.1"]

from solution import Resolver


def test_alias_chain():
    r = Resolver()
    r.add_record("lb.example.com", "1.2.3.4")
    assert r.add_alias("web.example.com", "lb.example.com") is True
    assert r.add_alias("www.example.com", "web.example.com") is True
    assert r.resolve("www.example.com") == ["1.2.3.4"]


def test_alias_and_addresses_are_exclusive():
    r = Resolver()
    r.add_record("a.com", "1.1.1.1")
    assert r.add_alias("a.com", "b.com") is False
    r.add_alias("c.com", "a.com")
    assert r.add_record("c.com", "2.2.2.2") is False


def test_cycles_and_dangling_aliases_resolve_empty():
    r = Resolver()
    r.add_alias("a.com", "b.com")
    r.add_alias("b.com", "a.com")
    assert r.resolve("a.com") == []
    r.add_alias("x.com", "missing.com")
    assert r.resolve("x.com") == []


def test_long_chain_is_cut_off():
    r = Resolver()
    for i in range(20):
        r.add_alias(f"n{i}.com", f"n{i + 1}.com")
    r.add_record("n20.com", "9.9.9.9")
    assert r.resolve("n10.com") == ["9.9.9.9"]   # 10 hops is fine
    assert r.resolve("n0.com") == []             # 20 hops is too many

from solution import Resolver


def test_expiry_boundary():
    r = Resolver()
    r.add_record("a.com", "1.1.1.1", ts=100, ttl=50)
    assert r.resolve("a.com", ts=149) == ["1.1.1.1"]
    assert r.resolve("a.com", ts=150) == []


def test_ttl_is_the_minimum_along_the_chain():
    r = Resolver()
    r.add_record("web.com", "10.0.0.1", ts=0, ttl=60)
    r.add_alias("www.com", "web.com", ts=0, ttl=300)
    assert r.resolve_with_ttl("www.com", ts=10) == (["10.0.0.1"], 50)
    r.add_record("static.com", "10.0.0.9")
    r.add_alias("cdn.com", "static.com")
    assert r.resolve_with_ttl("cdn.com", ts=10) == (["10.0.0.9"], None)


def test_expired_alias_frees_the_name():
    r = Resolver()
    r.add_alias("a.com", "b.com", ts=0, ttl=10)
    assert r.add_record("a.com", "1.1.1.1", ts=5) is False
    assert r.add_record("a.com", "1.1.1.1", ts=10) is True
    assert r.resolve("a.com", ts=11) == ["1.1.1.1"]

from solution import Resolver


def test_closest_wildcard_and_exact_wins():
    r = Resolver()
    r.add_record("*.example.com", "1.1.1.1")
    r.add_record("*.eu.example.com", "2.2.2.2")
    r.add_record("api.eu.example.com", "3.3.3.3")
    assert r.resolve("x.example.com") == ["1.1.1.1"]
    assert r.resolve("a.b.example.com") == ["1.1.1.1"]
    assert r.resolve("x.eu.example.com") == ["2.2.2.2"]
    assert r.resolve("api.eu.example.com") == ["3.3.3.3"]
    assert r.resolve("example.com") == []


def test_wildcard_alias():
    r = Resolver()
    r.add_record("edge.net", "5.5.5.5")
    r.add_alias("*.shop.com", "edge.net")
    assert r.resolve("cart.shop.com") == ["5.5.5.5"]

Follow-ups

1. Iterative resolution, the real "stepwise" part. A real resolver asks a root server, which refers it to the .com servers, which refer it to the domain's servers, which answer. Model each server as a resolver that returns either an answer or a referral (NS names plus their addresses, the "glue"), and loop with the same hop limit and cycle detection. Missing glue means resolving the name server's own name first, which is where loops come from.
2. Caching. Cache each link (alias or address set) separately with its own expiry, not the final answer, so a change to one link only invalidates that link. Cache negative answers too (NXDOMAIN), with their own shorter TTL, or a missing name gets hammered.
3. Concurrency. Many clients asking for the same uncached name should trigger one upstream query (request coalescing: a per-name future that later callers wait on).
4. Load balancing. Return the address list in rotated order per query (round-robin DNS), or weighted by health checks. Clients often take the first address, so order matters.
5. Wildcard edge cases. In real DNS a wildcard does not match a name that exists with other record types, and an empty non-terminal (a name that exists only because a child exists) blocks the wildcard. Say this to show you know the simplification.

Interviewer expectations

Mid-level (L4)

• Gets Level 1 right with normalization, deduplication and sorted output.
• Follows alias chains and detects cycles.
• Applies expiry consistently.

Senior (L5)

• Writes resolution as a bounded loop with a seen set, and enforces alias-versus-address exclusivity with expiry taken into account.
• Explains and implements the chain TTL as the minimum over links.
• Implements closest-enclosing wildcards with exact names winning.

Staff (L6+)

• Describes iterative resolution with referrals and glue, and how loops arise there.
• Designs per-link and negative caching, request coalescing and load-balancing order.
• Knows where the model simplifies real DNS (wildcard rules, record types) and says so.