Disk Storage: Simulate a File System Disk Allocator with Block Fragmentation Tracking

Question

## Problem

Simulate a disk with `N` blocks. Implement a storage allocator that supports: `allocate(file_id, num_blocks)` (find contiguous free blocks and assign them), `free(file_id)` (release all blocks for a file), and `fragmentation_ratio()` (fraction of free space that is in non-contiguous segments).

```python
class DiskStorage:
    def __init__(self, total_blocks: int): ...
    def allocate(self, file_id: str, num_blocks: int) -> int:  # returns start block or -1
    def free(self, file_id: str) -> None: ...
    def fragmentation_ratio(self) -> float: ...
```

**Example:**
```
ds = DiskStorage(10)
ds.allocate("A", 3)   -> 0   (blocks 0,1,2)
ds.allocate("B", 4)   -> 3   (blocks 3,4,5,6)
ds.free("A")
ds.allocate("C", 5)   -> -1  (largest contiguous free = 3 + 3... wait: free=3 at front + 3 at end = non-contiguous)
ds.fragmentation_ratio() -> 0.5  (2 free segments out of total free blocks)
```

## Follow-ups

1. What is the time complexity of finding contiguous free blocks with a naive scan vs. using a free-list?
2. What is external fragmentation vs. internal fragmentation, and which does this simulator measure?
3. How does a real OS file system (e.g., ext4) use extents or bitmaps to track free blocks?
4. How would you implement a compaction routine that defragments the disk by moving files to consolidate free space?

Disk Storage: Simulate a File System Disk Allocator with Block Fragmentation Tracking

Question Details

Full Details

Topics

More from Uber