|
1 | | -classUser { |
2 | | - |
3 | | -privateintuid; |
4 | | -privateSet<Integer>followingIDs; |
5 | | -privateList<Integer>tweetIDs; |
6 | | - |
7 | | -publicUser(intuid) { |
8 | | -this.uid =uid; |
9 | | -this.followingIDs =newHashSet<>(); |
10 | | -this.followingIDs.add(this.uid);// by default, follows self |
11 | | -this.tweetIDs =newArrayList<>(); |
12 | | - } |
13 | | - |
14 | | -publicSet<Integer>getFollowingIDs() { |
15 | | -returnthis.followingIDs; |
16 | | - } |
17 | | - |
18 | | -publicList<Integer>getTweetIDs() { |
19 | | -returnthis.tweetIDs; |
20 | | - } |
21 | | - |
22 | | -publicintgetID() { |
23 | | -returnthis.uid; |
24 | | - } |
25 | | - |
26 | | -@Override |
27 | | -publicStringtoString() { |
28 | | -return ( |
29 | | -"[" + |
30 | | -this.uid + |
31 | | -", following: " + |
32 | | -this.followingIDs + |
33 | | -", tweets: " + |
34 | | -this.tweetIDs + |
35 | | -"]" |
36 | | - ); |
37 | | - } |
38 | | - |
39 | | -// Most recent ones are at the end |
40 | | -publicvoidfollow(intfid) { |
41 | | -this.followingIDs.add(fid); |
42 | | - } |
43 | | - |
44 | | -publicvoidunfollow(intfid) { |
45 | | -this.followingIDs.remove(fid); |
46 | | - } |
47 | | - |
48 | | -// If remove tweet existed, treeSet would've been used (to maintain ordering) |
49 | | -publicvoidpostTweet(inttweetID) { |
50 | | -this.tweetIDs.add(tweetID); |
51 | | - } |
52 | | -} |
53 | | - |
54 | | -classTweet { |
55 | | - |
56 | | -privateinttweetID; |
57 | | -privateinttimestamp; |
58 | | - |
59 | | -publicTweet(inttweetID,inttimestamp) { |
60 | | -this.tweetID =tweetID; |
61 | | -this.timestamp =timestamp; |
62 | | - } |
63 | | - |
64 | | -publicintgetTimeStamp() { |
65 | | -returnthis.timestamp; |
66 | | - } |
67 | | - |
68 | | -publicIntegergetTweetID() { |
69 | | -returnthis.tweetID; |
70 | | - } |
71 | | - |
72 | | -@Override |
73 | | -publicStringtoString() { |
74 | | -return"{" +this.tweetID +"," +this.timestamp +"}"; |
75 | | - } |
76 | | -} |
77 | | - |
78 | | -classDatabase { |
79 | | - |
80 | | -privatestaticintGLOBAL_TIME =0; |
81 | | - |
82 | | -// 1 <= userID <= 500 ---> Can be 501 sized array instead of HashMap |
83 | | -privatestaticintNUM_USERS =501; |
84 | | -privateUser[]users; |
85 | | -privateboolean[]userExists; |
86 | | - |
87 | | -// 0 <= tweetID <= 10^4 --> Can be 10^4 + 1 sized array instead of HashMap |
88 | | -privatestaticintNUM_TWEETS =10000 +1; |
89 | | -privateTweet[]tweets; |
90 | | - |
91 | | -// Acts like a 'node' to indicate where to go next |
92 | | -classTriplet { |
93 | | - |
94 | | -intuserId; |
95 | | -intindex; |
96 | | -inttweetID; |
97 | | - |
98 | | -publicTriplet(intuserId,intindex,inttweetID) { |
99 | | -this.userId =userId; |
100 | | -this.index =index; |
101 | | -this.tweetID =tweetID; |
102 | | - } |
103 | | - |
104 | | -@Override |
105 | | -publicStringtoString() { |
106 | | -return ( |
107 | | -"[" +this.userId +"," +this.index +"," +this.tweetID +"]" |
108 | | - ); |
109 | | - } |
110 | | - } |
111 | | - |
112 | | -// Compare the linked list of tweets present in the user class |
113 | | -// Nested class to access the 'tweets' |
114 | | -classTweetComparatorimplementsComparator<Triplet> { |
115 | | - |
116 | | -@Override |
117 | | -publicintcompare(Tripleto1,Tripleto2) { |
118 | | -// Compare max. with respect to timestamp |
119 | | -return ( |
120 | | -tweets[o2.tweetID].getTimeStamp() - |
121 | | -tweets[o1.tweetID].getTimeStamp() |
122 | | - ); |
123 | | - } |
124 | | - } |
125 | | - |
126 | | -// From outside, Database.TweetComparator obj = databaseObj.new TweetComparator() |
127 | | -privateTweetComparatorcomparator; |
128 | | - |
129 | | -// Constructor |
130 | | -publicDatabase() { |
131 | | -this.users =newUser[NUM_USERS]; |
132 | | -this.userExists =newboolean[NUM_USERS]; |
133 | | -Arrays.fill(this.userExists,false); |
134 | | - |
135 | | -this.tweets =newTweet[NUM_TWEETS]; |
136 | | -this.comparator =newTweetComparator(); |
137 | | - } |
138 | | - |
139 | | -privatevoidcreateUserMaybe(intuid) { |
140 | | -if (this.userExists[uid])return; |
141 | | - |
142 | | -this.userExists[uid] =true; |
143 | | -Useruser =newUser(uid); |
144 | | -this.users[uid] =user; |
145 | | - } |
146 | | - |
147 | | -privatevoidcreateTweet(inttweetId) { |
148 | | -Tweettweet =newTweet(tweetId,Database.GLOBAL_TIME); |
149 | | -Database.GLOBAL_TIME++; |
150 | | -this.tweets[tweetId] =tweet; |
151 | | - } |
152 | | - |
153 | | -publicvoidpostTweet(intuid,inttweetId) { |
154 | | -// Create new User if doesn't exist |
155 | | -createUserMaybe(uid); |
156 | | - |
157 | | -// Create new Tweet |
158 | | -createTweet(tweetId); |
159 | | - |
160 | | -// Post the tweet |
161 | | -this.users[uid].postTweet(tweetId); |
162 | | - } |
163 | | - |
164 | | -publicvoidfollow(intfollowerId,intfolloweeId) { |
165 | | -// Create users if doesn't exist |
166 | | -createUserMaybe(followerId); |
167 | | -createUserMaybe(followeeId); |
168 | | - |
169 | | -// Follow |
170 | | -this.users[followerId].follow(followeeId); |
171 | | - } |
172 | | - |
173 | | -publicvoidunfollow(intfollowerId,intfolloweeId) { |
174 | | -// Create users if doesn't exist |
175 | | -createUserMaybe(followerId); |
176 | | -createUserMaybe(followeeId); |
177 | | - |
178 | | -// Unfollow |
179 | | -this.users[followerId].unfollow(followeeId); |
180 | | - } |
181 | | - |
182 | | -privateList<Tweet>getMaxTopK(intuserId,intk) { |
183 | | -// Check if this user exists or not |
184 | | -if (!this.userExists[userId])returnnewArrayList<>(); |
185 | | - |
186 | | -// Use top k of sorted list type logic |
187 | | -PriorityQueue<Triplet>pq =newPriorityQueue<>(this.comparator); |
188 | | - |
189 | | -Useruser =this.users[userId]; |
190 | | -Set<Integer>followingIDs =user.getFollowingIDs(); |
191 | | - |
192 | | -// Take the most recent (i.e. last) tweet for each of the following user |
193 | | -for (intfollowingID :followingIDs) { |
194 | | -UserfollowingUser =this.users[followingID]; |
195 | | -List<Integer>followingUserTweetIds =followingUser.getTweetIDs(); |
196 | | - |
197 | | -if (followingUserTweetIds.isEmpty())continue; |
198 | | - |
199 | | -intlastIndex =followingUserTweetIds.size() -1; |
200 | | -intmostRecentTweetID =followingUserTweetIds.get(lastIndex); |
201 | | -Triplettriplet =newTriplet( |
202 | | -followingID, |
203 | | -lastIndex, |
204 | | -mostRecentTweetID |
205 | | - ); |
206 | | - |
207 | | -pq.add(triplet); |
208 | | - } |
209 | | -// Now, remove from pq, and "move required pointers/links" accordingly |
210 | | -List<Tweet>maxTweets =newArrayList<>(); |
211 | | - |
212 | | -while (!pq.isEmpty() && (maxTweets.size() <k)) { |
213 | | -Triplettop =pq.remove(); |
214 | | -maxTweets.add(tweets[top.tweetID]); |
215 | | - |
216 | | -// For this top's user, if 'lesser' recent tweet is available, add to pq |
217 | | -intuserID =top.userId; |
218 | | -intnextIndex =top.index -1;// move backwards due to ArrayList |
219 | | -if (nextIndex <0)continue; |
220 | | - |
221 | | -intnewTweetID =users[userID].getTweetIDs().get(nextIndex); |
222 | | -TripletnewTriplet =newTriplet(userID,nextIndex,newTweetID); |
223 | | -pq.add(newTriplet); |
224 | | - } |
225 | | - |
226 | | -returnmaxTweets; |
227 | | - } |
228 | | - |
229 | | -publicList<Integer>getMaxTop10TweetIDs(intuserId) { |
230 | | -List<Tweet>tweets =getMaxTopK(userId,10); |
231 | | -// Instead of streams, normal for loop may also be used |
232 | | -returntweets |
233 | | - .stream() |
234 | | - .map(x ->x.getTweetID()) |
235 | | - .collect(Collectors.toList()); |
236 | | - } |
237 | | -} |
238 | | - |
239 | 1 | classTwitter { |
240 | | - |
241 | | -privateDatabasedb; |
242 | | - |
243 | | -publicTwitter() { |
244 | | -this.db =newDatabase(); |
245 | | - } |
246 | | - |
247 | | -publicvoidpostTweet(intuserId,inttweetId) { |
248 | | -this.db.postTweet(userId,tweetId); |
249 | | - } |
250 | | - |
251 | | -publicList<Integer>getNewsFeed(intuserId) { |
252 | | -returndb.getMaxTop10TweetIDs(userId); |
253 | | - } |
254 | | - |
255 | | -publicvoidfollow(intfollowerId,intfolloweeId) { |
256 | | -this.db.follow(followerId,followeeId); |
257 | | - } |
258 | | - |
259 | | -publicvoidunfollow(intfollowerId,intfolloweeId) { |
260 | | -this.db.unfollow(followerId,followeeId); |
261 | | - } |
| 2 | +intcount; |
| 3 | +HashMap<Integer,List<int[]>>tweetMap; |
| 4 | +HashMap<Integer,HashSet<Integer>>followerMap; |
| 5 | + |
| 6 | +publicTwitter() { |
| 7 | +count =0; |
| 8 | +tweetMap =newHashMap<>(); |
| 9 | +followerMap =newHashMap<>(); |
| 10 | + } |
| 11 | + |
| 12 | +publicvoidpostTweet(intuserId,inttweetId) { |
| 13 | +tweetMap.computeIfAbsent(userId, |
| 14 | +k ->newArrayList<>() |
| 15 | + ); |
| 16 | + |
| 17 | +tweetMap.computeIfPresent(userId, (k,v) -> { |
| 18 | +v.add(newint[]{count,tweetId}); |
| 19 | +returnv; |
| 20 | + }); |
| 21 | + |
| 22 | + ++count; |
| 23 | + } |
| 24 | + |
| 25 | +publicList<Integer>getNewsFeed(intuserId) { |
| 26 | +List<Integer>res =newArrayList<>(); |
| 27 | + |
| 28 | +PriorityQueue<int[]>pq =newPriorityQueue<>((a,b) -> |
| 29 | +Integer.compare(b[0],a[0]) |
| 30 | + ); |
| 31 | + |
| 32 | +followerMap.computeIfAbsent(userId, |
| 33 | +k ->newHashSet<>() |
| 34 | + ); |
| 35 | + |
| 36 | +followerMap.get(userId).add(userId); |
| 37 | + |
| 38 | +followerMap.get(userId).forEach((followeeId) -> { |
| 39 | +if (tweetMap.containsKey(followeeId)) { |
| 40 | +inti =tweetMap.get(followeeId).size() -1; |
| 41 | +int[]tweet =tweetMap.get(followeeId).get(i); |
| 42 | +pq.offer(newint[]{tweet[0],tweet[1], |
| 43 | +followeeId, --i}); |
| 44 | + } |
| 45 | + }); |
| 46 | + |
| 47 | +while (!pq.isEmpty() &&res.size() <10) { |
| 48 | +int[]data =pq.poll(); |
| 49 | +res.add(data[1]); |
| 50 | + |
| 51 | +if (data[3] >=0) { |
| 52 | +int[]tweet =tweetMap.get(data[2]).get(data[3]); |
| 53 | +pq.offer(newint[]{tweet[0],tweet[1], |
| 54 | +data[2], --data[3]}); |
| 55 | + } |
| 56 | + } |
| 57 | + |
| 58 | +returnres; |
| 59 | + } |
| 60 | + |
| 61 | +publicvoidfollow(intfollowerId,intfolloweeId) { |
| 62 | +followerMap.computeIfAbsent(followerId, |
| 63 | +k ->newHashSet<>()); |
| 64 | + |
| 65 | +followerMap.computeIfPresent(followerId, (k,v) -> { |
| 66 | +v.add(followeeId); |
| 67 | +returnv; |
| 68 | + }); |
| 69 | + } |
| 70 | + |
| 71 | +publicvoidunfollow(intfollowerId,intfolloweeId) { |
| 72 | +HashSet<Integer>set =followerMap.computeIfAbsent(followerId, |
| 73 | +k ->newHashSet<>()); |
| 74 | + |
| 75 | +if (set.contains(followeeId)) { |
| 76 | +set.remove(followeeId); |
| 77 | + } |
| 78 | + } |
262 | 79 | } |
| 80 | + |
263 | 81 | /** |
264 | 82 | * Your Twitter object will be instantiated and called as such: |
265 | 83 | * Twitter obj = new Twitter(); |
|