junminstorage

package org.blueocean.hash;

import java.util.Arrays;
import java.util.Random;

/*
 * an implementation of int to int hash based on open addressing linear probing approach
 * 
 * only int[] array is maintained, <k, v> is inserted using a serial of steps and 
 * based on a hash function hash(k, step) to find a open slot 

junminstorage

public class SortQ {

	public static class Node {
		int d;
		Node next;
	}
	
	
	public static Node merge_sort2(Node head){
		assert(head!=null);

junminstorage

package org.blueocean;

public class RabinKarpString {
	static final int prime = 101;
	static final int base = 103;
	
	public static void rabinKarp(String s){
		assert(s!=null && !s.isEmpty());
		long leftHash = s.charAt(0);
		long rightHash = s.charAt(0);

junminstorage

public static void rotateMatrixByElement(int[][] matrix){
		int num = matrix.length;
		for(int i=0; i<num/2; i++){
			int start = matrix[i][i];
			//shift up on column i
			for(int row=i; row<num-i-1; row++){
				matrix[row][i] = matrix[row+1][i];
			}
			//shift left on row num-i-1
			for(int col=i; col<num-i-1; col++){

junminstorage

public static int findContinuous1s(String s, int maxFlips){
		int[] max = new int[1];
		findContinuous1sRec(s, 0, 0, maxFlips, 0, max);
		return max[0];
	}
	
	public static void findContinuous1sRec(String s, int start, int current, int maxFlips, int flips, int[] max){		
		//keep on eating up 1s if we can
		while(current<s.length() && s.charAt(current) == '1')
			current++;

junminstorage

public static int findContinuous1s(String s, int maxFlips){
		int[] max = new int[1];
		findContinuous1sRec(s, 0, 0, maxFlips, 0, max);
		return max[0];
	}
	
	public static void findContinuous1sRec(String s, int start, int current, int maxFlips, int flips, int[] max){		
		//keep on eating up 1s if we can
		while(current<s.length() && s.charAt(current) == '1')
			current++;

junminstorage

public static int minPath(List<int[]> input){
  int levels = input.size();
  int[][] dp = new int[levels][levels];

  //we start at the bottom
  //here the min path sum is the numbers at the bottom
  dp[levels-1] = input.get(levels-1);

  //now we go up
  for(int l=levels-2; l>=0; l--){

junminstorage

public static int minPathBetter(List<int[]> input){
  int levels = input.size();
  int[] dp = new int[levels];
  //we start at the bottom
  //here the min path sum is the numbers at the bottom
  dp = input.get(levels-1);
  //now we go up
  for(int l=levels-2; l>=0; l--){
   for(int pos = 0; pos<=l; pos++){
    dp[pos] = Math.min(dp[pos], dp[pos+1]) + input.get(l)[pos];

junminstorage

/*
	 * the algorithm will generate sums for all possible subset of the array
	 * and put them into a hash, return true if the target is found in the hash
	 * the optimization here is to check hash contains the target during the update
	 */
	public static boolean sumOfSubSet(int[] nums, int target){
		Set<Integer> sums = new HashSet<Integer>();
		//start with empty set
		sums.add(0);
		if(sums.contains(target))

junminstorage

public static int minimumSizeArray(int[] nums, int s){
	int min = Integer.MAX_VALUE, sum = 0;
	int p1=0,p2=0,len=nums.length;
	while(p2<len && p1<len){
		sum += nums[p2];

		while(p1<len && sum >=s){
			min = Math.min(p2-p1+1, min);
			sum -= nums[p1];
			p1++;