Data Structures | Learn for Master
• ### Best articles to explain Binary Indexed Trees

Binary Indexed Trees (Fenwick Tree)

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 – sum.

• ### 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/

• ### 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]”,

• ### Leetcode Sliding Window Maximum 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.

• ### 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

• ### LeetCode Shuffle an Array (Java)

Shuffle a set of numbers without duplicates.

Example:

Java Solution

• ### 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.

• ### 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.

• ### 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.