Untitled
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