Design File System - Practice Coding Problems

Design File System - Problem

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn't exist.
int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["FileSystem", "createPath", "get"], parameters = [[], ["/a", 1], ["/a"]]

› Output: [null, true, 1]

💡 Note: Create FileSystem, create path /a with value 1, then get /a returns 1

Example 2 — Parent Path Required

$ Input: operations = ["FileSystem", "createPath", "createPath"], parameters = [[], ["/leet", 1], ["/leet/code", 2]]

› Output: [null, true, true]

💡 Note: Create /leet first, then /leet/code succeeds because parent /leet exists

Example 3 — Missing Parent

$ Input: operations = ["FileSystem", "createPath"], parameters = [[], ["/leet/code", 2]]

› Output: [null, false]

💡 Note: Cannot create /leet/code because parent /leet doesn't exist

Constraints

1 ≤ operations.length ≤ 10⁴
1 ≤ path.length ≤ 100
1 ≤ value ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Series of createPath and get operations on file paths

Parent Validation

Check parent path exists before creating new paths

Hash Map Storage

Store paths and values for fast O(1) access

Key Takeaway

🎯 Key Insight: Use hash map for O(1) path operations and extract parent paths by string manipulation for validation

Asked in

F Facebook 35 a Amazon 28 G Google 22

The key insight is to use a hash map for O(1) path lookups and extract parent paths by string manipulation. For createPath, verify the parent exists before creating new paths. Best approach uses hash map with O(1) time complexity and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(1)	O(n)	Use hash map for O(1) path lookups and parent verification
Brute Force with List Storage	O(n)	O(n)	Store all paths in a list and search linearly for operations

Hash Map Optimization — Algorithm Steps

Use hash map to store path -> value mappings
For createPath: check if path exists and verify parent exists
For get: direct O(1) lookup in hash map

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash Storage

Store paths as keys with O(1) access

Parent Check

Extract parent path and check existence in O(1)

Fast Lookup

Direct hash map lookup for get operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PATHS 1000
#define HASH_SIZE 1009

typedef struct Node {
    char path[100];
    int value;
    struct Node* next;
} Node;

typedef struct {
    Node* table[HASH_SIZE];
} FileSystem;

unsigned int hash(char* str) {
    unsigned int hash = 5381;
    while (*str) hash = ((hash << 5) + hash) + *str++;
    return hash % HASH_SIZE;
}

FileSystem* fileSystemCreate() {
    FileSystem* fs = calloc(1, sizeof(FileSystem));
    return fs;
}

int fileSystemCreatePath(FileSystem* fs, char* path, int value) {
    unsigned int idx = hash(path);
    
    // Check if path exists
    Node* curr = fs->table[idx];
    while (curr) {
        if (strcmp(curr->path, path) == 0) return 0;
        curr = curr->next;
    }
    
    // Check parent exists
    char* lastSlash = strrchr(path, '/');
    if (lastSlash != path) {
        char parent[100];
        strncpy(parent, path, lastSlash - path);
        parent[lastSlash - path] = '\0';
        
        unsigned int parentIdx = hash(parent);
        Node* parentCurr = fs->table[parentIdx];
        int parentExists = 0;
        while (parentCurr) {
            if (strcmp(parentCurr->path, parent) == 0) {
                parentExists = 1;
                break;
            }
            parentCurr = parentCurr->next;
        }
        if (!parentExists) return 0;
    }
    
    // Add new path
    Node* newNode = malloc(sizeof(Node));
    strcpy(newNode->path, path);
    newNode->value = value;
    newNode->next = fs->table[idx];
    fs->table[idx] = newNode;
    return 1;
}

int fileSystemGet(FileSystem* fs, char* path) {
    unsigned int idx = hash(path);
    Node* curr = fs->table[idx];
    while (curr) {
        if (strcmp(curr->path, path) == 0) return curr->value;
        curr = curr->next;
    }
    return -1;
}

int main() {
    printf("[null,true,true,1,-1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Hash map provides O(1) average time for lookup and insertion operations

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all n paths with their associated values

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler