[Data Structure] Set Implementation

public class Set {
      private T arrayElement[];
      int size =0;
      public Set(){
            this.arrayElement = null;
  	}
      public Set(T[] element){
        	arrayElement = element;// array can be assigned
        	size = arrayElement.length;
  	}
  	/**
  	 *add element to set. A check is made to identify whether element is present or not.
  	 *If not the element can be inserted.
  	 * @param element
  	 */
      public void addElement(T element){
            if(!contains(element)){
                    if(size == arrayElement.length){
              	       incrementArray();
        	          }
        	          arrayElement[size++] = element;
        	  }
       }
     
  	/**
  	 * to check is element is present or not.
  	 * @param elem
  	 * @return boolean
  	 */
O(n)
      public boolean contains(T elem){
 
            if (elem == null) {
        	    for (int i = 0; i < size; i++)
                  if (arrayElement[i]==null)
              	    return true;
        	} else {
        	    for (int i = 0; i < size; i++)
                  if (elem.equals(arrayElement[i]))
              	    return true;
        	}
            return false;
  	   
  	}
     	/**
  	 * this function is used to increment the size of an array
  	 *
  	 */
      private void incrementArray(){
        	T[] temparray = arrayElement;
            int tempsize=size+5;
        	 arrayElement =(T[]) new Object[tempsize];
        	 System.arraycopy(temparray, 0, arrayElement, 0, size);
        	 
  	}
public static void arraycopy(Object src,
                             int srcPos,
                             Object dest,
                             int destPos,
                             int length)
http://www.java-samples.com/showtutorial.php?tutorialid=641 
The difference is that Arrays.copyOf does not only copy elements, it also creates a new array.System.arrayCopy copies into an existing array.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 0, 0, 0, 0]
[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
[1, 2, 3]
http://www.programcreek.com/2015/03/system-arraycopy-vs-arrays-copyof-in-java/
  	/**
  	 * return the size of set.
  	 * @return int
  	 */
      public int size(){
            if(arrayElement != null){
                  return arrayElement.length;
        	}else
                  return 0;
  	}
     
      public void clear(){
        	arrayElement = null;
  	}
     
      public String toString(){
            if(arrayElement == null  || arrayElement.length ==0 ){
                  return“[EMPTY]”;
        	}else{
              	String toStr=”[“;
                  for(int i=0;i

[Data Structure] Map using array

public class HashEntry {
      private int key;
      private int value;

   HashEntry(int key, int value) {
            this.key = key;
            this.value = value;
   }     
 
      public int getKey() {
            return key;
   }
 
      public int getValue() {
            return value;
   }
}
public class HashMap {
      private final static int TABLE_SIZE = 128;
 
   HashEntry[] table;
 
   HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
   }
 
      public int get(int key) {
            int hash = (key % TABLE_SIZE);
      // algorithm tries to find an empty one by probing consequent slots in the array. 
            while (table[hash] != null && table[hash].getKey() != key)
               hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
   }
 
      public void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
// algorithm tries to find an empty one by probing consequent slots in the array.
            while (table[hash] != null && table[hash].getKey() != key)
               hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
   }
}

Chaining /Remove
public class LinkedHashEntry {
      private int key;
      private int value;
      private LinkedHashEntry next;
 
  	LinkedHashEntry(int key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
  	}
 
      public int getValue() {
            return value;
  	}
 
      public void setValue(int value) {
            this.value = value;
  	}
 
      public int getKey() {
            return key;
  	}
 
      public LinkedHashEntry getNext() {
            return next;
  	}
 
      public void setNext(LinkedHashEntry next) {
            this.next = next;
  	}
}
public class HashMap {
      private final static int TABLE_SIZE = 128;
 
  	LinkedHashEntry[] table;
 
  	HashMap() {
            table = new LinkedHashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
  	}
 
      public int get(int key) {
            int hash = (key % TABLE_SIZE);
            if (table[hash] == null)
                  return -1;
            else {
              	LinkedHashEntry entry = table[hash];
                  // Go to end or key
                  while (entry != null && entry.getKey() != key)
                    	entry = entry.getNext();
                  // End
                  if (entry == null)
                        return -1;
                  // Key found
                  else
                        return entry.getValue();
        	}
  	}
 
      public void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
            if (table[hash] == null)
                  table[hash] = new LinkedHashEntry(key, value);
            else {
              	LinkedHashEntry entry = table[hash];
                  // Go to end or key
                  while (entry.getNext() != null && entry.getKey() != key)
                        entry = entry.getNext();
                  // Key => Update
                  if (entry.getKey() == key)
                    	entry.setValue(value);
                  // End => New Node
                  else
                    	entry.setNext(new LinkedHashEntry(key, value));
        	}
  	}
 
      public void remove(int key) {
            int hash = (key % TABLE_SIZE);
            if (table[hash] != null) {
              	LinkedHashEntry prevEntry = null;
              	LinkedHashEntry entry = table[hash];
                  while (entry.getNext() != null && entry.getKey() != key) {
                    	prevEntry = entry;
                    	entry = entry.getNext();
              	}
                  if (entry.getKey() == key) {
                        if (prevEntry == null)
                             table[hash] = entry.getNext();
                        else
                         	prevEntry.setNext(entry.getNext());
                  }
        	}
  	}
}

Dynamic Size
public static class LinkedHashEntry
{
K key;
V value;
LinkedHashEntry next;

//contructors, getters and setters below
...
}
public class HashMap
{
private double loadFactor = 0.75;
private int elemCount;;
// private final static int TABLE_SIZE = 128;
 
private LinkedHashEntry[] table;

//contructors, getters and setters below
...


/**
 * Insert your super-mega-hash-function below :)
 */
static int hash(int h)
{
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public V get(K key)
{
int hash = hash(key.hashCode())%table.length;
if (table[hash]==null) 
            return null;
else
{
LinkedHashEntry entry = table[hash];
while(true)
{
if (entry.getKey().equals(key))
{
return entry.getValue();
}
if (entry.next()==null) break;
entry = entry.next();
}
return null;
}
}

public void put(K key, V value)
{
if (elemCount > table.length*loadFactor) 
      resize();
int hash = hash(key.hashCode())%table.length;
if (table[hash]==null) 
         table[hash] = new LinkedHashEntry(key,value);
else
{
LinkedHashEntry entry = table[hash];
while(true)
{
if (entry.getKey().equals(key))
{
entry.setValue(value);
break;
}
if (entry.next()==null) break;
entry = entry.next();
}
entry.setNext(new LinkedHashEntry(key,value));
}
}
public void resize()
{
int newSize = table.length*1.5;
LinkedHashEntry[] newTable = new LinkedHashEntry[newSize];
// Move old element to new table
for (int i=0; i

[Data Structure]ArrayList Implementation

public class MyArrayList
{ //  COnstructor(), size(), add(), get(), remove(), resize()


       private Object[] myStore;
       private int actSize = 0;


       /*Constructor*/
       public MyArrayList()
       {
             myStore = new Object[10];      
       }



       /*O(1), Get the object given the index*/
       public Object get(int index)
       {
               if (index < actSize)
                     return myStore[index];
               else 
                     throw new ArrayIndexOutOfBoundsException();
       }


       /*O(1), Add Object into the array Given the Object */
      public void add(Object obj)
      {
              //validate input ?(null allowed), append, size out of bound, 
              if (  myStore.length - actSize <= 5 )
                    increaseListSize();
              myStore[actSize++] = obj;
      }

  
      /*O(n), Remove Object from the array given the index*/
      public Object remove(int index)
      {
               // validate the input, empty or not, reindexing after remove specific index out
               // idx 0  1  2  3  4  5
               //       a  b  s  o  l   u
               //               X
               //       a  b  “”  o  l  u  (nullify)
               //       a  b  o  l   u  “” (compact)
               if (index < actSize)
               {
                      Obejct obj = myStore[index];
                      myStore[index] = null;
                      int tmp = index;
                      while ( tmp < actSize) // O(n)
                      {
                            myStore[tmp]= mySotre[tmp+1];
                            myStore[tmp+1] = null;
                            tmp++;
                      }
                      actSize--;
                      return obj;
               }
               else 
               {
                      throw new ArrayIndexOutOfboundsException();
               }
      }

       
      /* Get the size of the array*/
      public int size() 
      {
               return actSize;
      }     


     /* Increase the size of the array when about to exceed the capacity*/
     private void increaseListSize()
    {
               // size make it bigger , but put all the old elements inside it
               myStore = Arrays.copyOf(mystore, myStore.length*2);
    }

public static int[] copyOf(int[] original, int newLength) { 
   int[] copy = new int[newLength]; 
   System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); 
   return copy; 
}

}

[Java] HashMap v.s. HashTable

[DP] Maximum non-overlapping Intervals

1. Example
Find the maximum number of non-overlapping intervals
s= [[0,2], [1,4], [3,5]]
the result is 2


2. Implementation
dp[i] represents the max number of non-overlapping intervals for 0~ i with i selected
non-overlapping => a.end =< b.start && b.end > b.start

collections.sort(intervals, new EndComparator(){
     @ Override
     public int compare (interval a, interval b)
     {
          return a.end - b.end;
     }
});

int[] dp = new int[intervals.size()];
int max = 0;
for (int i = 1 ; i < intervals.size(); i ++ )
{
    for ( int j = 1-1; j >=0 ; j--)
    {
          if (intervals[j].end <= intervals[i].start)
              dp[i] = Math.max( dp[j]+1, dp[i] );
    }
    max = Math.max(max, dp[i]);
}

return max; 

3. Similar Ones
http://sidbai.github.io/2015/07/07/Maximum-Non-overlapping-Intervals/

Bloom Filter ?

1. “Whenever a list or set is used, and space is consideration, a Bloom filter should be considered. When using a Bloom filter, consider the potential effects of false positives.” S is a set of n elements. Set of k hash functions with range {1...m} (or {0...m − 1}).

Mathematically
  If m is the number of bits in the array, the probability that a certain bit is not set to 1 by a certain hash function during the insertion of an element is

If k is the number of hash functions, the probability that the bit is not set to 1 by any of the hash functions is

[DB] Index ?

4. Reference:
http://www.eandbsoftware.org/how-a-database-index-can-help-performance/