Skip to content

In-Memory Filesystem#

Problem statement (interviewer prompt)

Design an in-memory filesystem that supports mkdir, addContent, readContent, ls, rm, and mv. Paths are POSIX-like. Concurrency-safe; extensible to add file metadata (size, mtime, permissions).

classDiagram
  class FileSystem {
    -root : Dir
    +mkdir(path)
    +addContent(path, content)
    +readContent(path) string
    +ls(path) List~string~
    +rm(path)
    +mv(src, dst)
    -resolve(path) Node
  }
  class Node {
    <<abstract>>
    +name : string
    +parent : Dir
    +createdAt : Instant
  }
  class Dir {
    -children : Map~string, Node~
  }
  class File {
    -content : string
    -size : int
  }
  Node <|-- Dir
  Node <|-- File
  Dir *-- "many" Node
  FileSystem --> Dir : root

Tree of Nodes; path resolution walks segments. Most operations are O(depth × children-per-dir).

A common interview problem; tests recursion, path handling, and OO modelling all at once.

Class diagram#

classDiagram
  class FileSystem {
    -root : Dir
    +mkdir(path, parents=false)
    +addContent(path, content)
    +readContent(path) string
    +ls(path) List~string~
    +rm(path, recursive=false)
    +mv(src, dst)
    +stat(path) Stat
    -resolve(path, create=false) Node
    -split(path) List~string~
  }
  class Node {
    <<abstract>>
    +name : string
    +parent : Dir
    +createdAt : Instant
    +modifiedAt : Instant
  }
  class Dir {
    -children : Map~string, Node~
    +get(name) Node
    +put(name, node)
    +remove(name)
  }
  class File {
    -content : StringBuilder
    +append(s)
    +size() int
  }
  class Stat {
    +size, type, mtime, ctime
  }
  Node <|-- Dir
  Node <|-- File
  Dir *-- "many" Node
  FileSystem --> Dir : root
  FileSystem ..> Stat : returns

Path resolution#

def resolve(self, path, create=False):
    parts = [p for p in path.split("/") if p]
    cur = self.root
    for p in parts:
        if not isinstance(cur, Dir):
            raise NotADirectoryError(path)
        if p not in cur.children:
            if create:
                cur.children[p] = Dir(name=p, parent=cur)
            else:
                raise FileNotFoundError(path)
        cur = cur.children[p]
    return cur

Operations#

mkdir#

def mkdir(self, path, parents=False):
    parts = self.split(path)
    cur = self.root
    for i, p in enumerate(parts):
        if p not in cur.children:
            if i < len(parts) - 1 and not parents:
                raise FileNotFoundError(...)
            cur.children[p] = Dir(name=p, parent=cur)
        cur = cur.children[p]
        if isinstance(cur, File):
            raise NotADirectoryError(...)

rm recursive#

def rm(self, path, recursive=False):
    node = self.resolve(path)
    if isinstance(node, Dir) and node.children and not recursive:
        raise DirNotEmpty(...)
    node.parent.children.pop(node.name)

mv with cycle detection#

def mv(self, src, dst):
    s = self.resolve(src)
    # cannot move into descendant
    cur = self.resolve_parent(dst)
    while cur:
        if cur is s: raise ValueError("cycle")
        cur = cur.parent
    s.parent.children.pop(s.name)
    new_parent = self.resolve_parent(dst)
    s.name = self.basename(dst)
    s.parent = new_parent
    new_parent.children[s.name] = s

Thread safety#

Strategy Notes
Single global lock Simplest; serialises all operations
Per-directory ReadWriteLock Concurrent reads; writers exclusive
Lock ordering mv across subtrees must lock both in canonical order
Copy-on-write Immutable snapshots; expensive for big trees

Extensions#

  • Permissions / users: extend Node with owner, mode bits; check on open.
  • Symlinks: a Symlink node with target path; cycle detection on resolve.
  • Soft-delete + trash: rm moves to /.trash/; periodic GC.
  • Snapshots: copy-on-write Dir; mount as new root.
  • Streaming reads: replace StringBuilder with ByteBuffer chunks.

Common bugs#

  • Trailing slash handling (/a/ vs /a).
  • .. segments not resolved (/a/../b should equal /b).
  • Allowing rm on root.
  • Move into self or descendant (infinite tree).
  • Race between two concurrent mkdirs at same path.

Where in-memory FS fits#

flowchart TB
  FS((In-memory<br/>FS))
  OOP[OOP pillars<br/>Dir / File inheritance]
  DSC[Data structures complexity<br/>tree analysis]
  CON[Concurrency primitives<br/>locking strategy]
  DFS[Distributed file system<br/>scaled sibling]
  OOP --> FS
  DSC --> FS
  CON --> FS
  FS -. scaled .-> DFS

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class FS service;
    class OOP,DSC,CON,DFS datastore;

Glossary & fundamentals#

Tag Concept What it is Page
LLD OOP pillars inheritance Dir/File oop-pillars
LLD Data structures complexity tree traversal analysis data-structures-complexity
LLD Concurrency primitives locking strategy concurrency-primitives
HLD Distributed File System the scaled-up sibling distributed-file-system

Quick reference#

Classes#

  • FileSystem (root + ops)
  • Node (abstract: name, parent)
  • Dir (children map)
  • File (content)
  • Stat (metadata)

API#

mkdir, addContent, readContent, ls, rm, mv, stat.

Path resolution#

Split on /, walk children. Empty segments skipped. Handle . and ...

Tricky bits#

  • Trailing slash
  • .. resolution
  • mv into descendant → cycle
  • Concurrent mkdir same path
  • Removing root

Concurrency#

Lock Use
Global Simplest
Per-Dir RWLock Concurrent reads
mv Lock both sides in canonical order

Extensions#

  • Permissions / users
  • Symlinks (with cycle check)
  • Soft-delete to /trash
  • Snapshots (COW)
  • Streaming reads

Refs#

  • LeetCode #588
  • POSIX fs man pages

FAQ#

How is an in-memory filesystem structured?#

As a tree where each Dir has a map from name to child Node, and each File holds bytes. Path resolution walks the tree segment by segment starting at the root.

Which design pattern fits files and directories?#

The Composite pattern: Dir and File share a common Node interface so operations like size or delete recurse uniformly across the tree.

How do you implement ls efficiently?#

Walk to the target node by path, then return the sorted keys of its children map. Sorting at read time avoids maintaining a sorted structure on every insert.

How do you make an in-memory filesystem thread-safe?#

Per-directory locks let independent subtrees mutate in parallel; for atomic mv across directories, lock both targets in a stable order to avoid deadlock.

How is mv implemented?#

Resolve the source and destination parents, atomically remove the node from the source's children map, and insert it under the new name in the destination.

Further reading#

  • LeetCode #588 - Design In-Memory File System
  • POSIX filesystem semantics (man fs)