Design a File Sharing System — LeetCode 1500 Python Solution

MediumLeetCode PremiumDesignHash TableData StreamSortingHeap (Priority Queue)
Problem
#1500
Reading time
7 min

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

MeasureComplexity
TimeO(n)
SpaceO(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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity — invisible to screen sharing.

Get Stealth Interview