DNS resolver

def normalize(name):
    return name.lower().rstrip(".")      # "WWW.Shop.com." -> "www.shop.com"


class Resolver:
    def __init__(self, records):
        self.records = records           # name -> ("A", ip) or ("CNAME", target)
        self.cache = {}                  # name -> ip, "NXDOMAIN" or "LOOP"
        self.lookups = 0                 # how many times we read the record store

    def resolve(self, name):
        name = normalize(name)
        chain, seen = [], set()
        while name not in self.cache:
            if name in seen:             # back to a name on this chain: a cycle
                result = "LOOP"
                break
            seen.add(name)
            chain.append(name)
            self.lookups += 1
            record = self.records.get(name)
            if record is None:
                result = "NXDOMAIN"      # the chain ends at a name with no record
                break
            kind, value = record
            if kind == "A":
                result = value
                break
            name = normalize(value)      # a CNAME: follow it
        else:
            result = self.cache[name]    # reached a name we already know
        for visited in chain:            # every name on the chain has the same answer
            self.cache[visited] = result
        return result

#include <algorithm>
#include <cctype>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

string normalize(string name) {                   // "WWW.Shop.com." -> "www.shop.com"
    for (char& c : name) c = tolower((unsigned char)c);
    while (!name.empty() && name.back() == '.') name.pop_back();
    return name;
}

class Resolver {
    unordered_map<string, pair<string, string>> records;   // name -> {"A", ip} or {"CNAME", target}
    unordered_map<string, string> cache;                   // name -> ip, "NXDOMAIN" or "LOOP"

public:
    int lookups = 0;                                       // how many times we read the record store

    explicit Resolver(unordered_map<string, pair<string, string>> records) : records(move(records)) {}

    string resolve(string name) {
        name = normalize(name);
        vector<string> chain;
        unordered_set<string> seen;
        string result;
        while (true) {
            auto hit = cache.find(name);
            if (hit != cache.end()) { result = hit->second; break; }   // a name we already know
            if (seen.count(name)) { result = "LOOP"; break; }          // back on this chain: a cycle
            seen.insert(name);
            chain.push_back(name);
            lookups++;
            auto rec = records.find(name);
            if (rec == records.end()) { result = "NXDOMAIN"; break; }  // the chain ends at nothing
            auto& [kind, value] = rec->second;
            if (kind == "A") { result = value; break; }
            name = normalize(value);                                   // a CNAME: follow it
        }
        for (auto& visited : chain) cache[visited] = result;          // the whole chain shares the answer
        return result;
    }
};

import java.util.*;

class Resolver {
    private final Map<String, String[]> records;            // name -> {"A", ip} or {"CNAME", target}
    private final Map<String, String> cache = new HashMap<>();   // name -> ip, "NXDOMAIN" or "LOOP"
    int lookups = 0;                                        // how many times we read the record store

    Resolver(Map<String, String[]> records) { this.records = records; }

    static String normalize(String name) {                  // "WWW.Shop.com." -> "www.shop.com"
        String n = name.toLowerCase(Locale.ROOT);
        while (n.endsWith(".")) n = n.substring(0, n.length() - 1);
        return n;
    }

    String resolve(String name) {
        name = normalize(name);
        List<String> chain = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        String result;
        while (true) {
            if (cache.containsKey(name)) { result = cache.get(name); break; }   // a name we already know
            if (!seen.add(name)) { result = "LOOP"; break; }                     // back on this chain: a cycle
            chain.add(name);
            lookups++;
            String[] record = records.get(name);
            if (record == null) { result = "NXDOMAIN"; break; }                  // the chain ends at nothing
            if (record[0].equals("A")) { result = record[1]; break; }
            name = normalize(record[1]);                                         // a CNAME: follow it
        }
        for (String visited : chain) cache.put(visited, result);                // the whole chain shares the answer
        return result;
    }
}