Implement Cloud File Storage with User Quotas and Backups
Quick Overview
Implement cloud file storage with largest-file queries, user quotas, ownership merges, and backup restoration under explicit collision and capacity rules.
Implement Cloud File Storage with User Quotas and Backups
Company: Duolingo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an in-memory cloud file storage system supporting four levels: file addition/removal, largest-file queries, user quotas and merges, and per-user backup/restore. Keep file sizes, ownership, and capacity consistent across all operations.
### Constraints & Assumptions
The source names these operations but omits their exact signatures and collision policies. Use the following explicit practice contract: filenames are globally unique; sizes and capacities are nonnegative integers; duplicate adds fail; largest-file ties sort by filename; there is a reserved unlimited administrative owner for unowned adds, and it cannot participate on either side of a merge; user IDs cannot be reused. A backup is a copy of filename-size metadata. Restore replaces that user's current files, skips names now owned by others, and fails atomically if the remaining snapshot exceeds quota. Merge transfers files and remaining capacity, preserves the destination backup, and discards the removed user's backup. These policies are assumptions, not claimed original judge rules.
### Clarifying Questions to Ask
- Does restore skip conflicting filenames or reject the whole operation?
- What happens to backups when users merge, and does restore change quota?
- Are the largest-file results global or filtered by a filename prefix?
### Part 1 — File operations and ranking
Implement add and remove with success/failure results, and a global largest-N query returning filename-size pairs ordered by descending size and then filename.
#### What This Part Should Cover
- Canonical size and ownership records and duplicate-name validation.
- Deterministic ranking and removal from all relevant indexes.
### Part 2 — Users and merging
Add users with quotas, add files owned by a user if capacity permits, and merge user 2 into user 1 by transferring all files and remaining capacity. Reject missing or identical users.
#### What This Part Should Cover
- Used-space accounting and quota validation before writes.
- A merge that preserves both occupied and free capacity.
### Part 3 — Backup and restore
Snapshot a user's filename-size metadata, then restore according to the explicit practice contract. If no backup exists, restore to an empty file set. Preserve live state if quota validation fails.
#### What This Part Should Cover
- An independent snapshot that survives file deletion and size changes.
- Planning conflict resolution and total restored size before mutation.
```hint Preserve enough snapshot data
A set of filenames cannot restore an old file size after the live file has changed or disappeared.
```
### What a Strong Answer Covers
- Executable operations sharing one ownership and capacity model.
- Invariants covering add, delete, merge, backup, and restore.
- Tests for name conflicts, snapshot independence, and quota accounting.
### Follow-up Questions
- How would prefix-filtered largest-file queries change the indexes?
- What transaction boundaries would preserve these invariants in a persistent implementation?
Overview: Implement cloud file storage with largest-file queries, user quotas, ownership merges, and backup restoration under explicit collision and capacity rules.
Implement an in-memory cloud file storage system supporting four levels: file addition/removal, largest-file queries, user quotas and merges, and per-user backup/restore. Keep file sizes, ownership, and capacity consistent across all operations.
Constraints & Assumptions
The source names these operations but omits their exact signatures and collision policies. Use the following explicit practice contract: filenames are globally unique; sizes and capacities are nonnegative integers; duplicate adds fail; largest-file ties sort by filename; there is a reserved unlimited administrative owner for unowned adds, and it cannot participate on either side of a merge; user IDs cannot be reused. A backup is a copy of filename-size metadata. Restore replaces that user's current files, skips names now owned by others, and fails atomically if the remaining snapshot exceeds quota. Merge transfers files and remaining capacity, preserves the destination backup, and discards the removed user's backup. These policies are assumptions, not claimed original judge rules.
Clarifying Questions to Ask Guidance
Does restore skip conflicting filenames or reject the whole operation?
What happens to backups when users merge, and does restore change quota?
Are the largest-file results global or filtered by a filename prefix?
Part 1 — File operations and ranking
Implement add and remove with success/failure results, and a global largest-N query returning filename-size pairs ordered by descending size and then filename.
What This Part Should Cover Guidance
Canonical size and ownership records and duplicate-name validation.
Deterministic ranking and removal from all relevant indexes.
Part 2 — Users and merging
Add users with quotas, add files owned by a user if capacity permits, and merge user 2 into user 1 by transferring all files and remaining capacity. Reject missing or identical users.
What This Part Should Cover Guidance
Used-space accounting and quota validation before writes.
A merge that preserves both occupied and free capacity.
Part 3 — Backup and restore
Snapshot a user's filename-size metadata, then restore according to the explicit practice contract. If no backup exists, restore to an empty file set. Preserve live state if quota validation fails.
What This Part Should Cover Guidance
An independent snapshot that survives file deletion and size changes.
Planning conflict resolution and total restored size before mutation.
What a Strong Answer Covers Guidance
Executable operations sharing one ownership and capacity model.
Invariants covering add, delete, merge, backup, and restore.
Tests for name conflicts, snapshot independence, and quota accounting.
Follow-up Questions Guidance
How would prefix-filtered largest-file queries change the indexes?
What transaction boundaries would preserve these invariants in a persistent implementation?