How should I practice Filesystem Hash Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Cursor phone screen problems in FastPrep.

Is Filesystem Hash Tree associated with Cursor?

FastPrep tags this as a Cursor phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Filesystem Hash Tree

Learn this problem

● Medium

CursorFULLTIMEPHONE SCREEN

Problem statement

Build the hash tree for one finite rooted filesystem.

The filesystem is described by three parallel arrays:

paths[i] is a normalized absolute path. The root path is /.
types[i] is either FILE or DIRECTORY.
contents[i] is the UTF-8 text of a file and is the empty string for a directory.

Hash every node with 64-bit FNV-1a. Start from offset basis 0xcbf29ce484222325. For each input byte, XOR it into the current value and multiply by prime 0x100000001b3, keeping only the low 64 bits. Render the result as exactly 16 lowercase hexadecimal digits.

A file's hash is the FNV-1a hash of its UTF-8 content bytes.
A directory's hash is the FNV-1a hash of the ASCII bytes formed by concatenating the 16-digit hashes of its direct children in lexicographic child-name order.
An empty directory therefore hashes the empty byte sequence.

Return one string path=hash for every node, sorted in lexicographic path order.

Function

hashFileSystem(paths: String[], types: String[], contents: String[]) → String[]

Examples

Example 1

paths = ["/","/docs","/docs/a.txt","/docs/b.txt"]types = ["DIRECTORY","DIRECTORY","FILE","FILE"]contents = ["","","hi","bye"]return = ["/=2ff0bacda65bbb3f","/docs=f065768922a4a2f1","/docs/a.txt=08ba5f07b55ec3da","/docs/b.txt=008a2f19137d94c3"]

The two file contents are hashed first. The directory /docs concatenates the hash of a.txt before the hash of b.txt, then the root hashes the resulting /docs hash.

Example 2

paths = ["/","/empty","/readme"]types = ["DIRECTORY","DIRECTORY","FILE"]contents = ["","","hello"]return = ["/=e4e38674a4d63445","/empty=cbf29ce484222325","/readme=a430d84680aabd0b"]

The empty directory hashes the empty byte sequence. The root concatenates the hash of child empty before the hash of child readme.

Example 3

paths = ["/","/z.txt","/a","/a/x.txt"]types = ["DIRECTORY","FILE","DIRECTORY","FILE"]contents = ["","same","","same"]return = ["/=d8493d74efdbb133","/a=a303de6ee1bde850","/a/x.txt=097b5e18bf93ef5b","/z.txt=097b5e18bf93ef5b"]

Equal file contents produce equal file hashes. Directory /a hashes its one child's hash, and the root processes child name a before z.txt.

Constraints

1 <= paths.length = types.length = contents.length <= 100000.
paths contains exactly one / root and one unique normalized absolute path per node.
Every non-root parent path appears in paths.
Every path component contains only lowercase English letters, decimal digits, ., _, and -.
Every types[i] is FILE or DIRECTORY.
A file has no descendants. Its content may be empty. A directory has empty contents[i].
Each path contains at most 500 UTF-8 bytes, and the total file-content size is at most 1000000 UTF-8 bytes.