progress

~/problems / Arrays & hashing / Hash maps and counting

Merkle tree directory diff

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~40 min Cursor

Level 1 Hash every folder

A code editor keeps a copy of your project on its servers so it can search it. Uploading the whole project after every edit would be wasteful. Instead, both sides build a Merkle tree: every file gets a hash of its content, and every folder gets a hash of its children's names and hashes. If two folders have the same hash, everything inside them is the same, so a sync only has to look where hashes differ. This level builds the hashes; the next one uses them.

A directory tree is a nested dict. A key is a file or folder name. A file's value is its content (a str), and a folder's value is another dict. The tree you are given is the root folder.

Write node_hashes(tree) -> dict[str, str], which maps the path of every node, files and folders, to its hash:

  • The root's path is "". Any other node's path is the names from the root down to it joined by /, like "src/app/main.py".
  • sha256_hex(text) is the SHA-256 of the text's bytes, written as 64 lowercase hex digits. The starter defines it.
  • A file with content c has hash sha256_hex("file:" + c).
  • A folder has hash sha256_hex("dir:" + lines), where lines has one line per child, sorted by child name: the name, a colon, the child's hash, and a newline. So a folder with children b and a uses "a:" + hash_a + "\n" + "b:" + hash_b + "\n". An empty folder has hash sha256_hex("dir:").

Names are compared as plain strings (by character code, so "B" < "a"). The file: and dir: prefixes make sure a file can never have the same hash as a folder.

Don't change tree.

node_hashes({"a.txt": "hi"})
# {"a.txt": "9da65b3f0372ffbe9499b3ad8064736c287b30f2ef1374672225297abca29209",   # sha256_hex("file:hi")
#  "":      "4829b36d484f47de5bcefb89731beaa5fa4ded2f5c20125e67ee592070d01f1b"}   # sha256_hex("dir:a.txt:9da6...9209\n")

node_hashes({})
# {"": "9d1ae5a6cdbe837d499a16cb32234ea2d953c60e8e8fdc88f84a3bbe2d629143"}         # sha256_hex("dir:")

In C++ and Java the tree is a Node, and sha256Hex (C++) or Hashing.sha256Hex (Java) is provided. The starter shows both.

Constraints: up to 10^5 nodes, at most 100 levels deep. Names are 1 to 50 characters from letters, digits, ., _ and -. File contents are ASCII text (they may contain newlines and colons), up to 10^6 characters in total.

⭐ Bonus: a speed test with a 100,000-node tree earns a star if every node is hashed once.

Level 2 unlocks when level 1 passes.

Topic: Hash maps and counting. Counter/defaultdict, complement lookups, prefix-sum + hash map.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc