Design In-Memory File System

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design In-Memory File System

Design a data structure that represents an in-memory file system. Support ls, mkdir, addContentToFile, and readContentFromFile.

Hard

Examples

Input: mkdir("/a/b/c"), addContentToFile("/a/b/c/d", "hello"), ls("/a/b/c"), readContentFromFile("/a/b/c/d")
Output: ["d"], "hello"

Approach 1

Level I: Map of Full Paths

Intuition

Maintain a Map<String, String> where the key is the full path and the value is the content. For ls, iterate through keys to find children. This is simple but slow for deep trees.

⏱ Ls: O(PathCount), Mkdir: O(1).💾 O(TotalContentLength).

java

class FileSystem {
    Map<String, String> paths = new HashMap<>();
    public List<String> ls(String path) {
        Set<String> res = new TreeSet<>();
        if (paths.containsKey(path)) return Arrays.asList(path.substring(path.lastIndexOf('/')+1));
        for (String p : paths.keySet()) {
            if (p.startsWith(path + "/")) {
                String sub = p.substring(path.length() + (path.equals("/") ? 0 : 1));
                res.add(sub.split("/")[0]);
            }
        }
        return new ArrayList<>(res);
    }
    public void mkdir(String path) { if (!paths.containsKey(path)) paths.put(path, null); }
    public void addContentToFile(String path, String content) {
        paths.put(path, paths.getOrDefault(path, "") + content);
    }
    public String readContentFromFile(String path) { return paths.get(path); }
}

Approach 2

Level III: Trie-based Tree Structure

Intuition

Model the file system as a tree (Trie), where each node is either a directory or a file. Directories contain a Map<String, Node> of children. This allows for efficient path traversal.

⏱ Ls, Mkdir, Read, Write: O(PathLength).💾 O(Nodes * FileNamesLength).

java

class FileSystem {
    class Node { boolean isFile = false; TreeMap<String, Node> children = new TreeMap<>(); String content = ""; }
    Node root = new Node();
    public List<String> ls(String path) {
        Node curr = traverse(path);
        if (curr.isFile) return Arrays.asList(path.substring(path.lastIndexOf("/") + 1));
        return new ArrayList<>(curr.children.keySet());
    }
    public void mkdir(String path) { traverse(path); }
    public void addContentToFile(String path, String content) {
        Node curr = traverse(path); curr.isFile = true; curr.content += content;
    }
    public String readContentFromFile(String path) { return traverse(path).content; }
    private Node traverse(String path) {
        Node curr = root; String[] parts = path.split("/");
        for (String p : parts) {
            if (p.isEmpty()) continue;
            curr.children.putIfAbsent(p, new Node()); curr = curr.children.get(p);
        }
        return curr;
    }
}

← Previous QuestionDesign Bounded Blocking Queue

Next Question →Design Browser History

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.