Cracking The Coding Interview Together – Problem 7.11: In-Memory File System

Have you ever wondered how operating systems represent hierarchical file systems in RAM, or how tools like Docker construct virtual layered file systems in memory during build steps? At first glance, a file system seems straightforward: files sit inside folders, and folders sit inside other folders. But when we transition from user-facing software to system architecture, handling nested paths, prefix lookups, file modifications, and directory traversals efficiently requires careful structural design.

Whether you are building a mock virtual file system for integration testing, designing an edge caching engine, or sitting across from an interviewer at a tech giant, designing an in-memory file system is a classic test of your object-oriented design and data structure skills. In this post, we will walk through constructing a clean, scalable in-memory file system in Java from the ground up.

Problem Statement

In Cracking the Coding Interview (Problem 7.11), we are asked to explain and implement the data structures and algorithms needed to design an in-memory file system.

Specifically, our file system must support the following core API operations:

• ls(String path): If the path points to a file, return a list containing only that file's name. If it points to a directory, return the list of file and directory names located directly inside that directory, ordered lexicographically.
• mkdir(String path): Create a new directory given a path string. If intermediate directories in the path do not exist, create them as well (similar to mkdir -p in Unix).
• addContentToFile(String filePath, String content): If the file does not exist, create it with the specified content. If the file already exists, append the new content to the existing content.
• readContentFromFile(String filePath): Return the content of the file specified by the path string.

Analyze the Problem Together

When we break this problem down together, the core challenge centers on path navigation and entity representation. Path strings like /a/b/c/file.txt represent a hierarchical tree structure. Each slash (/) acts as a delimiter separating parent and child nodes.

Let's evaluate two common approaches to structuring this data in memory:

The N-ary Tree (or Trie) structure is clearly superior. Each directory acts as an interior node holding a hash map of its immediate children, while each file acts as a leaf node containing a string buffer.

To keep our design robust and object-oriented, we can apply composite design principles: both File and Directory share common attributes (like name and timestamps) through a common base class Entry. This allows directories to store collections of generic Entry references without worrying about whether a child is a sub-folder or a file.

Questions for the Interviewer

In a real senior engineering interview, skipping clarifying questions is a red flag. Here are 3-4 critical questions we should ask before typing a single line of code:

• Path Formatting Constraints: Can we assume all input paths are absolute paths starting with /, or do we need to support relative paths like ./ and ../? (Assumed answer: Absolute paths starting with /.)
• Implicit Directory Creation: Should addContentToFile automatically create missing parent directories if they don't exist yet? (Assumed answer: Yes, standard system behavior.)
• Concurrency Requirements: Does our file system need to handle concurrent read and write operations from multiple threads? (Assumed answer: Implement single-threaded logic first, but discuss thread-safety design patterns.)
• Memory Limits & File Sizes: Are file contents small enough to fit into memory as contiguous strings, or should we support chunked byte blocks? (Assumed answer: In-memory strings are sufficient for this implementation.)

Think About the Solution

Let's map out our object architecture before writing the implementation:

• Entry (Abstract Class): Represents an abstract node in the file system tree. Holds common metadata such as node name, creation timestamp, and last modified timestamp.
• File (Extends Entry): Holds content as a StringBuilder to allow efficient string appends.
• Directory (Extends Entry): Holds a Map<String, Entry> children mapping child names to child nodes.
• FileSystem (Main Engine): Holds a reference to the root directory node and provides public API methods for system operations.

Path Navigation Helper: Notice that mkdir, ls, addContentToFile, and readContentFromFile all require traversing down the tree using a path string. Instead of duplicating traversal logic across all four methods, we can write a private helper method—navigateTo(String path, boolean createIfMissing)—that parses the path components and navigates step-by-step from the root directory.

Write Code and Explain

Here is our complete, production-ready Java implementation:

import java.util.*;

public class FileSystem {

    // Abstract base class representing a generic node in the file system
    private abstract static class Entry {
        protected String name;
        protected long createdTime;
        protected long lastModifiedTime;

        public Entry(String name) {
            this.name = name;
            this.createdTime = System.currentTimeMillis();
            this.lastModifiedTime = System.currentTimeMillis();
        }

        public String getName() {
            return name;
        }

        public abstract boolean isDirectory();
    }

    // Represents a leaf node holding textual content
    private static class File extends Entry {
        private final StringBuilder content = new StringBuilder();

        public File(String name) {
            super(name);
        }

        @Override
        public boolean isDirectory() {
            return false;
        }

        public void appendContent(String newContent) {
            content.append(newContent);
            this.lastModifiedTime = System.currentTimeMillis();
        }

        public String getContent() {
            return content.toString();
        }
    }

    // Represents an interior node holding child entries
    private static class Directory extends Entry {
        private final Map<String, Entry> children = new HashMap<>();

        public Directory(String name) {
            super(name);
        }

        @Override
        public boolean isDirectory() {
            return true;
        }

        public Map<String, Entry> getChildren() {
            return children;
        }
    }

    private final Directory root;

    public FileSystem() {
        this.root = new Directory("");
    }

    /**
     * Lists contents of a directory sorted lexicographically, or the file name if path is a file.
     */
    public List<String> ls(String path) {
        Entry entry = navigateTo(path, false);
        if (entry == null) {
            return Collections.emptyList();
        }

        List<String> result = new ArrayList<>();
        if (!entry.isDirectory()) {
            result.add(entry.getName());
            return result;
        }

        Directory dir = (Directory) entry;
        result.addAll(dir.getChildren().keySet());
        Collections.sort(result);
        return result;
    }

    /**
     * Creates directory path including missing parent directories.
     */
    public void mkdir(String path) {
        navigateTo(path, true);
    }

    /**
     * Appends content to a file at specified path, creating missing directories/files if needed.
     */
    public void addContentToFile(String filePath, String content) {
        int lastSlash = filePath.lastIndexOf('/');
        String dirPath = (lastSlash == 0) ? "/" : filePath.substring(0, lastSlash);
        String fileName = filePath.substring(lastSlash + 1);

        Directory parent = (Directory) navigateTo(dirPath, true);
        if (parent == null) {
            throw new IllegalArgumentException("Invalid directory path in: " + filePath);
        }

        Entry existingEntry = parent.getChildren().get(fileName);
        if (existingEntry == null) {
            File newFile = new File(fileName);
            newFile.appendContent(content);
            parent.getChildren().put(fileName, newFile);
        } else if (!existingEntry.isDirectory()) {
            ((File) existingEntry).appendContent(content);
        } else {
            throw new IllegalArgumentException("Path points to a directory, not a file: " + filePath);
        }
    }

    /**
     * Reads and returns content from file at specified path.
     */
    public String readContentFromFile(String filePath) {
        Entry entry = navigateTo(filePath, false);
        if (entry == null || entry.isDirectory()) {
            throw new IllegalArgumentException("Invalid file path: " + filePath);
        }
        return ((File) entry).getContent();
    }

    /**
     * Helper method to traverse tree based on slash-separated path string.
     */
    private Entry navigateTo(String path, boolean createIfMissing) {
        if (path == null || path.isEmpty() || path.equals("/")) {
            return root;
        }

        String[] parts = path.split("/");
        Entry current = root;

        for (String part : parts) {
            if (part.isEmpty()) {
                continue; // Skip initial empty element from leading slash
            }

            if (!current.isDirectory()) {
                return null; // Cannot traverse deeper into a file node
            }

            Directory currentDir = (Directory) current;
            if (!currentDir.getChildren().containsKey(part)) {
                if (createIfMissing) {
                    Directory newDir = new Directory(part);
                    currentDir.getChildren().put(part, newDir);
                } else {
                    return null;
                }
            }
            current = currentDir.getChildren().get(part);
        }
        return current;
    }
}

Step-by-Step Code Walkthrough

1. Inheritance Hierarchy: We define Entry as our abstract component class with concrete extensions File and Directory. This prevents us from storing file-specific properties in directory nodes or vice versa.
2. Path Splitting in navigateTo: When splitting /a/b/c by /, Java returns an array ["", "a", "b", "c"]. We filter out empty string parts using if (part.isEmpty()) continue;.
3. Auto-Creation Flag: The createIfMissing boolean allows single-pass creation during mkdir and addContentToFile operations without repeating loop logic.
4. Appending Content efficiently: By storing file content in a StringBuilder, appends run in amortized O(C) time where $C$ is the length of appended content, rather than reallocating large strings.

Time & Space Complexity

Let's analyze performance metrics for each API call. Assume $K$ represents the path depth (number of directory levels in path string), $L$ represents path string length, $N$ represents the number of entries in target directory, and $M$ represents content length.

• mkdir(path):
  • Time Complexity: $O(L + K)$ – $O(L)$ to split path components plus $O(K)$ HashMap lookups/insertions.
  • Space Complexity: $O(K)$ memory allocated for new directory nodes created along missing levels.
• ls(path):
  • Time Complexity: $O(L + K + N \log N)$ – Path navigation takes $O(L + K)$. Extracting and sorting $N$ directory keys takes $O(N \log N)$.
  • Space Complexity: $O(N)$ space required to hold the sorted output list of item names.
• addContentToFile(filePath, content):
  • Time Complexity: $O(L + K + M)$ – $O(L + K)$ for path navigation, $O(M)$ to append content to the StringBuilder.
  • Space Complexity: $O(M)$ memory added for new character content stored.
• readContentFromFile(filePath):
  • Time Complexity: $O(L + K + M)$ – $O(L + K)$ for path navigation, $O(M)$ to extract and return string copy.
  • Space Complexity: $O(M)$ for the returned string allocation.

Why This Problem Matters (The Senior Perspective)

While this interview question focuses on fundamental data structures, real-world file system architecture mirrors these exact concepts at scale:

1. Real Kernels vs. Virtual Trees: In Linux Virtual File Systems (VFS), directory structures use dentry (directory entry) objects cached in RAM that map directly to underlying inode structures on disk. Our Directory children map behaves almost identically to the Linux dentry cache.

2. Thread Safety and Granular Locking: In production systems, global synchronization on the root node would create severe bottleneck bottlenecks under high write throughput. To scale concurrent access, senior engineers introduce granular lock stripping:

• Use ReentrantReadWriteLock inside each Entry instance.
• Multiple readers can traverse non-overlapping paths concurrently.
• Writers only lock the specific parent directory node being modified during file addition or directory creation.

3. Chunked Memory Storage vs. Contiguous Arrays: Storing long file strings in contiguous heap arrays leads to high memory fragmentation and Garbage Collection pressure. Real-world in-memory engines chunk file contents into fixed-size blocks (e.g., 4KB byte arrays) linked via index tables, preventing allocation failures when managing gigabytes of virtual file data.

Final Thoughts

We've successfully constructed a flexible, object-oriented, in-memory file system using clean inheritance and path traversal techniques. By isolating path parsing into reusable helper methods and keeping our node abstractions separate, our system is easy to test and extend.

Want to push this design further? Try extending this code to support hard/soft symbolic links, or implement an rm(String path) method that handles recursive directory deletion (rm -rf)!

What architectural tweaks would you add to make this thread-safe under heavy load? Drop your thoughts in the comments below, and happy coding!