Maximum subarray in an array

         /*
	 * Returns a maximum sum value in an array of integers
	 */
	public int maxScan(int[] array)
	{
		if(array.length == 0) return -1;
		else if(array.length == 1) 
			return array[0];
		else
		{	
			int maxSum = array[0];
			int current_max = array[0];
			for(int i = 1; i < array.length; i++)
			{
				current_max = Math.max(array[i], current_max + array[i]); 
				maxSum = Math.max(maxSum, current_max);
			}
			return maxSum;
		}
	}

Print matrix in a sprial order

 

Recursive Solution (Java):

public class PrintMatrixSpiral
{
 public static void main(String[] args)
 {
  int[][] matrix =
  {
  { 2, 4, 6, 2, 5, 7 },
  { 2, 5, 7, 8, 9, 3 },
  { 6, 4, 7, 3, 5, 7 } };

  printSpiral(matrix);
 }

 public static void printSpiral(int[][] matrix)
 {
  printSpiral(matrix, 0);
 }

 private static void printSpiral(int[][] matrix, int depth)
 {
  if (matrix == null && matrix.length == 0)
   return;
  int rows = matrix.length;
  int cols = matrix[0].length;
  if (2 * depth > Math.min(rows, cols))
   return;
  for (int i = depth; i < cols - depth - 1; ++i)
  {
   System.out.print(matrix[depth][i] + ",");
  }
  for (int i = depth; i < rows - depth - 1; ++i)
  {
   System.out.print(matrix[i][cols - depth - 1] + ",");
  }
  for (int i = rows - depth; i > depth; --i)
  {
   System.out.print(matrix[rows - depth - 1][i] + ",");
  }
  for (int i = rows - depth - 1; i > depth; --i)
  {
   System.out.print(matrix[i][depth] + ",");
  }
  printSpiral(matrix, ++depth);
 }
}

Find the index i and j of an array where j>i and a[j] – a[i] is maximum

 

Given an unsorted array, find the index i and j such that, j>i and (a[j] – a[i]) is maximum?

A linear time solution which I find pretty elegant:

       private void MaxDiff(int[] a)
       {
           int min = a[0]; // assume first element as minimum
           int maxdiff = 0;
           int posi = -1, posj = -1, minpos = 0;

           for (int i = 1; i < a.Length; i++)
           {
               if (a[i] < min)
               {
                   min = a[i];
                   minpos = i;
               }
               else
               {
                   int diff = a[i] - min;
                   if (diff > maxdiff)
                   {
                       maxdiff = diff;
                       posi = minpos;
                       posj = i;
                   }
               }
           }
           System.out.format("i=%d, j=%d",posi,posj);
       }

Permutations of a String

public  static void permutation(String str) { 
    permutation("", str); 
 }

 private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
           permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

compute max-depth of a binary tree

int maxDepth(struct node* node)

{

if (node==NULL) { return(0);

}

else {

int leftDepth = maxDepth(node->left);

int rightDepth = maxDepth(node->right);

if (leftDepth > rightDepth)

return(leftDepth+1);

else

return(rightDepth+1);

} }

algorithm to determine number of 1’s in binary representation of a number

To determine the number of set bits in the binary representation of a number, the basic method would be-
Find if the least significant digit of the number is 1 or not by performing AND operation with 1. Keep shifting the bits and when there are no 1’s left, the number becomes zero.

This algorithm takes O(n) time.

I read an algorithm which performs real better. I actually likes the solution where in we can deduce the number of 1’s in O(m) time where m is the number of 1’s present in the number.

The basic login is to recognize a pattern where, ‘when we perform n AND (n-1) : last 1 bit of the number sets to zero’. So, the number of times we can do this will give the number of 1’s present in the number.

A short also snippet would be-

int numberOfOnes ( int num )
{
int numOfOnes = 0;
while( num != 0 ){
num = num & (num – 1);
numOnes++;
}
return numOfOnes;
}