Design a File Sharing System

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 of m 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 with userID will leave the system, you cannot take file chunks from them anymore.
int[] request(int userID, int chunkID): The user userID requested the file chunk with chunkID. Return a list of the IDs of all users that own this chunk sorted in ascending order.

Example 1:

 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


Input:
["FileSharing","join","join","join","request","request","leave","request","leave","join"]
[[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]]
Output:
[null,1,2,3,[2],[1,2],null,[],null,1]
Explanation:
FileSharing fileSharing = new FileSharing(4); // We use the system to share a file of 4 chunks.
fileSharing.join([1, 2]);    // A user who has chunks [1,2] joined the system, assign id = 1 to them and return 1.
fileSharing.join([2, 3]);    // A user who has chunks [2,3] joined the system, assign id = 2 to them and return 2.
fileSharing.join([4]);       // A user who has chunk [4] joined the system, assign id = 3 to them and return 3.
fileSharing.request(1, 3);   // The user with id = 1 requested the third file chunk, as only the user with id = 2 has the file, return [2] . Notice that user 1 now has chunks [1,2,3].
fileSharing.request(2, 2);   // The user with id = 2 requested the second file chunk, users with ids [1,2] have this chunk, thus we return [1,2].
fileSharing.leave(1);        // The user with id = 1 left the system, all the file chunks with them are no longer available for other users.
fileSharing.request(2, 1);   // The user with id = 2 requested the first file chunk, no one in the system has this chunk, we return empty list [].
fileSharing.leave(2);        // The user with id = 2 left the system.
fileSharing.join([]);        // A user who doesn't have any chunks joined the system, assign id = 1 to them and return 1. Notice that ids 1 and 2 are free and we can reuse them.
**Constraints:**
* `1 <= m <= 10^5`
* `0 <= ownedChunks.length <= min(100, m)`
* `1 <= ownedChunks[i] <= m`
* Values of `ownedChunks` are unique.
* `1 <= chunkID <= m`
* `userID` is guaranteed to be a user in the system if you **assign** the IDs **correctly**.
* At most `104` calls will be made to `join`, `leave` and `request`.
* Each call to `leave` will have a matching call for `join`.
**Follow-up:**
* What happens if the system identifies the user by their IP address instead of their unique ID and users disconnect and connect from the system with the same IP?
* If the users in the system join and leave the system frequently without requesting any chunks, will your solution still be efficient?
* If all users join the system one time, request all files, and then leave, will your solution still be efficient?
* If the system will be used to share `n` files where the `ith` file consists of `m[i]`, what are the changes you have to make?

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 from user_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

 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


import heapq
from collections import defaultdict
class FileSharing:
    def __init__(self, m: int):
        self.m = m
        self.next_id = 1
        self.available = []  # min-heap for reusable user IDs
        self.chunk_to_users = defaultdict(set)  # chunkID -> set of userIDs
        self.user_to_chunks = defaultdict(set)  # userID -> set of chunkIDs
    def join(self, ownedChunks: list[int]) -> int:
        if self.available:
            uid = heapq.heappop(self.available)
        else:
            uid = self.next_id
            self.next_id += 1
        for c in ownedChunks:
            self.chunk_to_users[c].add(uid)
        self.user_to_chunks[uid] = set(ownedChunks)
        return uid
    def leave(self, userID: int) -> None:
        for c in self.user_to_chunks[userID]:
            self.chunk_to_users[c].discard(userID)
            if not self.chunk_to_users[c]:
                del self.chunk_to_users[c]
        del self.user_to_chunks[userID]
        heapq.heappush(self.available, userID)
    def request(self, userID: int, chunkID: int) -> list[int]:
        owners = sorted(self.chunk_to_users.get(chunkID, set()))
        if owners:
            self.chunk_to_users[chunkID].add(userID)
            self.user_to_chunks[userID].add(chunkID)
        return owners

 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


#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
class FileSharing {
    int m, next_id;
    priority_queue<int, vector<int>, greater<int>> available;
    unordered_map<int, unordered_set<int>> chunk_to_users;
    unordered_map<int, unordered_set<int>> user_to_chunks;
public:
    FileSharing(int m): m(m), next_id(1) {}
    int join(vector<int> ownedChunks) {
        int uid;
        if (!available.empty()) {
            uid = available.top(); available.pop();
        } else {
            uid = next_id++;
        }
        for (int c : ownedChunks) chunk_to_users[c].insert(uid);
        user_to_chunks[uid] = unordered_set<int>(ownedChunks.begin(), ownedChunks.end());
        return uid;
    }
    void leave(int userID) {
        for (int c : user_to_chunks[userID]) {
            chunk_to_users[c].erase(userID);
            if (chunk_to_users[c].empty()) chunk_to_users.erase(c);
        }
        user_to_chunks.erase(userID);
        available.push(userID);
    }
    vector<int> request(int userID, int chunkID) {
        vector<int> owners(chunk_to_users[chunkID].begin(), chunk_to_users[chunkID].end());
        sort(owners.begin(), owners.end());
        if (!owners.empty()) {
            chunk_to_users[chunkID].insert(userID);
            user_to_chunks[userID].insert(chunkID);
        }
        return owners;
    }
};

 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


import java.util.*;
public class FileSharing {
    private int m, nextId = 1;
    private PriorityQueue<Integer> available = new PriorityQueue<>();
    private Map<Integer, Set<Integer>> chunkToUsers = new HashMap<>();
    private Map<Integer, Set<Integer>> userToChunks = new HashMap<>();
    public FileSharing(int m) {
        this.m = m;
    }
    public int join(int[] ownedChunks) {
        int uid = available.isEmpty() ? nextId++ : available.poll();
        Set<Integer> chunks = new HashSet<>();
        for (int c : ownedChunks) {
            chunkToUsers.computeIfAbsent(c, k -> new HashSet<>()).add(uid);
            chunks.add(c);
        }
        userToChunks.put(uid, chunks);
        return uid;
    }
    public void leave(int userID) {
        for (int c : userToChunks.get(userID)) {
            Set<Integer> users = chunkToUsers.get(c);
            users.remove(userID);
            if (users.isEmpty()) chunkToUsers.remove(c);
        }
        userToChunks.remove(userID);
        available.offer(userID);
    }
    public int[] request(int userID, int chunkID) {
        Set<Integer> owners = chunkToUsers.getOrDefault(chunkID, Collections.emptySet());
        int[] arr = owners.stream().sorted().mapToInt(i -> i).toArray();
        if (arr.length > 0) {
            chunkToUsers.computeIfAbsent(chunkID, k -> new HashSet<>()).add(userID);
            userToChunks.computeIfAbsent(userID, k -> new HashSet<>()).add(chunkID);
        }
        return arr;
    }
}

 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


import (
    "container/heap"
    "sort"
)
type FileSharing struct {
    m int
    nextId int
    available IntHeap
    chunkToUsers map[int]map[int]struct{}
    userToChunks map[int]map[int]struct{}
}
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}
func Constructor(m int) FileSharing {
    return FileSharing{
        m: m,
        nextId: 1,
        available: IntHeap{},
        chunkToUsers: map[int]map[int]struct{}{},
        userToChunks: map[int]map[int]struct{}{},
    }
}
func (fs *FileSharing) Join(ownedChunks []int) int {
    var uid int
    if len(fs.available) > 0 {
        heap.Init(&fs.available)
        uid = heap.Pop(&fs.available).(int)
    } else {
        uid = fs.nextId
        fs.nextId++
    }
    fs.userToChunks[uid] = map[int]struct{}{}
    for _, c := range ownedChunks {
        if fs.chunkToUsers[c] == nil {
            fs.chunkToUsers[c] = map[int]struct{}{}
        }
        fs.chunkToUsers[c][uid] = struct{}{}
        fs.userToChunks[uid][c] = struct{}{}
    }
    return uid
}
func (fs *FileSharing) Leave(userID int) {
    for c := range fs.userToChunks[userID] {
        delete(fs.chunkToUsers[c], userID)
        if len(fs.chunkToUsers[c]) == 0 {
            delete(fs.chunkToUsers, c)
        }
    }
    delete(fs.userToChunks, userID)
    heap.Push(&fs.available, userID)
}
func (fs *FileSharing) Request(userID, chunkID int) []int {
    owners := []int{}
    for uid := range fs.chunkToUsers[chunkID] {
        owners = append(owners, uid)
    }
    sort.Ints(owners)
    if len(owners) > 0 {
        fs.chunkToUsers[chunkID][userID] = struct{}{}
        fs.userToChunks[userID][chunkID] = struct{}{}
    }
    return owners
}

Complexity

⏰ Time complexity: O(k log n) per operation, where k is the number of owners for a chunk and n is the number of users, due to heap and sorting operations.
🧺 Space complexity: O(n + m), for user and chunk tracking structures.

Problem#

Example 1:#

Solution#

Method 1 – Hash Map and Min-Heap for User and Chunk Management#

Intuition#

Approach#

Code#

Complexity#