Friday, June 19, 2015

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)); } }