Design a File Sharing System - Practice Coding Problems

Design a File Sharing System - Problem

Design 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.

Input & Output

Example 1 — Basic Operations

$ Input: FileSharing(4), join([1,2]), join([2,3]), request(1,2), leave(1), join([4])

› Output: [null,1,2,[1,2],null,1]

💡 Note: Initialize with 4 chunks. User 1 joins with chunks [1,2], gets ID 1. User 2 joins with chunks [2,3], gets ID 2. User 1 requests chunk 2, returns [1,2] (both users have it). User 1 leaves, ID 1 becomes available. New user joins with chunk [4], gets reused ID 1.

Example 2 — ID Reuse

$ Input: FileSharing(3), join([1]), join([2]), leave(1), join([3])

› Output: [null,1,2,null,1]

💡 Note: Two users join and get IDs 1,2. User 1 leaves, making ID 1 available. Next user gets the smallest available ID which is 1 (reused).

Example 3 — Empty Request

$ Input: FileSharing(2), join([1]), request(1,2)

› Output: [null,1,[]]

💡 Note: User 1 has chunk 1 but requests chunk 2. Since no one owns chunk 2, return empty list and user doesn't get the chunk.

Constraints

1 ≤ m ≤ 10⁵
0 ≤ ownedChunks.length ≤ 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 ID to them
At most 10⁴ calls will be made to join, leave and request

Visualization

Tap to expand

Understanding the Visualization

System Setup

Initialize with m chunks and prepare for user management

User Operations

Handle join (assign IDs), leave (free IDs), and request (find owners)

Efficient Sharing

Return sorted list of users who own requested chunks

Key Takeaway

🎯 Key Insight: Use hash maps for bidirectional lookups and min-heap for optimal ID management to achieve fast operations in a scalable file sharing system

Asked in

G Google 15 a Amazon 12 M Microsoft 8 D Dropbox 10

The key insight is to use hash maps for O(1) lookups and a min-heap for efficient ID reuse. Best approach uses bidirectional mappings (user→chunks and chunk→users) with priority queue for smallest available ID. Time: O(log k + c), Space: O(nm + mc).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Linear Search	O(n)	O(nm)	Store user chunks in simple arrays and search linearly for available IDs and chunk owners
Hash Map with Min-Heap for ID Reuse	O(log k + c)	O(nm + mc)	Use hash maps for O(1) lookups and min-heap for efficient ID management

Brute Force with Linear Search — Algorithm Steps

Store user chunks in a simple array structure
For join: scan all IDs linearly to find smallest available
For request: scan all users to find who owns the chunk
For leave: mark user as inactive

Visualization

Tap to expand

Step-by-Step Walkthrough

Join User

Scan all IDs 1,2,3... to find smallest available

Store Chunks

Store user's owned chunks in simple array

Request Chunk

Scan all users to find who owns the requested chunk

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_USERS 1000
#define MAX_CHUNKS 1000

typedef struct {
    int m;
    int userChunks[MAX_USERS][MAX_CHUNKS];
    int userChunkCount[MAX_USERS];
    int nextId;
    int availableIds[MAX_USERS];
    int availableCount;
    int userExists[MAX_USERS];
} FileSharing;

FileSharing* fileSharingCreate(int m) {
    FileSharing* fs = (FileSharing*)malloc(sizeof(FileSharing));
    fs->m = m;
    fs->nextId = 1;
    fs->availableCount = 0;
    memset(fs->userChunkCount, 0, sizeof(fs->userChunkCount));
    memset(fs->userExists, 0, sizeof(fs->userExists));
    return fs;
}

int fileSharingJoin(FileSharing* obj, int* ownedChunks, int ownedChunksSize) {
    int userId;
    if (obj->availableCount > 0) {
        userId = obj->availableIds[0];
        for (int i = 0; i < obj->availableCount; i++) {
            if (obj->availableIds[i] < userId) {
                userId = obj->availableIds[i];
            }
        }
        
        int newCount = 0;
        for (int i = 0; i < obj->availableCount; i++) {
            if (obj->availableIds[i] != userId) {
                obj->availableIds[newCount++] = obj->availableIds[i];
            }
        }
        obj->availableCount = newCount;
    } else {
        userId = obj->nextId++;
    }
    
    for (int i = 0; i < ownedChunksSize; i++) {
        obj->userChunks[userId][i] = ownedChunks[i];
    }
    obj->userChunkCount[userId] = ownedChunksSize;
    obj->userExists[userId] = 1;
    return userId;
}

void fileSharingLeave(FileSharing* obj, int userID) {
    if (obj->userExists[userID]) {
        obj->userExists[userID] = 0;
        obj->userChunkCount[userID] = 0;
        obj->availableIds[obj->availableCount++] = userID;
    }
}

int* fileSharingRequest(FileSharing* obj, int userID, int chunkID, int* returnSize) {
    int* owners = (int*)malloc(MAX_USERS * sizeof(int));
    int count = 0;
    
    for (int uid = 1; uid < obj->nextId; uid++) {
        if (obj->userExists[uid]) {
            for (int i = 0; i < obj->userChunkCount[uid]; i++) {
                if (obj->userChunks[uid][i] == chunkID) {
                    owners[count++] = uid;
                    break;
                }
            }
        }
    }
    
    if (count > 0 && obj->userExists[userID]) {
        obj->userChunks[userID][obj->userChunkCount[userID]++] = chunkID;
    }
    
    *returnSize = count;
    return owners;
}

FileSharing* solution(int m) {
    return fileSharingCreate(m);
}

int main() {
    int m;
    scanf("%d", &m);
    FileSharing* fs = solution(m);
    printf("null\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each join and request operation requires linear scan through all users

✓ Linear Growth

Space Complexity

O(nm)

Store chunks for each user, worst case all users own all chunks

⚡ Linearithmic Space

18.2K Views

Medium Frequency

~35 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler