gistfile1.txt

Suppose you are supplied with a file containing a list of words like ABC,ACD, ABC 
( say each word in new line ). now you have to suggest algorithm for this problem - 
When a user type some character, we have to suggest him next character and basis of 
suggestion is that the character you are going to suggest should have maximum occurrence at that position with the given prefix. 

For example , Let's say words are 
ABC 
ACD
ABC
Now if user types 'A' we have to suggest him 'B' as next character with the prefix ‘A’, ‘B’ 
has 2 times, and ‘C’ has 1. similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index since C has 2 times


keywords:

Constraint: the given prefix -> check its occurrence 

ask: maximum occurrence char -> if there are more than one, check first occurrence with smaller index

       A                                B  ...  Z
/                  \
B                    C
/  \                 \
                    
C   A                  D
[ABC count = 2, leaf = true]      [ACD 1]

for example: 
ABC
ABC
ABC (ABC prefix count = 3) C 
ABA (ABA prefix count = 1)
Work on three string and put into trie, add count variable 
ABC 
ACD
ABC

             A
    /                  \
    B  iterate 2    C  iterate 1
   /                       \ 
  C  “ABC” 2       ACD “ACD 1”
 
https://docs.google.com/document/d/1Wyuaq9vTShZmjX9MpHJhcYDSNi40bKZSOcGbqH5vFho/edit?usp=sharing

Class Node{
public char c;
public int   number; 

public Node[] Children; // 26, 256

Public Node(char cc)
{
   C = cc;
}
};

Private static Node addToTrie(string[] words)
{
if(words == null)
  Return null;

// dummy node
Var dummyNode = new Node(‘’);

foreach(var word in words)
{
  Var iterate = dummyNode;
 //  foreach(var item in word) // ABC
   for(int index = 0; index < word.Length; index++)
  {
      Var item = word[index];
       Var currentIndex = (int) item;
       if(iterate .Children[currentIndex] == null)
       {
          iterate .Children[currentIndex] = new Node(item);
         iterate .Children[currentIndex].number = 1;
       }
       Else
       {
 iterate .Children[currentIndex].number++;
       }
       if(index == word.Length - 1)
            iterate.Children[currentIndex].WordInDict = false;

       Iterate = iterate .Children[currentIndex];
  }
            }

Return dummyNode;
}
//ABC 
//ACD
//ABC
// test case: given prefix “A”, find ‘B’
Private static char PrefixSuggest(string prefix, Node trie)  // A
{
	if(prefix == null || trie == null)
             Return null;
          
           Var iterate = trie;  // dummy node
           Var length = prefix.Length;  // 1
           Var index = 0;
       while(iterate != null && index < length) // find the prefix first, and then look up its children and find its maximum number
{
	    Var visit = prefix[index];
                Iterate = trie[(int)visit]; 
	    if(index == length - 1)
                {
                // find maximum value of children 
               Var maxIndex = 0; 
               Var maxNo = 0;
               for(int i = 0; i < 256; i++)
               {
                     if(iterate.children[i] != null && iterate.children[i].number > maxNo)
                     {
                           maxIndex = i;
                          maxNo = iterate.children[i].number;
                      }
               }

               index++;
               Return (char) maxIndex;
              }
            }

            Return  ‘’;           // default no found -> 
}