Saturday 23 January 2016

Singleton Pattern in Java

Singleton pattern is required when we want to create only 1 instance of the class through out the application. There are many ways to create a singleton class and, so many loopholes/ways to break the Singleton behavior. We have to consider below points before writing the code.

1) Creation of Object Should be lazy.
2) Same object should be returned while deserializing
3) It should not allow to create a object using reflection
4) It should not allow to create new object through clone method
5) It should be thread safe.

Code:
public class Singleton implements Serializable {

    /**
     *
     */
    private static final long serialVersionUID = 1L;
    private   Singleton singleton=MySingleton.INSTANCE;

     private static class MySingleton {
        private static final Singleton INSTANCE = new Singleton();
    }

    private Singleton() {
        if (singleton != null) {
            throw new RuntimeException("Can't instantiate singleton twice");
        }
    }

    public static Singletone getInstance() {
        return MySingleton.INSTANCE;
    }

    protected Object readResolve() {
        return getInstance();
    }
protected Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException();
    }
}

Thursday 21 January 2016

Search all the words for a given prefix in Dictionary

TRIE is best suitable Structure to maintain a Dictionary. Suppose we want to get the words which has given word as prefix.
To provide this functionality, Our TRIE Node will slightly different from what we have seen in previous post.  Trie will have one more attribute to store the actual word.

New TRIE Node: 


import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TrieNode {
    char data;
    boolean is_end_of_string;
    Map<Character, TrieNode> nodes;
    String actualWord;

    public TrieNode(char data) {
        this.data = data;
        is_end_of_string = false;
        nodes = new HashMap<Character, TrieNode>();
    }

    public TrieNode children(char data) {
        return nodes.get(data);
    }
    private Map<Character, TrieNode> getAllchildren() {
        return nodes;
    }

    public boolean isChildExist(char c) {
        return children(c) != null;
    }

    public void insert(String s) {
        if (s == null || s.trim().length() == 0) {
            return;
        }
        TrieNode current = this;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!current.isChildExist(c)) {
                TrieNode node = new TrieNode(c);
                current.nodes.put(c, node);
            }
            current = current.children(c);
        }
        current.actualWord=s;
        current.is_end_of_string = true;
    }

    public boolean search(String s) {
        TrieNode current = getLastNode(s);
        return current!=null?current.is_end_of_string:false;
    }

    private TrieNode getLastNode(String s) {
        TrieNode current = this;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!current.isChildExist(c)) {
                return null;
            }
            current = current.children(c);
        }
        return current;
    }

    public List<String> searchWithPrefix(String s) {
        List<String> retval=new ArrayList<String>();
        TrieNode current = getLastNode(s);
        if(current!=null){
            if(current.is_end_of_string){
                retval.add(s);
            }
            current.getAllChildrens(retval);
           
        }
        return retval;
    }
    private void getAllChildrens(List<String> retval){
        TrieNode current=this;
        Map<Character, TrieNode> nodes=current.getAllchildren();
        Collection< TrieNode> sets=nodes.values();
        for (TrieNode trieNode : sets) {
            if(trieNode.is_end_of_string){
                retval.add(trieNode.actualWord);
            }
            trieNode.getAllChildrens(retval);
        }
    }

}







TRIE looks like :



import java.util.List;

public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode(' ');
    }

    public void insert(String s) {
        if (s == null || s.trim().length() == 0) {
            return;
        }
        root.insert(s);
    }

    public boolean search(String s) {
        if (s == null || s.trim().length() == 0) {
            return false;
        }
        return root.search(s);
    }
    public void searchWithPrefix(String s) {
        List<String> list=root.searchWithPrefix(s);
        for (String string : list) {
            System.out.println(string);
        }
       
    }
}





Main Class:


public class TrieMain {
    public static void main(String[] args) {
        Trie t=new Trie();
        t.insert("vishnu");
        t.insert("vishnu");
        t.insert("vishnu");
        t.insert("vishnu");
        t.insert("agarwal");
        t.insert("agarwal");
        t.insert("vishal");
        t.insert("vishal");
        t.insert("vishal");
        t.insert("vishal");
        t.insert("vish");
        t.insert("vish");
        t.insert("vish");
        t.insert("vikash");
        t.insert("vijay");
        t.insert("vimal");
        t.insert("agara");
        t.insert("agara");
        t.insert("agara");
        t.insert("agara");
        t.insert("agara");
        t.insert("agara");
        t.searchWithPrefix("vi");
       
    }
}



OUTPUT will be:


vish
vishal
vishnu
vimal
vijay
vikash