Design In-Memory File System
Design In-Memory File System is a hard tries problem solved with the basics pattern.
The best approach, optimal (trie of path components), runs in O(L + k) per call time and O(total names and content) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flat maps of full paths) up.
Problem
Build a class FileSystem that simulates a small in-memory file system made of directories and text files. FileSystem() starts with only the empty root directory "/".
ls(String path): ifpathis a file, return a list containing only that file’s name. If it is a directory, return the names of the files and directories directly inside it, in lexicographic order.mkdir(String path): create the directorypath, along with any missing directories on the way to it. Directories that already exist are left alone.addContentToFile(String filePath, String content): if the file does not exist, create it (and any missing directories above it) withcontent; otherwise appendcontentto the end of what it already holds.readContentFromFile(String filePath): return the full content of the file.
Examples
Example 1
- Input
FileSystem(), mkdir("/docs/notes"), addContentToFile("/docs/todo", "buy milk"), ls("/"), ls("/docs"), addContentToFile("/docs/todo", " and eggs"), readContentFromFile("/docs/todo")- Output
["docs"], ["notes", "todo"], "buy milk and eggs"- Why
- mkdir creates both docs and docs/notes; the second write appends to the existing file instead of replacing it.
Example 2
- Input
FileSystem(), addContentToFile("/a/b/report", "hi"), ls("/a/b/report"), mkdir("/a/apple"), ls("/a"), ls("/a/apple")- Output
["report"], ["apple", "b"], []- Why
- ls on a file lists just that file's name; ls on a directory lists its entries in lexicographic order, and an empty directory gives an empty list.
Constraints
1 <= path.length, filePath.length <= 100- Every path is absolute: it starts with
/, and has no trailing/unless it is the root"/"itself. - Directory and file names are non-empty and use lowercase English letters only.
- No name is used for both a file and a directory at the same location.
lsis only called on paths that exist, andreadContentFromFileonly on files that exist.1 <= content.length <= 50- At most
300calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flat maps of full paths) | O(N · L + k log k) per ls, O(L) per other call | O(N · L) |
| Optimal (trie of path components) | O(L + k) per call | O(total names and content) |
1Brute force (flat maps of full paths)
O(N · L + k log k) per ls, O(L) per other callls scans all N stored paths of length up to L, then sorts the k names it found.O(N · L)Every directory and file path is stored in full.Do not build a tree at all. Keep a set of every directory path and a map from each file path to its content. To list a directory, scan every stored path, keep the ones directly or indirectly below it, cut each down to its first name after the directory, and sort the distinct names.
- dirs = {"/"}, files = empty map.
- mkdir(path): add the path and every ancestor prefix to dirs.
- addContentToFile(fp, c): add the parent directory and its ancestors to dirs, then append c to files[fp] (starting from an empty string).
- readContentFromFile(fp): return files[fp].
- ls(path): if path is a file, return its last name. Otherwise, with prefix = path + "/" (or "/" for the root), collect the first name after the prefix from every stored path that starts with it, and return those names sorted.
class FileSystem {
private final Set<String> dirs = new HashSet<>();
private final Map<String, String> files = new HashMap<>();
public FileSystem() {
dirs.add("/");
}
private void makeDirs(String path) {
int i = path.indexOf('/', 1);
while (i != -1) {
dirs.add(path.substring(0, i));
i = path.indexOf('/', i + 1);
}
dirs.add(path);
}
private void collect(String p, String prefix, Set<String> names) {
if (p.length() > prefix.length() && p.startsWith(prefix)) {
String rest = p.substring(prefix.length());
int k = rest.indexOf('/');
names.add(k < 0 ? rest : rest.substring(0, k));
}
}
public List<String> ls(String path) {
List<String> res = new ArrayList<>();
if (files.containsKey(path)) {
res.add(path.substring(path.lastIndexOf('/') + 1));
return res;
}
String prefix = path.equals("/") ? "/" : path + "/";
TreeSet<String> names = new TreeSet<>();
for (String p : dirs) collect(p, prefix, names);
for (String p : files.keySet()) collect(p, prefix, names);
res.addAll(names);
return res;
}
public void mkdir(String path) {
makeDirs(path);
}
public void addContentToFile(String filePath, String content) {
int k = filePath.lastIndexOf('/');
if (k > 0) makeDirs(filePath.substring(0, k));
files.put(filePath, files.getOrDefault(filePath, "") + content);
}
public String readContentFromFile(String filePath) {
return files.get(filePath);
}
}class FileSystem:
def __init__(self):
self.dirs = {"/"}
self.files = {}
def _make_dirs(self, path: str) -> None:
i = path.find("/", 1)
while i != -1:
self.dirs.add(path[:i])
i = path.find("/", i + 1)
self.dirs.add(path)
def ls(self, path: str) -> List[str]:
if path in self.files:
return [path[path.rfind("/") + 1:]]
prefix = "/" if path == "/" else path + "/"
names = set()
for p in list(self.dirs) + list(self.files):
if len(p) > len(prefix) and p.startswith(prefix):
names.add(p[len(prefix):].split("/")[0])
return sorted(names)
def mkdir(self, path: str) -> None:
self._make_dirs(path)
def addContentToFile(self, filePath: str, content: str) -> None:
k = filePath.rfind("/")
if k > 0:
self._make_dirs(filePath[:k])
self.files[filePath] = self.files.get(filePath, "") + content
def readContentFromFile(self, filePath: str) -> str:
return self.files[filePath]class FileSystem {
unordered_set<string> dirs;
unordered_map<string, string> files;
void makeDirs(const string& path) {
size_t i = path.find('/', 1);
while (i != string::npos) {
dirs.insert(path.substr(0, i));
i = path.find('/', i + 1);
}
dirs.insert(path);
}
void collect(const string& p, const string& prefix, set<string>& names) {
if (p.size() > prefix.size() && p.compare(0, prefix.size(), prefix) == 0) {
string rest = p.substr(prefix.size());
size_t k = rest.find('/');
names.insert(k == string::npos ? rest : rest.substr(0, k));
}
}
public:
FileSystem() {
dirs.insert("/");
}
vector<string> ls(string path) {
if (files.count(path)) return {path.substr(path.rfind('/') + 1)};
string prefix = path == "/" ? "/" : path + "/";
set<string> names;
for (const string& p : dirs) collect(p, prefix, names);
for (const auto& f : files) collect(f.first, prefix, names);
return vector<string>(names.begin(), names.end());
}
void mkdir(string path) {
makeDirs(path);
}
void addContentToFile(string filePath, string content) {
size_t k = filePath.rfind('/');
if (k > 0) makeDirs(filePath.substr(0, k));
files[filePath] += content;
}
string readContentFromFile(string filePath) {
return files[filePath];
}
};class FileSystem {
constructor() {
this.dirs = new Set(["/"]);
this.files = new Map();
}
makeDirs(path) {
let i = path.indexOf("/", 1);
while (i !== -1) {
this.dirs.add(path.substring(0, i));
i = path.indexOf("/", i + 1);
}
this.dirs.add(path);
}
ls(path) {
if (this.files.has(path)) return [path.substring(path.lastIndexOf("/") + 1)];
const prefix = path === "/" ? "/" : path + "/";
const names = new Set();
for (const p of [...this.dirs, ...this.files.keys()]) {
if (p.length > prefix.length && p.startsWith(prefix)) {
names.add(p.substring(prefix.length).split("/")[0]);
}
}
return [...names].sort();
}
mkdir(path) {
this.makeDirs(path);
}
addContentToFile(filePath, content) {
const k = filePath.lastIndexOf("/");
if (k > 0) this.makeDirs(filePath.substring(0, k));
this.files.set(filePath, (this.files.get(filePath) ?? "") + content);
}
readContentFromFile(filePath) {
return this.files.get(filePath);
}
}2Optimal (trie of path components)
O(L + k) per callA call walks the L characters of its path (each step a sorted-map lookup on a short name) and ls copies out the k child names.O(total names and content)Each directory or file name is stored once in the tree, shared by every path that goes through it.Model the file system as a tree: each node is a directory or a file and maps child names to child nodes, kept in a sorted map. Walking a path means following one child per name, creating missing nodes as you go, which handles mkdir -p style creation for free. A file node also has a content buffer. ls on a directory is just the sorted keys of its child map.
- Node = { sorted map name -> Node, isFile flag, content buffer }; root is an empty directory.
- walk(path): split on
/, skip empty pieces, and for each name step into that child, creating it if missing. - mkdir(path): walk(path).
- addContentToFile(fp, c): node = walk(fp); mark it as a file and append c.
- readContentFromFile(fp): return walk(fp)'s content.
- ls(path): node = walk(path); if it is a file, return [its last name]; otherwise return its child names in order.
class FileSystem {
private static class Node {
TreeMap<String, Node> children = new TreeMap<>();
boolean isFile;
StringBuilder content = new StringBuilder();
}
private final Node root = new Node();
public FileSystem() {}
private Node walk(String path) {
Node cur = root;
for (String part : path.split("/")) {
if (part.isEmpty()) continue;
cur = cur.children.computeIfAbsent(part, k -> new Node());
}
return cur;
}
public List<String> ls(String path) {
Node node = walk(path);
List<String> res = new ArrayList<>();
if (node.isFile) {
res.add(path.substring(path.lastIndexOf('/') + 1));
} else {
res.addAll(node.children.keySet());
}
return res;
}
public void mkdir(String path) {
walk(path);
}
public void addContentToFile(String filePath, String content) {
Node node = walk(filePath);
node.isFile = true;
node.content.append(content);
}
public String readContentFromFile(String filePath) {
return walk(filePath).content.toString();
}
}class Node:
def __init__(self):
self.children = {}
self.is_file = False
self.content = []
class FileSystem:
def __init__(self):
self.root = Node()
def _walk(self, path: str) -> Node:
cur = self.root
for part in path.split("/"):
if part:
if part not in cur.children:
cur.children[part] = Node()
cur = cur.children[part]
return cur
def ls(self, path: str) -> List[str]:
node = self._walk(path)
if node.is_file:
return [path[path.rfind("/") + 1:]]
return sorted(node.children)
def mkdir(self, path: str) -> None:
self._walk(path)
def addContentToFile(self, filePath: str, content: str) -> None:
node = self._walk(filePath)
node.is_file = True
node.content.append(content)
def readContentFromFile(self, filePath: str) -> str:
return "".join(self._walk(filePath).content)class FileSystem {
struct Node {
map<string, Node*> children;
bool isFile = false;
string content;
};
Node* root = new Node();
Node* walk(const string& path) {
Node* cur = root;
stringstream ss(path);
string part;
while (getline(ss, part, '/')) {
if (part.empty()) continue;
Node*& child = cur->children[part];
if (child == nullptr) child = new Node();
cur = child;
}
return cur;
}
public:
FileSystem() {}
vector<string> ls(string path) {
Node* node = walk(path);
if (node->isFile) return {path.substr(path.rfind('/') + 1)};
vector<string> res;
for (const auto& kv : node->children) res.push_back(kv.first);
return res;
}
void mkdir(string path) {
walk(path);
}
void addContentToFile(string filePath, string content) {
Node* node = walk(filePath);
node->isFile = true;
node->content += content;
}
string readContentFromFile(string filePath) {
return walk(filePath)->content;
}
};class FileSystem {
constructor() {
this.root = { children: new Map(), isFile: false, content: "" };
}
walk(path) {
let cur = this.root;
for (const part of path.split("/")) {
if (part === "") continue;
if (!cur.children.has(part)) {
cur.children.set(part, { children: new Map(), isFile: false, content: "" });
}
cur = cur.children.get(part);
}
return cur;
}
ls(path) {
const node = this.walk(path);
if (node.isFile) return [path.substring(path.lastIndexOf("/") + 1)];
return [...node.children.keys()].sort();
}
mkdir(path) {
this.walk(path);
}
addContentToFile(filePath, content) {
const node = this.walk(filePath);
node.isFile = true;
node.content += content;
}
readContentFromFile(filePath) {
return this.walk(filePath).content;
}
}Edge cases to test
ls("/")on a brand new file system returns an empty listlson a file returns a one-element list with the file's own namemkdiron a deep path creates every missing directory along the way, and is harmless if they already exist- Writing to a new file inside missing directories creates those directories too
- Several writes to the same file append, in order
Hints
Hint 1
A path is a sequence of names. Split it on / and ignore the empty pieces.
Hint 2
A tree whose nodes are directories or files, with each node mapping child names to child nodes, mirrors the file system directly. That is a trie over path components.
Hint 3
If each node keeps its children in a sorted map, ls on a directory is simply the list of its keys. A node also needs a flag saying it is a file and a buffer for the content.
FAQ
What is the best time complexity for Design In-Memory File System?
Optimal (trie of path components) runs in O(L + k) per call time and O(total names and content) extra space. A call walks the L characters of its path (each step a sorted-map lookup on a short name) and ls copies out the k child names.
Which pattern does Design In-Memory File System use?
It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design Search Autocomplete System.
Is there a brute force solution for Design In-Memory File System?
Yes. Brute force (flat maps of full paths) takes O(N · L + k log k) per ls, O(L) per other call time and O(N · L) space. Do not build a tree at all.
Which edge cases should I test for Design In-Memory File System?
ls("/") on a brand new file system returns an empty list; ls on a file returns a one-element list with the file's own name; mkdir on a deep path creates every missing directory along the way, and is harmless if they already exist; Writing to a new file inside missing directories creates those directories too; Several writes to the same file append, in order.