Thiết Kế Hệ Thống File (File System) Trong Python: createPath & get

Đề bài: Triển khai hệ thống file đơn giản với 2 operation:

• createPath(path, value): Tạo path mới gán giá trị. Trả về True nếu thành công, False nếu path đã tồn tại hoặc parent path không tồn tại.
• get(path): Trả về giá trị của path, hoặc -1 nếu không tồn tại.

Path format: /a/b/c (bắt đầu bằng /, các segment là chữ thường).

Cấu trúc dữ liệu: Nested Dictionary (Trie-like)

Mỗi node là dict: {segment: [value, children_dict]}. Root là {}.

Code Python

class FileSystem:
    def __init__(self):
        self.root = {}
    
    def createPath(self, path: str, value: int) -> bool:
        parts = path.split('/')  # ['', 'a', 'b', 'c']
        node = self.root
        
        # Duyệt qua các parent segment (bỏ qua phần tử đầu rỗng và segment cuối)
        for part in parts[1:-1]:
            if part not in node:
                return False  # Parent không tồn tại
            node = node[part][1]  # node[part] = [value, children], lấy children
        
        last = parts[-1]
        if last in node:
            return False  # Path đã tồn tại
        
        node[last] = [value, {}]
        return True
    
    def get(self, path: str) -> int:
        parts = path.split('/')
        node = self.root
        
        for part in parts[1:-1]:
            if part not in node:
                return -1
            node = node[part][1]
        
        last = parts[-1]
        if last in node:
            return node[last][0]
        return -1

# Test
fs = FileSystem()
print(fs.createPath("/a", 1))      # True
print(fs.get("/a"))                # 1
print(fs.createPath("/a/b", 2))    # True
print(fs.get("/a/b"))              # 2
print(fs.createPath("/c/d", 3))    # False (parent /c không tồn tại)
print(fs.get("/c/d"))              # -1

Kết quả

True
1
True
2
False
-1

Phân tích

• Time: O(L) với L = số segment trong path.
• Space: O(Tổng độ dài path).
• Cấu trúc nested dict mô phỏng trie, phù hợp cho hierarchical path.

Mở rộng thực tế

• Thêm deletePath, listDir.
• Lưu metadata (timestamp, permission, owner).
• Persistence: serialize ra JSON/file.
• Thread-safety: thêm lock.