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
chas hashsha256_hex("file:" + c). - A folder has hash
sha256_hex("dir:" + lines), wherelineshas one line per child, sorted by child name: the name, a colon, the child's hash, and a newline. So a folder with childrenbandauses"a:" + hash_a + "\n" + "b:" + hash_b + "\n". An empty folder has hashsha256_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.