Katkat
Back

Hash a Repository with a Merkle Tree and Find Changed Files

CursorSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Hash a repository with canonical Merkle nodes, compare changed subtrees, report file changes, and account for symlinks, cached hashes, and snapshot limits.

Design a Merkle-tree representation of a repository. Compute a hash for the complete repository, use it to locate a modified file, and extend the comparison to inspect changed directories and report the changed files inside them.

Constraints & Assumptions

  • The source describes repository/file operations without supplying an in-memory serialization or a hash function. Discuss a real filesystem scan and choose an explicit canonical hashing policy.
  • Define whether metadata, symlinks, renames, and ignored paths affect equality.
  • Compare coherent snapshots or state the limits of scanning files while they are changing.

Clarifying Questions to Ask

  • Does equality mean file bytes only, or also executable bits and other metadata?
  • Should symlinks be hashed as links or followed, and how are cycles handled if followed?
  • Should a rename be reported as delete-plus-add or detected as a separate operation?
  • Is an old Merkle manifest available, or must both snapshots be scanned?

Hints

Hint 1

Hash boundaries and names as well as contents: A directory digest must distinguish two differently named children and must encode concatenated fields unambiguously.

Follow-up questions

  • How would a cached tree update after one known file change?
  • What extra work is needed for byte-exact equality rather than equality under a collision-resistance assumption?