Watson uses Social Network BOOKSHEF
Published in
4 min readOct 24, 2016
PROBLEM BOOKSHEF link SUBMIT link
Prerequisite –Sorting ,vector in C++, Hashing C/C++.
Coding Difficulty: Easy
Algorithms Used: Sorting
Problem Description:
We have an integer M represents chef’s special friends and N represents total number of posts.
Next line contains N integers A1, A2, …, AN denoting the identifiers of special friends of Chef represents identifier
of special friend.Each of the next M lines contains a pair of integers and a string denoting f, p and s, identifier of the
friend who created the post, the popularity of the post and the contents of the post, respectively.It is guaranteed that
no two posts have same popularity.
Now you have to print the post in order as follows:
- Posts of special friends should be shown first, irrespective of popularity. Among all such posts the popular ones should be shown earlier.
- Among all other posts, popular posts should be shown earlier.
Solution Description:
What we’ll do:
- One array can be used to store identifiers of special friends in sorted order for O(log n) time searching, or we can use hashing for O(1) time searching.
- We will use pair<pair<int,int>,string> to store post(f,p,s) in a single cell of array, we can also use
structure. - Use a sorting algorithm to sort array of pairs or structures on the basis of condition.
Solution:
Now sort both the array of structures on the basis of popularity.
// use inbuilt sort function:
sort(start_address,end_address,compare function).EXAMPLE-
for array int arr[10]- sort(arr,arr+10,comp); //by default comparision function does sorting in increasing orderfor vector vectorvect - sort(vect.begin(),vect.end(),comp);//by default comparision function does sorting in increasing orderHow to define compare function:As in the sort function we will pass vector of pair<pair<int,int>,string> and for each comparison it call compare function defined by you.We want to sort both the array in decreasing order of popularity so define compare function in the following way :define compare functionbool compare( pair<pair<int,int>,string>post1,pair<pair<int,int>,string>post2 ){
/*
comparision function comp(a,b) asks if a should come before b in sorted.
if it returns true then it puts a before b
else it puts b before a
*/if(sfi.find(post1.first.first)!=sfi.end()){
// if author of first post is in special friend listif(sfi.find(post2.first.first)!=sfi.end()){
// if author of second post is also in special friend list//now comparision happens on the basis of popularity, which is second of first in post((authorid,popularity),stringcontent)
return post1.first.second>post2.first.second;
//here condition means post1 will come before post2 only when popularity of post1 is more
}
else{
//if author of first is special and author of second is not special so post1 will come before post2
return true ;
}
}
if(sfi.find(post2.first.first)!=sfi.end()){
// if author of second post is in special friend list
if(sfi.find(post1.first.first)!=sfi.end()){
// if author of first post is in special friend listreturn post1.first.second>post2.first.second;
//here condition means post1 will come before post2 only when popularity of post1 is more
}
else{
//if author of second is special and author of first is not special so post2 will come before post1
return false;
}
}
// if no author is special then it depend on popularity
return post1.first.second>post2.first.second;}
Now the only task remaining is to print both the vector of posts ...Full Code C/C++#include<bits/stdc++.h>//this includes all headers at onceusing namespace std;
unordered_set<int> sfi;//making a hashset to store ids of all special friends
/*
when we search an element using find(element) function,
if
it is found then returns iterator(same as pointer) to that element.
else
it returns end of container , which here is sfi
*/
bool comp(pair<pair<int,int>,string>&post1,pair<pair<int,int>,string>&post2){
/*
comparision function comp(a,b) asks if a should come before b in sorted.
if it returns true then it puts a before b
else it puts b before a
*/if(sfi.find(post1.first.first)!=sfi.end()){
// if author of first post is in special friend listif(sfi.find(post2.first.first)!=sfi.end()){
// if author of second post is also in special friend list//now comparision happens on the basis of popularity, which is second of first in post((authorid,popularity),stringcontent)
return post1.first.second>post2.first.second;
//here condition means post1 will come before post2 only when popularity of post1 is more
}
else{
//if author of first is special and author of second is not special so post1 will come before post2
return true ;
}
}
if(sfi.find(post2.first.first)!=sfi.end()){
// if author of second post is in special friend list
if(sfi.find(post1.first.first)!=sfi.end()){
// if author of first post is in special friend listreturn post1.first.second>post2.first.second;
//here condition means post1 will come before post2 only when popularity of post1 is more
}
else{
//if author of second is special and author of first is not special so post2 will come before post1
return false;
}
}
// if no author is special then it depend on popularity
return post1.first.second>post2.first.second;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){ int temp; cin>>temp;
sfi.insert(temp);
}
vector<pair<pair<int,int>,string>>posts; // post((authorid,popularity),stringcontent)
int f,p;
string s;
for(int i=0;i<m;i++){ cin>>f;cin>>p;cin>>s;
posts.push_back(make_pair(make_pair(f,p),s));
}
sort(posts.begin(),posts.end(),comp);
for(int i=0;i<posts.size();i++)
cout<<posts[i].second<<endl;
}
#happy_coding #codebraceIf you find something wrong or have any question about the solution then comment down below, you can also contact us using contact form
