LeetCode 1500: Design a File Sharing System

Explanation:

To design a file sharing system, we can implement a system that supports the following operations:

1. join(int[] ownedChunks): A new user joins the system with the given list of owned file chunks.
2. leave(int userID): A user leaves the system.
3. request(int userID, int chunkID): A user requests a chunk with a specific ID.
4. share(int userID, int chunkID): A user shares a chunk with another user.

We can use a combination of data structures such as HashMaps, Sets, and Lists to efficiently implement the file sharing system.

Algorithm:

1. Maintain a HashMap where the key is the user ID and the value is a Set of chunks owned by that user.
2. To join a new user, add an entry to the HashMap with the user ID and the Set of owned chunks.
3. To leave a user, remove the entry from the HashMap.
4. To request a chunk, iterate through all users and check if any user owns the requested chunk. If found, return the user ID.
5. To share a chunk, add the chunk to the Set of owned chunks for the target user.

Time Complexity:

• join(): O(1)
• leave(): O(1)
• request(): O(n) where n is the number of users
• share(): O(1)

Space Complexity:

• O(n) where n is the total number of users and chunks in the system.

: :

import java.util.*;

class FileSharingSystem {
    Map<Integer, Set<Integer>> userChunks;

    public FileSharingSystem() {
        userChunks = new HashMap<>();
    }

    public void join(int[] ownedChunks) {
        Set<Integer> chunks = new HashSet<>();
        for (int chunk : ownedChunks) {
            chunks.add(chunk);
        }
        userChunks.put(userChunks.size() + 1, chunks);
    }

    public void leave(int userID) {
        userChunks.remove(userID);
    }

    public List<Integer> request(int userID, int chunkID) {
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Set<Integer>> entry : userChunks.entrySet()) {
            if (entry.getValue().contains(chunkID)) {
                res.add(entry.getKey());
            }
        }
        return res;
    }

    public void share(int userID, int chunkID) {
        userChunks.get(userID).add(chunkID);
    }
}