Dynamic Programming : ZigZag : TCCC03 Semi Final 3 level 1

December 31, 2012
	public int longestZigZag(int[] sequence){
		if(sequence.length == 1) return 1;
		int[] L = new int[sequence.length];
		int[] diff = new int[sequence.length-1];
		int maxLength = 1;
		boolean maxValue;
		
		for(int j =0; j<(sequence.length - 1);j++){
			diff[j] = sequence[j+1] - sequence[j];
		}
		if(diff[0] >= 0) maxValue = true;
		else maxValue = false;
		
		for(int j = 1; j< diff.length;j++){
			boolean curValue= maxValue;
			if(diff[j] > 0 ) curValue = true;
			else if(diff[j]<0) curValue = false;
			if(curValue != maxValue){
				maxLength++;
				maxValue = curValue;
			}
		}
		
		return maxLength+1;
	}
Advertisements

Benchmark Trade Bond Price Challenge : kaggle

December 26, 2012

This post was long overdue. I participated in the benchmark trade bond pricing challenge and used a regression based approach to predict bond prices. Here is an outline of the approach.

  1. Build on the training set and predict on the test set. The dependent variable we are trying to predict is the bond price and the independent variables are last 10 trade prices.
  2. Prepare frequency charts based on callability is 0 or 1.
  3. Divide the data into 12 parts – callability, price > 100 or price < 100(bond price will always converge to 100 so the curve will look different), types of trade in the bond (dealer to dealer, dealer to client, client to client – quotes driven market)
  4. Some of the values were missing – missing value treatment (based on exponential weights)
  5. Run regression on these sub-data sets and analyze the results
  6. Some of the t-tests failed – bond ids and time to delay – p value that was kept as cut off for rejecting the coefficients is 3%

Notes :

  1. R2 is a statistic that will give some information about the goodness of fit of a model. In regression, the R2 coefficient of determination is a statistical measure of how well the regression line approximates the real data points. An R2 of 1.0 indicates that the regression line perfectly fits the data.
  2. R2   measures goodness of fit. But it will not detect overfit because it will increase with any new predictor (unless it has already reached 1).
  3. Assumptions of Regression
  4. L Linear relationship
    I Independent observations
    N Normally distributed around line
    E Equal variance across X’s
  5. Multicollinearity : When two independent variables are correlated and its detection – Variance Inflation Factor
  6. A p-value is the probability of an observed or more extreme result arising by chance. So, if p<.03, then that probability is quite less and hence, we can keep that independent variable

 

I have been away from data science now because of job change and interviewing. New Year Resolution : get back to kaggle .


Learning and Mastering Java

December 25, 2012

Here is my target list for the enxt year. I have read all these books in some bits and pieces, but this year I want to be thorough with my knowledge.

1) SUN Certified Java programmer for  Java 6 exam

2) A programmer’s guide to SCJP Certification

3) Effective Java

4) Java Concurrency in Parctice

5) Head First Design Patterns

6) Java Puzzlers

7) Java Generics and Collections


SRM 208 Div 1 : TallPeople

December 25, 2012

public int[] getPeople(String[] people) {
int[] ret = new int[2];
int R=people.length,C=people[0].split(" ").length;
int[][] arr = new int[R][C];

for(int i = 0;i<R;i++){
String[] split = people[i].split(" ");
for(int j=0;j<C;j++){
arr[i][j] = Integer.parseInt(split[j]);
}
}

int maxMinRow = Integer.MIN_VALUE;
for(int i = 0;i<R;i++){
int minRow = Integer.MAX_VALUE;
for(int j=0;j<C;j++){
if(arr[i][j]< minRow)
minRow = arr[i][j];

}
if(maxMinRow < minRow)
maxMinRow = minRow;
}
ret[0] = maxMinRow;

int minMaxCol = Integer.MAX_VALUE;
for(int i = 0;i<C;i++){
int maxCol = Integer.MIN_VALUE;
for(int j=0;j<R;j++){
if(arr[j][i]> maxCol)
maxCol = arr[j][i];

}
if(minMaxCol > maxCol)
minMaxCol = maxCol;
}
ret[1] = minMaxCol;

return ret;
}


SRM 236 Div 1 : BusinessTasks

December 25, 2012

Hello Competitive Programming ! My first entry into topcoder :

SRM236 Div 1 : BusinessTasks


public class BusinessTasks
{
public String getTask(String[] list, int n)
{
List<String> myList = new ArrayList<String>();
for(int i=0;i<list.length;i++) {
myList.add(list[i]);
}
int pos = 0;
while (myList.size() > 1) {
pos = (pos + n - 1)%myList.size();
myList.remove(pos);
pos = pos % myList.size();
}
return myList.get(0);
}
}

Related Links :

  1. Josephus problem
  2. A variant of this also appeared in Amazon interviews

Implement an algorithm to print all valid (e g , properly opened and closed) combinations of n-pairs of parentheses

December 25, 2012

Input : 3

Output : ()()(), ()(()), (())(), ((()))


public static void printPar(int l, int r, char[] str, int count) {
if (l < 0 || r < l) return; // invalid state
if (l == 0 && r == 0) {
System.out.println(str); // found one, so print it
} else {
if (l > 0) { // try a left paren, if there are some available
str[count] = ‘(‘;
printPar(l - 1, r, str, count + 1);
}
if (r > l) { // try a right paren, if there’s a matching left
str[count] = ‘)’;
printPar(l, r - 1, str, count + 1);
}
}
}



Sudoku Solver

December 2, 2012

The Sudoku solver can be implemented as a recursive backtracking solution.

Pseudo Code for any backtracking solution :

bool Solve(configuration conf)
{
if (no more choices) // BASE CASE
return (conf is goal state);
for (all available choices) {
try one choice c;
// solve from here, if works out, you’re done
if (Solve(conf with choice c made)) return true;
unmake choice c;
}
return false;  // tried all choices, no soln found
}