Design a File Sharing System

To implement the FileSharing system, we need to track both the chunks that each user has and the chunks that are available in the system. In addition, we need to maintain a pool of available user IDs to assign to new users. This can be achieved by using Python’s built-in data structures like sets and lists.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

from typing import List
from heapq import heappush, heappop

class FileSharing:
    def __init__(self, m: int):
        self.user_chunks = {}
        self.chunk_users = {i: set() for i in range(1, m+1)}
        self.available_ids = []

    def join(self, ownedChunks: List[int]) -> int:
        # If there are available IDs, use the smallest one.
        # Otherwise, create a new ID.
        if self.available_ids:
            user_id = heappop(self.available_ids)
        else:
            user_id = len(self.user_chunks) + 1

        self.user_chunks[user_id] = set(ownedChunks)
 
        # Register the user as an owner of each chunk they have.
        for chunk in ownedChunks:
            self.chunk_users[chunk].add(user_id)
 
        return user_id

    def leave(self, userID: int) -> None:
        # Remove the user from the owners of each chunk they have.
        for chunk in self.user_chunks[userID]:
            self.chunk_users[chunk].remove(userID)
 
        # Add the user's ID to the pool of available IDs.
        heappush(self.available_ids, userID)
 
        # Remove the user from user_chunks.
        del self.user_chunks[userID]

    def request(self, userID: int, chunkID: int) -> List[int]:
        owners = sorted(self.chunk_users[chunkID])
 
        # If the chunk is available, add it to the user's chunks.
        if owners:
            self.user_chunks[userID].add(chunkID)
            self.chunk_users[chunkID].add(userID)
 
        return owners

Here is how it works:

  1. The __init__ method initializes the user-chunks mapping, chunk-users mapping, and the pool of available user IDs.
  2. The join method assigns an ID to a new user, adds the chunks they own to their entry in the user-chunks mapping, and adds them to the set of owners of each chunk they own.
  3. The leave method removes a user from the system. It removes the user from the set of owners of each chunk they own, adds their ID to the pool of available IDs, and removes them from the user-chunks mapping.
  4. The request method handles a chunk request from a user. It returns the sorted list of owners of the chunk. If the chunk is available, it also adds the chunk to the user’s chunks and adds the user to the set of owners of the chunk.