Infosys | Infytq Advantage Round 2022
Anonymous User
360
InfosysTrieInterview

Problem Statement

You are given a string array S of size N. Your are also given Q queries as lowercase English characters as string Queries.

For each query i, you have to check if you can use some suffix in Queries[0:i] to make some strings in array S. If there can be multiple matches for a query take the indexes in increasing order of size.

Let the result of all matches be stored in an array A.

Find the score of A where the score is calculated as shown below:

score = A[0]*1 + A[1]*10 + A[2]*100 + A[3]*1000 + . . . + A[n-1]*10(n-1)

Find the score modulo 109 + 7. Print 0 if there are no matches.

Notes:

  1. There can be multiple matches for a query. Consider all of them in order of size.
  2. A string in S may occur multiple times in Queries. You need t oconsider all occurences in increasing order of index.

Constraints:
1<=N<=105
1<=|S[i]|<=100 for all i 1 to N.
1<=Q<=105
1<=|Queries|<=105

Sample InputSample OutputExplanation
1
ukwy
2
sl		0No matchings. 0 is the result.
5
ly
k
kbgb
j
qc
3
kzy		1Matching for index 1 in S at k
4
ab
abc
def
rf
6
abcdef		210Matching for index 0 in array at ab.
Matching for index 1 in array at abc.
Matching for index 2 in array at abcdef.
A = [0,1,2]
Score = 0*1+1*10+2*100 = 210

My approach:

  • Stored reverse of each string of given list in Trie DS.
  • For each node vector<int> words stored the index of word which start with current character.
  • For each query searched for any possible suffix match.

class Node
{
    int child[26];
    vector<int> words;

public:
    bool containsKey(char c)
    {
        return child[c - 'a'] != NULL;
    }
    void put(char c, Node *node)
    {
        child[c - 'a'] = node;
    }
    Node *get(char c)
    {
        return child[c - 'a'];
    }
    void setWord(int id)
    {
        words.push_back(id);
    }
    vector<int> getWords()
    {
        return words;
    }
};

class Trie
{
    Node *root;

public:
    Trie()
    {
        root = new Node();
    }
    void insert(string &s, int id)
    {
        Node *curr = root;

        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (!curr->containsKey(s[i]))
                curr->put(s[i], new Node());
            curr = curr->get(s[i]);
        }
        curr->setWord(id);
    }

    vector<int> search(string &s, vector<int> &matches)
    {
        Node *curr = root;

        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (!curr->containsKey(s[i]))
                return;
            curr = curr->get(S[i]);

            vector<int> temp = curr->getWords();
            for (auto &x : temp)
                matches.push_back(x);
        }
    }
};

//complete the following function

int solve(int N, vector<string> &S, int Q, string Queries)
{
    Trie *obj = new Trie();

    for (int i = 0; i < N; i++)
    {
        obj->insert(S[i], i);
    }

    vector<int> A;
    string qStr = "";

    for (int i = 0; i < Q; i++)
    {
        qStr += Queries[i];
        vector<int> temp = obj->search(qStr);
        obj->search(qStr, A);
    }

    const int MOD = 1000000007;
    int p = 1, score = 0;

    for (auto &x : A)
    {
        score = (score + 1LL * x * p % MOD) % MOD;
        p = 1LL * p * 10 % MOD;
    }

    return score;
}

Above approach passed only 2 test case and gave WA for remaining.
Anyone know any other approach or could point out the mistake in above approach. :)

Comments (1)