Design a File Sharing System solution and explanation
9 more videos on this problem
Design Google Drive or Dropbox (Cloud File Sharing Service) | System Design Interview PrepInterview Pen · 28:40 · 94K views
Design file-sharing system like Google Drive / Dropbox (System design interview with EM)IGotAnOffer: Engineering · 48:40 · 56K views
19. Design File System using Composite Design Pattern | Low Level Design Interview Question | LLDConcept && Coding - by Shrayansh · 21:30 · 52K views
DESIGN IN-MEMORY FILE SYSTEM | LEETCODE # 588 | PYTHON SOLUTIONCracking FAANG · 21:37 · 11K views
Google Coding Interview Question | Leetcode 588 | Design In-Memory File SystemWorkWithGoogler · 29:11 · 11K views
[Java] Leetcode 588. Design In-Memory File System [Trie #2]Eric Programming · 16:19 · 9K views
1166 Design File SystemKelvin Chandra · 6:10 · 6K views
Design Dropbox / Google Drive - System Design Interview Question - Cloud File Sharing ServiceTechPrep · 13:29 · 5K views
Amazon Coding Interview Question | Leetcode 1166 | Design File SystemWorkWithGoogler · 20:05 · 4K views
1166. Design File System (LeetCode)hakunamatasq · 6:13 · 2K views
The 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 ofmchunks.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 withuserIDwill leave the system, you cannot take file chunks from them anymore.int[] request(int userID, int chunkID): The useruserIDrequested the file chunk withchunkID. Return a list of the IDs of all users that own this chunk sorted in ascending order.
Example:
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 <= 1050 <= ownedChunks.length <= min(100, m)1 <= ownedChunks[i] <= m- Values of
ownedChunksare unique. 1 <= chunkID <= muserIDis guaranteed to be a user in the system if you assign the IDs correctly.- At most
104calls will be made tojoin,leaveandrequest. - Each call to
leavewill have a matching call forjoin.
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
nfiles where theithfile consists ofm[i], what are the changes you have to make?
Approach overview
Problem Overview: Design a system that tracks which users own specific file chunks. Users can join with a list of chunks, leave the system, and request chunks from others. The system must reuse the smallest available user ID and return a sorted list of users who own a requested chunk.
Approach 1: Naive Simulation with Sorting (O(n log n) per request)
A straightforward implementation stores chunkId -> list of users and userId -> owned chunks using a hash table. When a user joins, assign the next increasing ID and update mappings for each chunk. For request(), iterate through the stored list of users for that chunk and sort the result before returning it. When users leave, remove them from every chunk list they appear in. This works but repeated sorting and list removals make operations expensive, leading to O(n log n) time per request and O(n) space.
Approach 2: Hash Maps + Min Heap for Reusable IDs (O(log n) operations)
The optimized design uses multiple structures working together. Maintain a chunkOwners map from chunk ID to a sorted set of user IDs, and a userChunks map from user ID to the set of chunks they own. To reuse the smallest available ID, maintain a min heap of released IDs. During join(), either pop from the heap or assign the next new ID, then insert the user into every relevant chunk owner set. For leave(), remove the user from all chunk owner sets and push the freed ID back into the heap. During request(), read the sorted owners directly, return them, and if the list is non-empty add the chunk to the requester. Sorted sets eliminate repeated sorting work while the heap guarantees the smallest available ID. Most updates run in O(log n) time with O(n + m) space where n is users and m is chunk relationships.
Recommended for interviews: The hash map + min heap design is the expected solution. It demonstrates strong system simulation skills and efficient data structure choices. A naive simulation shows you understand the mechanics, but interviewers usually expect the optimized version that reuses IDs with a priority queue and avoids repeated sorting.
Solution
class FileSharing:
def __init__(self, m: int):
self.cur = 0
self.chunks = m
self.reused = []
self.user_chunks = defaultdict(set)
def join(self, ownedChunks: List[int]) -> int:
if self.reused:
userID = heappop(self.reused)
else:
self.cur += 1
userID = self.cur
self.user_chunks[userID] = set(ownedChunks)
return userID
def leave(self, userID: int) -> None:
heappush(self.reused, userID)
self.user_chunks.pop(userID)
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)
# Your FileSharing object will be instantiated and called as such:
# obj = FileSharing(m)
# param_1 = obj.join(ownedChunks)
# obj.leave(userID)
# param_3 = obj.request(userID,chunkID)class FileSharing {
private int chunks;
private int cur;
private TreeSet<Integer> reused;
private TreeMap<Integer, Set<Integer>> userChunks;
public FileSharing(int m) {
cur = 0;
chunks = m;
reused = new TreeSet<>();
userChunks = new TreeMap<>();
}
public int join(List<Integer> ownedChunks) {
int userID;
if (reused.isEmpty()) {
++cur;
userID = cur;
} else {
userID = reused.pollFirst();
}
userChunks.put(userID, new HashSet<>(ownedChunks));
return userID;
}
public void leave(int userID) {
reused.add(userID);
userChunks.remove(userID);
}
public List<Integer> request(int userID, int chunkID) {
if (chunkID < 1 || chunkID > chunks) {
return Collections.emptyList();
}
List<Integer> res = new ArrayList<>();
for (Map.Entry<Integer, Set<Integer>> entry : userChunks.entrySet()) {
if (entry.getValue().contains(chunkID)) {
res.add(entry.getKey());
}
}
if (!res.isEmpty()) {
userChunks.computeIfAbsent(userID, k -> new HashSet<>()).add(chunkID);
}
return res;
}
}
/**
* Your FileSharing object will be instantiated and called as such:
* FileSharing obj = new FileSharing(m);
* int param_1 = obj.join(ownedChunks);
* obj.leave(userID);
* List<Integer> param_3 = obj.request(userID,chunkID);
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation with Lists | O(n log n) per request | O(n) | Simple implementation when constraints are small and sorting overhead is acceptable |
| Hash Maps + Sorted Sets + Min Heap | O(log n) per update | O(n + m) | Best general solution for large systems where IDs must be reused and chunk owners must stay sorted |
Frequently asked questions
Is Design a File Sharing System easy or hard?
Design a File Sharing System is considered a Medium problem on LeetCode. The difficulty comes from coordinating multiple data structures and correctly handling edge cases like ID reuse, user removal, and maintaining sorted chunk owner lists.
Design a File Sharing System Python/Java solution
Python implementations typically use dictionaries for mappings and heapq for the priority queue, while Java solutions use HashMap, HashSet, and PriorityQueue. TreeSet or sorting logic is used to keep chunk owner lists ordered when returning results.
How to solve Design a File Sharing System in O(log n)?
Maintain three structures: a hash map from chunkId to a sorted set of user IDs, a hash map from userId to owned chunks, and a min heap for reusable IDs. When users join, assign the smallest available ID from the heap or increment a counter. Updates to chunk ownership and heap operations keep all major operations around O(log n).
What is the best approach for Design a File Sharing System?
The most efficient solution uses hash maps to track user-to-chunk and chunk-to-user relationships, combined with a min heap to reuse the smallest available user ID. Chunk owners are stored in sorted sets so the system can return users in ascending order without extra sorting. This design supports join, leave, and request operations in about O(log n) time.
Is Design a File Sharing System asked at Google/Amazon/Meta?
Design-style data structure problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. They evaluate your ability to combine multiple structures such as hash tables, heaps, and ordered sets while maintaining efficient updates and queries.
What data structure is used in Design a File Sharing System?
The typical solution uses hash tables for fast lookups, a min heap (priority queue) to track reusable user IDs, and sorted sets or balanced trees to keep chunk owners ordered. These structures allow efficient joins, removals, and sorted retrieval of chunk owners.
What is the time complexity of Design a File Sharing System?
Using the optimized design with hash maps and a min heap, most operations run in O(log n) time due to heap and ordered set updates. Accessing mappings is O(1) on average with hash tables. Space complexity is O(n + m), where n is the number of users and m is the total number of chunk ownership relationships.