Common Interview Questions - Algorithms & Data Structures

Auto Complete (Word Search) using Trie [Java]

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.ListIterator; 
 
 /**  
  * @author sumith.puri  
  *   
  * AutoComplete using Trie  
  */  
 public class AutoComplete {  

      TrieC root = null;  

      public static void main(String[] args) {  

           // tea party, tea park, tea parking, ten park, tee park, tel number  
           AutoComplete autoComplete = new AutoComplete();  
           autoComplete.loadTrie("tea party");  
           autoComplete.loadTrie("taa park");  
           autoComplete.loadTrie("tal park");  
           autoComplete.loadTrie("tea pair object f");  
           autoComplete.loadTrie("tea party was long");  
           autoComplete.loadTrie("tea party america");  
           autoComplete.loadTrie("tea par japan");  
           autoComplete.loadTrie("tea nol");  
           List<String> ac=autoComplete.search("tea");  
           for(String s: ac) System.out.println(s);  
      }  

      public void loadTrie(String word) {  

           boolean isRoot=false;  
           if(root==null) {  
                TrieC trie = new TrieC(new Character(' '));  
                root = trie;                                
           }   

           TrieC start = root;  
           char[] characters = word.toCharArray();  

           for(char c: characters) {                      

                if(start.getNext().size()==0) {                      
                     start=start.setNext(c);                           
                } else {  
                     ListIterator<TrieC> it = start.getNext().listIterator();  
                     TrieC ch = null;  
                     while(it.hasNext()) {  
                          ch = it.next();                           
                          if(ch.getNode() == c) {                                
                               break;                                
                          }  
                     }       
                     if(ch.getNode()==c) {                                     
                          start=ch;                      
                     } else {                                     
                          start=start.setNext(c);  
                     }  
                }  
           }  
      }  

      public List<String> search(String prefix) {  

           List<String> list = new ArrayList<String>();  
           if(prefix==null || prefix.length()==0) return list;  
           TrieC start = root;  
           char[] chars = prefix.toCharArray();  
           boolean flag=true;  

           for(char c: chars) {  

                if(start.getNext().size() > 0) {  

                     for(TrieC ch: start.getNext()) {  
                          if(ch.getNode()==c) {  
                               start=ch;  
                               flag=true;  
                               break;  
                          }  
                     }  
                } else {  
                     flag=false;  
                     break;  
                }  
           }  

           if(flag) {  
                System.out.println(start.getNode()+":"+prefix);  
                List<String> matches = this.getAllWords(start, prefix);  
                return matches;  
           }  

           return list;  
      }  

      private List<String> getAllWords(TrieC start, String prefix) {  

           if(start==null || start.getNext().size() == 0) {  

                List<String> list = new java.util.LinkedList<String>();  
                list.add(prefix);  
                return list;  
           } else {                 

                List<String> list = new java.util.LinkedList<String>();  
                for(TrieC ch: start.getNext()) {  
                     if(start!=null) {  
                          start = ch;  
                     }  
                          list.addAll(getAllWords(start, prefix+ch.getNode()+""));  
                }  
                return list;  
           }  
      }  
 }  

 class TrieC {  

      Character node;  
      List<TrieC> next;  

      TrieC(Character c) {  
           this.node=c;  
           next=new java.util.LinkedList<TrieC>();  
      }  

      public TrieC setNext(Character c) {  
           TrieC trie = null;  
           trie=new TrieC(c);  
           next.add(trie);  
           return trie;  
      }  

      public TrieC getNextByCharacter(Character c) {  
           return next.get(c);  
      }  

      public List<TrieC> getNext() {  
           return next;  
      }  

      public Character getNode() {  
           return node;  
      }  
 }  

Longest Palindrome (Continuous Substring) in a String [Java]

 /**  
  * @author sumith.puri  
  *   
  * O(n*n) : Time Complexity   
  */  
 public class LongestPalindrome {  
      
    public static String longestPalindrome(String gString) {  

           String lString=gString.substring(0,1), pString=null;            

           for(int i=0;i<gString.length()-1;i++) {                 

                pString=findPalindrome(gString, i, i);  

                if(pString.length()>lString.length()) {  
                     lString = pString;  
                }                 

                pString=findPalindrome(gString, i, i+1);  

                if(pString.length()>lString.length()) {  
                     lString = pString;  
                }  
           }  
           return lString;  
      }  

      public static String findPalindrome(String gString, int start, int end) {            

           int length=gString.length();  
           if(start > end) return null;  

           while(start>=0 && end < length && gString.charAt(start)==gString.charAt(end)) {  
                start--;  
                end++;  
           }            

           return gString.substring(start+1, end);  
      }  

      public static void main(String[] args) {            

           String iString="12232133123111";  
           System.out.println(longestPalindrome(iString));  
      }  
 }