Fibonacci Problem :Calculate the sum (F(X) + F(X + 1) + ... + F(Y)) mod 1000000007, where F(N)=F(N-1)+F(N-2),N>=2

Interview question asked in OYO Rooms company.

You are given two non-negative integers X and Y, you have to calculate the sum
(F(X) + F(X + 1) + ... + F(Y)) mod 1000000007, where F(N)=F(N-1)+F(N-2),N>=2.

Input

The two non-negative integers X and Y.

Output

For each test case you have to output a single line containing the answer.
Since the answer can be huge i.e go out of the bounds of integers, You are required to print the answer MOD 10^9+7

Example

Input:

2 6

Output:

19

Explanation

The fibonacci series is like this  0 ,1, 1, 2, 3, 5, 8, 13, 21,....

For the test case, we need to calculate the sum of the Fibonacci series from its 2nd term till 6th. ( i.e 1 + 2 + 3 + 5 + 8 ) = 19%(10^9+7) = 19

import java.math.BigInteger;  
 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Scanner;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class FibonacciProblem {  
      /**  
       * @param args  
       */  
      public static void main(String a[]) {  
           int mod = 1000000007;  
           Scanner sc = new Scanner(System.in);  
           int x = sc.nextInt();  
           int y = sc.nextInt();  
           List<Integer> list = new ArrayList<Integer>();  
           list = getFibo(y);  
           if (!list.isEmpty()) {  
                int sum = 0;  
                BigInteger result = BigInteger.valueOf(0);  
                for (int j = x; j <= y; j++) {  
                     sum = sum + list.get(j);  
                }  
                result = BigInteger.valueOf(sum % mod);  
                System.out.println("Result:" + result);  
           }  
      }  
      private static List<Integer> getFibo(int y) {  
           // TODO Auto-generated method stub  
           List<Integer> l = new ArrayList<Integer>();  
           int a = 0;  
           int b = 1;  
           if (y == 0) {  
                return l;  
           }  
           if (y == 1) {  
                l.add(a);  
                l.add(b);  
                return l;  
           } else {  
                l.add(a);  
                l.add(b);  
                for (int i = 2; i <= y; i++) {  
                     int sum = a + b;  
                     a = b;  
                     b = sum;  
                     l.add(sum);  
                }  
           }  
           return l;  
      }  
 }  

 Output  
 2  
 6  
 Result:19  

Enjoy Programming

How to find continuous sequence with largest sum

You are given an array of integers both positive and negative integers.Find the continuous sequence with largest sum.

For Example:

Input:-{2,-8,3,-2,4,-10}
Output:-5(i.e {3,-2,4})

/**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class LargestSumSequence {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           int a[]={2, -8, 3, -2, 4, -10};  
           System.out.println("Continuous sequence with Largest sum :"+getMaxSum(a));  
      }  
      public static int getMaxSum(int[] a) {  
           int maxsum = 0;  
           int sum = 0;  
           for (int i = 0; i < a.length; i++) {  
                sum += a[i];  
                if (maxsum < sum) {  
                     maxsum = sum;  
                } else if (sum < 0) {  
                     sum = 0;  
                }  
           }  
           return maxsum;  
      }  
 }  

Output:-  
 Continuous sequence with Largest sum :5 

Enjoy Programming

How to count occurrence of word in String Array

The most basic technical question asked in interview to find the count of occurrence of words in String array.we can also find count of occurrence of characters in String by simple converting String into array.

In this solution we have used Hashtable where we keep word as a key and count of its occurrence as value.

import java.util.Hashtable;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class CountOfWordOccurence {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           String []s={"bat","ball","bat"};  
           Hashtable<String, Integer> hashtable=setup(s);  
           System.out.println("Occurrences of bat is:"+getFrequency(hashtable, "bat"));  
           System.out.println("Occurrences of ball is:"+getFrequency(hashtable, "ball"));  
      }  
      static Hashtable<String, Integer> setup(String[] array) {  
           Hashtable<String, Integer> table = new Hashtable<String, Integer>();  
           for (String word : array) {  
                word = word.toLowerCase();  
                if (word.trim() != "") {  
                     if (!table.containsKey(word))  
                          table.put(word, 0);  
                     table.put(word, table.get(word) + 1);  
                }  
           }  
           return table;  
      }  
      static int getFrequency(Hashtable<String, Integer> table, String word) {  
           if (table == null || word == null)  
                return -1;  
           word = word.toLowerCase();  
           if (table.containsKey(word)) {  
                return table.get(word);  
           }  
           return 0;  
      }  
 }  

Output  
 Occurrences of bat is:2  
 Occurrences of ball is:1  

Enjoy Programming.

Java program to compute all permutation of String

To understand this solution first understand the concept of recursion.
So here lets assume a given string S represented by S1,S2,S2....,Sn.
To permute String S ,we can select the first character S1,permute the remainder of string to get a new list.Then with a new list we can push S1 into each possible positions.

import java.util.ArrayList;  
 import java.util.List;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class StringPermutation {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> listOfAllPermutatuons=getPerms("abc");  
           for(String s:listOfAllPermutatuons)  
           {  
                System.out.println(s);  
           }  
      }  
      public static ArrayList<String> getPerms(String s) {  
           ArrayList<String> permutations = new ArrayList<String>();  
           if (s == null) {   
                return null;  
           } else if (s.length() == 0) {   
                permutations.add("");  
                return permutations;  
           }  
           char first = s.charAt(0); // get the first character  
           String remainder = s.substring(1); // remove the first character  
           ArrayList<String> words = getPerms(remainder);  
           for (String word : words) {  
                for (int j = 0; j <= word.length(); j++) {  
                     permutations.add(insertCharAt(word, first, j));  
                }  
           }  
           return permutations;  
      }  
      public static String insertCharAt(String word, char c, int i) {  
           String start = word.substring(0, i);  
           String end = word.substring(i);  
           return start + c + end;  
      }  
 }  

Output  
 abc  
 bac  
 bca  
 acb  
 cab  
 cba  

NOTE:- To understand this solution clearly,try to put a debug point and go through each line.

Enjoy Programming

How to determine if String has all unique characters

It is a most basic question asked in interviews to check if string contains all unique characters or not.
Below sample program is a basic solution to this problem.

 /**  
  *   
  */  
 /**  
  * Program to determine if a string has all unique characters.  
  *   
  * @author Dixit  
  *   
  */  
 public class StringUniqueCharacters {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           String firstString = "America";  
           String secondString = "India";  
           String thridString = "Italy";  
           System.out  
                     .println("Result:" + isUniqueChars(firstString.toLowerCase()));  
           System.out.println("Result:"  
                     + isUniqueChars(secondString.toLowerCase()));  
           System.out  
                     .println("Result:" + isUniqueChars(thridString.toLowerCase()));  
      }  
      public static boolean isUniqueChars(String str) {  
           //Initialise a boolean array  
           boolean[] char_set = new boolean[256];  
           for (int i = 0; i < str.length(); i++) {  
                //get ASCII value of characters  
                int val = str.charAt(i);  
                //Check in the boolean array if it is unique then set the value to true at corresponding index position  
                //if value is already set at the required index position then return false  
                if (char_set[val])  
                     return false;  
                char_set[val] = true;  
           }  
           return true;  
      }  
 }  

Enjoy Programming.