Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Design an Advanced File System

Design an Advanced File System

Solve a hard-level problem for developing a file system using tries.

We'll cover the following...

Problem statement

Design a file system that allows the user to perform the following operations.

ls: Allows the users to list all the files and folders present in a directory path. The function should take in the directory path as input and return a list of all files and folder names present in this directory.

mkdir: Allows the users to create new directories. The function takes the directory name as the input and creates a new directory in the current directory.

pwd: Returns the path to the present working directory.

cd: Allows the users to enter a directory. The user cannot enter a file using this command.

touch: Allows the user to create a new file in the current directory. If a file with the same name already exists in the directory, it shows an error.

Example

Sample input

{"mkdir", "home"},
{"ls"},
{"cd", "/home"},
{"pwd"},
{"touch", "newFile.txt"},
{"touch", "newFile.txt"},
{"touch", "newFile.csv"},
{"ls"},
{"mkdir", "Ben"},
{"cd", "/Ben"},
{"mkdir", "Movies"},
{"mkdir", "College"},
{"ls"},
{"pwd"},
{"cd" , "/Movies"},
{"touch", "HarryPotter.mp4"},
{"pwd"},
{"ls"},
{"cd", "/~"},
{"cd", "/home/Ben/Movies"},
{"ls"},
{"pwd"},
{"cd", "/Narnia"}

Sample output

Created directory home
home
Changed to directory
/home
Created newFile.txt
newFile.txt already exists
Created newFile.csv
newFile.csv newFile.txt
Created directory Ben
Changed to directory
Created directory Movies
Created directory College
College Movies
/home/Ben
Changed to directory
Created HarryPotter.mp4
/home/Ben/Movies
HarryPotter.mp4
Changed back to root directory
Changed to directory
HarryPotter.mp4
/home/Ben/Movies
Folder name Narnia not found. Cannot change directory.

Try it yourself

Try to solve the problem yourself before reading the solution.

#include<iostream>

#include<vector>

#include<unordered_map>

#include<set>

using namespace std;





class FileSystem {   

public:

    FileSystem(){

       

    }



    vector<string> ls() {

        // your code goes here

        return {};

    }



    string mkdir(string dirName) {

        // your code goes here

        return "";

    }

    

    string cd(string path){

        // your code goes here

        return "";

    }

    

    string pwd(){

        // your code goes here

        return "";

    }

    

    string touch(string fileName){

        // your code goes here

        return "";

    }

};
Solve designing an advanced file system in C++

Intuition

This problem is an extension of and similar to the previous problem. We solve it in a similar fashion using tries.

Custom trie node and pointer to working directory

//Definition of a trie node
class TrieNode
{
    public:
       	// map which stores the pointers from 
       	// folder names to the children nodes
        unordered_map<string, TrieNode*> children;
       	// a flag to identify if a 
       	// node represents a file
        bool isFile;
    
       	// to store the aboslute path of the file or directory
        string absolutePath;
};
Definition of a trie node in C++

Our custom trie node for this problem will contain three parameters:

absolutePath: The string representing the complete or absolute path of the current file or directory. The absolute path means a complete location of the file relative to the root directory.

isFile: A flag determining if the current node represents a file or a dictionary.

children: A dictionary representing the outgoing connections to child files or directories.

Algorithm

We can implement the required functions using the following algorithm.

ls: Listing the files and directories

For listing the contents of a directory:

  1. Traverse down the trie up to the last folder of the directory path.

  2. Iterate through all the children of the current trie node. If the path is a file, return the file name, or list all the folders present under the current directory.

Let's try to understand this better with an example.

mkdir: Making a new directory

This command creates a new directory in the user's current location (directory). If the user's current working directory is /home/Ben/ and the user types the command mkdir Movies, a new directory will be created inside the path /home/Ben. The absolute path of the new directory will be /home/Ben/Movies.

We'll maintain a pointer to the current working directory. Therefore, to create a new directory in the current path, add a new child in the children's map of the current trie node. The key would be the name of the new directory being added, and the value is the pointer to the newly created trie node. An error is returned if a folder with the same name already exists in the location.

Let's try to understand ...

Access this course and 1400+ top-rated courses and projects.