588. Design In-Memory File System - Detailed Explanation

Problem Statement

Design an in-memory file system that supports basic file and directory operations. You need to implement the following functions:

• ls(path): If the given path is a file path, return a list containing only that file name. If it is a directory path, return a list of all files and subdirectories in that directory. The output should be sorted in lexicographic (alphabetical) order.

• mkdir(path): Create a new directory given by path. This should create any intermediate directories that do not exist as well. This operation does not return anything.

• addContentToFile(filePath, content): If the file at filePath does not exist, create a new file and add content to it. If the file already exists, append the new content to the end of the current content. This operation does not return anything.

• readContentFromFile(filePath): Return the current content of the file at filePath.

The file system is hierarchical (like a standard file system). All paths are absolute (they begin with "/"). The root directory is "/" (forward slash). There are no trailing slashes at the end of paths (except for the root path itself). All file and directory names consist only of lowercase letters, and in each directory no two files or subdirectories share the same name.

Examples:

Example 1:

Input:

["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]  
[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]  

Output:

[null, [], null, null, ["a"], "hello"]  

Explanation:

1. FileSystem: Instantiate the file system (initially empty). Returns null (no output).
2. ls("/"): List contents of the root directory "/". It's empty at the start, so output [].
3. mkdir("/a/b/c"): Create a directory path /a/b/c. This creates directories "a", "b", and "c" recursively. No output (null).
4. addContentToFile("/a/b/c/d", "hello"): Create a new file "d" in directory /a/b/c with content "hello". (Since /a/b/c exists after the previous step, we can create file "d" there.) No output (null).
5. ls("/"): List contents of root "/". Now it contains a directory "a", so output ["a"] (sorted lexicographically; only one entry here).
6. readContentFromFile("/a/b/c/d"): Read content of file "d" at path /a/b/c/d. The content is "hello", so output "hello".

Example 2:

Input:

["FileSystem","mkdir","addContentToFile","addContentToFile","ls","readContentFromFile"]  
[[],["/g"],["/g/file1","Hello"],["/g/file1","World"],["/g"],["/g/file1"]]  

Output:

[null, null, null, null, ["file1"], "HelloWorld"]  

Explanation:

1. FileSystem: Instantiate the file system.
2. mkdir("/g"): Create directory "/g".
3. addContentToFile("/g/file1", "Hello"): Create file "file1" in "/g" with content "Hello".
4. addContentToFile("/g/file1", "World"): Append "World" to the content of /g/file1. The file’s content becomes "HelloWorld".
5. ls("/g"): List contents of directory "/g". It contains one file "file1", so output ["file1"].
6. readContentFromFile("/g/file1"): Read the content of /g/file1. Outputs "HelloWorld" (the concatenated content from steps 3 and 4).

Example 3:

Input:

["FileSystem","addContentToFile","mkdir","mkdir","ls"]  
[[],["/z","zzz"],["/a"],["/b"],["/"]]  

Output:

[null, null, null, null, ["a","b","z"]]  

Explanation:

1. FileSystem: Instantiate the file system.
2. addContentToFile("/z", "zzz"): Create a file "z" in the root directory with content "zzz".
3. mkdir("/a"): Create directory "/a" in root.
4. mkdir("/b"): Create directory "/b" in root.
5. ls("/"): List contents of root. Now root contains a directory "a", a directory "b", and a file "z". Lexicographically sorted, these names appear as ["a","b","z"]. (Note that both files and subdirectories are listed together in sorted order.)

Constraints:

• All file paths and directory paths are absolute (start with "/"). The only path that ends with "/" is the root itself.
• You can assume all operations are given valid parameters. For example, you won't be asked to list a directory that doesn’t exist or read a file that hasn’t been created. Similarly, if a path is supposed to be a file path, the file will exist by the time you read it.
• All file and directory names consist only of lowercase English letters (a-z). There will be no duplicate names in any given directory.
• This is a design problem focused on the data structure; the number of operations can be large (potentially thousands), so each operation should be designed to run efficiently under those constraints.

Hints to Guide the Thought Process

1. Think of a Hierarchical Structure: The file system is naturally a tree-like hierarchy (directories contain subdirectories or files). Consider representing the paths using a data structure that reflects this hierarchy, such as a tree or trie. Each node in this tree could represent a directory or a file.

2. Distinguish Files from Directories: In your design, you need to differentiate between a directory node and a file node. A directory holds children (subdirectories or files), whereas a file holds content. Think about how you can mark a node as a file and store its content.

3. Path Parsing: Each operation will involve parsing a path like "/a/b/c" into its components. Consider using string split operations (e.g., splitting by "/") to navigate or build the structure. Be careful with the root path ("/") and empty path components from splitting.

4. Implement Operations Step by Step: For each function (ls, mkdir, addContentToFile, readContentFromFile), outline how to traverse or modify your data structure:

   • Listing (ls): Find the node corresponding to the given path. If it's a file, return its name; if it's a directory, gather and sort the names of its children.
   • Making Directories (mkdir): Traverse from the root, creating any missing directory nodes along the path.
   • Adding Content (addContentToFile): Traverse to the file's parent directory. If the file node exists, append content; if not, create a new file node.
   • Reading Content (readContentFromFile): Simply retrieve the content stored in the file node.

5. Lexicographic Order: Remember that when listing directory contents, the result must be sorted lexicographically. You can achieve this by sorting the list of child names before returning, or by maintaining the children in a sorted structure as you insert them.

By considering these hints, you should be able to piece together a design for the in-memory file system. Try to sketch out how you would store the directories and files in memory and how each operation would interact with that storage.

Approach Explanation

We will discuss two possible approaches to design the in-memory file system: a naive approach using a flat mapping (brute force) and an optimal approach using a hierarchical tree (trie-like structure). We will go through each approach step-by-step, explaining how the data is organized and how each operation can be implemented.

Approach 1: Using a Flat Map (Naive Solution)

Idea:
This approach uses a simple dictionary or hash map to store the file system entries in a flat structure. One map can hold full paths as keys and either file content or directory listings as values. For example, we might maintain:

• A map from full path (string) to content (string) for files.
• A map from directory path to a list or set of children names for directories.

Using this structure, each operation can be implemented as follows:

1. mkdir(path):

   • Split the given path by "/" to get each directory in the hierarchy. For example, "/a/b/c" splits into ["a","b","c"].
   • Iterate through these parts, building the path progressively. For each prefix ("/a", "/a/b", "/a/b/c"), ensure that it exists in the directory map. If not, add it and initialize its children list as empty.
   • (In the file-content map, directories are not entries since they have no content. They exist only in the directory-structure map.)

2. addContentToFile(filePath, content):

   • Split the filePath into directory parts and the file name. For example, "/a/b/c/d" splits into directories ["a","b","c"] and file name "d".
   • Traverse the directories as in mkdir to reach the parent directory path ("/a/b/c"). If any intermediate directory is missing (which should not happen if the input is valid and mkdir was called), you would create it (similar to mkdir).
   • In the parent directory's children list, ensure the file name "d" is present (if not, add it, since a new file is being created). In the file content map, if the file path doesn’t exist, create a new entry with the given content; if it exists, append the new content to the existing string.

3. ls(path):

   • If path is a file path (you can detect this by checking if it exists in the file content map or if it’s not a directory in the directory map), then simply return a list containing the last part of the path (the file’s name). For example, ls("/a/b/c/d") would return ["d"].
   • If path is a directory, retrieve the children list from the directory map. Sort this list lexicographically and return it. For example, if the directory /a contains ["foo", "bar"], ls("/a") should return ["bar", "foo"] (because "bar" comes before "foo" alphabetically).

4. readContentFromFile(filePath):

   • Look up the full filePath in the file content map and return the stored content string. For instance, readContentFromFile("/a/b/c/d") would return the content of that file (like "hello" from the earlier example).
   • (No traversal of directories is needed here if we store file content by full path. We directly use the path as a key.)

Summary of Approach 1: We effectively treat the file system as two lookup tables: one for directory structure (children lists) and one for file contents. This is straightforward to implement. However, operations like ls can be inefficient because we might need to sort the child names every time (if we didn't store them sorted). Also, if we had not stored children lists for directories, we would have to scan all stored paths to gather the names in a directory, which would be very slow for large numbers of files. Maintaining separate maps for directories and files helps, but we're still storing full path strings and doing a lot of string manipulation.

Drawbacks:

• Storing every full path string can be memory-inefficient if there are many files, since common path prefixes are repeated in many keys.
• If we did not maintain a children list for directories, ls would require scanning all keys (very slow). If we do maintain children lists, we need to update multiple structures on each operation (e.g., updating the directory’s child list and the file map when creating a file).
• Overall, many operations in this approach involve manipulating strings (splitting paths, concatenating parts, etc.) frequently, which can be less efficient.

Approach 2: Using a Trie-like Tree Structure (Optimal Solution)

Idea:
Use a tree (or trie) data structure to represent the file system hierarchy. Each node in the tree represents either a directory or a file:

• A directory node contains a mapping of names to child nodes (these children can be files or subdirectories).
• A file node stores a content string and does not need children (or you can treat its children map as empty). We also need a way to distinguish file nodes from directories (for example, a boolean flag isFile).

In this approach, the root is a directory node (with no name, representing path "/"). Each directory node’s children map maps names (strings) to nodes (the next level in the hierarchy).

Steps to implement each operation:

1. Data Structure Setup:
   Define a class (or structure) for a Node that has:

   • A flag or indicator (e.g., isFile) to tell if it's a file or a directory.
   • If it's a file, a string to hold its content.
   • If it's a directory, a dictionary/map to hold its children (mapping child name -> child Node).
     For a directory node, isFile = false and for a file node, isFile = true. The root will be a directory node with an empty children map initially.

2. mkdir(path):

   • Split the path by "/" into parts (ignoring the leading empty part for the root). For example, "/a/b/c" -> parts ["a","b","c"].
   • Start from the root node. For each part in the path:
     • If that part name is not already a child of the current node, create a new directory node for it (since mkdir implies these are directories).
     • Move the current pointer to the child node corresponding to that part. Continue until all parts are created/traversed.
   • After this, all directories in the given path exist. (If some directories were already present, we just reuse them without creating new ones.)

3. addContentToFile(filePath, content):

   • Split the filePath into directory parts and the final file name. For example, "/a/b/c/d" -> parts ["a","b","c"] and file name "d".
   • Traverse the directory parts just like in mkdir, starting from root:
     • For each directory part, if it doesn't exist as a child, create a new directory node. Move down to that child.
   • Once you reach the parent directory of the file, handle the file name:
     • If a child node with the file name already exists in this directory:
       • If it is already a file node, append the new content to that node’s content string.
       • If it somehow exists as a directory (which shouldn’t happen in valid usage, because that would mean a directory and file share the same name), you would need to decide how to handle it (in a valid scenario, this case won’t occur due to unique names constraint).
     • If no child node with that name exists, create a new file node for that name, set its content to the given content, and add it to the current directory’s children.
   • This ensures the file now exists at the given path with the correct content. If content was appended multiple times through repeated calls, the file node’s content accumulates all appended text.

4. ls(path):

   • Traverse the path from the root node to the target node (similar to how you traverse for mkdir). If the path is "/", you are already at the root. For a non-root path, split by "/" and go down child pointers for each part.
   • Once you reach the node corresponding to path:
     • If this node is a file node (isFile == true), simply return a list containing the last part of the path (the file’s name). This is because listing a file path should return the file name itself.
     • If this node is a directory node (isFile == false), retrieve all the keys (names) in its children map. Sort these names lexicographically (if they aren’t already stored in sorted order) and return the sorted list. If the directory is empty, return an empty list.
   • Example: if ls("/a/b") is called and /a/b is a directory containing subdirectory "c" and file "x", you would return ["c","x"] sorted (assuming "c" comes before "x" alphabetically).

5. readContentFromFile(filePath):

   • Traverse the path from root to the node just like in ls. The final node should be a file node.
   • Return the content string stored in that file node. For example, readContentFromFile("/a/b/c/d") returns the string content of file "d". (You can assume the file exists and is indeed a file when this operation is called, as per the problem constraints.)

Why this approach is optimal:

• Direct Access: By maintaining the directory tree, we avoid scanning unrelated parts of the file system. Each path traversal touches only the nodes along that path. For example, to access /a/b/c/d, we go straight down those four nodes.
• Shared Structure: Common path prefixes (like the directories "a", "b", "c") are not duplicated in memory. They are single nodes reused for any file or directory under them.
• Efficiency: Each operation runs in time roughly proportional to the length of the path (and for ls, the number of items in a directory). This is typically much faster than scanning a flat list of all paths. In the worst-case scenario, if a directory has n entries, listing it is O(n log n) due to sorting, but this is necessary for lexicographic order. Traversing a path of depth d is O(d).

Step-by-Step Example (Approach 2):
Imagine we call the following operations in order:

mkdir("/docs/tutorial");  
addContentToFile("/docs/tutorial/lesson1.txt", "Content1");  
addContentToFile("/docs/tutorial/lesson2.txt", "Content2");  
ls("/docs/tutorial");  

• After mkdir("/docs/tutorial"): The tree has root -> "docs" (directory) -> "tutorial" (directory).
• After adding two files, the "tutorial" node has two children which are file nodes "lesson1.txt" and "lesson2.txt" containing respective contents.
• The ls("/docs/tutorial") operation will go to the "tutorial" node and list its children. The children names are ["lesson1.txt", "lesson2.txt"], which are returned sorted (they might already be in order, but we ensure sorting).
• A subsequent readContentFromFile("/docs/tutorial/lesson1.txt") would directly return "Content1" from the file node.

This approach closely mimics how a real file system might organize files in memory (with directory inodes and file inodes, etc.), but here we manage it with simple data structures.

Code Implementation

Below are implementations of the in-memory file system in both Python and Java. The classes provide the methods ls, mkdir, addContentToFile, and readContentFromFile as described. The Java implementation includes a main method demonstrating how the file system can be used with the examples given.

Python Code