Design In-Memory File System - Solution & Explanation

Problem Overview: Design a file system that runs entirely in memory. You must support directory listing (ls), creating directories (mkdir), adding content to files (addContentToFile), and reading file content (readContentFromFile) while maintaining lexicographically sorted directory listings.

Approach 1: HashMap-Based Directory Tree (Trie Structure) (Time: O(p + k log k), Space: O(n))

Treat the file system as a tree where each directory is a node and edges represent path segments. Split the path by / and traverse the tree one segment at a time. Each node stores a hash map of children (name → node), a flag indicating whether it is a file, and a string builder for file content. Directory operations like mkdir simply create missing nodes during traversal. For ls, return the file name if the path is a file, otherwise collect child keys and sort them lexicographically. Traversal takes O(p) where p is the number of path components, and sorting the directory listing costs O(k log k) where k is the number of entries.

This approach behaves like a simplified Trie where each level represents a folder name instead of a character. Using a hash table for children ensures constant-time lookup during traversal. File content appends are efficient because you only modify the node representing the file.

Approach 2: Trie with File Metadata and Lazy Sorting (Time: O(p) average, O(k log k) for listing, Space: O(n))

Another implementation models directories and files explicitly with a Trie node class containing metadata such as isFile, content, and a children map. Path traversal works the same way: split the path, iterate through segments, and create nodes when necessary. Instead of sorting every time ls is called, some implementations maintain directory entries in sorted containers or cache sorted results when modifications occur. This reduces repeated sorting overhead when directories are listed frequently.

The Trie structure naturally represents hierarchical file paths, making operations predictable and easy to reason about. String parsing of paths relies on standard string operations, and node traversal handles all file system operations consistently.

Recommended for interviews: The HashMap-backed Trie is the expected solution. It directly models the hierarchical file system and keeps each operation near O(p). Interviewers mainly check whether you design a clean node structure, correctly parse paths, and handle the lexicographic ordering requirement for ls. A simpler map-only idea can show understanding, but the Trie-style directory tree demonstrates solid system design thinking.