.
  • Best articles to explain Binary Indexed Trees

    Binary Indexed Trees (Fenwick Tree)

    from: http://algorithmsandme.in/2015/02/binary-indexed-trees/

    Why Binary Indexed Tree?

    Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is “sum” :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum[5] – sum[1].

    [Read More...]
  • union find algorithm

    Here are some good resources to learn union find set:

    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

     

    [Read More...]
  • LeetCode Serialize and Deserialize Binary Tree (Java)

    Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

    Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

    For example, you may serialize the following tree

    as “[1,2,3,null,null,4,5]”,

    [Read More...]
  • Leetcode Sliding Window Maximum

    Maximum Element Sliding Window

    Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see thek numbers in the window. Each time the sliding window moves right by one position.

    For example,
    Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

    Therefore, return the max sliding window as [3,3,5,5,6,7].

    Note:
    You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

    [Read More...]
  • Leetcode Path Sum

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    For example:
    Given the below binary tree and sum = 22,

    return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

    Java Solution

     

    [Read More...]
  • LeetCode Shuffle an Array (Java)

    Shuffle a set of numbers without duplicates.

    Example:

     
    Java Solution
     

     

    [Read More...]
  • Java HashMap Examples

    In this post, I walk through the concept of Java HashMap, and use examples to describe its usage cases. 

    What is HashMap

    Java HashMap is a Hash table based implementation of the Java Map interface.  It provides all of the optional map operations, and permits null values and the null key.  The order of Keys in a HashMap is not guaranteed. So we should not reply on the order of the keys in a HashMap. 

    HashMap vs Hashtable

    Based on java doc, Java HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

    [Read More...]
  • Java Map vs HashMap vs TreeMap vs LinkedHashMap

    Java Map

    Java Map is an interface with the following signature. 

    public interface Map<K,V>

    Here are some properties of Java Map:

    1. It defines an operation to map keys to values.
    2. A map cannot contain duplicate keys; each key can map to at most one value.
    3. The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

    4. The order of a map is dependent on its implementations. 

    [Read More...]
  • Java PriorityQueue Example

    Queue is an important data structure that offers first-in, first-out service. However, some items or tasks put in the queue may be more important than others (higher priority), and we want the items with highest priority to be served first.  We need a data structure to put the item or task with highest oder at the head of the queue. Such a data structure is called PriorityQueue.  Heaps are usually used as the underlying data structures of priority queues. 

    There are basically two operations for a priority queue: remove the maximum (or minimum) and insert new items to the queue.  

    [Read More...]
  • Java SortedMap Tutorial

    In this post, I will use examples to show how to use Java Sorted Map. A SortedMap is a Map that sort its entries in ascending order according to the keys’ natural ordering, or according to a Comparator provided at the time of building a SortedMap. SortedMap is useful if you want to quickly locate an entry that is larger than a specified key. For example, it can be used to implement a Consistent hash

    Since the entries in SortedMap are sorted by keys, all the keys in a sortedMap must implement the Comparable interface or provided a comparator when creating the SortedMap.

    [Read More...]
Page 1 of 3123