Design File System: ออกแบบระบบไฟล์ใน Python

โจทย์

ออกแบบ File System ที่รองรับ 2 operation:

1. createPath(path, value): สร้าง path ใหม่ผูกค่า value คืน True ถ้าสำเร็จ, False ถ้า path มีอยู่แล้ว หรือ parent path ไม่มีอยู่
2. get(path): คืนค่าที่ผูกกับ path, หรือ -1 ถ้าไม่มี path นั้น

รูปแบบ path: / ตามด้วย lowercase letters หนึ่งขึ้นไป เช่น /programming, /programming/problems (แต่ "" และ "/" ไม่ valid)

วิธีแก้: Nested Dictionary (Trie-like)

ใช้ nested dict แทนโครงสร้างไดเรกทอรี: {"dir": [value, {"subdir": [...]}]}

การติดตั้ง (Python Implementation)

class FileSystem:
    def __init__(self):
        self.root = {}  # nested dict: {name: [value, children_dict]}
    
    def createPath(self, path: str, value: int) -> bool:
        parts = path.split('/')  # ['', 'a', 'b', 'c']
        # parts[0] คือ empty string จาก leading slash
        node = self.root
        
        # วนลูปหา parent (ถึงตัวก่อนสุดท้าย)
        for i in range(1, len(parts) - 1):
            name = parts[i]
            if name not in node:
                return False  # parent ไม่มีอยู่
            node = node[name][1]  # ไปที่ children dict
        
        # ตรวจสอบ path สุดท้าย
        last = parts[-1]
        if last in node:
            return False  # path มีอยู่แล้ว
        
        # สร้าง path ใหม่
        node[last] = [value, {}]
        return True
    
    def get(self, path: str) -> int:
        parts = path.split('/')
        node = self.root
        
        # วนลูปหา path
        for i in range(1, len(parts) - 1):
            name = parts[i]
            if name not in node:
                return -1
            node = node[name][1]
        
        last = parts[-1]
        if last in node:
            return node[last][0]
        return -1

# ทดสอบ
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("/a/b", 3))    # False (exists)
print(fs.createPath("/c/d", 4))    # False (parent /c not exist)
print(fs.get("/c"))                # -1

Output

True
1
True
2
False
False
-1

การทำงานภายใน (Internal Structure)

หลังจาก createPath("/a/b", 2) และ createPath("/a/c", 3):

{
  'a': [1, {
    'b': [2, {}],
    'c': [3, {}]
  }]
}

Complexity

• createPath: O(L) โดย L = จำนวน path components
• get: O(L)
• Space: O(Total paths × average depth)

ขยายความสามารถ (Extensions)

• deletePath(path): ลบ path (ต้องตรวจสอบว่าไม่มี children)
• listPath(path): แสดง children ทั้งหมด
• เพิ่ม metadata: timestamp, permissions, file type

สรุป

Nested Dictionary เป็นวิธีง่ายและมีประสิทธิภาพสำหรับออกแบบ File System แบบ In-Memory จริงๆ ระบบไฟล์จริงจะใช้ B-tree หรือ LSM-tree บนดิสก์

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ