CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 5 of 6 · 3 min read

Edge cases and changes

Links, permissions and threads.

Step 5: edge cases, tests and change requests

Edge cases:

Case Behaviour
Path without a leading slash Refused
Path with a double slash or trailing slash Cleaned by parts
.. above the root Ignored
File used as a folder in a path "not a directory"
Create over an existing name Refused
Delete a folder with content Allowed here, and removes the whole subtree. Some systems demand a flag
Move onto an existing name Refused here. Some systems overwrite
Move a node to its own parent folder under the same name Works as a no-op or refusal, decide and test it
Very deep trees Recursion depth equals tree depth, which is small in practice
Several threads Not safe. Add a read-write lock on the whole tree, as in Level 5, module 3

The cost of size on a folder is proportional to the number of nodes below it, since it walks the subtree each time. If sizes are asked often, cache each directory's size and update the chain of parents when a file changes. That trades extra work on writes for fast reads, and it adds a chance of the cache drifting out of step, so say both sides.

Tests to write first: each row of the run table; path cleaning with dots and double slashes; every refusal leaving the tree unchanged; moving a nested folder and reading a file inside it; and a find that returns nothing.

Change requests and the part that changes:

  • "Copy a file or a folder." The copyAs helper already exists for rename, and can be reused.
  • "Permissions and owners." Fields on Node and a check in each operation, ideally in one helper.
  • "Hard and soft links." A new node kind that points to another node, with a loop check.
  • "Wildcards in find, such as *.txt." A matcher object in the walk, replacing the suffix test.
  • "Quota per folder." Track sizes up the parent chain and refuse writes that exceed the limit.
  • "Undo and redo." Command objects for each change (Level 4, module 4).
  • "Thread safety." A read-write lock around the whole file system, or per-directory locks with a fixed order to avoid deadlock.
  • "Save to disk and reload." A visitor that writes the tree, and a loader that builds it.

Common mistake

Splitting the path by slashes and walking without cleaning it, or without checking that each step is a directory. Paths with .. go wrong, and a file in the middle of a path crashes with a cast error instead of a clear message.

Interview angle

Answer in your head first, then open it.

Which pattern fits?

Composite. Files and directories share a base type, and a directory holds nodes of that type.

How do you resolve a path?

Clean it into a list of names, then walk from the root one name at a time, checking each step is a directory.

How do you compute the size of a folder?

The sum of its children, by recursion. Cache it if reads dominate.

What can go wrong in move?

Moving a folder into itself, or onto an existing name. Check before changing anything.

Check yourself: 1. Which change request can reuse copyAs? 2. What does caching folder sizes cost? 3. Why must a lock order be fixed with per-directory locks?

Words you will meet

Word Meaning
Directory A node that holds other nodes
Root The top directory, named /
Absolute path A path that starts at the root
Composite A pattern where a group and a single item share one interface
Subtree A node and everything below it