Part 6 of 6 · 2 min read
Exercises
Easy
Easy 1: Clean the paths (20 minutes)
Give the cleaned name list for /a/./b/../c, //x//y/, and /../a.
Done when: you write a, c, then x, y, then a.
Hint
.. removes the last name, and an extra .. at the start does nothing.
Easy 2: Run the file system (20 minutes)
Type the code and reproduce the first three rows of the run table.
Done when: you print [2026, a.txt], hello, 12, 12 and the two found paths.
Hint
Create parents with mkdirs first.
Easy 3: Sizes by hand (20 minutes)
A tree has /a/x.txt with 4 characters, /a/b/y.txt with 10, and /c.txt with 3. Give the size of /a/b, /a, and /.
Done when: you write 10, 14 and 17.
Hint
A folder's size is the sum of its children.
Medium
Medium 1: Copy (45 minutes)
Add copy(from, to) for files and folders, refusing existing names and copying into itself.
Done when: after copying a folder, changing the copy leaves the original unchanged.
Hint
Reuse the recursive copy that rename already uses.
Medium 2: Wildcard find (45 minutes)
Replace the suffix test by a pattern with * meaning any characters. Test *.txt, a* and *.
Done when: three tests give the expected lists, and an empty result is an empty list.
Hint
Turn the pattern into a regular expression, escaping other characters.
Medium 3: Cached sizes (45 minutes)
Cache the size of each directory, and update the parent chain on every write, create and delete. Check against a slow recount after random operations.
Done when: 1,000 random operations never show a cached size that differs from the recount.
Hint
Walk up from the changed node and add the difference.
Hard
Hard 1: Links (90 minutes)
Add soft links that hold a path. Reading a link reads its target. Detect loops, such as a link that points to itself, with a depth limit.
Done when: a loop gives a clear error, and a link to a file reads that file's text.
Hint
Count the number of links followed, and stop at 10.
Hard 2: Undo and redo (90 minutes)
Wrap create, write, delete and move in command objects with undo. Undo three steps and redo two.
Done when: a test shows the tree equal to its earlier shape after each undo.
Hint
Each command stores what it needs to reverse itself.
Hard 3: Thread safety (90 minutes)
Add a read-write lock. Run 8 threads doing random reads and writes, and check that the tree is never in a broken state. Compare with an unlocked version.
Done when: the locked version passes a structure check after 100,000 operations, and the unlocked one fails at least once or is shown to be unsafe by reasoning.
Hint
Reads take the read lock and changes take the write lock.