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

*such Nodes it takes*

**N****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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions