Approach
Breadth-first search
For Design Twitter, 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
- 99 lines of Java from the credited upstream file 355.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 Tweet {2 public int id;3 public int time;4 public Tweet next = null;5 public Tweet(int id, int time) {6 this.id = id;7 this.time = time;8 }9}10 11class User {12 private int id;13 public Set<Integer> followeeIds = new HashSet<>();14 public Tweet tweetHead = null;15 16 public User(int id) {17 this.id = id;18 follow(id);19 }20 21 public void follow(int followeeId) {22 followeeIds.add(followeeId);23 }24 25 public void unfollow(int followeeId) {26 followeeIds.remove(followeeId);27 }28 29 public void post(int tweetId, int time) {30 final Tweet oldTweetHead = tweetHead;31 tweetHead = new Tweet(tweetId, time);32 tweetHead.next = oldTweetHead;33 }34}35 36class Twitter {37 38 public void postTweet(int userId, int tweetId) {39 users.putIfAbsent(userId, new User(userId));40 users.get(userId).post(tweetId, time++);41 }42 43 /**44 * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in45 * the news feed must be posted by users who the user followed or by the user46 * herself. Tweets must be ordered from most recent to least recent.47 */48 public List<Integer> getNewsFeed(int userId) {49 if (!users.containsKey(userId))50 return new ArrayList<>();51 52 List<Integer> newsFeed = new ArrayList<>();53 Queue<Tweet> maxHeap =54 new PriorityQueue<>(Comparator.comparingInt((Tweet tweet) -> - tweet.time));55 56 for (final int followeeId : users.get(userId).followeeIds) {57 Tweet tweetHead = users.get(followeeId).tweetHead;58 if (tweetHead != null)59 maxHeap.offer(tweetHead);60 }61 62 int count = 0;63 while (!maxHeap.isEmpty() && count++ < 10) {64 Tweet tweet = maxHeap.poll();65 newsFeed.add(tweet.id);66 if (tweet.next != null)67 maxHeap.offer(tweet.next);68 }69 70 return newsFeed;71 }72 73 /**74 * Follower follows a followee.75 * If the operation is invalid, it should be a no-op.76 */77 public void follow(int followerId, int followeeId) {78 if (followerId == followeeId)79 return;80 users.putIfAbsent(followerId, new User(followerId));81 users.putIfAbsent(followeeId, new User(followeeId));82 users.get(followerId).follow(followeeId);83 }84 85 /**86 * Follower unfollows a followee.87 * If the operation is invalid, it should be a no-op.88 */89 public void unfollow(int followerId, int followeeId) {90 if (followerId == followeeId)91 return;92 if (users.containsKey(followerId) && users.containsKey(followeeId))93 users.get(followerId).unfollow(followeeId);94 }95 96 private int time = 0;97 private Map<Integer, User> users = new HashMap<>(); 98}99