Practice/Netflix/Versioned File System

Versioned File System

CodingMust

Problem Overview

Design and implement an in-memory file management system with versioning support. The system should support basic CRUD operations (Create, Read, Update, Delete) and maintain version history for crash recovery.

This problem has similarities to LeetCode 1146 (Snapshot Array) and tests your understanding of versioning systems like Git.

You'll build this incrementally across multiple parts, with increasing complexity and production considerations.

Important Notes

• This is a multi-part problem with progressive complexity
• Start with the simplest data structure and extend it as parts get more complex
• Write your own test cases and ensure your code compiles and runs correctly
• Ask clarifying questions about API design, version management, and memory efficiency

Key Design Considerations

• API Design: What operations should the file system support? What should the method signatures look like?
• Version Management: How do you efficiently store and retrieve file versions?
• Crash Recovery: How can the system recover file contents after a crash?
• Memory Efficiency: How do you handle version storage without excessive memory usage?

Part 1: Basic In-Memory File System

Implement a FileSystem class with the following methods:

• create(path, content) - Create a new file
• read(path) - Read file content
• update(path, content) - Update existing file
• delete(path) - Delete a file

Example

` fs = FileSystem()

Create files

fs.create("/documents/report.txt", "Q1 Report") # True fs.create("/documents/report.txt", "Duplicate") # False (already exists)

Read files

print(fs.read("/documents/report.txt")) # "Q1 Report" print(fs.read("/nonexistent.txt")) # None

Update files

fs.update("/documents/report.txt", "Q1 Report - Updated") # True print(fs.read("/documents/report.txt")) # "Q1 Report - Updated"

Delete files

fs.delete("/documents/report.txt") # True print(fs.read("/documents/report.txt")) # None `

Requirements

• Path always starts with "/" (e.g., "/a/b/c.txt")
• For simplicity, treat paths as flat keys (no actual directory hierarchy)
• Return True for successful create/update/delete, False if operation fails
• Return None when reading non-existent files

Part 2: Adding Version Support

Extend the FileSystem class with versioning capabilities:

• snapshot() - Take a snapshot of the current state, returns snapshot ID
• read_at_version(path, snap_id) - Read file content at a specific snapshot

The user should be able to take a "snapshot" and later retrieve the file content at any previous snapshot.

Example

` fs = FileSystem()

fs.create("/config.txt", "v1") snap0 = fs.snapshot() # Returns 0

fs.update("/config.txt", "v2") snap1 = fs.snapshot() # Returns 1

fs.update("/config.txt", "v3")

Current content

print(fs.read("/config.txt")) # "v3"

Historical versions

print(fs.read_at_version("/config.txt", 0)) # "v1" print(fs.read_at_version("/config.txt", 1)) # "v2" `

Requirements

• Snapshots are 0-indexed and increment sequentially
• Each file maintains independent version history
• Deleted files should return None at snapshots after deletion
• Reading at a snapshot before file creation returns None
• Efficient version lookup (avoid copying entire file system on each snapshot)