In-Memory File System
Problem
Design an in-memory file system with absolute, slash-separated paths. mkdir(path) creates a directory and any missing parents. append(path, text) creates a file if needed, including missing parent directories, and adds text to its end. read(path) returns a file's whole content, ls(path) returns the sorted names inside a directory, or a one-item list with the file's own name for a file, and size(path) returns the total characters stored at or below a path. The structure must stay a valid tree: nothing may be created inside a file, and a directory may never be read or appended to, so those calls raise NotADirectoryError or IsADirectoryError and change nothing.
Examples
Input: mkdir("/logs/app"), append("/logs/app/today.txt", "boot ok\n"),
append("/logs/app/today.txt", "user in\n"), append("/notes/todo.md", "ship it")
ls("/"), ls("/logs/app"), ls("/notes/todo.md")
Output: ['logs', 'notes'] ['today.txt'] ['todo.md']Input: then read("/logs/app/today.txt"), size("/")
Output: 'boot ok\nuser in\n' 23
Why: 8 + 8 characters in today.txt and 7 in todo.mdInput: then mkdir("/notes/todo.md/drafts"), append("/logs", "x")
Output: NotADirectoryError IsADirectoryError
Why: edge case, the tree refuses a folder inside a file and text written to a folderHints
0 / 3
Pick one representation for a directory and a different one for a file, so a single isinstance check tells them apart everywhere.
Almost every operation starts by walking a path from the root, one name at a time. Write that walk once, with a flag for whether missing directories should be created on the way, and make it refuse to step into a file.
Use a dict for a directory (name -> child) and a list of text chunks for a file. append splits off the last name, walks to the parent with creation on, and refuses if the parent is a file or the name is a directory. size recurses: a file is the sum of its chunk lengths, a directory the sum of its children's sizes.
Solution
A directory is a dict from name to child and a file is a list of text chunks, so every rule reduces to one isinstance check at the right moment. All five operations share one path walk, which either creates missing directories or raises when a name is missing, and which refuses to descend into a file; that single guard is what keeps the tree valid, because no call can ever place a child under a file. append checks the parent and the target before creating anything, so a refused call leaves no half-built directories behind, and it stores chunks rather than joining strings so appends stay cheap until a read joins them once. A walk costs O(d) for a path of depth d, and size is O(n) over the n nodes below the path.
class FileSystem:
def __init__(self):
self.root = {} # a directory is a dict, a file is a list of chunks
def _walk(self, path, create=False):
node = self.root
for name in filter(None, path.split("/")):
if isinstance(node, list):
raise NotADirectoryError(path) # never step inside a file
if name not in node and not create:
raise FileNotFoundError(path)
node = node.setdefault(name, {})
return node
def mkdir(self, path):
if isinstance(self._walk(path, create=True), list):
raise NotADirectoryError(path) # the path names a file
def append(self, path, text):
parent, name = path.rsplit("/", 1)
folder = self._walk(parent, create=True)
if isinstance(folder, list) or isinstance(folder.get(name), dict):
raise IsADirectoryError(path)
folder.setdefault(name, []).append(text)
def read(self, path):
node = self._walk(path)
if isinstance(node, dict):
raise IsADirectoryError(path)
return "".join(node)
def ls(self, path):
node = self._walk(path)
return [path.rsplit("/", 1)[1]] if isinstance(node, list) else sorted(node)
def size(self, path):
node = self._walk(path)
if isinstance(node, list):
return sum(len(chunk) for chunk in node)
return sum(self.size(path.rstrip("/") + "/" + name) for name in node)
def attempt(action, *args):
try:
action(*args)
return "ok"
except OSError as error:
return type(error).__name__
fs = FileSystem()
fs.mkdir("/logs/app")
fs.append("/logs/app/today.txt", "boot ok\n")
fs.append("/logs/app/today.txt", "user in\n")
fs.append("/notes/todo.md", "ship it")
print(fs.ls("/"), fs.ls("/logs/app"), fs.ls("/notes/todo.md")) # -> ['logs', 'notes'] ['today.txt'] ['todo.md']
print(repr(fs.read("/logs/app/today.txt")), fs.size("/")) # -> 'boot ok\nuser in\n' 23
print(attempt(fs.mkdir, "/notes/todo.md/drafts"), attempt(fs.append, "/logs", "x")) # -> NotADirectoryError IsADirectoryErrorStuck on the idea rather than the code? Designing a File System covers it.