Design In-Memory File System Solution in C++

Ah, the classic dilemma of managing files in a digital world! Imagine your life without a file system—like trying to find your favorite shirt in a messy closet where every item is thrown in without any order. You’d be digging through piles of clothes, cursing under your breath, and probably wearing mismatched socks. Well, welcome to the world of the Design In-Memory File System problem on LeetCode, where we get to create a virtual closet for our files, but without the risk of losing that favorite shirt!

In this problem, you are tasked with designing a file system that can handle directories and files in memory. You’ll be able to create directories, add content to files, read from files, and list the contents of directories. It’s like being the digital Marie Kondo of your own file system—except you don’t have to thank your files for sparking joy!

Code Solution

Before we dive into the nitty-gritty, here’s the code solution that will make your file management dreams come true:


struct TrieNode {
  map> children;  // lexicographical
  bool isFile = false;
  string content;
};

class FileSystem {
 public:
  vector ls(string path) {
    auto [node, lastDir] = createDirAndGetPair(path);
    if (node->isFile)
      return {lastDir};

    vector ans;

    for (const auto& [file, _] : node->children)
      ans.push_back(file);

    return ans;
  }

  void mkdir(string path) {
    createDirAndGetPair(path);
  }

  void addContentToFile(string filePath, string content) {
    shared_ptr node = createDirAndGetPair(filePath).first;
    node->isFile = true;
    node->content += content;
  }

  string readContentFromFile(string filePath) {
    shared_ptr node = createDirAndGetPair(filePath).first;
    return node->content;
  }

 private:
  shared_ptr root = make_shared();

  pair, string> createDirAndGetPair(const string& path) {
    const vector dirs = getDirs(path);
    shared_ptr node = root;

    for (const string& dir : dirs) {
      if (!node->children.contains(dir))
        node->children[dir] = make_shared();
      node = node->children[dir];
    }

    return {node, dirs.empty() ? "" : dirs.back()};
  }

  vector getDirs(const string& path) {
    vector dirs;
    istringstream iss(path);

    for (string dir; getline(iss, dir, '/');)
      if (!dir.empty())
        dirs.push_back(dir);

    return dirs;
  }
};

Approach Explanation

The code uses a Trie (prefix tree) structure to represent the file system. Each node in the Trie corresponds to a directory or a file. The ls, mkdir, addContentToFile, and readContentFromFile methods allow you to interact with this structure seamlessly.

Methods Overview

ls(path): Lists files in a directory. If the path points to a file, it returns just that file.
mkdir(path): Creates directories as needed, ensuring that the structure is built correctly.
addContentToFile(filePath, content): Adds content to a file, creating the file if it doesn’t exist.
readContentFromFile(filePath): Reads the content of a file.

Time and Space Complexity

Time Complexity

Each operation (like ls, mkdir, addContentToFile, and readContentFromFile) takes O(N) time, where N is the number of directories/files in the path. This is because we may need to traverse the entire path to reach the desired node.

Space Complexity

The space complexity is O(M), where M is the total number of files and directories stored in the Trie. Each node in the Trie represents a directory or file.

Real-World Example

Think of this file system as your personal digital library. You can create sections (directories) for different genres (like Fiction, Non-Fiction, Science Fiction), add books (files) to those sections, and even read the content of those books whenever you want. Just like how you would organize your physical books, this in-memory file system allows you to do the same digitally—without the risk of paper cuts!