Build a Merkle Tree over a Directory with Hash Lookup and Tree Diff

Build a Merkle tree that represents a directory on the local file system, so that two snapshots of a directory can be compared quickly. Every file is a leaf whose hash depends on the file's content. Every directory is an internal node whose hash is computed from its children, and a directory can have any number of children rather than exactly two as in a binary Merkle tree. Implement the class below in Python, working against the real file system. No test harness is provided: write your own tests for all three methods. The interview lasts 60 minutes, and the three methods and the tests are all expected to be written and working within it. ```python class MerkleTree: def build(self, path): """Build the tree for the directory at `path` and return it.""" def get_hash(self, path, tree): """Return the hash of the file or directory at `path` inside `tree`.""" def diff(self, tree_a, tree_b): """Compare two trees and report what differs between them.""" ``` ### Constraints and Clarifications - The tree is built by reading an actual directory from disk, not an in-memory description of one. - Directory nodes are N-ary: a directory may hold any number of files and subdirectories. - The tree returned by `build` is the value passed to `get_hash` and `diff`, so its representation is your choice. ### Clarifying Questions - Is the `path` given to `get_hash` absolute, or relative to the directory the tree was built from? - What should `diff` return: a flat list of changed paths, or paths labeled as added, removed and modified? When a whole directory is added, should `diff` report the directory once or every file inside it? - Should an entry's name contribute to the hashes, so that renaming a file changes its parent directory's hash? - How should empty directories, symbolic links, hidden files and unreadable files be treated? - Does only file content matter, or also metadata such as permissions and modification times? - Which hash function should be used, and in what form should hashes be returned? - What should `get_hash` do for a path that is not in the tree? ### Part 1 — Build the tree Implement `build(path)`: walk the directory, create a leaf for every file and an internal node for every directory, and compute every node's hash from the bottom up. ```hint Make directory hashes order-independent The file system does not promise any particular order when it lists a directory, yet the same contents must always produce the same hash. ``` ```hint Keep the encodings unambiguous Consider whether a file and a directory, or two different sets of children, could ever feed exactly the same bytes into the hash function, and how to rule that out. ``` #### What This Part Should Cover - A node structure that holds the name, the kind of entry, the hash and the children - Deterministic directory hashes that do not depend on listing order - What goes into each hash (content, names, kind of entry) and why - Reading large files without loading them into memory at once ### Part 2 — Look up a hash Implement `get_hash(path, tree)`: return the hash stored for the file or directory at `path`. ```hint Walk, do not rebuild The tree already holds every hash. The path only says which children to follow, starting from the root. ``` #### What This Part Should Cover - Resolving the path into components relative to the tree's root - Behavior for the root itself and for paths that are not in the tree - Lookup cost in terms of the path's depth ### Part 3 — Diff two trees Implement `diff(tree_a, tree_b)`: report the files and directories that were added, removed or changed between the two trees. ```hint Let equal hashes end the search Ask what two equal hashes tell you about everything underneath those two nodes. ``` #### What This Part Should Cover - Skipping identical subtrees without visiting them - Matching children by name and classifying each difference - A path that is a file in one tree and a directory in the other - Deterministic output order, and cost in terms of how much actually changed ### Part 4 — Test it Write tests showing that all three methods work. ```hint Build fixtures on disk Create small directory trees in a temporary location, so that each test controls exactly what differs between two builds. ``` #### What This Part Should Cover - Temporary-directory fixtures that are always cleaned up - Identical trees, a single edited file, added and removed entries, nested changes, and empty directories - Assertions on which hashes change and which stay the same ### What a Strong Answer Covers - The Merkle property: editing one file changes exactly the hashes on the path from that file to the root - A clean split between walking the disk, hashing, and comparing trees - Complexity of `build`, `get_hash` and `diff`, stated and justified - Complete, working code and passing tests within the time limit ### Follow-up Questions - One file changes after the tree is built. How do you update the tree without rebuilding all of it? - The two directories live on different machines. How would you use the hashes to find the differences while sending as little data as possible? - The directory holds millions of files. What would you change in `build` to make it fast? - How would you detect that a file was moved or renamed, rather than reporting a deletion and an addition?