Twitter Application

Moderate
0/80
Average time to solve is 50m
profile
Contributed by
2 upvotes
Asked in companies
AmazonMicrosoftFlipkart limited

Problem statement

Your task is to design a Twitter application with your DSA which have the following functions:

‘POST’(USERID, TWEETID) tells that a user having ID as USERID has posted a tweet having ID as TWEETID.
‘GET_FEED’( ‘USERID’ ) returns the list of 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
‘FOLLOW(USERID, FOLLOWERID) tells that user is followed by the user having ID as ‘FOLLOWERID’.
 UNFOLLOW(USERID, FOLLOWERID) tells that the user ‘FOLLOWERID’ has unfollowed the user.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of function calls.

Next ‘N’ lines of each test case contain an integer denoting the function type followed by the parameter list.
   Type 1 denotes POST().
   Type 2 denotes GET_FEED().
   Type 3 denotes FOLLOW().
   Type 4 denotes UNFOLLOW().
Output Format: 
For each test case, output the lists returned by the GET_FEED() function.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10000.
1 <= ‘USERID’ <= 500 . 
Time limit: 1 sec
Sample Input 1:
2
5
1 1 100   
1 2 200
3 1 2
2 2
2 1
3
1 1 100
1 1 110
2 1
Sample Output 1:
200 100
100
110 100
Explanation of sample input 1:
For the first test case,
User 1 posted a tweet with ID as 100.
User 2 posted a tweet with ID as 200.
User 2 followed user 1.
Now, the get_Feed for user 2 will show his own posts and user 1’s posts.So,the posts will be [200,100]. 
get_Feed for user 1 will show only his own posts as he didn’t follow any other user. So, the posts will be [100]. 


For the second test case:
 User 1 posted a tweet with ID as 100.
 User 1 posted a tweet with ID as 110.
  get_Feed for user 1 will show only his own posts as he didn’t follow any other user.So, the posts will be [110, 100].
Sample Input 2:
2
8
1 1 1
3 1 2
4 1 2
2 1
1 1 2
1 1 3
1 2 4
2 1
9
1 1 1
2 1
1 3 2
3 1 3
4 1 3
1 3 3
1 1 4
3 3 1
2 1
Sample Output 2:
1 
3 2 1 
1 
4 3 2 1
Hint

Try to check all the tweets for the user feed.

Approaches (2)
Brute Force

In this approach, we will use a matrix M of size 501*501 .M[i][j] will be 1 is the user ‘i’ is followed by user ‘j’ otherwise 0. And we will use an array ‘TWEETS’  having two fields {tweetID,userID} to store all the tweets. For follow() and unfollow() functions we will update the values of matrix M.For get_Feed() function, we will iterate the TWEETS array from backward and find the suitable tweets for the user.


 

Algorithm:

  • Defining TWITTER():
    • Declare a dynamic array ‘TWEETS’.
    • Declare a matrix ‘M’ of size 501*501.
    • Set all values of M to 0.
  • Defining POST(USERID, TWEETID):
    • Append {TWEETID,USERID} into TWEETS list.
  • Defining GET_FEED(‘USERID’):
    • Declare a list ‘ANS’ to store the suitable tweet IDs.
    • For i in range length of TWEET -1 to 0:
      • Set TWEETID as TWEET[i][0].
      • Set USER as TWEET[i][0].
      • If USER== USERID or M[USER][USERID] == 1:
        • Append TWEETID into  ‘ANS’ array.
      • If the size of ANS is 10:
        • Return ANS.
    • Return ‘ANS’.
  • Defining FOLLOW(USERID, FOLLOWERID):
    • Set M[USERID][FOLLOWERID] as 1.
  • Defining UNFOLLOW(USERID, FOLLOWERID):
Time Complexity

O(N * M), where ‘M’ is the maximum length of ‘TWEETS’ and ‘N’ is the number of functions calls.

 

In this approach, GET_FEED() functions use O(M) time to search for suitable tweets. Hence the overall time complexity is O(N*M).

Space Complexity

O(M), where ‘M’ is the maximum length of ‘array’.

 

An array of size M is used to store all the tweets. Hence the overall space complexity is O(M). 

Code Solution
(100% EXP penalty)
Twitter Application
Full screen
Console