Sweaty Imposter

In-Memory File System

Design an in-memory file system that supports directories and files, path-based operations (mkdir, ls, create, read, write, move, and delete), and metadata such as size and timestamps.

Clarifying Questions

  • Absolute paths only, or relative paths with a current working directory?
  • Do we need symbolic links or hard links?
  • Should mkdir create missing parents, like mkdir -p?
  • Are permissions and owners in scope?
  • Will multiple threads use the file system at once?

Core Requirements

  • Create directories and files at a given path.
  • List a directory's children in sorted order, or return the name for a file path.
  • Read, write, and append file content.
  • Move and rename files and directories.
  • Delete files and directories, recursively when asked.
  • Report size and created and modified times for any entry.

Canonical class breakdown

FileSystem: Facade exposing path operations; resolves paths and delegates to the tree.
Entry (abstract): Shared base for files and directories with name, parent, and timestamps.
File: Leaf entry holding content bytes; its size is the content length.
Directory: Composite entry holding a sorted map of child names to Entries; its size sums its children.
PathResolver: Parses and normalizes paths (., .., and repeated slashes) into components and walks the tree.
FileSystemException / NotFound, AlreadyExists, NotADirectory, DirectoryNotEmpty: Specific errors callers can catch individually.

Java sketchjava

// Java skeleton

abstract class Entry {
    protected String name;
    protected Directory parent;
    protected final Instant createdAt;
    protected Instant modifiedAt;
    public abstract long size();
    public String path() { /* walk parents */ }
}

class File extends Entry {
    private byte[] content = new byte[0];
    public long size() { return content.length; }
    public byte[] read() { ... }
    public void write(byte[] data) { ... }
    public void append(byte[] data) { ... }
}

class Directory extends Entry {
    private final TreeMap<String, Entry> children = new TreeMap<>();
    public long size() { /* sum of children, computed on demand */ }
    public Entry child(String name) { ... }
    public void add(Entry e) { /* throws AlreadyExists */ }
    public Entry remove(String name) { ... }
    public List<String> list() { return new ArrayList<>(children.keySet()); }
}

class PathResolver {
    public List<String> parse(String path) { /* handles ., .., and repeated slashes */ }
    public Entry resolve(Directory root, List<String> parts) { /* throws NotFound, NotADirectory */ }
}

class FileSystemException extends RuntimeException { ... }
class NotFound extends FileSystemException { ... }
class AlreadyExists extends FileSystemException { ... }
class NotADirectory extends FileSystemException { ... }
class DirectoryNotEmpty extends FileSystemException { ... }

class FileSystem {
    private final Directory root;
    private final PathResolver resolver;
    public void mkdir(String path, boolean createParents) { ... }
    public List<String> ls(String path) { ... }
    public void createFile(String path) { ... }
    public byte[] read(String path) { ... }
    public void write(String path, byte[] data) { ... }
    public void move(String from, String to) { /* reject moving a directory into itself */ }
    public void delete(String path, boolean recursive) { ... }
}

Key Decisions to Defend

  • Composite pattern: File and Directory share Entry, so ls, size, and delete recurse without type checks at every level.
  • Children live in a TreeMap keyed by name, which gives sorted ls for free and O(log n) lookup.
  • Path parsing lives in PathResolver; FileSystem methods never split strings themselves.
  • Move unlinks the Entry from its old parent and links it under the new one, O(depth) regardless of subtree size.
  • Directory size is computed on demand; caching it means updating every ancestor on each write, worth it only if size is a hot query.

Likely follow-ups

  • · Add symbolic links, how do you detect a cycle during resolution?
  • · Support find by name pattern across the whole tree.
  • · Add per-entry permissions with owner, group, and other bits.
  • · Make it thread safe, one lock or a lock per directory?

Dive Deeper

The in-memory file system is a direct test of the Composite pattern and clean path handling. Strong candidates give File and Directory a shared base, push path parsing into one place, and define precise errors for missing paths and name collisions. Move is a good tell: it should relink one node, and checking that the destination is not inside the source shows care for edge cases.

All OOD Prompts