Compute Entity Size and Validate a Hierarchical File System

Problem Statement

You are building an audit and measurement tool for a virtual file system. Each entity in the file system is either a file or a directory:

• A file has a non-negative byte size and no children.
• A directory has a size of 0 and a list of child entity IDs.

Implement the FileSystemAnalyzer class with two methods:

1. validate_system() -> bool: Returns True if the file system forms a valid strict tree hierarchy, or False otherwise. A valid hierarchy satisfies:

   • Every child ID referenced by any directory exists in the file system.
   • No entity is referenced as a child more than once (every non-root entity has exactly one parent).
   • There are no directed cycles.
   • There is at most one root node (an entity with no incoming parent references) if entities exist. An empty file system is valid.
   • Every file has an empty children list.

2. compute_size(entity_id: str) -> int: Returns the total recursive size of the entity with ID entity_id. If entity_id does not exist or if the subgraph reachable from entity_id contains a cycle or invalid reference, return -1.

Interface

class Entity:
    def __init__(self, id: str, is_dir: bool, size: int, children: list[str]):
        self.id = id
        self.is_dir = is_dir
        self.size = size
        self.children = children

class FileSystemAnalyzer:
    def __init__(self, entities: list[Entity]):
        """Initialize with the list of all entities in the file system."""
        pass

    def validate_system(self) -> bool:
        """Validates the entire file system hierarchy."""
        pass

    def compute_size(self, entity_id: str) -> int:
        """Computes total size of entity_id, or -1 if invalid or cycle detected."""
        pass

Examples

Example 1

entities = [
    Entity("root", True, 0, ["bin", "file1"]),
    Entity("bin", True, 0, ["tool"]),
    Entity("file1", False, 120, []),
    Entity("tool", False, 80, [])
]
analyzer = FileSystemAnalyzer(entities)
assert analyzer.validate_system() == True
assert analyzer.compute_size("bin") == 80
assert analyzer.compute_size("root") == 200

Example 2

# Cycle: dirA -> dirB -> dirA
entities = [
    Entity("dirA", True, 0, ["dirB"]),
    Entity("dirB", True, 0, ["dirA"])
]
analyzer = FileSystemAnalyzer(entities)
assert analyzer.validate_system() == False
assert analyzer.compute_size("dirA") == -1

Constraints

• 0 <= len(entities) <= 10^5
• 0 <= Entity.size <= 10^9
• Entity IDs are alphanumeric strings of length 1 <= len(id) <= 64.
• Total number of child references across all entities does not exceed 2 * 10^5.
• Sum of sizes may exceed standard 32-bit signed integers; handle 64-bit integer values appropriately.