Interviewbit - Hotel Reviews

help
1

Hotel Reviews - InterviewBit

My Approach 
map <string,int> good;

int fun(string &a)
{
    int cnt1=0,cnt2=0;
    for(int i=0;i<a.size();i++)
    {
        string tmp="";
        int j=i-1;
        while(j+1<a.size() && a[j+1]!='_')
        {
            tmp+=a[j+1];
            j++;
        }
        i=j;
        cnt1+=good[tmp];
        i++;
    }
    return cnt1;
}

bool comp(pair <int,int> a, pair <int,int> b)
{
    if(a.first!=b.first)
    return a.first>b.first;
    
    return a.second<b.second;
}

vector<int> Solution::solve(string A, vector<string> &B) {
    good.clear();
    for(int i=0;i<A.size();i++)
    {
        string tmp="";
        int j=i-1;
        while(j+1<A.size() && A[j+1]!='_')
        {
            tmp+=A[j+1];
            j++;
        }
        i=j;
        good[tmp]++;
        i++;
    }
    
    vector <pair<int,int>> v;
    
    for(int i=0;i<B.size();i++)
    {
        int count=fun(B[i]);
        v.push_back({count,i});
    }
    
    sort(v.begin(),v.end(), comp);
    
    // for(int i=0;i<B.size();i++)
    // cout<<v[i].first<<" "<<v[i].second<<" A ";
    
    vector <int> ans;
    for(int i=0;i<v.size();i++)
    ans.push_back(v[i].second);
    
    return ans;
}

Is my approach correct?

2

Yeah approach seems to be correct to me, I used a similar approach but with tries instead of map, it passed.

CODE 
const int mxN =1e5+2 ;
#define ar array
int c[mxN+1][26],n=1,ok[mxN+1]; 
void insert(string s){
  int u=0 ;
  for(char x:s){
    if(!c[u][x-'a'])
      c[u][x-'a']=n++ ;
    u=c[u][x-'a'] ;
  }
  ok[u]=1 ;
}
bool find(string s){
  int u=0 ;
  for(char x:s){
    if(!c[u][x-'a'])
      return 0 ;
    u=c[u][x-'a'] ;
  }
  return ok[u]  ;
}
vector<int> Solution::solve(string A, vector<string> &B) {
	stringstream x(A);
	string t  ;
	while(getline(x,t,'_'))
		insert(t) ;
	vector<ar<int,2>>a ;
	for(int i=0;i<B.size();i++){
		int c=0 ;
		stringstream y(B[i]) ;
		while(getline(y,t,'_'))
			c+=find(t) ; 
		a.push_back({i,c}) ;
	}
	sort(a.begin(),a.end(),[&](const ar<int,2>&i,const ar<int,2>&j){
	    return (i[1]>j[1]||(i[1]==j[1]&&i[0]<j[0])) ;
	}) ;
	vector<int>ans ;
	for(ar<int,2> x:a)
		ans.push_back(x[0]) ;
	memset(c,0,sizeof(c)) ;
    memset(ok,0,sizeof(ok)) ;n=1 ;
	return ans   ;
}

EDIT:
We don’t care about multiple occurrences of any string in the good set.

This passes 
map <string,int> good;

int fun(string &a)
{
    int cnt1=0,cnt2=0;
    for(int i=0;i<a.size();i++)
    {
        string tmp="";
        int j=i-1;
        while(j+1<a.size() && a[j+1]!='_')
        {
            tmp+=a[j+1];
            j++;
        }
        i=j;
        cnt1+=good[tmp];
        i++;
    }
    return cnt1;
}

bool comp(pair <int,int> a, pair <int,int> b)
{
    if(a.first!=b.first)
    return a.first>b.first;
    
    return a.second<b.second;
}

vector<int> Solution::solve(string A, vector<string> &B) {
    good.clear();
    for(int i=0;i<A.size();i++)
    {
        string tmp="";
        int j=i-1;
        while(j+1<A.size() && A[j+1]!='_')
        {
            tmp+=A[j+1];
            j++;
        }
        i=j;
        good[tmp]=1;
        i++;
    }
    
    vector <pair<int,int>> v;
    
    for(int i=0;i<B.size();i++)
    {
        int count=fun(B[i]);
        v.push_back({count,i});
    }
    
    sort(v.begin(),v.end(), comp);
    
    // for(int i=0;i<B.size();i++)
    // cout<<v[i].first<<" "<<v[i].second<<" A ";
    
    vector <int> ans;
    for(int i=0;i<v.size();i++)
    ans.push_back(v[i].second);
    
    return ans;
}
1 Like
3

Thanks bro

1 Like