Design a File Sharing System

Design a File Sharing System

1. What is this problem about?

The Design a File Sharing System interview question requires you to implement a peer-to-peer ID management system. Users join the system and are assigned the smallest available unique ID. Users can also leave, making their ID available for reuse. Additionally, the system tracks which users own which "chunks" of a file, allowing users to request chunk ownership data and "download" chunks from others.

2. Why is this asked in interviews?

Twitch asks this to evaluate a candidate's ability to manage state and resources. It tests your proficiency with Heap (Priority Queue) interview patterns for ID reuse and Hash Table interview patterns for mapping file chunks to users. It's a great test of clean API design and efficient data organization.

3. Algorithmic pattern used

• ID Management: Use a Min-Heap to store "released" IDs. Use a simple counter for the next new ID if the heap is empty.
• Ownership Tracking: Use a Map<Integer, Set<Integer>> where the key is the user ID and the value is a set of chunks they own.
• Chunk Lookup: To find who has a chunk, you might need another Map<Integer, Set<Integer>> (Chunk ID -> User IDs).

4. Example explanation

1. User A joins: Assigned ID 1.
2. User B joins: Assigned ID 2.
3. User A leaves: ID 1 is pushed onto the min-heap.
4. User C joins: System pops from heap, assigns ID 1.
5. request(chunk: 5): System looks up the chunk map and returns [1, 2] if users 1 and 2 have it. User C (ID 1) then "downloads" it and is added to the chunk 5 ownership list.

5. Common mistakes candidates make

• Linear ID Search: Iterating through an array to find the smallest available ID ($O(N)$), when a heap can do it in $O(\log N)$.
• Incomplete Cleanup: Failing to remove a user's chunk ownership from all relevant maps when that user leaves the system.
• Slow Chunk Queries: Not maintaining a reverse mapping (Chunk -> Users), leading to $O( ext{Users})$ search time per request.

6. Interview preparation tip

Think of this as a "Service Design" problem. Modularize your logic: have one part handle IDs and another handle data ownership. This makes the code easier to extend, such as if the system later needs to handle multiple different files.