Course4all

Design In-Memory File System

Expert Answer & Key Takeaways

# 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)O(1) read and O(N)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)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)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)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionDesign Bounded Blocking Queue
Next Question →Design Browser History