Design a File Sharing System — LeetCode 1500 Python Solution
MediumLeetCode PremiumDesignHash TableData StreamSortingHeap (Priority Queue)
- Problem
- #1500
- Pattern
- Heap / Priority Queue
- Reading time
- 7 min
- Source
- leetcode.com
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.
Example
- Input
- ["FileSharing","join","join","join","request","request","leave","request","leave","join"]
- 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.
Python solution
Python
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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1500. Design a File Sharing System is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1500. Design a File Sharing System?
- LeetCode 1500. Design a File Sharing System is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1500. Design a File Sharing System?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1500. Design a File Sharing System?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1500. Design a File Sharing System cover?
- LeetCode 1500. Design a File Sharing System is tagged Design, Hash Table, Data Stream, Sorting and Heap (Priority Queue) on LeetCode.
- Is LeetCode 1500. Design a File Sharing System a premium problem?
- Yes. LeetCode 1500. Design a File Sharing System is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.