Level 1 Region permissions that flow downhill
An ads platform lets advertisers target places organised in a fixed tree: a planet splits into continents, continents into countries, countries into cities, and so on. Permissions are handed out per advertiser per subtree: access to a place means access to everything inside it.
Implement RegionAccess:
RegionAccess(edges: list[tuple[str, str]]): each pair is(parent, child). Together the pairs form one rooted tree (the root is the only region that is never a child; every other region has exactly one parent). Region names are unique. With no edges there are no regions.grant(advertiser: str, region: str) -> None: the advertiser gains access toregionand every region below it.revoke(advertiser: str, region: str) -> None: the advertiser loses access toregionand every region below it. Anything outside that subtree is unaffected.has_access(advertiser: str, region: str) -> bool.
All three raise ValueError for a region that isn't in the tree. An advertiser that has never been granted anything simply has no access.
Later calls override earlier ones on the regions they cover. So a grant on a big region followed by a revoke on a small region inside it leaves a "hole", and a grant on a small region after a revoke on a big one opens just that small subtree.
edges = [("Earth", "Asia"), ("Earth", "Americas"), ("Asia", "Japan"), ("Asia", "India"),
("Japan", "Tokyo"), ("Japan", "Osaka"), ("Americas", "Peru")]
ra = RegionAccess(edges)
ra.grant("acme", "Asia")
ra.has_access("acme", "Osaka") # True inside Asia
ra.has_access("acme", "Earth") # False access flows down, never up
ra.revoke("acme", "Japan")
ra.has_access("acme", "Tokyo") # False the hole
ra.has_access("acme", "India") # True
ra.grant("acme", "Osaka")
ra.has_access("acme", "Osaka") # True
ra.has_access("acme", "Tokyo") # False
ra.has_access("zeta", "Asia") # False never granted anything
ra.has_access("acme", "Mars") # ValueError
Size: up to 100,000 regions, but the tree is shallow (depth at most about 30), with many advertisers and many operations. Granting "Earth" must not visit all 100,000 regions: make grant and revoke cost O(1) or O(depth), and has_access O(depth).
Show hint
Don't expand a grant into every region it covers. Store, per advertiser, only the regions you were told about, with a timestamp and whether it was a grant or a revoke. To answer has_access, walk from the region up to the root; the most recent instruction on that path decides.