Solution For Design In Memory File System
The problem statement for Design In Memory File System on LeetCode is as follows:
Design an in-memory file system to simulate the following functions:
ls: Given a path in string format. If it is a file path, return a list that only contains this file’s name. If it is a directory path, return the list of file and directory names under this directory in lexicographic order. The directory path is given in the Unix file format.
mkdir: Given a directory path that does not exist, you should create a new directory according to the path. If the middle directories in the path don’t exist either, you should create them as well. This function has void return type.
addContentToFile: Given a file path and file content in string format. If the file doesn’t exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function also has void return type.
readContentFromFile: Given a file path, return its content in string format.
Before we dive into the solution, we should first discuss the data structure that we will be using to store our file system.
We will be using a Trie data structure to represent our file system. Each Trie node will represent a directory or a file. If a node represents a directory, it will have a map of child nodes, where the keys are the child node names and the values are the child nodes themselves. If a node represents a file, it will have a content string that holds the file’s content. We will also have a boolean flag in each node to indicate if the node represents a file or a directory.
With the data structure in mind, we can start implementing the four functions in our class.
“`
class FileSystem {
public:
struct TrieNode {
map
bool is_file;
string content;
TrieNode(bool flag=false) {
is_file = flag;
}
};
FileSystem() {
root = new TrieNode();
}
vector<string> ls(string path) {
TrieNode* curr = traverse(path);
if (curr->is_file) {
return {split(path).back()};
}
vector<string> res;
for (auto& p : curr->children) {
res.push_back(p.first);
}
sort(res.begin(), res.end());
return res;
}
void mkdir(string path) {
traverse(path);
}
void addContentToFile(string filePath, string content) {
TrieNode* curr = traverse(filePath);
curr->is_file = true;
curr->content += content;
}
string readContentFromFile(string filePath) {
return traverse(filePath)->content;
}
private:
TrieNode* root;
vector<string> split(string path) {
vector<string> res;
string temp = "";
for (int i = 1; i < path.size(); i++) {
if (path[i] == '/') {
res.push_back(temp);
temp = "";
}
else {
temp += path[i];
}
}
res.push_back(temp);
return res;
}
TrieNode* traverse(string path) {
TrieNode* curr = root;
vector<string> paths = split(path);
for (auto& p : paths) {
if (curr->children.find(p) == curr->children.end()) {
curr->children[p] = new TrieNode();
}
curr = curr->children[p];
}
return curr;
}
};
“`
Let’s go through the four functions one by one.
The ls function takes in a path and returns a vector of file and directory names under this directory if the path is a directory path, and a vector with only the name of the file if the path is a file. We first traverse the Trie to get the node that represents the file or directory at this path. If the node is a file, we return a vector with only this file name. If the node is a directory, we iterate through its child nodes and add their names to a vector. We then sort this vector and return it.
The mkdir function takes in a path and creates a directory according to this path. We first traverse the Trie to get the node that represents the deepest directory that exists in this path. Then we iterate through the rest of the path and create new nodes for each directory that doesn’t exist yet.
The addContentToFile function takes in a file path and content, and either creates a new file with this content or appends the content to an existing file. We first traverse the Trie to get the node that represents this file. If this node doesn’t exist yet, we create it and set its content to the given content. If it does exist, we append the given content to its original content.
The readContentFromFile function takes in a file path and returns the content of this file. We simply traverse the Trie to get the node that represents this file and return its content.
The time complexity of all four functions depends on the length of the input path. The worst case time complexity is O(n) where n is the length of the input path. The space complexity of the class is also O(n) where n is the total number of nodes in the Trie.
Step by Step Implementation For Design In Memory File System
Design a class to represent a file system in memory. The class should provide the following methods:
createFile(path, data): Creates a file with the given path and data. If a file with the same path already exists, the method should overwrite the existing file.
getData(path): Returns the data associated with the file at the given path. If the file does not exist, the method should return null.
getChildren(path): Returns the list of files and directories in the directory at the given path. The method should return null if the directory does not exist.
class FileSystem {
public void createFile(String path, String data) {
// TODO: Implement this method
}
public String getData(String path) {
// TODO: Implement this method
}
public List getChildren(String path) {
// TODO: Implement this method
}
} class FileSystem:
def __init__(self):
self.root = {"dirs": {}, "files": {}}
def createPath(self, path: str, value: str) -> bool:
# Base case: If the path is just the root directory, return False.
if path == "/":
return False
# Split the path into a list of directory names.
dirs = path.split("/")[1:]
# Set the current node to the root.
node = self.root
# Iterate through the directory names.
for i, dir in enumerate(dirs):
# If the current directory name is not in the current node's directory list, return False.
if dir not in node["dirs"]:
return False
# If we are at the last directory name, check if the file name is in the current node's file list.
# If it is, return False. Otherwise, add the file name to the list and return True.
if i == len(dirs) - 1:
if dirs[-1] in node["files"]:
return False
else:
node["files"][dirs[-1]] = value
return True
# If we are not at the last directory name, set the current node to the node corresponding to the current directory name
# and continue iterating.
else:
node = node["dirs"][dir]var FileSystem = function() {
// key is the path, value is the file content
this.files = {};
// key is the path, value is the set of file names in that directory
this.directories = {};
};
/**
* @param {string} path
* @param {string} content
* @return {void}
*/
FileSystem.prototype.create = function(path, content) {
// get the directory path
const dir = path.substring(0, path.lastIndexOf('/'));
// get the file name
const file = path.substring(path.lastIndexOf('/') + 1);
// if the directory doesn't exist, create it
if (!this.directories[dir]) {
this.directories[dir] = new Set();
}
// if the file doesn't exist, create it
if (!this.files[path]) {
// add the file to the directory
this.directories[dir].add(file);
}
// set the file content
this.files[path] = content;
};
/**
* @param {string} path
* @return {string}
*/
FileSystem.prototype.readContentFromFile = function(path) {
// if the file exists, return its content
// otherwise, return an empty string
return this.files[path] || '';
};
/**
* @param {string} path
* @return {string[]}
*/
FileSystem.prototype.ls = function(path) {
// if the path is a file, return an array with the file name
if (this.files[path]) {
return [path.substring(path.lastIndexOf('/') + 1)];
}
// if the path is a directory, return an array with the sorted file names in the directory
if (this.directories[path]) {
return Array.from(this.directories[path]).sort();
}
// if the path doesn't exist, return an empty array
return [];
};class FileSystem {
public:
FileSystem() {
root = new Dir();
}
bool createPath(string path, int value) {
if (path.empty()) return false;
if (path[0] != '/') return false;
Dir* cur = root;
stringstream ss(path);
string dir;
while (getline(ss, dir, '/')) {
if (!cur->dirs.count(dir)) {
cur->dirs[dir] = new Dir();
}
cur = cur->dirs[dir];
}
if (cur->files.count(dir)) return false;
cur->files[dir] = value;
return true;
}
int get(string path) {
if (path.empty()) return -1;
if (path[0] != '/') return -1;
Dir* cur = root;
stringstream ss(path);
string dir;
while (getline(ss, dir, '/')) {
if (!cur->dirs.count(dir)) {
return -1;
}
cur = cur->dirs[dir];
}
if (!cur->files.count(dir)) return -1;
return cur->files[dir];
}
private:
struct Dir {
unordered_map dirs;
unordered_map files;
};
Dir* root;
}; using System;
using System.Collections.Generic;
public class FileSystem {
Dictionary fileToId;
Dictionary> idToChildrenIds;
Dictionary idToContent;
public FileSystem() {
fileToId = new Dictionary();
idToChildrenIds = new Dictionary>();
idToContent = new Dictionary();
}
public bool CreatePath(string path, string content) {
if (fileToId.ContainsKey(path)) {
return false;
}
int id = fileToId.Count;
fileToId.Add(path, id);
idToContent.Add(id, content);
int parentId = path.LastIndexOf('/') == -1 ? 0 : fileToId[path.Substring(0, path.LastIndexOf('/'))];
if (!idToChildrenIds.ContainsKey(parentId)) {
idToChildrenIds.Add(parentId, new List());
}
idToChildrenIds[parentId].Add(id);
return true;
}
public string GetContent(string path) {
if (!fileToId.ContainsKey(path)) {
return "";
}
return idToContent[fileToId[path]];
}
public IList GetFiles(string path) {
if (!fileToId.ContainsKey(path)) {
return new List();
}
List files = new List();
int id = fileToId[path];
Queue queue = new Queue();
queue.Enqueue(id);
while (queue.Count > 0) {
int currId = queue.Dequeue();
if (idToContent.ContainsKey(currId)) {
files.Add(path + "/" + idToContent[currId]);
}
if (idToChildrenIds.ContainsKey(currId)) {
foreach (int childId in idToChildrenIds[currId]) {
queue.Enqueue(childId);
}
}
}
return files;
}
}