Problem
We will use a file-sharing system to share a very large file which consists of
m
small chunks with IDs from 1
to m
.
When users join the system, the system should assign a unique ID to them. The unique ID should be used once for each user, but when a user leaves the system, the ID can be reused again.
Users can request a certain chunk of the file, the system should return a list of IDs of all the users who own this chunk. If the user receives a non-empty list of IDs, they receive the requested chunk successfully.
Implement the FileSharing
class:
FileSharing(int m)
Initializes the object with a file ofm
chunks.int join(int[] ownedChunks)
: A new user joined the system owning some chunks of the file, the system should assign an id to the user which is the smallest positive integer not taken by any other user. Return the assigned id.void leave(int userID)
: The user withuserID
will leave the system, you cannot take file chunks from them anymore.int[] request(int userID, int chunkID)
: The useruserID
requested the file chunk withchunkID
. Return a list of the IDs of all users that own this chunk sorted in ascending order.
Example 1:
|
|
Solution
Method 1 – Hash Map and Min-Heap for User and Chunk Management
Intuition
We need to efficiently assign the smallest available user ID, track which users own which chunks, and support fast join, leave, and request operations. A min-heap allows us to quickly reuse the smallest available user ID, and hash maps allow us to track chunk ownership and user-chunk relationships efficiently.
Approach
- Use a min-heap to store available user IDs for reuse. Track the next new user ID to assign if the heap is empty.
- Use a hash map
chunk_to_users
mapping each chunk ID to a set of user IDs who own it. - Use a hash map
user_to_chunks
mapping each user ID to the set of chunk IDs they own. - On
join(ownedChunks)
, assign the smallest available user ID, add the user to all relevant chunk sets, and return the user ID. - On
leave(userID)
, remove the user from all chunk sets they own, remove the user fromuser_to_chunks
, and add the user ID back to the min-heap. - On
request(userID, chunkID)
, return a sorted list of all user IDs who own the chunk. If the list is non-empty, add the chunk to the requesting user’s set and update the chunk’s user set.
Code
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(k log n)
per operation, wherek
is the number of owners for a chunk andn
is the number of users, due to heap and sorting operations. - 🧺 Space complexity:
O(n + m)
, for user and chunk tracking structures.