Stream Of Characters
You are given a list, ‘DICTIONARY[]’ containing a list of words and a stream of characters (queries). Your task is to choose a suitable data structure to implement ‘CharacterStreamChecker’ class described as follows:

1) ‘CharacterStreamChecker(dictionary)’: Constructor to initialize the data structure with given words present in ‘DICTIONARY[]’.

2) ‘solveQuery(character)’: Function to check whether the string formed by last ‘C’ (C = 1) queried characters (in order from oldest to newest, including the character just queried) is present in the ‘DICTIONARY[]’. If yes, return true. Otherwise, return false.

Note :

The ‘DICTIONARY[]’ contains only distinct strings.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains an integer ‘N’ representing the number of strings in the list, ‘DICTIONARY[]’. The second line of each test case contains ‘N’ space-separated strings present in the list, ‘DICTIONARY[]’. The third line of each test case contains an integer ‘Q’ representing the number of queries (or characters in the stream). The last line of each test case contains ‘Q’ space-separated characters.

Output Format :

For each query in a test case, return true if the string formed by the last ‘C’ characters (C = 1) is present in the ‘DICTIONARY[]’. Otherwise, return false. The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Stream Of Characters

You are given a list, ‘DICTIONARY[]’ containing a list of words and a stream of characters (queries). Your task is to choose a suitable data structure to implement ‘CharacterStreamChecker’ class described as follows:

1) ‘CharacterStreamChecker(dictionary)’: Constructor to initialize the data structure with given words present in ‘DICTIONARY[]’.

2) ‘solveQuery(character)’: Function to check whether the string formed by last ‘C’ (C >= 1) queried characters (in order from oldest to newest, including the character just queried) is present in the ‘DICTIONARY[]’. If yes, return true. Otherwise, return false.

Note :

The ‘DICTIONARY[]’ contains only distinct strings.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of strings in the list, ‘DICTIONARY[]’.

The second line of each test case contains ‘N’ space-separated strings present in the list, ‘DICTIONARY[]’.

The third line of each test case contains an integer ‘Q’ representing the number of queries (or characters in the stream).

The last line of each test case contains ‘Q’ space-separated characters.

Output Format :

For each query in a test case, return true if the string formed by the last ‘C’ characters (C >= 1) is present in the ‘DICTIONARY[]’. Otherwise, return false.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 200
1 <= |DICTIONARY[i]| <= 200
1 <= Q <= 400
‘DICTIONARY[i]’ and ‘QUERY’ contains only lowercase english letters.

Time limit: 1 second

Accepted Answer

Brute Force

The idea is to use the brute force approach for this problem. At every queried character, we will form strings in a backward direction and will simultaneously check for the string in the ‘DICTIONARY’. If we found the string, then return true. Otherwise, check till the first queried character. If still no string found in ‘DICTIONARY’, return false.

Note:

For faster search, we can store the strings present in the ‘DICTIONARY’ in a hash set.
Suppose the maximum length of the word present in the ‘DICTIONARY’ is ‘M’, then it is optimal to search till the last ‘M’ queried characters because a string of length greater than ‘M’ can never be found in the ‘DICTIONARY’.

Algorithm:

Declare three data members in the ‘private’ part of ‘CharacterStreamChecker’ class.
- HASHSET: A hash set to store the strings present in the ‘DICTIONARY’.
- STREAM: A string to store the stream of characters.
- MAXLENGTH: An integer variable to store the maximum length of the string present in the ‘DICTIONARY’.
The ‘public’ part of ‘CharacterStreamChecker’ class contains the ‘CharacterStreamChecker’ constructor and ‘solveQuery’ function.
In the ‘CharacterStreamChecker’ constructor:
- Clear the ‘HASHSET’ to remove any strings already present in the ‘HASHSET’.
- Run a loop to traverse each string, ‘STR’ in the ‘DICTIONARY’.
  - Insert ‘STR’ in the ‘HASHSET’.
  - Declare an integer variable ‘STRLENGTH’ that will store the length of string, ‘STR’.
  - Assign the maximum of ‘MAXLENGTH’ and ‘STRLENGTH’ in the ‘MAXLENGTH’ variable.
In the ‘solveQuery’ function:
- Push the queried character in ‘STREAM’.
- Declare an integer variable ‘STREAMLENGTH’ that will store the length of string, ‘STREAM’.
- Create a temporary string, ‘TEMP’ that will store the last queried characters to be searched in ‘DICTIONARY’.
- Run a loop from i = STREAMLENGTH - 1 to i = max (0, STREAMLENGTH- MAXLENGTH).
  - Insert ‘STREAM[i]’ to the beginning of ‘TEMP’.
  - If HASHSET.COUNT(TEMP) > 0 that shows that ‘TEMP’ is present in the ‘HASHSET’. So, return true.
- In the end, return false.

Space Complexity: O(n)Explanation:

O(N + Q + M), where ‘N’ is the number of strings in the ’dictionary’, ‘Q’ is the number of queries, and ‘M’ is the maximum length of the string present in the ‘dictionary’.

Since the ‘HASHSET’ requires O(N) space to store the strings present in the ‘DICTIONARY’, string, ‘STREAM’ will store ‘Q’ characters at the end resulting in O(Q) space and string ‘TEMP’ will store a maximum of ‘M’ characters at any instant that will result in O(M) space.

Time Complexity: O(n^3)Explanation:

O(N + (Q * (M ^ 2))), where ‘N’ is the number of strings in the ’DICTIONARY’, ‘Q’ is the number of queries, and ‘M’ is the maximum length of the string present in the ‘DICTIONARY’.

The time complexity of the ‘CharacterStreamChecker’ constructor is O(N). Since the loop inside the constructor runs ‘N’ times to insert the string in ‘HASHSET’ (Insertion in a hash set is O(1)).

Time Complexity of ‘solveQuery’ function is O((M ^ 2)) because in the worst case, the loop inside the ‘solveQuery’ function run ‘M’ times wherein each iteration of the loop, inserting the character at the beginning of the ‘temp’ string takes O(M) time. Because of ‘Q’ queries, it will result in O(Q * (M ^ 2)).

Hence, overall time complexity is O(N) + O(Q * (M ^ 2)) = O(N + (Q * (M ^ 2))).

Python (3.5)

"""

    Time Complexity  :   O(N + (Q * (M ^ 2)))

    Space Complexity :   O(N + Q + M)



    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,

    and 'M' is the maximum length of the string present in the 'DICTIONARY'.

"""





class CharacterStreamChecker:

    def __init__(self, dictionary):

        self.hashSet = set()

        self.stream = ""

        self.maxLength = 0

        # Inserting the strings in the 'hashSet'.

        for str in dictionary:

            self.hashSet.add(str)

            strLength = len(str)



            # Keeping track of maximum length string in 'dictionary'.

            self.maxLength = max(self.maxLength, strLength)



    def solveQuery(self, character):

        self.stream += character

        streamLength = len(self.stream)



        # The 'temp' will store the last queried characters to be searched.

        temp = ""



        # Appending the queried characters (in backward direction) at the front of 'temp' and searching in the 'hashSet'.

        for i in range(streamLength - 1, max(0, streamLength - self.maxLength) - 1, -1):

            temp = self.stream[i] + temp



            # The 'temp' is found in 'hashSet'.

            if temp in self.hashSet:

                return True

        return False

Java (SE 1.8)

/*
    Time Complexity  :   O(N + (Q * (M ^ 2)))
    Space Complexity :   O(N + Q + M)

    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,
    and 'M' is the maximum length of the string present in the 'DICTIONARY'.
*/

import java.util.HashSet;
import java.util.ArrayList;

public class CharacterStreamChecker {

	HashSet hashSet = new HashSet<>();
	String stream;
	int maxLength = 0;

	CharacterStreamChecker(ArrayList dictionary) {
		hashSet.clear();

		// Inserting the Strings in the 'hashSet'.
		for (String str : dictionary) {
			hashSet.add(str);
			int strLength = str.length();

			// Keeping track of maximum length String in 'dictionary'.
			maxLength = Math.max(maxLength, strLength);
		}
	}

	Boolean solveQuery(char character) {
		stream += (character);
		int streamLength = stream.length();

		// The 'temp' will store the last queried characters to be searched.
		String temp = "";

		// Appending the queried characters (in backward direction) at the front of 'temp' and searching in the 'hashSet'.
		for (int i = streamLength - 1; i >= Math.max(0, streamLength - maxLength); i--) {
			temp = stream.charAt(i) + temp;

			// The 'temp' is found in 'hashSet'.
			if (hashSet.contains(temp)) {
				return true;
			}
		}

		return false;
	}
}

C++ (g++ 5.4)

/*

    Time Complexity  :   O(N + (Q * (M ^ 2)))

    Space Complexity :   O(N + Q + M)



    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,

    and 'M' is the maximum length of the string present in the 'DICTIONARY'.

*/



#include 



class CharacterStreamChecker

{

private:

    unordered_set hashSet;

    string stream;

    int maxLength = 0;



public:

    CharacterStreamChecker(vector &dictionary)

    {

        hashSet.clear();



        // Inserting the strings in the 'hashSet'.

        for (string &str : dictionary)

        {

            hashSet.insert(str);

            int strLength = str.length();



            // Keeping track of maximum length string in 'dictionary'.

            maxLength = max(maxLength, strLength);

        }

    }



    bool solveQuery(char character)

    {

        stream.push_back(character);

        int streamLength = stream.length();



        // The 'temp' will store the last queried characters to be searched.

        string temp;



        // Appending the queried characters (in backward direction) at the front of 'temp' and searching in the 'hashSet'.

        for (int i = streamLength - 1; i >= max(0, streamLength - maxLength); i--)

        {

            temp = stream[i] + temp;



            // The 'temp' is found in 'hashSet'.

            if (hashSet.count(temp))

            {

                return true;

            }

        }

        return false;

    }

};

Accepted Answer

Trie Data Structure

It is not easier to develop a solution to this problem by the usual approach. But if we look at the problem in a way to match the reverse of ‘C’ stream of characters with reversed strings present in the ‘dictionary’. Then the entire problem is reduced to a prefix matching problem. The idea is to use trie data structure as it is the most suitable and fastest data structure for prefix matching.

First, we will build a trie and insert all the strings of ‘DICTIONARY’ in reversed order in the ‘TRIE’. We will maintain a string, ‘STREAM’, that will store the stream of characters at any instant. For every queried character, search the ‘STREAM’ from the end in the ‘TRIE’. If we found a node representing the end of the word, it means that character present at that node till the queried character is a valid word present in the ‘DICTIONARY’. So, we will return true.

If not, then we have two cases:

We have reached the end of the ‘TRIE’. So, return false.
We have reached the beginning of the ‘STREAM’. If the node representing the first character of ‘STREAM’ is the end of the word. Then, return true otherwise false.

‘Trie’ Class:

A pointer array, ‘CHILD’ of type ‘TRIE’ of size 26 to point to the string’s next character.
A boolean variable, ‘ISND’, to mark the end of the string.
Constructor of ‘TRIE’ initializes all the elements of ‘CHILD’ by NULL and ‘ISEND’ by false.
Destructor of ‘TRIE’ to deallocate the memory used by ‘CHILD’ pointers.

Algorithm:

Create a ‘TRIE’ class.
Declare two data members and one member function in the ‘private’ part of ‘CharacterStreamChecker’ class.
- STREAM: A string to store the stream of characters.
- ROOT: Pointer to the ‘Trie’ node.
- insert: A function to insert the reverse of string in a ‘TRIE’.
The ‘public’ part of ‘CharacterStreamChecker’ class contains the ‘CharacterStreamChecker’ constructor and ‘solveQuery’ function.
In the ‘CharacterStreamChecker’ constructor:
- Allocate memory for the ‘ROOT’ node of ‘TRIE’.
- Run a loop to traverse each string, ‘STR’ in the ‘DICTIONARY’.
  - Call the ‘insert’ function to store the reverse of ‘STR’ in the ‘TRIE’.
In the ‘solveQuery’ function:
- Push the queried character in ‘STREAM’.
- Declare a pointer of ‘TRIE’, ‘TEMPROOT’ and assign ‘ROOT’ to it. The pointer ‘TEMPROOT’ will act as a temporary ‘ROOT’ and will be used to traverse the ‘TRIE’.
- Declare an integer variable, ‘i’ and assign ‘str.length() - 1’.
- Run a loop while ‘i’ is greater than or equal to zero.
  - Declare an integer variable, ‘INDEX’ and assign STREAM[i] - ‘a’, that stores the index of the character in the ‘TRIE’.
  - If TEMPROOT->CHILD[INDEX] == NULL, that shows that the current character is not present in the ‘TRIE’. So, return false.
  - Else, update ‘TEMPROOT’ by ‘TEMPROOT->CHILD[INDEX]’.
  - If TEMPROOT->ISEND == true, that shows that a complete word is found. So, return true.
  - Else, decrement ‘i’ by 1.
- Return ‘TEMPROOT->ISEND’.

Description of ‘insert’ function

This function will take one parameter :

STR: A string variable to store the string from ‘DICTIONARY’.

void insert(str):

Declare a pointer of ‘TRIE’, ‘TEMPROOT’ and assign ‘ROOT’ to it. The pointer ‘TEMPROOT’ will act as a temporary ‘ROOT’ and will be used to traverse the ‘TRIE’.
Declare an integer variable, ‘i’ and initialize with ‘STR.length() - 1’ to traverse the string, ‘STR’.
Run a loop while ‘i’ is greater than or equal to zero
- Declare an integer variable, ‘INDEX’ and assign STR[i] - ‘a’, that stores the index of the current character of ‘STR’ in the ‘TRIE’.
  - If TEMPROOT->CHILD[index] == NULL, that shows that the current character of ‘STR’ is not present in the ‘TRIE’. So, create a new node and update ‘TEMPROOT->CHILD[i]’ by the address of the new node.
- Update ‘TEMPROOT’ by ‘TEMPROOT->CHILD[i]’.
- Decrement ‘i’ by 1.
Update ‘ROOT->ISEND’ by true.

Space Complexity: O(n^2)Explanation:

O(26 * N * M), where ‘N’ is the number of strings in the ’DICTIONARY’ and and ‘M’ is the maximum length of the string present in the ‘DICTIONARY’.

Since we are storing all the ‘N’ strings in ‘TRIE’ of maximum length, ‘M’. It will lead to ‘M * N’ nodes in the ‘TRIE’. At every ‘TRIE’ node, we have 26 pointers. So, overall space complexity will be O(26 * N * M).

Time Complexity: O(n^2)Explanation:

O((N + Q) * M), where ‘N’ is the number of strings in the ‘DICTIONARY’, ‘Q’ is the number of queries, and ‘M’ is the maximum length of the string present in the ‘DICTIONARY’.

The time complexity of ‘CharacterStreamChecker’ constructor is O(N * M). Since the loop inside the constructor runs ‘N’ times and in each iteration, the ‘insert’ function is called, which will take O(M) time in the worst case.

The time complexity of ‘solveQuery’ function is O(M) because in the worst case, the loop inside the ‘solveQuery’ function runs ‘M’ times wherein each iteration of the loop is a constant operation. Because of ‘Q’ queries, it will result in O(Q * M).

Hence, overall time complexity is O(N * M) + O(Q * M) = O((N + Q) * M).

Python (3.5)

"""

    Time Complexity  :   O((N + Q) * M)

    Space Complexity :   O(26 * N * M)



    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,

    and 'M' is the maximum length of the string present in the 'DICTIONARY'.

"""



# 'Trie' Class.

class Trie:



    # 'Trie' Constructor.

    def __init__(self):

        self.child = [None] * 26

        self.isEnd = False



    # 'Trie' Destructor.

    def __del__(self):

        del self.child





class CharacterStreamChecker:



    # Function to insert the reverse of 'str' in the 'Trie'.

    def insert(self, str):

        tempRoot = self.root

        i = len(str) - 1

        while i >= 0:

            index = ord(str[i]) - ord("a")



            if tempRoot.child[index] == None:

                tempRoot.child[index] = Trie()



            tempRoot = tempRoot.child[index]

            i -= 1

        tempRoot.isEnd = True



    def __init__(self, dictionary):

        self.root = Trie()

        self.stream = ""



        # Inserting the reverse of the strings in the 'Trie'.

        for str in dictionary:

            self.insert(str)



    def __del__(self):

        del self.root



    def solveQuery(self, character):

        self.stream += character



        tempRoot = self.root



        # Searching the last queried characters in the 'Trie'.

        i = len(self.stream) - 1

        while i >= 0:

            index = ord(self.stream[i]) - ord("a")



            # The current character is not present in the 'Trie'.

            if tempRoot.child[index] == None:

                return False



            tempRoot = tempRoot.child[index]



            # We reached at the end of the string formed by the last 'stream.length() - i' queried characters.

            if tempRoot.isEnd:

                return True

            i -= 1

        return tempRoot.isEnd

C++ (g++ 5.4)

/*

    Time Complexity  :   O((N + Q) * M)

    Space Complexity :   O(26 * N * M)



    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,

    and 'M' is the maximum length of the string present in the 'DICTIONARY'.

*/



// 'Trie' Class.

class Trie

{

public:

    Trie *child[26];

    bool isEnd;



    // 'Trie' Constructor.

    Trie()

    {

        for (int i = 0; i < 26; i++)

        {

            child[i] = NULL;

        }

        isEnd = false;

    }



    // 'Trie' Destructor.

    ~Trie()

    {

        for (int i = 0; i < 26; i++)

        {

            if (child[i] != NULL)

            {

                delete child[i];

            }

        }

    }

};



class CharacterStreamChecker

{

private:

    string stream;

    Trie *root;



    // Function to insert the reverse of 'str' in the 'Trie'.

    void insert(string &str)

    {

        Trie *tempRoot = root;

        int i = str.length() - 1;

        while (i >= 0)

        {

            int index = str[i] - 'a';



            if (tempRoot->child[index] == NULL)

            {

                tempRoot->child[index] = new Trie();

            }



            tempRoot = tempRoot->child[index];

            i--;

        }

        tempRoot->isEnd = true;

    }



public:

    CharacterStreamChecker(vector &dictionary)

    {

        root = new Trie();



        // Inserting the reverse of the strings in the 'Trie'.

        for (string &str : dictionary)

        {

            insert(str);

        }

    }



    ~CharacterStreamChecker() 

    {

        delete root;

    }



    bool solveQuery(char character)

    {

        stream.push_back(character);



        Trie *tempRoot = root;



        // Searching the last queried characters in the 'Trie'.

        int i = stream.length() - 1;

        while (i >= 0)

        {

            int index = stream[i] - 'a';



            // The current character is not present in the 'Trie'.

            if (tempRoot->child[index] == NULL)

            {

                return false;

            }



            tempRoot = tempRoot->child[index];



            // We reached at the end of the string formed by the last 'stream.length() - i' queried characters.

            if (tempRoot->isEnd)

            {

                return true;

            }

            i--;

        }

        return tempRoot->isEnd;

    }

};

Java (SE 1.8)

/*
    Time Complexity  :   O((N + Q) * M)
    Space Complexity :   O(26 * N * M)

    Where 'N' is the number of strings in the 'DICTIONARY', 'Q' is the number of queries,
    and 'M' is the maximum length of the string present in the 'DICTIONARY'.
*/

import java.util.ArrayList;

//'Trie' Class.
class Trie {

	Trie[] child = new Trie[26];
	boolean isEnd;

	// 'Trie' Constructor.
	Trie() {
		for (int i = 0; i < 26; i++) {
			child[i] = null;
		}
		isEnd = false;
	}
}

public class CharacterStreamChecker {

	String stream;
	Trie root = new Trie();

	// Function to insert the reverse of 'str' in the 'Trie'.
	void insert(String str) {
		Trie tempRoot = root;
		int i = str.length() - 1;
		while (i >= 0) {
			int index = str.charAt(i) - 'a';

			if (tempRoot.child[index] == null) {
				tempRoot.child[index] = new Trie();
			}

			tempRoot = tempRoot.child[index];
			i--;
		}
		tempRoot.isEnd = true;
	}

	CharacterStreamChecker(ArrayList dictionary) {
		root = new Trie();

		// Inserting the reverse of the Strings in the 'Trie'.
		for (String str : dictionary) {
			insert(str);
		}
	}

	Boolean solveQuery(char character) {
		stream += (character);

		Trie tempRoot = root;

		// Searching the last queried characters in the 'Trie'.
		int i = stream.length() - 1;
		while (i >= 0) {
			int index = stream.charAt(i) - 'a';

			// The current character is not present in the 'Trie'.
			if (tempRoot.child[index] == null) {
				return false;
			}

			tempRoot = tempRoot.child[index];

			// We reached at the end of the string formed by the last 'stream.length() - i' queried characters.
			if (tempRoot.isEnd) {
				return true;
			}
			i--;
		}
		
		return tempRoot.isEnd;
	}
}

You are given a list, ‘DICTIONARY[]’ containing a list of words and a stream of characters (queries). Your task is to choose a suitable data structure to implement ‘CharacterStreamChecker’ class described as follows:

1) ‘CharacterStreamChecker(dictionary)’: Constructor to initialize the data structure with given words present in ‘DICTIONARY[]’.

2) ‘solveQuery(character)’: Function to check whether the string formed by last ‘C’ (C >= 1) queried characters (in order from oldest to newest, including the character just queried) is present in the ‘DICTIONARY[]’. If yes, return true. Otherwise, return false.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Amazon Research Analyst interview questions & answers

Popular interview questions of Research Analyst

Top HR questions asked in Amazon Research Analyst