Maximum Sum of a Set of Contiguous Positive Numbers in an Array:

An Array contains random positive as well as negative numbers. It may contain a streak of positive numbers and then a few negative numbers. This behaviour can occur multiple times.

You need to find out the maximum sum out of all streaks of the positive numbers.

For example:

Input1: 6

Input2: {1,2,3-4,3,1}

Output: 6

Input2: 7

Input2: {-1,3,1,2,-1,2,7}

Output: 9

The explanation for First Example :

Input 1: Number of Elements in the array

Input 2: Array Elements

Output: Maximum Sum of a Set of Contagious Positive Number in an Array:

In the first example there are two contagious set of positive numbers:

{1,2,3} and {3,1}. for which the sum is: 6 and 4, so the maximum out of them is 6.

CODE:

package arrays;

import java.util.Scanner;

public class MaximumSumContPositiveNum

     {

     public static void main(String[] args)

     {

     int curSum = 0, maxSum = -1;

     Scanner sc = new Scanner(System.in);

     System.out.println("Enter the length of Array");

     int n = sc.nextInt();

     int ar[] = new int[n];

     System.out.println("Enter the array Elements");

     for (int i = 0; i < n; i++)

     {

          ar[i] = sc.nextInt();

     }

     for (int idx = 0; idx < n; idx++)

     {

          if (ar[idx] >= 0)

          {

               curSum = curSum + ar[idx];

               if (curSum > maxSum)

               {

                    maxSum = curSum;

               }

          } 

          else

          {

               curSum = 0;

          }

     }

     System.out.println("Maximum Sum of a Set of Contagious Positive Number in an Array is " + maxSum);

     }

}

OUTPUT:

Enter the length of Array

7

Enter the array Elements

-1 3 1 2 -1 2 7

Maximum Sum of a Set of Contagious Positive Number in an Array is 9

Solution to Fibonacci series by Recursion through Dynamic Programming

Solution to Fibonacci series by Recursion through Dynamic Programming

Context: In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

• 1,1,2,3,5,8,13,21,34,55...

Here, the first two numbers in the Fibonacci sequence are 1 and each subsequent number is the sum of the previous two.

The sequence Fn of Fibonacci numbers is defined by the recurrence relation:

• Fn = Fn-1 + Fn-2 with Base values F1=1 and F2=1

Problem: Find the Fibonacci number at the given position entered by the user through Recursion.

Conventional Solution: 

package com.practice.recursion;

import java.util.Scanner;

public class Fibonacci
{
    public static void main(String...s)
    {
Scanner sc= new Scanner(System.in);
System.out.println("Please Enter the number");

int num=sc.nextInt();

int fibonacciNumber=getFibonacci(num);

System.out.println("The Fibonacci Number at Postion "+ num+" is:"+fibonacciNumber);

sc.close();

    }
    public static int getFibonacci(int n)
    {
if(n==1|| n==2)

{

           return 1;
}

return getFibonacci(n-1)+getFibonacci(n-2);

    }
 }

Output:

Please Enter the number

12

The Fibonacci Number at Position 12 is:144

The problem with this solution is that this solution will have serious performance issues for large numbers.

So we will use the technique of Memoization to reduce the time.

What we will do is, we will store each calculated Fibonacci in a storage array and use this value in the calculation of the upcoming calculation of Fibonacci.

Memoization Solution: 

package com.practice.recursion;

import java.util.Scanner;

public class Fibonacci
{
    public static void main(String...s)
    {
Scanner sc= new Scanner(System.in);
System.out.println("Please Enter the number");

int n=sc.nextInt();

int fibonacciNumber=fibonacciMemo(n,new int[n+1]);
System.out.println("The Fibonacci Number at Postion "+ n+" is:"+fibonacciNumber);
sc.close();

}

        public static int fibonacciMemo(int n, int strg[]) 
      {

if (n == 0 || n == 1) {

return n;

}

if (strg[n] != 0) {

return strg[n];

}

int fnm1 = fibonacciMemo(n - 1,strg);

int fnm2 = fibonacciMemo(n - 2,strg);

int res = fnm1 + fnm2;

strg[n] = res;

return res;

}

}

Please Enter the number

43

The Fibonacci Number at Position 43 is:433494437

PS: Try to notice that I have made a storage array of size equal to n+1.

The reason for that is the zeroth index value will contain the value of 0th Fibonacci and 43rd index value will contain the value of 43rd Fibonacci but to accommodate the 43rd value we should also have an index 43rd. And for the 43rd index, the array should be made of size 44 !!

Simple Solution 2 Scenario --(Odd or Even length ) 

Base condition &  Algo recursive(str, i, j)

1. i==j //even len
2. if i< j  recurve call (str, i +1,j-1)
3. else ch[i] ==ch[j] // Extra base condition odd len

public class HelloWorld {

 static boolean ispalindrome(char ch[], int i, int j) {
  if (i == j) return true;
  if (i < j) {
   if (ch[i] != ch[j])
    return false;
   else
    return ispalindrome(ch, i + 1, j - 1);
  }
  if (ch[i] != ch[j])
   return false;
  else
   return true;
 }
 public static void main(String[] args) {
  System.out.println(ispalindrome("jatin".toCharArray(), 0, 4));
  System.out.println(ispalindrome("nitin".toCharArray(), 0, 4));
  System.out.println(ispalindrome("jatinn".toCharArray(), 0, 5));
  System.out.println(ispalindrome("nittin".toCharArray(), 0, 5));
 }
}

Josh : playtime with array

Question:Sorted Array have given to you.now a hacker swap odd index value with other odd index value.WAP that serach the element and return it's index in logn complexity.
Example: original sorted  array :{1,2,3,4,5,6,7,8}
              swapped given array:{1,4,3,2,5,8,7,6},key,5(element for searching)
              Output 4(it's index).

Print Start Pattern Using Recursion

Output :

X 
X X 
X X X 
X X X X 
---------------------
X X X X 
X X X 
X X 
X 

JAVA Code:

public class HelloWorld {

 static int count = 0;

 public static void print(int i, int j) {

  if (i <= 0 || j < 0 ) return;

  System.out.print("X ");

  print(i, j - 1);

  if (j == 0) {

   count++;

   System.out.println();

   print(i - 1, count);





  }

 }

   public static void print2(int i, int j) {

  if (i <= 0 || j < 0 ) return;

System.out.print("X ");

print2(i, j - 1);





  if (j == 0) {



   System.out.println();

   print2(i - 1, i-2);





  }

}





 public static void main(String[] args) {

  //System.out.println("Hello World2");

  print(4, 0);

  System.out.println("---------------------");



  print2(4, 3);

 }

}

Big Data Analytics:Deep Findings

Question
You are given a tree with N nodes. Each node is given an integer value from 0 to N­1 . Tree given as an input will be an array of parent nodes.
You need to find following (all mandatory):
1 . The depth of the tree (Aim for O(N))
2. Maximum number of children for any node in whole tree (Aim for O(N))
3. Nearest Common Ancestor for two given nodes (Aim for O(log(N)))
INPUT FORMAT
First line has the value of N
Second line has list of N values where the number at index ‘i’ is the parent of node ‘i’. The parent of root is
­1 . ( The index has the range [0,N­1 ] )
Third line contains two integers within the range of [0,N­1 ] whose common ancestor you have to find.
OUTPUT FORMAT
First line has the depth of the tree. Second line has the max children.
Third has the nearest common ancestor to two
given nodes n1 and n2.

Sorting Tutorial

What is Sorting ? Why Sorting?

Sotring is an algorithms  that arranges the elements of a list in certain order.it can be in ascending , descending or any other fashion.sometimes sorting reduces the problem complexity.we can reduce the search complexity.

Classification  categories of sorting ?

1.Number of Comparision 

2.Number of Swap

3.Memory Usages

4.By Recursion

5.Adaptability

Other ways are :

1.INTERNAL(uses main memory only) 

2.EXTERNAL SORT(uses external memory ).

1. Bubble Sort

2. Insertion Sort

3. others

Bubble Sort

Bubble Sort is the simplest sorting algorithm. It works by iterating the input from the first to last.Comparing each pair and swapping them if needed. Bubble sort continues until no swapping needed.it got its name  from the way smaller elements "bubble"  to the top of the list.

Google code jam :Standing Ovation

Problem

It's opening night at the opera, and your friend is the prima donna (the lead female singer). You will not be in the audience, but you want to make sure she receives a standing ovation -- with every audience member standing up and clapping their hands for her.