Home » Interview coding problems/challenges

Check the consistency of the numbers (Trie Data Structure Question)

Check the consistency of the numbers: This is a popular trie based question that has been featured in interview rounds of many companies such as Amazon, DE-Shaw, Factset and many more either in number format or character format. Submitted by Divyansh Jaipuriyar, on April 21, 2020

The consistency is that, no number is the prefix another number in that data set.

Problem statement

EARTH is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to traveling, millions of miles signal gets distorted. Now they asked you to check the consistency of their data sets. The consistency is that no number is the prefix another number in that data set.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases. Each case starts with an integer n (1 ≤ n ≤ 100000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has a length from 1 to 10.

Output

For each case, print the case number and 'YES' if the list is consistent or 'NO' if it's not.

Example with explanation:

    Input:
    T = 1 // Test case
    N = 3
    911
    9629986
    9112545643

    Output:
    "NO" 
    Since the number 911 has occurred in the third case 9112545643. 
    Hence it is not consistent.

    Input:
    T = 1 // Test case
    N = 4
    1234
    1243
    1342
    3212

    Output:
    "YES"
    Since there is no number which is prefix of any other number.

Solution Approach

Since there are various methods to solve this type of problem but the major issue here is the time constraint. So to pass all the test cases we need to think of a data structure which can help to pass all the test cases, here we would use "TRIE" data structure, in which to search a string of length M and if there are N such Nodes it takes O(M) to search the Key present in a node.

Every node of Trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as the end of the word node. A Trie node field stop is used to distinguish the node as the end of the word node. A simple structure to represent nodes of the English alphabet can be as following,

struct trie {
    trie* next[10];
    int stop = 0;
    trie()
    {
        stop = 0;
        for (int i = 0; i < 10; i++)
            next[i] = NULL;
    }
};

Inserting a key to Trie is a simple approach. Every character of the input key is inserted as an individual Trie node. Note that the next is an array of pointers (or references) to next level trie nodes. The key character acts as an index into the array of children. If the input key is new or an extension of the existing key, we need to construct non-existing nodes of the key and mark the end of the word for the last node. If the input key is a prefix of the existing key in Trie, we simply mark the last node of the key as the stop=1.

Searching for a key is similar to insert operation, however, we only compare the characters and move down. The search can terminate due to the end of a string or lack of key in the trie.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//trie node
struct trie {
    ll stop;
    trie* next[10];
    trie()
    {
        stop = 0; //to check whether the string end is reached or not.
        for (ll i = 0; i < 10; i++)
            next[i] = NULL;
    }
} * root;

// insertion operation with simultaneouly checking if the prefix is present or not
bool insert(string str, trie* cur)
{
    ll l = str.size();
    bool test = 0;
    for (ll i = 0; i < l; i++) {
        ll now = str[i] - '0';
        if (cur->next[now] == NULL)
            // if there is no existing key the create new trie node
            cur->next[now] = new trie();
        if (cur->stop) {
            test = 1;
            break;
        } // if the prefix is present return true
        cur = cur->next[now];
    }
    cur->stop = 1; // reached the end of the given string
    return test;
}

int main()
{
    cout << "Enter the number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        root = new trie();
        
        ll n;
        cout << "Enter the number of String(Numbers): ";
        cin >> n;
        
        string str;
        vector<string> v;
        
        cout<<"Enter your string:\n";
        for (ll i = 0; i < n; i++) {
            cin >> str;
            v.push_back(str);
        }
        
        bool test = 0;
        
        for (ll i = 0; i < n; i++) {
            test = insert(v[i], root);
            if (test)
                break;
        }
        if (test)
            cout << "NO"
                 << "\n"; // Prefix is present hence inconsistent
        else
            cout << "YES"
                 << "\n"; //Prefix is not present hence consistent.
    }
    return 0;
}

Output

Enter the number of test cases: 3
Enter the number of String(Numbers): 3
Enter your string:
123
1234
12345
NO
Enter the number of String(Numbers): 3
Enter your string:
123
231
321
YES
Enter the number of String(Numbers): 4
Enter your string:
123
3214
34512
2312434
YES