1500. Design a File Sharing System - Leetcode Solution

Problem Description

The "Design a File Sharing System" problem on LeetCode asks you to implement a class that simulates a distributed file sharing service. In this system, files are split into k chunks, and users can join or leave the system, request files, and upload or delete chunks. The system must keep track of which user owns which chunks, and efficiently support the following operations:

join(userID): A user joins the system and is assigned a unique userID. Returns the assigned ID.
leave(userID): A user leaves, and all their chunks are deleted from the system.
request(userID, fileID): A user requests all chunks of a file. Returns a list of user IDs who own each chunk.
upload(userID, fileID, chunkID): A user uploads a chunk of a file.
delete(userID, fileID, chunkID): A user deletes a chunk of a file they own.

The key constraints are:

Each chunk can be owned by multiple users.
All operations must be efficient, as the number of users, files, and chunks can be large.
You must carefully manage the mapping between users, files, and chunk ownership.

Thought Process

To solve this problem, we need to simulate a distributed file sharing system efficiently. At first glance, a brute-force approach might use nested lists or arrays to store which users have which chunks, but this would be slow and memory-inefficient, especially with many users and files.

Instead, we should use data structures that allow us to quickly:

Look up which users have a particular chunk of a file.
Update ownership when users upload or delete chunks.
Clean up all a user's chunks when they leave.

This suggests using hash maps (dictionaries) to map from files and chunks to sets of users, and vice versa.

We also need to generate unique user IDs, and recycle IDs when users leave. This can be done with a pool of available IDs.

Solution Approach

Let's design the system step by step:

User ID Management:
- Maintain a min-heap (priority queue) of available IDs for recycling.
- Keep a counter for the next new ID if the heap is empty.
Chunk Ownership Mapping:
- For each (fileID, chunkID), keep a set of user IDs who own that chunk.
- For each user, keep a set of (fileID, chunkID) pairs they own, for efficient cleanup on leave.
Operations:
- join(): Assign the smallest available ID, or the next new ID.
- leave(userID): Remove user from all their chunk ownerships, and recycle their ID.
- request(userID, fileID): For each chunk of the file, return a sorted list of user IDs who own it.
- upload(userID, fileID, chunkID): Add user to the set of owners for that chunk.
- delete(userID, fileID, chunkID): Remove user from the set of owners for that chunk.

This design ensures that all operations are efficient, using hash maps and sets for constant-time lookups and updates.

Example Walkthrough

Let's walk through a sample scenario:

User 1 joins: Assigned ID 1.
User 1 uploads chunk 0 of file 10: Ownership mapping: {(10,0): {1}}.
User 2 joins: Assigned ID 2.
User 2 requests file 10: System checks ownership for each chunk (say file 10 has chunks 0 and 1). For chunk 0, user 1 owns it; for chunk 1, no one owns it yet. Returns [[1], []].
User 2 uploads chunk 1 of file 10: Ownership mapping: {(10,0): {1}, (10,1): {2}}.
User 1 leaves: Remove user 1 from all ownerships. Now, {(10,0): set(), (10,1): {2}}. ID 1 is recycled.
User 3 joins: Assigned ID 1 (recycled).

At each step, the ownership mappings and available IDs are updated efficiently.

Time and Space Complexity

Brute-force approach:

Time: O(U * F * C) per operation (U = users, F = files, C = chunks) if we scan all users/files/chunks.
Space: O(U * F * C) if we store all possible ownerships explicitly.

Optimized approach (using hash maps and sets):

Time: O(1) for join, upload, delete; O(C) for leave (where C is the number of chunks a user owns); O(K) for request (where K is the number of chunks in the file).
Space: O(total number of owned chunks), which is much less than the brute-force approach.

The use of hash maps and sets ensures that most operations are constant or linear in the number of relevant chunks/users, not the total system size.

Summary

In this problem, we efficiently simulate a distributed file sharing system by using hash maps and sets to manage ownership mappings and user IDs. Key insights include:

Use a min-heap and counter to manage unique/recycled user IDs.
Map each (fileID, chunkID) to a set of user IDs for fast lookup and update.
Store each user's owned chunks for efficient cleanup.
All operations are optimized for speed and memory efficiency, making the solution scalable and elegant.

This approach combines careful data structure choice with clear logic to meet all problem constraints.

Code Implementation

import heapq
from collections import defaultdict

class FileSharing:

    def __init__(self, m):
        self.next_id = 1
        self.available_ids = []
        self.chunk_owners = defaultdict(set)  # (fileID, chunkID) -> set of userIDs
        self.user_chunks = defaultdict(set)   # userID -> set of (fileID, chunkID)
        self.m = m  # number of chunks per file

    def join(self):
        if self.available_ids:
            user_id = heapq.heappop(self.available_ids)
        else:
            user_id = self.next_id
            self.next_id += 1
        return user_id

    def leave(self, userID):
        if userID not in self.user_chunks:
            return
        for file_chunk in self.user_chunks[userID]:
            self.chunk_owners[file_chunk].discard(userID)
        del self.user_chunks[userID]
        heapq.heappush(self.available_ids, userID)

    def request(self, userID, fileID):
        result = []
        for chunkID in range(self.m):
            owners = sorted(self.chunk_owners[(fileID, chunkID)])
            result.append(owners)
        return result

    def upload(self, userID, fileID, chunkID):
        self.chunk_owners[(fileID, chunkID)].add(userID)
        self.user_chunks[userID].add((fileID, chunkID))

    def delete(self, userID, fileID, chunkID):
        self.chunk_owners[(fileID, chunkID)].discard(userID)
        self.user_chunks[userID].discard((fileID, chunkID))

#include <vector>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;

class FileSharing {
public:
    int next_id;
    priority_queue<int, vector<int>, greater<int>> available_ids;
    unordered_map<pair<int,int>, set<int>, 
        function<size_t(const pair<int,int>&)>> chunk_owners;
    unordered_map<int, set<pair<int,int>>> user_chunks;
    int m;

    FileSharing(int m_) : m(m_),
        chunk_owners(10, [](const pair<int,int>& p){ return hash<int>() (p.first) ^ hash<int>()(p.second); }) {
        next_id = 1;
    }
    
    int join() {
        int user_id;
        if (!available_ids.empty()) {
            user_id = available_ids.top();
            available_ids.pop();
        } else {
            user_id = next_id++;
        }
        return user_id;
    }
    
    void leave(int userID) {
        if (user_chunks.find(userID) == user_chunks.end()) return;
        for (const auto& fc : user_chunks[userID]) {
            chunk_owners[fc].erase(userID);
        }
        user_chunks.erase(userID);
        available_ids.push(userID);
    }
    
    vector<vector<int>> request(int userID, int fileID) {
        vector<vector<int>> result;
        for (int chunkID = 0; chunkID < m; ++chunkID) {
            pair<int,int> fc = {fileID, chunkID};
            vector<int> owners(chunk_owners[fc].begin(), chunk_owners[fc].end());
            result.push_back(owners);
        }
        return result;
    }
    
    void upload(int userID, int fileID, int chunkID) {
        pair<int,int> fc = {fileID, chunkID};
        chunk_owners[fc].insert(userID);
        user_chunks[userID].insert(fc);
    }
    
    void deleteChunk(int userID, int fileID, int chunkID) {
        pair<int,int> fc = {fileID, chunkID};
        chunk_owners[fc].erase(userID);
        user_chunks[userID].erase(fc);
    }
};

import java.util.*;

class FileSharing {
    private int nextId;
    private PriorityQueue<Integer> availableIds;
    private Map<Pair, Set<Integer>> chunkOwners;
    private Map<Integer, Set<Pair>> userChunks;
    private int m;

    private static class Pair {
        int file, chunk;
        Pair(int f, int c) { file = f; chunk = c; }
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Pair)) return false;
            Pair p = (Pair) o;
            return file == p.file && chunk == p.chunk;
        }
        @Override
        public int hashCode() {
            return Objects.hash(file, chunk);
        }
    }

    public FileSharing(int m) {
        this.m = m;
        nextId = 1;
        availableIds = new PriorityQueue<>();
        chunkOwners = new HashMap<>();
        userChunks = new HashMap<>();
    }

    public int join() {
        int userId = availableIds.isEmpty() ? nextId++ : availableIds.poll();
        return userId;
    }

    public void leave(int userID) {
        if (!userChunks.containsKey(userID)) return;
        for (Pair fc : userChunks.get(userID)) {
            Set<Integer> owners = chunkOwners.get(fc);
            if (owners != null) owners.remove(userID);
        }
        userChunks.remove(userID);
        availableIds.offer(userID);
    }

    public List<List<Integer>> request(int userID, int fileID) {
        List<List<Integer>> result = new ArrayList<>();
        for (int chunkID = 0; chunkID < m; ++chunkID) {
            Pair fc = new Pair(fileID, chunkID);
            List<Integer> owners = new ArrayList<>();
            if (chunkOwners.containsKey(fc)) {
                owners.addAll(chunkOwners.get(fc));
                Collections.sort(owners);
            }
            result.add(owners);
        }
        return result;
    }

    public void upload(int userID, int fileID, int chunkID) {
        Pair fc = new Pair(fileID, chunkID);
        chunkOwners.computeIfAbsent(fc, k -> new HashSet<>()).add(userID);
        userChunks.computeIfAbsent(userID, k -> new HashSet<>()).add(fc);
    }

    public void delete(int userID, int fileID, int chunkID) {
        Pair fc = new Pair(fileID, chunkID);
        if (chunkOwners.containsKey(fc)) chunkOwners.get(fc).remove(userID);
        if (userChunks.containsKey(userID)) userChunks.get(userID).remove(fc);
    }
}

class FileSharing {
    constructor(m) {
        this.m = m;
        this.nextId = 1;
        this.availableIds = [];
        this.chunkOwners = new Map(); // key: fileID-chunkID, value: Set of userIDs
        this.userChunks = new Map();  // key: userID, value: Set of fileID-chunkID
    }
    
    join() {
        let userId;
        if (this.availableIds.length > 0) {
            this.availableIds.sort((a, b) => a - b);
            userId = this.availableIds.shift();
        } else {
            userId = this.nextId++;
        }
        return userId;
    }
    
    leave(userID) {
        if (!this.userChunks.has(userID)) return;
        for (let fc of this.userChunks.get(userID)) {
            if (this.chunkOwners.has(fc)) {
                this.chunkOwners.get(fc).delete(userID);
            }
        }
        this.userChunks.delete(userID);
        this.availableIds.push(userID);
    }
    
    request(userID, fileID) {
        let result = [];
        for (let chunkID = 0; chunkID < this.m; ++chunkID) {
            let fc = fileID + '-' + chunkID;
            let owners = [];
            if (this.chunkOwners.has(fc)) {
                owners = Array.from(this.chunkOwners.get(fc));
                owners.sort((a, b) => a - b);
            }
            result.push(owners);
        }
        return result;
    }
    
    upload(userID, fileID, chunkID) {
        let fc = fileID + '-' + chunkID;
        if (!this.chunkOwners.has(fc)) this.chunkOwners.set(fc, new Set());
        this.chunkOwners.get(fc).add(userID);
        if (!this.userChunks.has(userID)) this.userChunks.set(userID, new Set());
        this.userChunks.get(userID).add(fc);
    }
    
    delete(userID, fileID, chunkID) {
        let fc = fileID + '-' + chunkID;
        if (this.chunkOwners.has(fc)) this.chunkOwners.get(fc).delete(userID);
        if (this.userChunks.has(userID)) this.userChunks.get(userID).delete(fc);
    }
}

AlgoMap.io

Want Help Cracking FAANG?