HackerEarth Search Engine problem solution

In this HackerEarth Search Engine, problem-solution Let us see how search engines work. Consider the following simple auto-complete feature. When you type some characters in the text bar, the engine automatically gives the best matching options among its database. Your job is simple. Given an incomplete search text, output the best search result.

Each entry in the engine’s database has a priority factor attached to it. We consider a result/search suggestion best if it has maximum weight and completes the given incomplete search query. For each query in the input, print the maximum weight of the string in the database, that completes the given incomplete search string. In case no such string exists, print -1.

HackerEarth Search Engine problem solution.

#include <bits/stdc++.h>

using namespace std;

#define V vector

typedef long long LL;
typedef pair<int, int> pii;

typedef V<int> vi;
typedef V<string> vs;
typedef V<LL> vl;
typedef V<double> vd;

#define forup(i,a,b) for(int i=(a); i<(b); ++i)
#define fordn(i,a,b) for(int i=(a); i>(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define fov(i,a) rep(i,(a).size())
#define foreach(i,X) for(__typeof((X).begin()) i = (X).begin(); i != (X).end(); i++)

#define gi(x) scanf("%d",&x)
#define gl(x) scanf("%I64d",&x)
#define gd(x) scanf("%lf",&x)
#define gs(x) cin >> x

#define pi(x) printf("%d",x)
#define pin(x) printf("%dn",x)
#define pl(x) printf("%I6d",x)
#define pln(x) printf("%I64dn",x)
#define ps(s) cout << s;
#define psn(s) cout << s << "n"
#define pn printf("n")
#define spc printf(" ")
#define prec(x) cout<<fixed<<setprecision(x)

#define all(x) (x).begin(), (x).end()

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

#define fr freopen("input.in", "r", stdin)
#define fw freopen("output.out", "w", stdout)

const int inf = numeric_limits<int>::max();
const LL linf = numeric_limits<LL>::max();
const double EPS = 1e-7;

const int MAXN = 1000000;
const int LOGMAXN = log2(MAXN) + 3;

inline char toChar(int i) {
    return static_cast<char>('a' + i);
}

struct trie {
    trie *a[26];
    int weight;

    trie() {
        rep(i, 26) a[i] = NULL;
        weight = 0;
    }
};

trie* insert(const string &s, int wt, int idx, trie *root) {
    int cur = s[idx] - 'a';
    if (!root->a[cur]) root->a[cur] = new trie();
    root->a[cur]->weight = max(root->a[cur]->weight, wt);
    if (idx + 1 != s.size()) {
        root->a[cur] = insert(s, wt, idx + 1, root->a[cur]);
    }
    return root;
}

int searchBest(const string &s, trie *root) {
    int idx = 0, n = s.size(), cur, bestWt = -1;
    while (idx < n) {
        cur = s[idx] - 'a';
        if (!root->a[cur]) return -1;
        bestWt = root->a[cur]->weight;
        root = root->a[cur];
        ++idx;
    }
    return bestWt;
}

void print(string s, trie *root) {
    rep(i, 26) if (root->a[i]) print(s + toChar(i), root->a[i]);
    psn(s);
    pi(root->weight);
}

int main() {
    // fr; fw;
    int n, w, q, tot = 0, cnt = 0;
    string s, t;
    gi(n); gi(q);
    assert(n <= MAXN);
    trie *root = new trie();
    while (n--) {
        gs(s); gi(w);
        tot += s.size();
        root = insert(s, w, 0, root);
    }
    assert(tot <= MAXN); tot = 0;
    // print("", root);
    while (gs(s)) {
        // gs(s);
        ++cnt;
        tot += s.size();
        pin(searchBest(s, root));
    }
    assert(tot <= MAXN);
    assert(cnt == q);
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b and n>=a)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define repi(i,n) for(int i=0; i<(int)n;i++)
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define DRT()  int t; cin>>t; while(t--)
using namespace std;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
       cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
       const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;

#define MOD 1000000007ll
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}


struct node{
    int maxweight;
    node * next[26];
    node(){
        maxweight=0;
        for(int i=0; i<26; i++)
            next[i]=NULL;
    }
};
node * insert(node * root, string & s, int ind, int weight){
    if(ind==s.length()){
        return NULL;
    }
    root->maxweight=weight;
    node * & cur=root->next[s[ind]-'a'];
    if(cur==NULL)
        cur=new node();
    cur=insert(cur, s, ind+1, weight);
    return root;
}

int query(node * root, string & q, int i){
    if(i==q.length())return root->maxweight;
    if(root->next[q[i]-'a']==NULL)
        return -1;
    return query(root->next[q[i]-'a'], q, i+1);
}

int main()
{
    int n,q;
    sd(n),sd(q);
    vector< pair< int, string > > ar(n);
    for(int i=0; i<n; i++)
        cin >> ar[i].S >> ar[i].F;
    sort(all(ar));
    node * root=new node();
    for(int i=0; i<n; i++)
        root=insert(root, ar[i].S, 0, ar[i].F);
    while(q--){
        string s;
        cin >> s;
        cout << query(root, s, 0) << endl;
    }
    return 0;
}

HackerEarth Search Engine problem solution

HackerEarth Search Engine problem solution.

Second solution

Leave a Reply

Pages

Practice