bag

Definition: An unordered collection of values that may have duplicates.
Formal Definition: A bag has a single query function, numberIn(v, B), which tells how many copies of an element are in the bag, and two modifier functions, add(v, B) and remove(v, B).

A Bag is a data structure containing any amount of elements. It differs from a set in that it allows multiple instances of items to be contained in the collection, and is thus more geared towards "counting" items. The Bag data structure contained in this library is implemented by using a Dictionary{<T, int> data structure, keeping a reference to the number of items contained in the Bag.

Read full article from bag

Java里多个Map的性能比较（TreeMap、HashMap、ConcurrentSkipListMap） | Hongtium后端技术

TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。
ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。

Skip list的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法。
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

Ø  ConcurrentSkipListMap具有Skip list的性质 ，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

Ø  TreeMap插入数据时平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡，因此Skip list比较容易实现，而且相比平衡树有着较高的运行效率。

Read full article from Java里多个Map的性能比较（TreeMap、HashMap、ConcurrentSkipListMap） | Hongtium后端技术

Skip lists are fascinating!

Skip lists are a fascinating data structure: very simple, and yet have the same asymptotic efficiency as much more complicated AVL trees and red-black trees. 

skip list can be directly used to implement some operations that are not efficient on a typical sorted set:

• Find the element in the set that is closest to some given value, in O(log N) time.
• Find the k-th largest element in the set, in O(log N) time. Requires a simple  augmentation of the the skip list with partial counts.
• Count the number of elements in the set whose values fall into a given range, in O(log N) time. Also requires a simple augmentation of the skip list.

Instead of ensuring that the level-2 list skips every other node, a skip list is designed in a way that the level-2 list skips one node on average. In some places, it may skip two nodes, and in other places, it may not skip any nodes. But overall, the structure of a skip list is very similar to the structure of a sorted multi-level list.
It allows simple O(log N) insertions and deletions.

• Insertion: decide how many lists will this node be a part of. With a probability of 1/2, make the node a part of the lowest-level list only. With 1/4 probability, the node will be a part of the lowest two lists. With 1/8 probability, the node will be a part of three lists. And so forth. Insert the node at the appropriate position in the lists that it is a part of.

public void Insert(int value)
    {
        // Determine the level of the new node. Generate a random number R. The number of
        // 1-bits before we encounter the first 0-bit is the level of the node. Since R is
        // 32-bit, the level can be at most 32.
        int level = 0;
        for (int R = _rand.Next(); (R & 1) == 1; R >>= 1)
        {
            level++;
            if (level == _levels) { _levels++; break; }
        }

        // Insert this node into the skip list
        Node newNode = new Node(value, level + 1);
        Node cur = _head;
        for (int i = _levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = cur.Next[i])
            {
                if (cur.Next[i].Value > value) break;
            }

            if (i <= level) { newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode; }
        }
    }

Deletion: remove the node from all sorted lists that it is a part of.

   public bool Remove(int value)
    {
        Node cur = _head;

        bool found = false;
        for (int i = _levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = cur.Next[i])
            {
                if (cur.Next[i].Value == value)
                {
                    found = true;
                    cur.Next[i] = cur.Next[i].Next[i];
                    break;
                }

                if (cur.Next[i].Value > value) break;
            }
        }

        return found;
    }

   public bool Contains(int value)
    {
        Node cur = _head;
        for (int i = _levels - 1; i >= 0; i--)
        {
            for (; cur.Next[i] != null; cur = cur.Next[i])
            {
                if (cur.Next[i].Value > value) break;
                if (cur.Next[i].Value == value) return true;
            }
        }
        return false;
    }

Read full article from Skip lists are fascinating!

LeetCode - Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary

For example, given start = "hit", end = "cog", dict = ["hot","dot","dog","lot","log"], as one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

public int ladderLength(String start, String end, HashSet<String> dict) {
 
        if (dict.size() == 0)  
            return 0; 
 
        LinkedList<String> wordQueue = new LinkedList<String>();
        LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
 
        wordQueue.add(start);
        distanceQueue.add(1);
 
 
        while(!wordQueue.isEmpty()){
            String currWord = wordQueue.pop();
            Integer currDistance = distanceQueue.pop();
 
            if(currWord.equals(end)){
                return currDistance;
            }
 
            for(int i=0; i<currWord.length(); i++){
                char[] currCharArr = currWord.toCharArray();
                for(char c='a'; c<='z'; c++){
                    currCharArr[i] = c;
 
                    String newWord = new String(currCharArr);
                    if(dict.contains(newWord)){
                        wordQueue.add(newWord);
                        distanceQueue.add(currDistance+1);
                        dict.remove(newWord);
                    }
                }
            }
        }
 
        return 0;
    }

Also refer to http://www.darrensunny.me/leetcode-word-ladder/
Read full article from LeetCode – Word Ladder

LeetCode: Longest Common Prefix in Java | Param's Blog

1. Create Trie data structure
2. Initialize with the input Strings
3. Search for longest common prefix until word is completed or there is nothing left.

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0){
            return "";
        }
        Trie trie = new Trie();
        for(int i = 0; i < strs.length; i++){
            trie.insert(strs[i]);
            if(strs[i].equals("") || strs[i].length() <= 0){
                return "";
            }
        }
        
        return trie.longestPrefix();
    }

class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public Trie(String s){
        root = new TrieNode();
        root.insert(s);
    }
    
    public void insert(String s){
        root.insert(s);   
    }
    
    public String longestPrefix(){
        StringBuilder prefix = new StringBuilder();
        TrieNode node = root;
        while(node != null && node.children.keySet().size() == 1 && !node.isWord){
            Set set = node.children.keySet();
            for(Iterator itr = set.iterator();itr.hasNext();){
                node = node.children.get(itr.next());
            }
            prefix.append(node.val);
        }
        return prefix.toString();
    }
}
class TrieNode{
    char val;
    boolean isWord;
    HashMap children = new HashMap();
    
    public void insert(String s){
        if(s == null || s.length() <=0){
            isWord = true;
            return;
        }
        char curr = s.charAt(0);
        TrieNode child = null;
        if(children.containsKey(curr)){
            child = children.get(curr);
            
        }else{
            child = new TrieNode();
            child.val = curr;
            children.put(curr, child);
        }
        String remainder = s.substring(1);
        child.insert(remainder);
        
    }

Also read http://fisherlei.blogspot.com/2012/12/leetcode-longest-common-prefix.html
Read full article from LeetCode: Longest Common Prefix in Java | Param's Blog

Java Priority Queue (PriorityQueue) Example

PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order or we can provide a Comparator for ordering at the time of instantiation of queue.
PriorityQueue doesn’t allow null values and we can’t create PriorityQueue of Objects that are non-comparable.
The head of the priority queue is the least element based on the natural ordering or comparator based ordering, if there are multiple objects with same ordering, then it can poll any one of them randomly.
PriorityQueue is not thread safe, so java provides PriorityBlockingQueue class that implements the BlockingQueue interface to use in java multi-threading environment. PriorityBlockingQueue uses ReentrantLock to ensure thread safety.
Read full article from Java Priority Queue (PriorityQueue) Example

LeetCode - Merge k Sorted Lists (Java)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
The simplest solution is using PriorityQueue. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time (
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists.size() == 0)
return null;
//PriorityQueue is a sorted queue
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
if (a.val > b.val)
return 1;
else if(a.val == b.val)
return 0;
else 
return -1;
}
});
//add first node of each list to the queue
for (ListNode list : lists) {
if (list != null)
q.add(list);
}

ListNode head = new ListNode(0);
ListNode prev = head;

while (q.size() > 0) {
ListNode temp = q.poll();
prev.next = temp;

//keep adding next element of each list
if (temp.next != null)
q.add(temp.next);

prev = prev.next;
}

return head.next;

}
Read full article from LeetCode – Merge k Sorted Lists (Java)

Longest prefix matching - A Trie based solution in Java | GeeksforGeeks

Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.
We build a Trie of all dictionary words. Once the Trie is built, traverse through it using characters of input string. If prefix matches a dictionary word, store current length and look for a longer match. Finally, return the longest match.

class Trie {       

    // Constructor

    public Trie()   {     root = new TrieNode((char)0);       }   

   

    // Method to insert a new word to Trie

    public void insert(String word)  {

           

        // Find length of the given word

        int length = word.length();       

        TrieNode crawl = root;

           

        // Traverse through all characters of given word

        for( int level = 0; level < length; level++)

        {

            HashMap<Character,TrieNode> child = crawl.getChildren();           

            char ch = word.charAt(level);

               

            // If there is already a child for current character of given word

            if( child.containsKey(ch))

                crawl = child.get(ch);

            else   // Else create a child

            {             

                TrieNode temp = new TrieNode(ch);

                child.put( ch, temp );

                crawl = temp;

            }

        }

           

        // Set bIsEnd true for last character

        crawl.setIsEnd(true);

    }

    // The main method that finds out the longest string 'input'

    public String getMatchingPrefix(String input)  {

        String result = ""; // Initialize resultant string

        int length = input.length();  // Find length of the input string      

           

        // Initialize reference to traverse through Trie

        TrieNode crawl = root;  

          

        // Iterate through all characters of input string 'str' and traverse

        // down the Trie

        int level, prevMatch = 0;

        for( level = 0 ; level < length; level++ )

        {   

            // Find current character of str

            char ch = input.charAt(level);   

              

            // HashMap of current Trie node to traverse down

            HashMap<Character,TrieNode> child = crawl.getChildren();                       

             

            // See if there is a Trie edge for the current character

            if( child.containsKey(ch) )

            {

               result += ch;          //Update result

               crawl = child.get(ch); //Update crawl to move down in Trie

                 

               // If this is end of a word, then update prevMatch

               if( crawl.isEnd() )

                    prevMatch = level + 1;

            }           

            else  break;

        }

          

        // If the last processed character did not match end of a word,

        // return the previously matching prefix

        if( !crawl.isEnd() )

                return result.substring(0, prevMatch);       

         

        else return result;

    }

       

    private TrieNode root;     

}

Read full article from Longest prefix matching - A Trie based solution in Java | GeeksforGeeks