SDE - 1

You are given an undirected graph with N nodes in the form of an adjacency matrix. You are also given an integer M.

Your task is to find if you can color the vertices of the graph using at most M colors such that no two adjacent vertices are of the same color.

For example:

If the given adjacency matrix is:
[0 1 0]
[1 0 1]
[0 1 0] and M = 3.

The given adjacency matrix tells us that node 1 is connected to node 2 and node 2 is connected to node 3. 

So if we color vertex 1 with ‘red’, vertex 2 with ‘blue’, and vertex 3 with ‘red’, it is possible to color the given graph with two colors which is less than or equal to M.

Implement Trie Data Structure to support these operations:

insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Three type of queries denote these operations:

Type 1: To insert a string "word" in Trie.
1 word

Type 2: To check if the string "word" is present in Trie or not.
2 word

Type 3: To check if there is any string in the Trie that starts with the given prefix string "word".
3 word

Who should we hire you?

What are your expectations?