InMemory Transpose of a sqaure matrix

/* swap every row with the corresponding column-- Let this step be called exchange
* After every exchange operation , size of matrix decreases by 1.
So further exchanges are to be made on this new reduced matrix.
So let suppose a 5 x 5 matrix, whose transpose we need to find
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

After first exchange( swapping values of row 0 with column 0 )
1 6 11 16 21
2 7 8 9 10
3 12 13 14 15
4 17 18 19 20
5 22 23 24 25

So the reduced matrix upon with subsequent exchanges are to made is a 4 x 4

7 8 9 10
12 13 14 15
17 18 19 20
22 23 24 25

Hence, the exchange Method has a loop 'for ( int k = i + 1; k < len; k++ ) {'

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}


**
*/

###### Complete Code #############################

public class TransposeOfMatrixInMemory {

public static void main( String[] args ) {
int[][] in1 = new int [][] {
{ 1, 2, 3, 4, 5 } ,
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 },
{16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 }

};
TransposeOfMatrixInMemory obj = new TransposeOfMatrixInMemory();
int[][] in = obj.transpose( in1 ) ;
for ( int i = 0 ;i < in.length; i++ ) {
for ( int j = 0; j < in[i].length ; j ++ ) {
System.out.print( in[i][j] + " " );
}
System.out.println();
}

}

/**
* Matrix is a square matrix
* @param in
* @return
*/
public int[][] transpose( int[][] in ) {
if ( in == null || in.length == 0 ) return null;

int [][] tmp = in;


int len = tmp.length;
for ( int i = 0; i < len; i++ ) {
tmp = interchange( i, in );
}
return tmp;
}

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}



}

program to Unzip a file

/**
* This Unzip Unzips a zippedfile and returns the list of filesname unzipped
* @author Nitesh
*
*/
public class Unzip {

public static void main(String[] args) {
String dir = "E:\\data\\ad";
String zipFile = "zip.zip";
try{

Unzip list = new Unzip( );
List files = getUnZippedFile( dir, zipFile );
System.out.println("Unzipped file : ----------------");
for( File f : files ) {
System.out.println( f.getAbsolutePath() );
}
}
catch (Exception e)
{
e.printStackTrace();
}
}

/**
* Unzip all the files of the for 'zipfilename'. New folder created with the same name all the inner files
* written to the folder under the 'dir' directory
* @param dir
* @param zipFileName
* @return
*/
public static List getUnZippedFile(String dir, String zipFileName ) {

if ( dir == null || dir.length() == 0 || zipFileName == null || zipFileName.length() == 0 ) {
System.out.println("Cannot unzip. No Zip files found at location at directory : " + dir + " , filename :" + zipFileName );
return null;
}
if ( ! zipFileName.endsWith( ".zip") ) {
System.out.println("Unzipping fails. This file does not seem to be a ZipFile : " + zipFileName );
return null;
}
List unzipedFiles = null;
try {

File f = new File( dir, zipFileName );

byte[] buf = new byte[1024];
ZipInputStream zipinputstream = null;
ZipEntry zipentry;
zipinputstream = new ZipInputStream(
new FileInputStream( f ));

zipentry = zipinputstream.getNextEntry();
unzipedFiles = new ArrayList();

while (zipentry != null) {
//for each entry to be extracted
/* if the zip folder is test.zip and has file atest.csv then entryName = test/atest.csv */
String entryName = zipentry.getName();
System.out.println("entryname "+entryName);
int n;
FileOutputStream fileoutputstream;
File newFile = new File( entryName );
String innerZipFile = newFile.getName(); // e.g atest.csv

String parent = newFile.getParent(); // this determines if it is a folder zip or a file zip ??? strange , yep !
File ff = null;
if ( parent == null ) {
// This is the case of file zip. create a folder with the same name as 'zipfileName'
ff = new File( dir, zipFileName.substring(0, zipFileName.lastIndexOf("." ) ) );
}else {
ff = new File( dir, newFile.getParent() ); // create folder dir + test
}

if ( ! ff.exists() ) {
ff.mkdir() ;
}
File outputFile = new File( ff, innerZipFile );
fileoutputstream = new FileOutputStream( outputFile );

while ((n = zipinputstream.read(buf, 0, 1024)) > -1) {
fileoutputstream.write(buf, 0, n);
}

fileoutputstream.close();
zipinputstream.closeEntry();

unzipedFiles.add( outputFile );

zipentry = zipinputstream.getNextEntry();

}//while

zipinputstream.close();
}
catch (Exception e)
{
e.printStackTrace();
}
return unzipedFiles;
}
}

Print continuous longest substring without repeting chars from a charcter array

Longest consecutive substring without repetition

To find the longest substring without repetition of characters from an array of characters.
Let's suppose the string is "helloforhellowhy"
There are 1 continuous substring, with maximum length, without char repetition
"forhel" -- length =6

Another Example String: "nevertheless"  
 Maximum length without repetition: "verth" -- length = 5

String : aback
output: back -- length = 4

Belwo program prints the first string. It can be modified a bit to print all the possible substrings with maximum length



--------------------------------------------------------------------------------------

public class LongestSubstring {

    public static int[] longestWithoutRepeat(char[] input) {
        if (input == null || input.length == 0)
            return null;
        HashMap map = new HashMap<>(input.length);

        int[] lastIndices = new int[] { 0, 0 };
        int[] currentIndices = new int[] { 0, 0 };
        map.put(Character.valueOf(input[0]), 0);

        int j = input.length;
        int i = 1;

        while (i < j) {
            char c = input[i];
            Integer matchingCharIndex = null;

            if ((matchingCharIndex = map.get(Character.valueOf(c))) != null) {
                map.clear();
                updateLastIndices(lastIndices, currentIndices);
                currentIndices[0] = currentIndices[1] = matchingCharIndex.intValue() + 1;
                i = currentIndices[1];
                continue;
            }
            map.put(Character.valueOf(c), i);
            currentIndices[1] = i++;
        }
        updateLastIndices(lastIndices, currentIndices);
        return lastIndices;
    }

    private static int[] updateLastIndices(int[] lastIndices,
            int[] currentIndices) {
        if ((currentIndices[1] - currentIndices[0]) > (lastIndices[1] - lastIndices[0])) {
            lastIndices[1] = currentIndices[1];
            lastIndices[0] = currentIndices[0];
        }
        return lastIndices;
    }

    private static void print(char[] input, int[] lastIndices) {
        System.out.println("Greatest len = "
                + (lastIndices[1] - lastIndices[0] + 1));
        for (int m = lastIndices[0]; m <= lastIndices[1]; m++) {
            System.out.print(input[m]);
        }
    }

    public static void main(String[] args) {

        String test = "helloforhellowhy"; // forhel, 6 passed
        String test0 = "hellofaorhellowhyasmn"; // lowhyasmn 9, passed
        String test1 = "neverthaless"; // verthal 7, passed
        String test2 = "eee"; // e, paseed
        String test3 = "heeeeiop"; // eiop, passed
        String test4 = "343jbb6n78opnei"; // b6n78op7
        String test5 = "abcabcde";
        String test6 = "aback";
        String test7 = "hellofa";
        String test8 = "abcdefcghfa"; // abcdef 6
        String test9 = "abadbg";
        String test10 = "abakk";
       
        String input = test10;
        System.out.println("Input array = " + input + " ,Length="
                + input.length());
        int[] lastIndices = longestWithoutRepeat(input.toCharArray());

        print(input.toCharArray(), lastIndices);
    }
}

In a non-Empty binary tree Number of nodes of degree two is one less than number of leaf nodes

In a non-Empty binary tree
I.e a binary tree where every node has 2 child nodes or 0 child nodes
or a binary tree where every node has a degree 2 or is a leaf node

To prove : Number of nodes of degree two is one greater than number of leaf nodes
let n0 = no of leaf nodes
n1 = no of nodes with degree 2

then to prove that :
n0 = n1 + 1


Lets go about solving this problem with a simple imagination
Let assume a healthy binary tree to be one where each node is just healthy enough to give rise to 2 other nodes.
But due to some environmental complications, the tree gets diseased or little mutated i.e now every node either give rise to 2 nodes or none at all. So it's kind of saying that the nodes have now developed a flip-flop diseased nature.

Proof:
Let Nd denote nodes having dual nature, I.e which replicate into 2
Let Ns denote nodes having singular nature, I.e nodes which do not replicate at all

Let Kth level of tree has N1 dual nature nodes

So k+1 th level number of healthy nodes = 2*N1
but since the tree is diseased so
k+1 th level has nodes = ( 2*N1 – a1 ) + a1

where a1 is the nodes of nodes got diseased, So incapable of any further reproduction into duality

At level = k + 2
number of healthy nodes = 2 * ( 2N1 – a1 )
= 4*N1 – 2a1
but the tree is non-healthy so say b1 nodes again get diseased
so k+2 level nodes can be written as

k+2 has nodes = (4N1 – 2 a1 – b1 ) + b1
where b1 is the latest number of nodes to have got diseased, So incapable of any further reproduction into duality.

Extending the same logic at next level
At level = k + 3
number of healthy nodes = 2 * ( 4N1 – 2a1 – b1 )
= 8N1 – 4a1 -2b1

but the tree is non-healthy so, say, c1 nodes again get diseased
so k+3 level nodes can be written as
k + 3 has nodes = ( 8N1 – 4a1 – 2b1 – c1 ) + c1

Now let's take a break and find out how many leaf nodes and dual-nodes are present between Level=k and level=k+3

All the nodes at k+3 are leaf nodes
leaf nodes at level k+1 = a1
leaf nodes at level k+2 = b1
so total leaf nodes = 8N1 – 4a1 – 2b1 + a1 + b1
= 8N1 – 3a1 – b1

so Ns = 8N1 – 3a1 – b1

Now lets find out the total number of dual-nodes
level k+3 = 0
level k+2 = 4N1 – 2a1 – b1
level k+1 = 2N1 – a1
level k = N1

so total dual nodes = 7N1 – 3a1 – b1
so Nd = 7N1 – 3a1 – b1

Clearly Ns = Nd + 1

So number of leaf nodes is one greater than number of dual-nodes.

We stopped at level k + 3..... The same logic can be extended to fictitious infinite level binary tree

To Find the a subsequence of number having maximum sum in an array of numbers with positive negative values

Lets know the boundary conditions of the problem first

case 1:
If in negative plane:
conditions :
a. ) If the sum is negative.
keep treack of 2 variables :
1. downfall index ( index at which downfall started from a postive, i.e if the sum is negative )
2. upward index ( index at which upward movement began. i.e just check if the next number is postive )
if upward movement then sum=a[upwardindex]

case 2:
If in positive plane
keep adding as long the sum is positive

Case 3: Analysing transition periods

1. transition from positive plane to negative plane
sum till now of postive plane needs to stored as last_postive_sum

as long we keep moving in the negative plane there is no point in updating this last sum
as it can never increase with negative numbers.

2. But as soon as a trnasition again occurs from negative to positive i.e as sooon as a positive number is found
then new sum is the this found

3. At what time should we compare current_positive_sum and last_positive_sum
a. When a transition occurs from postive plane to negative. i.e when the downindex is freshly updated
then if current_postive_sum > last_positive_sum
then last_positive_Sum = current_positive_sum

4. The whole problem should be analysed by making a graph with y-axis, extending both in neg and posittive directions
values of y-axis are the array values
X-axis is the index of the array



/**
* @author Nitesh
*/
public class MaxSumInArray {

public static int maxSum( int[] in ) {
if ( in.length == 1 ) {
return in[0];
}
int negativeMax = in[0];
boolean notfound = true;
int i = 0;
for ( i = 1; i < in.length; i++ ) {

if ( in[i] < 0 && notfound ) {
if ( in[i] > negativeMax ) negativeMax = in[i];
continue;
}
notfound = false;
break;

}

if ( notfound && in[0] < 0 ) {
System.out.println( "all number are negative. Returning min negative");
return negativeMax;
}
if ( in[0] >= 0 ) {
i = 0;
}
System.out.println("Got the first postitive index :" + i + " , number=" + in[i] );

int current_max = in[i];
int last_max = current_max;
int downfall_index = -1;
int upward_iundex = -1;

for ( int j = i+1; j < in.length ; j++ ) {

/* first check the transition from negative plane to postive plane *
* in that case
* conditions :
* downward_index > -1
* and a[j] > 0
*/
if ( in[j] >= 0 && downfall_index > -1 ) {
downfall_index = -1;
current_max = in[j];
if ( current_max > last_max ) {
last_max = current_max;
}
continue;
}


/*
* If already moving in the negative plane then no need
* to update any pointer, either current_max, last_max, or any index
* condition :
* downward_index > -1
* and
* in[j] < 0
*/
if ( in[j] < 0 && downfall_index > -1 ) {
continue;
}

int t = current_max;
current_max += in[j];

/**
* If in positive plane then just update last max
* and continue
*/
if ( current_max >= 0 ) {
if ( current_max > last_max ) last_max = current_max;
continue;
}


/*
* if transition from positive plane to negative plane, i.e new_sum < 0 ?
*/

assert (current_max < 0 && downfall_index == -1);

if ( current_max < 0 && downfall_index == -1 ) {
downfall_index = j;
// now update last_max, i.e current_max might now be last_max
if ( t > last_max ) last_max = t;

}else {
System.out.println("Something wrong in ALGO ");
}

}

return last_max;
}

public static void main( String[] args ) {
int in[] = { 15,10, -3, -4, -5 }; // 25 ok ... pos, neg

int in1[] = { -3,-1,-22, -3, -4, -5 }; // -1 ok .... only negative

int in2[] = { 10, 13, -4, -6, 22, 1, -17, -19, 2 }; // 36 ok.. pos, neg, pos..

int in3[] = { 6,-11,-10,5 }; // 6 ok... pos, negative plane, positive plane

int max = maxSum( in3 );
System.out.println( "max=" + max );
}

}