Design a Basic File System

Explore how to design a basic file system that supports creating files, fetching their data, and appending content using a trie-based approach. Understand the limitations of hashmap solutions and discover the advantages of trie data structures for managing file paths efficiently. This lesson provides you with algorithms and complexity analysis to implement these features effectively.

We'll cover the following...

Problem statement
- Example 1
- Example 2
Try it yourself
Complexity analysis

Problem statement

Design a file system that allows you to create new text files and add content to them.

The paths in this file system are a set of strings concatenated by slashes ("/").

For example, “home” and “/home/ben” are valid paths, while an empty string and “/” are not.

Currently, this file system supports the following operations.

createFile: This allows the users to create a file and add data to it. The function should take in the file path and the content as input, create a new file at the given path, and add text content to it. It should return false if the path file already exists or its parent path doesn’t exist.

getFileData: This allows the users to fetch the data stored in a file. It returns the data stored in the file if the file exists and returns -1 if the path doesn’t exist.

appendContentToFile: This allows the user to add content to a file. The function should take in the file path and the string content as input. If the file already exists, it appends the given content to the original content.

Example 1

Sample input

Q1: ["createFile", "/home", "home directory"]
Q2: ["createFile", "/home/ben", "Ben’s home directory"]
Q3: ["createFile", "/home/ben/movies", "Ben’s favorite movies"]
Q4: ["createFile", "/home/ben/college", "Ben’s college books"]
Q5: ["createFile", "/home/ben/dance/videos", "Ben’s dance video"]
Q6: ["getFileData", "/home/ben/dance/videos"]
Q7: ["getFileData", "/home/ben/"]
Q8: ["getFileData", "/home/ben/movies"]
Q9: ["appendContentToFile", "/home/ben/movies", " includes Harry Potter"]
Q10: ["getFileData", "/home/ben/movies"]

Explanation

Q1: ["createFile", "/home", "home directory"] => creates a file home and adds data home directory to it.
Q2: ["createFile", "/home/ben", "Ben’s home directory"] => creates a file ben under home directory and adds data Ben’s home directory to it.
Q3: ["createFile", "/home/ben/movies", "Ben’s favorite movies"] => creates a file movies under /home/ben directory and adds data Ben’s favorite movies to it.
Q4: ["createFile", "/home/ben/college", "Ben’s college books"] => creates a file college under /home/ben directory and adds data Ben’s college books to it.
Q5: ["createFile", "/home/ben/dance/videos", "Ben’s dance video"] => returns false as the parent path /home/ben/dance does not exist.
Q6: ["getFileData", "/home/ben/dance/videos"] => returns -1 as the file not present.
Q7: ["getFileData", "/home/ben/"] => returns the file contents (Ben’s home directory).
Q8: ["getFileData", "/home/ben/movies"] => returns the file contents (Ben’s favorite movies).
Q9: ["appendContentToFile", "/home/ben/movies", "includes Harry Potter"] => Adds to the content of the file and returns true. The final content becomes Ben’s favorite movies includes Harry Potter.
Q10: ["getFileData", "/home/ben/movies"] => returns the file contents (Ben’s favorite movies includes Harry Potter).

Try it yourself

Try to solve the problem yourself before reading the solution.

C++

Java

#include<iostream>
#include<vector>
using namespace std;

class FileSystem {
  public:
      FileSystem() {
      }

      bool createFile(string path, string data) {
         // your code goes here
         return false;
      }

      bool appendContentToFile(string path, string newData) {
         // your code goes here
          return false;
      }

      string getFileData(string path) {
        // your code goes here
        return "";
      }
};

Solve designing a basic file system in C++

1.Introduction to Tries

2.Prefix Search

3.Suffix Search

4.Bitwise Tries

5.Pattern Matching

6.File Systems

7.Trie Traversal

8.Search Engine

9.Miscellaneous

10.Conclusion

Design a Basic File System

Problem statement

Example 1

Example 2

Try it yourself

Intuition