Untitled

 avatar
unknown
plain_text
a year ago
4.7 kB
4
Indexable
class UserSolution {

    class FileRequest {
        int userID;
        String fileName;
        int fileSize;
        ArrayList<Integer> path;

        FileRequest(int userID, String fileName, int fileSize) {
            this.userID = userID;
            this.fileName = fileName;
            this.fileSize = fileSize;
            path = new ArrayList<>();
        }
    }

    class NetworkUser {
        ArrayList<Integer> connectedUsers;
        HashMap<String, Boolean> sharedFiles;

        NetworkUser() {
            connectedUsers = new ArrayList<>();
            sharedFiles = new HashMap<>();
        }
    }

    String convertToString(char[] characters) {
        int index = 0;
        StringBuilder result = new StringBuilder();
        while (characters[index] != 0) {
            result.append(characters[index++]);
        }
        return result.toString();
    }

    NetworkUser[] users = new NetworkUser[205];
    FileRequest[] fileRequests = new FileRequest[5005];
    int[][] networkBandwidth = new int[205][205];
    HashMap<String, Integer> fileSizes = new HashMap<>();
    int totalUsers;

    public void init(int totalUsers, int user1IDs[], int user2IDs[], int bandwidths[]) {
        this.totalUsers = totalUsers;
        fileSizes.clear();

        for (int i = 0; i <= totalUsers; i++)
            users[i] = new NetworkUser();

        for (int i = 0; i < totalUsers; i++) {
            int id1 = user1IDs[i];
            int id2 = user2IDs[i];
            networkBandwidth[id1][id2] = bandwidths[i];
            networkBandwidth[id2][id1] = bandwidths[i];

            users[id1].connectedUsers.add(id2);
            users[id2].connectedUsers.add(id1);
        }
    }

    public int share(int userID, char fileName[], int fileSize) {
        String fileKey = convertToString(fileName);
        fileSizes.put(fileKey, fileSize);
        users[userID].sharedFiles.put(fileKey, true);
        return users[userID].sharedFiles.size();
    }

    public int request(int userID, char fileName[], int requestID) {
        String fileKey = convertToString(fileName);
        if (fileSizes.get(fileKey) == null)
            return -1;
        int fileSize = fileSizes.get(fileKey);

        boolean found = false;
        int visited[] = new int[205];
        int parent[] = new int[205];
        LinkedList<Integer> queue = new LinkedList<>();
        int answer = 205;

        // BFS
        queue.add(userID);
        visited[userID] = 1;
        parent[userID] = -1;

        while (!queue.isEmpty()) {
            if (found)
                break;
            int size = queue.size();
            while (size > 0) {
                int currentUser = queue.poll();
                for (int connectedUser : users[currentUser].connectedUsers) {
                    if (visited[connectedUser] == 0 && networkBandwidth[currentUser][connectedUser] >= fileSize) {
                        visited[connectedUser] = 1;
                        parent[connectedUser] = currentUser;
                        queue.add(connectedUser);
                        boolean hasFile = users[connectedUser].sharedFiles.getOrDefault(fileKey, false);
                        if (hasFile) {
                            found = true;
                            answer = Math.min(answer, connectedUser);
                        }
                    }
                }
                size--;
            }
        }

        // Check if user with file is found and save the path
        if (!found)
            return -1;

        fileRequests[requestID] = new FileRequest(userID, fileKey, fileSize);

        int temp = answer;
        while (parent[temp] != -1) {
            fileRequests[requestID].path.add(temp);
            networkBandwidth[temp][parent[temp]] -= fileSize;
            networkBandwidth[parent[temp]][temp] -= fileSize;
            temp = parent[temp];
        }
        fileRequests[requestID].path.add(userID);

        return answer;
    }

    public int complete(int requestID) {
        int userID = fileRequests[requestID].userID;
        String fileKey = fileRequests[requestID].fileName;

        for (int i = 0; i < fileRequests[requestID].path.size() - 1; i++) {
            int currentUser = fileRequests[requestID].path.get(i);
            int nextUser = fileRequests[requestID].path.get(i + 1);
            networkBandwidth[currentUser][nextUser] += fileRequests[requestID].fileSize;
            networkBandwidth[nextUser][currentUser] += fileRequests[requestID].fileSize;
            users[currentUser].sharedFiles.put(fileKey, true);
        }
        users[userID].sharedFiles.put(fileKey, true);

        return users[userID].sharedFiles.size();
    }
}
Editor is loading...
Leave a Comment