Implement Hierarchical Region Access Overrides

Problem Statement

Geographic regions are modeled as a static tree hierarchy where each region has at most one parent (e.g., "GLOBAL" -> "NA" -> "US" -> "CA"). Access permissions (True for granted, False for denied) set at any node inherit down to all of its descendants.

Over time, administrators can set access overrides at any node with an associated integer timestamp. An override takes effect at its given timestamp and persists indefinitely unless overridden. Because log events may be delivered out of order, override records can arrive in any order of their timestamps.

When checking whether access is granted to a region at a query timestamp t:

1. Consider all overrides on the path from the root down to the target region with an override timestamp <= t.
2. The override with the strictly largest timestamp determines the access permission.
3. If two overrides on the path have the exact same timestamp, the one closest to the target region (deepest in the tree) takes precedence.
4. If no overrides on the path occurred at or before t, access defaults to False.

Implement the RegionAccessManager class:

class RegionAccessManager:
    def __init__(self, hierarchy: dict[str, str | None]):
        """
        Initializes the hierarchy where hierarchy[region] = parent_region.
        Root regions have None as their parent.
        """
        pass

    def set_override(self, region: str, allowed: bool, timestamp: int) -> None:
        """
        Records an access override for the specified region starting at timestamp.
        """
        pass

    def has_access(self, region: str, timestamp: int) -> bool:
        """
        Returns whether access is permitted for region at query timestamp.
        """
        pass

Examples

Example 1

hierarchy = {
    "GLOBAL": None,
    "NA": "GLOBAL",
    "US": "NA",
    "CA": "US"
}
manager = RegionAccessManager(hierarchy)

manager.set_override("GLOBAL", True, 10)
manager.set_override("US", False, 20)

# Query at t=15 for "CA":
# Path: GLOBAL (t=10, True)
manager.has_access("CA", 15)  # Returns True

# Query at t=25 for "CA":
# Path: GLOBAL (t=10, True), US (t=20, False)
# Max timestamp is 20 (US), which is False
manager.has_access("CA", 25)  # Returns False

# Out-of-order override set at "NA" with timestamp 30
manager.set_override("NA", True, 30)

# Query at t=35 for "CA":
# Path: GLOBAL (10, True), NA (30, True), US (20, False)
# Max timestamp is 30 (NA), which is True
manager.has_access("CA", 35)  # Returns True

Constraints

• Number of regions N <= 10,000
• Maximum tree depth D <= 50
• Total calls to set_override and has_access <= 50,000
• 1 <= timestamp <= 10^9
• All region names are non-empty strings of alphanumeric characters.
• The hierarchy is guaranteed to form a valid forest/tree (no cycles).