CareerCup

public boolean findSequenceSum (int [] a ,int T){
		for(int i=0; i<a.length; i++) {
			int sum = 0;
			int j=i;
			while (sum<T && j < a.length) {
				sum += a[j];
				j++;
			}
			if(sum==T)
				return true;
		}
		
		return false;
	}

public boolean findSequenceSum2(int[] a, int T){
		int sum = 0;
		int start = 0;
		for(int i=0; i<a.length; i++) {
			sum += a[i];
			if(sum>T) {
				while(sum >= T && start <= i) {
					sum -= a[start];
					start++;
					if(sum==T)
						return true;
				}
			} else {
				if(sum==T)
					return true;
			}
		}
		
		return false;
	}

public static int[] findMaxSubSet(int[] array){
		int max = 0;
		int startKey = 0;
		int tempCnt = 0;
		int[] maxSub = null;
		for(int i=1; i<array.length; i++){
			if(array[i]-array[i-1] == 1) {
				tempCnt++;
				
			} else {
				if(max <= tempCnt) {
					max = tempCnt;
					maxSub = Arrays.copyOfRange(array, startKey, i);
				}
				startKey = i;
				tempCnt = 0;
			}
		}
		
		return maxSub;
	}
	
	public static int[] removeDuplication(int[] array){
		int[] maxSub = new int[array.length];
		int temp = -1;
		int tempKey = 0;
		for(int a:array) {
			if(temp != a) {
				maxSub[tempKey] = a;
				tempKey++;
			}
		}
		
		return maxSub;
	}

	public static void main(String[] args) {
		//Sort (O(logn))
		int[] array = {1, 6, 10, 4, 7, 7, 9, 5};
		QuickSort qsort = new QuickSort(array.length);
		qsort.setArray(array);
		qsort.quickSort(0, array.length-1);
		array = qsort.getArray();
		//find subset (O(n))
		int[] maxSub = findMaxSubSet(array);
		maxSub = removeDuplication(maxSub);
		System.out.println(maxSub);
	}

public class Compressor {

	static StringBuffer compressed = new StringBuffer();
	public static void main(String[] args) {
		String original = "AAAABBBCXYZEEEEPPPPPKKABC";
		charCount(original);
		System.out.println(compressed);
	}
	
	public static void addString(char c, int cnt){
		if(cnt == 1)
			compressed.append(Character.toString(c));
		else
			compressed.append(Character.toString(c) + Integer.toString(cnt));
	}
	
	public static void charCount(String str){
		str += " ";
		Character temp = null;
		int cnt = 0;
		for(int i=0; i<str.length(); i++) {
			if(temp == null) {
				temp = str.charAt(i);
				cnt = 1;
			} else if(!temp.equals(str.charAt(i)) || i==str.length()-1){
				addString(str.charAt(i-1), cnt);
				temp = str.charAt(i);
				cnt = 1;
			} else {
				cnt++;
			}
		}
	}
}

/*
* compare ith char from 0 to i with (legnth -i)th char from length to length-i
* i = 0 to n/2 
* */
public boolean process(String s){
		char [] array = s.toCharArray();
		for(int i=0; i<(array.length)/2; i++){
			if(array[i] != array[array.length-i-1])
				return false;
		}
		
		return true;

private static void interSwap(){
		String[] array = {"a1","a2","a3", "a4", "a5", "b1", "b2", "b3","b4","b5"};
		
		for(int i=0; i<array.length/2-1; i++) {
			int m = array.length/2 - i;
			for(int j=0; j<i+1; j++) {
				String temp = array[m];
				array[m] = array[m-1];
				array[m-1] = temp;
				m = m+2;
			}
		}
	}

n 0 1 2 3 4
value -1 1 3 -2 2

1. define boolean inProcess = false;

2. From 0 to n, if value(n) = negative, continue

else
inProcess = true;
tempA = n;

while(inProcess) {

if(value[n] = negative)
inProcess = false;

tempB = value(n+1)
shift value(n) from n to n+1

increase n until find a negative value (m).
}

value[tempA] = tempB;

int[] array = {-1, 1, 3, 4, -2, 2};
boolean inProcess = false;
while(i<array.length) {
	if(array[i] < 0) {
	i++;
} else {
	inProcess = true;
	tempNo = i;
	while(inProcess) {

             if(tempB == null)
	           tempA = array[i];
             else
                   tampA = tempB;
                   tempB = array[i+1];
                   if(array[i+1] < 0) 
	                inProcess = false;

                   array[i+1] = tempA;
                   i++;
              }
             array[tempNo] = tempB;
       }
}