Last Updated: 24 Dec, 2021

Twitter Application

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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):

Solve now

02 Approach

In this approach, we will define a map TWEETS where TWEETS[U] will store the list of tweets of USER ‘U’.The tweet data will have two fields {TWEETID, TIME}. We will also maintain a map FOLLOWING.FOLLOWING[i] will contain the set of all users that i is following. In GET_FEED() function, we will exact the list of all users whom the current user is following and pick the 10 recent tweets using the help of the TWEETS map.

Defining TWITTER():
- Declare a map of arrays ‘TWEETS’.
- Declare a map of sets ‘FOLLOWING’.
- Set TIME as 1.
Defining POST(USERID, TWEETID):
- Append {TWEETID,TIME} into TWEETS[USERID].
- Set TIME to TIME + 1.
Defining GET_FEED(‘USERID’):
- Declare a list ‘ANS’ to store the suitable tweet IDs.
- Declare an list ‘INDEXPAIR’.
- For i in FOLLOWING[USERID]:
  - Append{i,size of TWEETS[i] -1 } into INDEXPAIR.
- Append {USERID,size of TWEETS[USERID] -1} into INDEXPAIR.
- While True:
  - Set LASTTIME as 0.
  - For i in range 0 to length of INDEXPAIR -1:
    - Set ID as INDEXPAIR[i][0].
    - Set ‘IDX’ as INDEXPAIR[i][1].
    - IF IDX>=0 and TWEETS[ID][IDX][1]>LASTTIME:
      - Found a new latest tweet.
      - Update LASTTIME to TWEETS[ID][IDX][1].
      - Set TWEET_ID as TWEETS[ID][IDX][0].
      - Set INDEX as i.
  - IF LASTTIME == 0:
    - All tweets are searched.
    - Return ANS.
  - Append TWEET_ID to ANS.
  - Update the index of the element whose TWEET is used.
  - Set INDEXPAIR[index][1] as INDEXPAIR[index][1]-1.
  - If size of ‘ANS’ == 10:
    - Return ANS.
Defining FOLLOW(USERID, FOLLOWERID):
- Insert USERID into FOLLOWING[FOLLOWERID].
Defining UNFOLLOW(USERID, FOLLOWERID):
- Erase USERID from FOLLOWING[FOLLOWERID].

Solve now