class MerkleTree:
The round: Cursor's technical phone screen, the first round in most reports: implement a Merkle tree (one report calls it a hash tree) over a real repository you are given. Ten reports from May 2025 to September 2026. One report gives 45 minutes, two give 60. In one, Google or AI was allowed for syntax but not for the implementation; in the earliest, the interviewer allowed ChatGPT. One report lists Python, TypeScript, Rust or Go; one candidate had to write their own tests. The interviewer gives the hashing rule; in one report, a text file's hash is a function of its contents and a folder's hash is the hash of its children's hashes concatenated. The tree follows the folder structure, so a folder can have any number of children; it is not a binary tree.
How the reports split it: one lists three parts (hash the whole repository; change a file and find it; change a folder and find every file in it). One lists two (build the hash tree; use it to optimise client/server updates). In the earliest, the server offers upload(filename, content) and check(filename), and the question is how client and server keep the tree in sync. This page grades three parts, one program that grows.
Given here: hash_bytes(data) returns the SHA-256 hex digest, and folder_hash(children) hashes a folder from its (name, hash) children: one name:hash line per child, in name order, joined by newlines. Both are ours. The reported rule above uses only the children's hashes; this page adds each child's name, because otherwise renaming a file changes no hash at all and neither diff nor sync can see it. Ask which the interviewer wants, and say why it matters. Paths are relative to the root with / separators, and the root itself is "".
Part 1 — build the tree and get_hash: MerkleTree(root) walks the folder at root and computes every hash. get_hash(path) returns the hash of the file or folder at path ("" for the whole repository), or None when nothing is there.
Part 2 in one report: change one file and find it. Compare hashes from the root down: when a directory's hash differs, descend only into children whose hashes differ, until you reach the changed file; a diff that returns (added, modified, removed) gives it directly.
When a directory's hash differs, recurse into all of its children and collect every file underneath it. The diff traversal should not stop at the directory level but continue down to enumerate individual changed files. Candidates were expected to extend the same diff logic to handle folder-level changes and return all affected leaf files.
In the earliest report the server offers upload(filename, content) and check(filename), and the interviewer's point was that once the server detects a changed file, the chain of ancestors up to the root tells you which nodes need a new hash. A later report lists the part as 'optimise sending client/server updates using the hash tree'. Comparing hashes from the root down, so unchanged subtrees are skipped and only changed files are uploaded, is the standard way to use the tree; that part is our note.
Standard explanation — no candidate report records what the interviewer accepted here.
Client holds local MerkleTree, server holds its own; client compares root hash with server, then recursively finds diverging subtrees and only uploads changed files.
Ten reports: this is the phone screen, on a real repository. 45 minutes in one report, 60 in two. Parts reported: build and get_hash, diff, change a file and find it, change a folder and find all its files, and client/server sync. Two candidates never saw the client/server part. One candidate finished the part they were given and was still rejected without seeing part two; they and a reply guess the bar is a fast, uninterrupted implementation. In the earliest report the interviewer allowed ChatGPT; a later one allows Google or AI for syntax only.
The round: Cursor's technical phone screen, the first round in most reports: implement a Merkle tree (one report calls it a hash tree) over a real repository you are given. Ten reports from May 2025 to September 2026. One report gives 45 minutes, two give 60. In one, Google or AI was allowed for syntax but not for the implementation; in the earliest, the interviewer allowed ChatGPT. One report lists Python, TypeScript, Rust or Go; one candidate had to write their own tests. The interviewer gives the hashing rule; in one report, a text file's hash is a function of its contents and a folder's hash is the hash of its children's hashes concatenated. The tree follows the folder structure, so a folder can have any number of children; it is not a binary tree.
How the reports split it: one lists three parts (hash the whole repository; change a file and find it; change a folder and find every file in it). One lists two (build the hash tree; use it to optimise client/server updates). In the earliest, the server offers upload(filename, content) and check(filename), and the question is how client and server keep the tree in sync. This page grades three parts, one program that grows.
Given here: hash_bytes(data) returns the SHA-256 hex digest, and folder_hash(children) hashes a folder from its (name, hash) children: one name:hash line per child, in name order, joined by newlines. Both are ours. The reported rule above uses only the children's hashes; this page adds each child's name, because otherwise renaming a file changes no hash at all and neither diff nor sync can see it. Ask which the interviewer wants, and say why it matters. Paths are relative to the root with / separators, and the root itself is "".
Part 1 — build the tree and get_hash: MerkleTree(root) walks the folder at root and computes every hash. get_hash(path) returns the hash of the file or folder at path ("" for the whole repository), or None when nothing is there.
Part 2 — diff two trees: diff(old, new) returns every file that differs from old to new as a (path, change) pair, where change is "added", "modified" or "removed", sorted by path. A changed file comes back as modified; a renamed file as removed under its old path and added under its new one; a new folder lists every file in it as added; a deleted folder lists every file it held as removed. Descend only into folders whose hashes differ: that is what the tree is for. One report writes it as a method returning a ChangeType enum (ADDED, MODIFIED, REMOVED); an enum with those names passes here too.
Part 3 — keep a server in sync: SyncServer is the server's copy. upload(path, content) stores a file and recomputes the hashes of that file and of every folder above it, and nothing else. check(path) returns the server's current hash for a file or folder, or None. sync(tree, server) uploads only what the server lacks or holds stale, comparing hashes from the root down and skipping every subtree whose hash already matches, and returns the uploaded paths, sorted. The server holds files, so an empty folder is never synced. The reported server offers only upload and check, so deleting files on the server is a discussion point, not graded.
Modify a single file in the repo. Can you find which file changed?
Now if a whole folder changed, find all files under that folder.
How would you use the HashTree to optimize syncing between a client and server? The server provides upload(filename, content) and check(filename) APIs.
Implement both client and server components of this sync protocol.
| Approach | Notes |
|---|---|
| Flat map of path → hash | Simpler to implement but loses the structural benefit of Merkle trees — diff requires comparing all paths instead of pruning unchanged subtrees, making it O(N) instead of O(changed files). |
| Pre-build full hash map then diff | Build complete path→hash dictionaries for both trees, then set-diff the keys and compare hashes for shared keys. Easier to reason about correctness but foregoes the tree-pruning optimization. |
Common mistakes: Not finishing the diff: one candidate built the tree but did not finish the comparison, so never reached the follow-ups.; Not knowing Python's file-system library: one candidate says anyone who has never used it, or never written a file system, will not finish.; Writing too slowly: a candidate who finished every part, wrote tests and fixed two small bugs was still rejected, and guesses the bar is an uninterrupted run; a reply guesses the same.; In the earliest report the interviewer allowed ChatGPT; the candidate wonders whether leaning on it is why they failed.
Interviewer hints: For the sync follow-up in the earliest report, the interviewer's point was that once the server detects a changed file, the chain of ancestors tells you which nodes need a new hash.; You build the tree over a real repository you are given, folders as tree nodes rather than a binary tree, and write your own tests.; In a recent report Google or AI is allowed for syntax but not for the implementation; in the earliest report the interviewer allowed ChatGPT.
What passers do: One candidate's advice: settle the interface first, for example a ChangeType enum (ADDED, MODIFIED, REMOVED) and diff(self, other) returning (path, ChangeType) pairs, because their own comparison function was not finished in time.
Why people fail: Not completing the diff/compare function within 60 minutes; Having small bugs that prevent code from running end-to-end; Writing too slowly — candidates who finished the core logic still failed if test case writing was shaky; Getting stuck on binary tree assumptions instead of adapting to N-ary folder structure; Relying on AI to generate implementation (flagged); Completing the main problem but failing the client/server follow-up extension
Edge cases probed: Empty directories; Files added in one version that don't exist in the other (ADDED vs REMOVED symmetry); Directory renamed (appears as removal + addition); Sorting of child hashes must be lexicographic by name for determinism; Handling binary vs text files when computing hash; Large repositories with ~100k files (mentioned in OJ constraint)