SwadhyAI Notes

All Low-Level Design notes

Machine coding · not HLD

In-memory file system

You start with a HashMap from full path to bytes. mkdir /a/b and write /a/b/c.txt look easy. Then they ask ls /a, and you scan every key for a prefix. Then they create a file named /a, and /a/b is suddenly illegal. That is why this round wants a tree, not a path map.

An in-memory file system is a tree: a node is either a file (bytes) or a directory of child nodes, and path resolution walks that tree. If File and Directory duplicate path logic as unrelated classes, you will write find() twice. Blocks, replication, and metadata services belong on the related System Design note: File storage . If you mention , you wandered off.

The four commands

1

mkdir /a/b

Walk from root and create each missing DirectoryNode along the path.

2

write /a/b/c.txt

Parents must be directories; the FileNode leaf holds cloned bytes.

3

ls /a

Return the named children of that DirectoryNode, not a prefix scan.

4

Reject file-in-the-middle

A name is a file or a directory, not both at once.

What actually happens when you skip the tree

The HashMap story above is the usual first sketch, and it fails for two reasons that show up in every follow-up. ls of a directory becomes a prefix scan over every stored path. A file named /a then blocks /a/b, because the map has no place to say "this name is a directory that can still have children." Model the tree.

is the pattern because Node is the shared contract: File is a leaf with bytes, Directory is a composite with named children, and mkdir, ls, write, and read all walk from a root. See Composite. A is a sequence of names, not the storage model. Resolve starts at root and rejects a file in the middle of a path.

Ownership is composition: a directory owns its children, so deleting a directory deletes the subtree. A is the controller. Do not put bytes on Directory. ls can use Iterator on children. Size of a directory is a recursive query, Composite's classic extra. A size cache is optional and easy to get wrong; compute it first. , blocks, and permission bits are not this interview.

Simple rule of thumb

Once you have seen why the path map fails, the scope decision is small: what belongs in the first forty-five minutes, and what you should decline.

1. Model a tree. A HashMap of full paths cannot ls a directory cleanly or stop a file named /a from blocking /a/b (see the story above).

2. Keep paths absolute. Empty segment, trailing slash, and ".." are product choices. Relative paths need a ; skip cwd unless they ask. Absolute-only is the honest first scope.

3. Stay in machine coding. , path resolution, and a small API are the product. Designing an OS file system is a different round.

How to explain this in an interview

Say you will build a of FileNode leaves and DirectoryNode children, walk it with a value, and put mkdir, ls, write, read, and delete on a . Then decline and come back to mkdir.

From problem to mechanism

Here is the same HashMap failure, slowed down so you can see which object owns each job.

Problem. Callers need mkdir, write, read, and ls on paths such as /a/b/c.txt. A name cannot be a file and a directory at once.

Naive system. Store a String path as the only model. ls becomes a prefix scan. There is no walk that can reject a file in the middle.

Break it. write /a, then mkdir /a/b. The second command should fail because /a is a file. The map cannot say that cleanly, and a later delete can leave an orphan FileNode reachable by an old path string.

Mechanism. : Node is the component, FileNode is the leaf, DirectoryNode holds named children. A splits and validates. walks from root. Clone bytes on read and write so callers cannot mutate internals (encapsulation, same as not leaking an LRU Node). Directory size is a recursive sum of file byte lengths; compute it before you cache, because a cache goes stale on every write.

Node

Shared contract: a name, and whether this node is a directory.

FileNode

Holds bytes; read and write clone so callers cannot mutate storage.

DirectoryNode

Named children with add, get, and ls. No content bytes. LinkedHashMap keeps ls order.

Path

Value object that splits and validates. Resolve rules live in one place.

FileSystem

Facade for mkdir, ls, write, read, and delete. Always walks from root.

Java API sketch

The types above become this sketch. FileNode clones on the boundary; DirectoryNode uses LinkedHashMap so ls order is stable.

java
interface Node {
  String name();
  boolean isDirectory();
}

abstract class AbstractNode implements Node {
  private final String name;
  protected AbstractNode(String name) { this.name = Objects.requireNonNull(name); }
  public final String name() { return name; }
}

class FileNode extends AbstractNode {
  private byte[] content = new byte[0];
  FileNode(String name) { super(name); }
  public boolean isDirectory() { return false; }
  void write(byte[] bytes) { content = bytes.clone(); }
  byte[] read() { return content.clone(); }
}

class DirectoryNode extends AbstractNode {
  private final Map<String, Node> children = new LinkedHashMap<>();
  DirectoryNode(String name) { super(name); }
  public boolean isDirectory() { return true; }
  void add(Node child) { children.put(child.name(), child); }
  Optional<Node> get(String name) { return Optional.ofNullable(children.get(name)); }
  Collection<Node> children() { return Collections.unmodifiableCollection(children.values()); }
}

class Path {
  static List<String> parts(String raw) { /* split, reject empty, reject .. if out of scope */ }
}

class FileSystem {
  private final DirectoryNode root = new DirectoryNode("");
  void mkdir(String path) { /* walk, create dirs */ }
  void write(String path, byte[] content) { /* parent must be dir */ }
  byte[] read(String path);
  List<String> ls(String path);
}

Tests that prove the seams

Tests never touch java.io.File. The tree is the product.

java
@Test
void mkdirWriteLs() {
  FileSystem fs = new FileSystem();
  fs.mkdir("/a/b");
  fs.write("/a/b/c.txt", "hello".getBytes());
  assertEquals(List.of("b"), fs.ls("/a"));
  assertEquals("hello", new String(fs.read("/a/b/c.txt")));
}

Walk /a/b/c.txt by hand

The mechanism names a walk from root. This is that walk after mkdir /a/b and write /a/b/c.txt hello, which is the tree the diagram shows.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.
Read the diagram definition
flowchart TB
    R["/ (DirectoryNode)"]
    A["a (DirectoryNode)"]
    B["b (DirectoryNode)"]
    C["c.txt (FileNode)"]
    R --> A
    A --> B
    B --> C

mkdir /a/b starts at root. Part "a" is missing, so create DirectoryNode a under root. Part "b" is missing, create b under a. write /a/b/c.txt hello: walk a, walk b (must be directories), create FileNode c.txt, write bytes. ls /a returns [b]. ls /a/b returns [c.txt].

FileNode.write clones the array so external arrays cannot corrupt file contents. Callers must not retain a mutable alias into the tree. read() clones too. Deleting a directory must define whether non-empty deletes are allowed; composition means the children go away.

First tests

mkdir /a/b, ls /a → [b], write /a/b/c.txt, read equals hello, ls /a/b → [c.txt].

Reject tests

write /a then mkdir /a/b. Second command fails. Name /a is a file.

Invalid cases, concurrency, and what still breaks

The walk above assumes every parent is a directory. These cases are how the design says no, how two threads collide, and which follow-ups stay in scope.

Invalid cases

  • write /a when /a is a directory: a name is a file or a directory, not both.
  • mkdir /a/b when /a is a file: a file in the middle makes resolve fail.
  • ls a missing path: pick a domain error or empty; do not NPE.
  • String path as the only model: cannot ls or protect prefix collisions.
  • Designing an OS file system: Composite, path resolution, and a small API are the product.

Concurrency

Two mkdir on the same path: serialize on or on the parent directory. Children maps are not thread-safe by default. A single lock on the facade is an honest first answer for machine coding.

What the follow-up changes

  • mkdir -p creates missing intermediates; still a walk, still .
  • Directory size is a recursive query first; cache later only if they insist.
  • Distributed storage: open the System Design note; keep off this page.

Still fails when…

  • A size cache goes stale on every write, which is why you compute first.
  • Delete leaves an orphan FileNode reachable by an old path string.
  • Callers keep a mutable byte[] alias if write or read skips clone.

Trade-offs

  • One lock on the facade is honest; the other option is the parent directory.
  • Absolute-only is the first scope; waits until they ask.
  • ls order from LinkedHashMap is enough for this machine-coding round.

Wrap-up

You have the tree, the walk, and the rejections. Use the forty-five-minute plan below, then the related notes.

Forty-five minutes

  1. 0–8Sketch Node, FileNode, and DirectoryNode so the shared tree contract exists.
  2. 8–20Implement mkdir /a/b and ls /a by walking from the root.
  3. 20–32write and read c.txt; reject a file sitting in the middle of a path.
  4. 32–40Delete a directory so the whole subtree disappears with it.
  5. 40–45Name out loud, then decline and blocks.

Read next

Iterator on directory children is a polite extra. The required idea is Composite plus a Path value that walks from root. Mention the file-storage HLD when they ask blocks and replication, then come back to mkdir.

Key takeaway

Creating /a as a file blocks creating /a/b; that rejection is why you modeled a tree. Directories are composites, files hold cloned bytes, and size is recursive. Inode and distributed-storage interviews are a different round.