1500. Design a File Sharing System

• Time:
  • Constructor: $O(1)$
  • join(ownedChunks: list[int]): $O(|\texttt{ownedChunks}|)$
  • leave(userID: int): $O(\texttt{userToChunks[userID]})$
  • request(userID: int, chunkID: int): $O(\texttt{chunkToUsers[chunkID]})$
• Space: $O(|\texttt{join()}| + |\texttt{request()}|)$

C++JavaPython

class FileSharing {
 public:
  FileSharing(int m) {}

  int join(vector<int> ownedChunks) {
    const int userId = getMinUserId();
    userToChunks[userId] = {ownedChunks.begin(), ownedChunks.end()};
    for (const int chunk : ownedChunks)
      chunkToUsers[chunk].insert(userId);
    return userId;
  }

  void leave(int userID) {
    for (const int chunk : userToChunks[userID]) {
      chunkToUsers[chunk].erase(userID);
      if (chunkToUsers[chunk].empty())
        chunkToUsers.erase(chunk);
    }
    userToChunks.erase(userID);
    availableUserIds.push(userID);
  }

  vector<int> request(int userID, int chunkID) {
    const auto it = chunkToUsers.find(chunkID);
    if (it == chunkToUsers.end())
      return {};
    vector<int> userIds{it->second.begin(), it->second.end()};
    userToChunks[userID].insert(chunkID);
    chunkToUsers[chunkID].insert(userID);
    return userIds;
  }

 private:
  unordered_map<int, set<int>> userToChunks;
  unordered_map<int, set<int>> chunkToUsers;
  priority_queue<int, vector<int>, greater<>> availableUserIds;

  int getMinUserId() {
    if (availableUserIds.empty())
      return userToChunks.size() + 1;
    const int minUserId = availableUserIds.top();
    availableUserIds.pop();
    return minUserId;
  }
};

class FileSharing {
  public int join(List<Integer> ownedChunks) {
    final int userId =
        availableUserIds.isEmpty() ? userToChunks.size() + 1 : availableUserIds.poll();
    userToChunks.put(userId, new HashSet<>(ownedChunks));
    for (final int chunk : ownedChunks) {
      chunkToUsers.putIfAbsent(chunk, new TreeSet<>());
      chunkToUsers.get(chunk).add(userId);
    }
    return userId;
  }

  public void leave(int userID) {
    for (final int chunk : userToChunks.get(userID)) {
      chunkToUsers.get(chunk).remove(userID);
      if (chunkToUsers.get(chunk).isEmpty())
        chunkToUsers.remove(chunk);
    }
    userToChunks.remove(userID);
    availableUserIds.offer(userID);
  }

  public List<Integer> request(int userID, int chunkID) {
    if (!chunkToUsers.containsKey(chunkID))
      return new ArrayList<>();
    List<Integer> userIds = new ArrayList<>(chunkToUsers.get(chunkID));
    userToChunks.get(userID).add(chunkID);
    chunkToUsers.get(chunkID).add(userID);
    return userIds;
  }

  private Map<Integer, Set<Integer>> userToChunks = new HashMap<>();
  private Map<Integer, Set<Integer>> chunkToUsers = new HashMap<>();
  private Queue<Integer> availableUserIds = new PriorityQueue<>();
}

from sortedcontainers import SortedSet


class FileSharing:
  def __init__(self, m: int):
    self.userToChunks: dict[int, SortedSet[int]] = {}
    self.chunkToUsers: dict[int, SortedSet[int]] = {}
    self.availableUserIds: list[int] = []

  def join(self, ownedChunks: list[int]) -> int:
    userId = (heapq.heappop(self.availableUserIds) if self.availableUserIds
              else len(self.userToChunks) + 1)
    self.userToChunks[userId] = SortedSet(ownedChunks)
    for chunk in ownedChunks:
      self.chunkToUsers.setdefault(chunk, SortedSet()).add(userId)
    return userId

  def leave(self, userID: int) -> None:
    if userID not in self.userToChunks:
      return
    for chunk in self.userToChunks[userID]:
      self.chunkToUsers[chunk].discard(userID)
      if not self.chunkToUsers[chunk]:
        del self.chunkToUsers[chunk]
    del self.userToChunks[userID]
    heapq.heappush(self.availableUserIds, userID)

  def request(self, userID: int, chunkID: int) -> list[int]:
    if chunkID not in self.chunkToUsers:
      return []
    userIds = list(self.chunkToUsers[chunkID])
    self.userToChunks[userID].add(chunkID)
    self.chunkToUsers[chunkID].add(userID)
    return userIds