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.

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.

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.

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.

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.

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