CSE Roadmap

Core tier · about 4 hours · 6 parts

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.