Approach
Breadth-first search
For Design a File Sharing System, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 38 lines of Java from the credited upstream file 1500.java.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup, work queue.
- 2 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class FileSharing {2 public FileSharing(int m) {}3 4 public int join(List<Integer> ownedChunks) {5 final int userId =6 availableUserIds.isEmpty() ? userToChunks.size() + 1 : availableUserIds.poll();7 userToChunks.put(userId, new HashSet<>(ownedChunks));8 for (final int chunk : ownedChunks) {9 chunkToUsers.putIfAbsent(chunk, new TreeSet<>());10 chunkToUsers.get(chunk).add(userId);11 }12 return userId;13 }14 15 public void leave(int userID) {16 for (final int chunk : userToChunks.get(userID)) {17 chunkToUsers.get(chunk).remove(userID);18 if (chunkToUsers.get(chunk).isEmpty())19 chunkToUsers.remove(chunk);20 }21 userToChunks.remove(userID);22 availableUserIds.offer(userID);23 }24 25 public List<Integer> request(int userID, int chunkID) {26 if (!chunkToUsers.containsKey(chunkID))27 return new ArrayList<>();28 List<Integer> userIds = new ArrayList<>(chunkToUsers.get(chunkID));29 userToChunks.get(userID).add(chunkID);30 chunkToUsers.get(chunkID).add(userID);31 return userIds;32 }33 34 private Map<Integer, Set<Integer>> userToChunks = new HashMap<>();35 private Map<Integer, Set<Integer>> chunkToUsers = new HashMap<>();36 private Queue<Integer> availableUserIds = new PriorityQueue<>();37}38