Domain Operation Simulator
Process rows of [op, domain, ip] in order and return the outputs of the GET and COUNT rows.
PUT domain ipstores the IP for the domain, replacing any earlier one. It outputs nothing.GET domainoutputs the stored IP, or"404".COUNT domainoutputs, as a string, how many stored domains equaldomainor sit under it.
["PUT", "www.apple.com", "10.20.30.40"] ["PUT", "jobs.apple.com", "10.20.30.50"] ["PUT", "sites.google.com", "142.258.145.693"] ["GET", "sample.com"] ["GET", "www.apple.com"] ["COUNT", "apple.com"] ["COUNT", "com"] Expected: ["404", "10.20.30.40", "2", "3"]
"Under" means on a label boundary: www.apple.com is under apple.com, and pineapple.com is not.
Make COUNT's cost independent of how many domains are stored — scanning every stored domain per COUNT is the first answer, not the goal. The tests don't time you, so say the complexity out loud.
Hints
Hint 1
Keep a Map from domain to IP for PUT and GET. A COUNT can then scan the keys with d === domain || d.endsWith("." + domain). The dot is what stops pineapple.com from counting under apple.com.
Hint 2
For the fast version, keep a trie of labels read right to left (com, then apple, then www), with a counter on each node. A PUT of a new domain adds 1 along its path, and a COUNT walks to its node and reads the counter.
Hint 3
A second PUT for the same domain only changes the IP. Check the map first so the trie counts it once.