# Compute Entity Size and Validate a Hierarchical File System You are given in-memory entities representing files and directories. Every entity has a unique ID. A file has a nonnegative size. A directory contains IDs of files or child directories. Given an entity ID, compute its total size: a file's own size, or the sum of all files reachable below a directory. As a follow-up, design a validation pass for the filesystem. The original validity rules are not fully specified, so first state which invariants you propose to check and which structures, such as hard links, are allowed. ### Clarifying Questions to Ask - Is there exactly one root, and must every entity be reachable from it? - May one entity have multiple parents, or are hard links forbidden? - Can symbolic links exist, and should their targets contribute to size? - How should missing child IDs, cycles, duplicate child references, and integer overflow be reported? - Is the structure immutable during the query? ### Part 1 — Compute total entity size Give an algorithm for one query and explain how you would support many size queries or updates. #### What This Part Should Cover - File and directory base cases, recursive or iterative traversal, and cycle defense. - Time and space complexity in terms of reachable entities. - Memoization or cached subtree sizes only when the ownership model makes double counting unambiguous. ### Part 2 — Validate the filesystem Define a concrete validity contract, then return actionable errors rather than a single unexplained Boolean. #### What This Part Should Cover - Unique IDs, valid child references, allowed node types, nonnegative file sizes, and directories owning child lists. - Cycle detection and, if required, exactly one parent and root reachability. - Distinguishing malformed input from a supported shared-reference or link feature. - A traversal that does not recurse past stack limits on a deep hierarchy. ### What a Strong Answer Covers - Does not invent forgotten interview requirements as facts. - States whether shared descendants count once per path, once globally, or are forbidden. - Prevents infinite traversal on cycles and protects 64-bit accumulation. - Explains cache invalidation when file sizes or directory membership changes. ### Follow-up Questions 1. How would you update cached directory sizes after moving a large subtree? 2. What changes if hard links are allowed and disk usage should count a file only once? 3. How would you report every validation error without letting one cycle block the rest of the audit?