Problem Description

This problem asks you to design a file-sharing system that manages users and file chunks. The system needs to handle three main operations:

System Overview:

• A large file is divided into m chunks, numbered from 1 to m
• Users can join the system with certain chunks they already own
• Users can request chunks from other users
• Users can leave the system

Key Requirements:

1. User ID Management:

   • When a user joins, assign them the smallest available positive integer ID
   • IDs start from 1 and increment
   • When a user leaves, their ID becomes available for reuse
   • Reused IDs should be assigned before creating new higher IDs

2. Operations to Implement:

   • FileSharing(m): Initialize the system with a file containing m chunks
   • join(ownedChunks): Register a new user who owns the specified chunks, return their assigned ID
   • leave(userID): Remove a user from the system, making their ID available for reuse
   • request(userID, chunkID): User requests a specific chunk
     • Returns a sorted list of all user IDs who own that chunk
     • If the list is non-empty (meaning the chunk was found), the requesting user also receives the chunk

Example Walkthrough:

• User joins with chunks [1,2] → gets ID 1
• User joins with chunks [2,3] → gets ID 2
• User joins with chunk [4] → gets ID 3
• User 1 requests chunk 3 → gets [2] (only user 2 has it), now user 1 has chunks [1,2,3]
• User 2 requests chunk 2 → gets [1,2] (both users have it)
• User 1 leaves → ID 1 becomes available
• User 2 requests chunk 1 → gets [] (no one has it after user 1 left)
• New user joins → gets ID 1 (reused)

The solution uses a min-heap to efficiently track and reuse the smallest available user IDs, and a dictionary to map each user to their set of owned chunks. When requesting a chunk, it searches through all users to find owners and automatically adds the chunk to the requester if found.

Intuition

The key insight is that we need to efficiently manage two things: user IDs and chunk ownership. Let's think through each requirement:

For User ID Assignment: We need to always assign the smallest available ID. Initially, this seems simple - just use a counter starting at 1. But the challenge comes when users leave and we need to reuse their IDs. If users 1, 2, 3 exist and user 2 leaves, the next user should get ID 2, not ID 4.

This naturally leads us to use a min-heap to track available IDs. When a user leaves, we push their ID into the heap. When a new user joins, we first check if there are any reusable IDs in the heap (take the smallest one), otherwise increment our counter for a new ID.

For Chunk Ownership Tracking: We need to quickly answer "which users own chunk X?" and also track what chunks each user owns. A dictionary mapping user IDs to sets of chunks works perfectly here:

• user_chunks[userID] gives us all chunks a user owns
• To find who owns a specific chunk, we iterate through all users and check if the chunk is in their set

Using a set for each user's chunks makes sense because:

• Checking if a user owns a chunk is O(1)
• Adding a new chunk when a request succeeds is O(1)
• The problem guarantees owned chunks are unique per user

For the Request Operation: When a user requests a chunk, we need to:

1. Find all users who own it (iterate through our dictionary)
2. If found, give the chunk to the requesting user
3. Return the sorted list of owners

The sorting requirement at the end is straightforward - we collect all owner IDs in a list and sort before returning.

This approach balances simplicity with efficiency - we're not over-engineering with complex data structures, but we're using the right tools (heap for ID management, dictionary with sets for ownership) to make operations reasonably fast.

Learn more about Data Stream, Sorting and Heap (Priority Queue) patterns.

Solution Approach

Let's walk through the implementation step by step:

Data Structure Setup:

def __init__(self, m: int):
    self.cur = 0                    # Track the highest ID assigned so far
    self.chunks = m                 # Total number of chunks in the file
    self.reused = []                # Min-heap for reusable IDs
    self.user_chunks = defaultdict(set)  # Map userID -> set of owned chunks

We initialize four instance variables:

• cur: Counter for the next new ID to assign (when no reused IDs are available)
• chunks: Store the total number of chunks for validation
• reused: Min-heap to efficiently get the smallest reusable ID
• user_chunks: Dictionary mapping each user to their set of owned chunks

Join Operation:

def join(self, ownedChunks: List[int]) -> int:
    if self.reused:
        userID = heappop(self.reused)  # Reuse smallest available ID
    else:
        self.cur += 1
        userID = self.cur              # Assign new ID
    self.user_chunks[userID] = set(ownedChunks)
    return userID

The algorithm follows this logic:

1. Check if there are any reusable IDs in the heap
2. If yes, pop the smallest one (min-heap property guarantees this)
3. If no, increment cur and use it as the new ID
4. Store the user's chunks as a set in our dictionary
5. Return the assigned ID

Leave Operation:

def leave(self, userID: int) -> None:
    heappush(self.reused, userID)      # Make ID available for reuse
    self.user_chunks.pop(userID)       # Remove user's chunk ownership

When a user leaves:

1. Push their ID into the reused heap for future assignment
2. Remove their entry from the user_chunks dictionary

Request Operation:

def request(self, userID: int, chunkID: int) -> List[int]:
    if chunkID < 1 or chunkID > self.chunks:
        return []
    res = []
    for k, v in self.user_chunks.items():
        if chunkID in v:
            res.append(k)
    if res:
        self.user_chunks[userID].add(chunkID)
    return sorted(res)

The request logic:

1. First validate the chunk ID is within valid range [1, m]
2. Iterate through all users in the system
3. For each user, check if they own the requested chunk (O(1) set lookup)
4. Collect all user IDs who own the chunk
5. If at least one user owns it (non-empty result), add the chunk to the requester's set
6. Return the sorted list of owner IDs

Time Complexity Analysis:

• join: O(log k) where k is the number of reused IDs, due to heap operations
• leave: O(log k) for heap push operation
• request: O(n + n log n) where n is the number of users, for iterating through all users and sorting the result

Space Complexity:

• O(n × c) where n is the number of users and c is the average number of chunks per user
• Additional O(k) for the reused IDs heap

The solution elegantly handles ID reuse with a min-heap while maintaining efficient chunk ownership queries using sets, providing a good balance between implementation simplicity and performance.

Example Walkthrough

Let's trace through a small example to see how the solution works:

Initial Setup: FileSharing(4) - System initialized with 4 chunks

• cur = 0, reused = [] (empty heap), user_chunks = {} (empty dict)

Step 1: User joins with chunks [1, 3]

• Check reused heap - it's empty
• Increment cur to 1, assign userID = 1
• Store user_chunks[1] = {1, 3}
• Return 1

State: cur = 1, reused = [], user_chunks = {1: {1, 3}}

Step 2: User joins with chunks [2]

• Check reused heap - still empty
• Increment cur to 2, assign userID = 2
• Store user_chunks[2] = {2}
• Return 2

State: cur = 2, reused = [], user_chunks = {1: {1, 3}, 2: {2}}

Step 3: User 1 requests chunk 2

• Iterate through all users:
  • User 1: chunk 2 not in {1, 3}
  • User 2: chunk 2 IS in {2} ✓
• Result list = [2]
• Since result is non-empty, add chunk 2 to user 1: user_chunks[1] = {1, 2, 3}
• Return sorted([2]) = [2]

State: user_chunks = {1: {1, 2, 3}, 2: {2}}

Step 4: User 2 leaves

• Push userID 2 into reused heap: heappush(reused, 2)
• Remove user 2: user_chunks.pop(2)

State: cur = 2, reused = [2], user_chunks = {1: {1, 2, 3}}

Step 5: New user joins with chunks [4]

• Check reused heap - contains [2]
• Pop smallest ID: userID = heappop(reused) = 2 (ID reused!)
• Store user_chunks[2] = {4}
• Return 2

State: cur = 2, reused = [], user_chunks = {1: {1, 2, 3}, 2: {4}}

Step 6: User 2 requests chunk 3

• Iterate through all users:
  • User 1: chunk 3 IS in {1, 2, 3} ✓
  • User 2: chunk 3 not in {4}
• Result list = [1]
• Since result is non-empty, add chunk 3 to user 2: user_chunks[2] = {3, 4}
• Return sorted([1]) = [1]

Final State: user_chunks = {1: {1, 2, 3}, 2: {3, 4}}

This example demonstrates:

• How the min-heap ensures we reuse the smallest available ID (user 2's ID was reused)
• How chunk ownership is tracked with sets for O(1) lookup
• How successful requests automatically grant the chunk to the requester
• How the system maintains sorted order in request results

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(m): O(1) - Simply initializes variables with constant time operations.
• join(ownedChunks): O(k + log n) where k is the length of ownedChunks and n is the number of reused user IDs in the heap. The heap operation heappop takes O(log n) time, and creating a set from ownedChunks takes O(k) time.
• leave(userID): O(log n) where n is the number of reused user IDs. The heappush operation takes O(log n) time, and dictionary pop is O(1).
• request(userID, chunkID): O(u) where u is the total number of active users. We iterate through all users in user_chunks to find those who own the chunk, which takes O(u) time. The set membership check (chunkID in v) is O(1) for each user. Sorting the result takes O(u log u) in the worst case when all users have the chunk, but since we're iterating through all users anyway, the overall complexity is O(u log u).

Space Complexity:

• Overall space: O(u * c) where u is the number of active users and c is the average number of chunks per user.
• self.reused: O(n) where n is the number of left users (reused IDs in the heap).
• self.user_chunks: O(u * c) where u is the number of active users and c is the average number of chunks each user owns.
• The maximum possible space would be O(u * m) if all users own all chunks, where m is the total number of chunks.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Cases in Request Method

A common mistake is forgetting to handle the case where the requesting user already owns the chunk they're requesting. This could lead to duplicate additions or incorrect return values.

Pitfall Example:

def request(self, userID: int, chunkID: int) -> List[int]:
    users_with_chunk = []
    for user_id, owned_chunks in self.user_to_chunks.items():
        if chunkID in owned_chunks:
            users_with_chunk.append(user_id)
  
    # Bug: Always adds chunk even if user already has it
    if users_with_chunk:
        self.user_to_chunks[userID].add(chunkID)  # Set handles duplicates, but logic is unclear
  
    return sorted(users_with_chunk)

Better Approach:

def request(self, userID: int, chunkID: int) -> List[int]:
    if chunkID < 1 or chunkID > self.total_chunks:
        return []
  
    users_with_chunk = []
    already_has_chunk = False
  
    for user_id, owned_chunks in self.user_to_chunks.items():
        if chunkID in owned_chunks:
            users_with_chunk.append(user_id)
            if user_id == userID:
                already_has_chunk = True
  
    # Only add if user doesn't already have it and someone else does
    if users_with_chunk and not already_has_chunk:
        self.user_to_chunks[userID].add(chunkID)
  
    return sorted(users_with_chunk)

2. Incorrect User ID Reuse Logic

Many implementations fail to properly manage the reusable ID pool, especially when dealing with consecutive leave/join operations.

Pitfall Example:

def join(self, ownedChunks: List[int]) -> int:
    # Bug: Not using a min-heap, just a list
    if self.reusable_user_ids:
        user_id = self.reusable_user_ids.pop()  # Gets last element, not smallest!
    else:
        self.current_max_user_id += 1
        user_id = self.current_max_user_id
  
    self.user_to_chunks[user_id] = set(ownedChunks)
    return user_id

Correct Implementation:

def join(self, ownedChunks: List[int]) -> int:
    # Properly use heappop to get smallest ID
    if self.reusable_user_ids:
        user_id = heappop(self.reusable_user_ids)
    else:
        self.current_max_user_id += 1
        user_id = self.current_max_user_id
  
    self.user_to_chunks[user_id] = set(ownedChunks)
    return user_id

3. Memory Leak from Not Cleaning Up After Leave

Forgetting to remove user data when they leave can cause memory leaks and incorrect results in future requests.

Pitfall Example:

def leave(self, userID: int) -> None:
    heappush(self.reusable_user_ids, userID)
    # Bug: Forgot to remove user's chunks!
    # self.user_to_chunks still contains userID's data

Correct Implementation:

def leave(self, userID: int) -> None:
    heappush(self.reusable_user_ids, userID)
    # Must remove user's data to prevent memory leak and wrong results
    if userID in self.user_to_chunks:
        del self.user_to_chunks[userID]

4. Not Validating Chunk IDs

Failing to validate chunk IDs can lead to storing invalid chunks or returning incorrect results.

Pitfall Example:

def request(self, userID: int, chunkID: int) -> List[int]:
    # Bug: No validation of chunkID
    users_with_chunk = []
    for user_id, owned_chunks in self.user_to_chunks.items():
        if chunkID in owned_chunks:
            users_with_chunk.append(user_id)
  
    if users_with_chunk:
        self.user_to_chunks[userID].add(chunkID)  # Could add invalid chunk!
  
    return sorted(users_with_chunk)

5. Using List Instead of Set for Chunk Storage

Using a list to store chunks leads to O(n) lookup time and potential duplicates.

Pitfall Example:

def __init__(self, m: int):
    self.user_to_chunks = defaultdict(list)  # Bug: Using list instead of set

def join(self, ownedChunks: List[int]) -> int:
    # ...
    self.user_to_chunks[user_id] = ownedChunks  # O(n) lookups later!

Correct Approach:

def __init__(self, m: int):
    self.user_to_chunks = defaultdict(set)  # Use set for O(1) lookups

def join(self, ownedChunks: List[int]) -> int:
    # ...
    self.user_to_chunks[user_id] = set(ownedChunks)  # Convert to set