Wednesday, 30 September 2015

Important String interview questions



Important String questions which are mostly asked in interviews.Many interviewer focus on String concepts to check the fundamentals of interviewee.Go through the below questions which will help you to improve your understanding about String.


1) Find the output of below program ?

 public class TestProgram {  
      public void method(Object o) {  
           System.out.println("Object ");  
      }  
      public void method(String s) {  
           System.out.println("String ");  
      }  
      public static void main(String a[]) {  
           TestProgram testProgram = new TestProgram();  
           testProgram.method(null);  
      }  
 }  

 Output:-  
 String   

Reason:- null value is considered as String which calls the method with String as an argument.

2) Find the output of below program ?

 public class TestProgram {  
   public static void main(String a[]) {  
    String s1=new String("Hello");  
    String s2=new String("Helloo");  
    System.out.println(s1=s2);  
   }  
 }  

Output:-  
 Helloo  

Reason:- String s2 value is assigned to s1 in System.out.println(s1=s2) statement.

3)  Find the output of below program ?

 public class TestProgram {  
      public void method(StringBuffer sb) {  
           System.out.println("StringBuffer Version");  
      }  
      public void method(String s) {  
           System.out.println("String Version");  
      }  
      public static void main(String a[]) {  
           TestProgram q = new TestProgram();  
           q.method(null);  
      }  
 }  

Output:- Compile time error.

Reason:- The method method(StringBuffer sb) is ambiguous for the type TestProgram.
If you comment the public void method(String s), then code works fine and it will print StringBuffer Version.

4) Find the output of below program ?

 public class TestProgram {  
      public static void main(String a[]) {  
           String s1 = new String("Hello");  
           String s2 = new String("s1");  
           System.out.println(s1 == s2);  
      }  
 }  


 Output:-  
 false  

Reason:- Both the instances s1 and s2 does not refer to the same object.They are referring to different object with different memory address.Hence equality comparison returns false whereas if we check the contents of both the strings using equals method, then it will return true.

5) Find the output of below program ?

public class TestProgram {  
      public static void main(String a[]) {  
           String s1 = new String("Hello");  
           StringBuffer s2 = new StringBuffer(s1);  
           System.out.println(s1 == s2.toString());  
           System.out.println(s1.equals(s2));  
      }  
 }  

 Output:-  
 false  
 false 

Reason:- first print statement returns false because both s1 and s2 are referring to distinct object with distinct memory address and second print statement returns false because the equals method from StringBuffer is not overridden from Object class, so it uses reference equality(==).

6) Find the output of below program ?

1:  public class TestProgram {  
2:       public static void main(String a[]) {  
3:            String obj = "hello";  
4:            String obj2 = obj;  
5:            obj2 = " world";  
6:            System.out.println(obj + " " + obj2);  
7:       }  
8:  }  

 Output:-  
 hello world 

Reason:- In line number 3,obj is referring to String literal "hello".In line 4,obj2 is referring to same String as referred by obj.In line 5,obj2 is referring to new String literal " world".

7) Find the output of below program ?

 public class TestProgram {  
      public static void main(String a[]) {  
           String x = "hello ";  
           x.concat("world");  
           System.out.println(x);  
      }  
 } 

 Output:-  
 hello  

Reason:- concat method called on String x creates a new String object which needs to be assigned to a reference variable.String x is still referring to original String literal "hello ".

8) How many String objects created below ?

 public class TestProgram {  
      public static void main(String a[]) {  
           String s1 = "Hello ";  
           String s2 = s1 + "john ";  
           s1.concat("pallavi");  
           s2.concat(s1);  
           s1 += "ashish";  
           System.out.println(s1 + " " + s2);  
      }  
 }  

 Output:-  
 Hello ashish Hello john 

8 Strings objects get created.

Reason:-
1 :- "Hello " object gets created in String pool.
2:- "john " gets created in String pool and lost because no String variable is directly referring to it.
3:- "Hello john " s2 gets created.
4:- "pallavi" gets created in String pool and lost because no String variable is directly referring to it.
5:- "Hello pallavi " gets created in String pool and lost because no String variable is directly referring to it.
6:- "Hello john Hello" gets created in String pool and lost because no String variable is directly referring to it.
7:- "ashish " gets created in String pool and lost because no String variable is directly referring to it.
8:- "Hello ashish" gets created in String pool.

9) How many String objects created below ?

 public class TestProgram {  
   public static void main(String a[]) {  
    String s1 = new String("Hello");  
    String s2 = new String("Hello");  
   }  
 }  

Answer:- 3

Reason:-
1:- first String literal object "Hello"  gets created in String pool.
2:- a new String object with the value "Hello" placed in Heap memory.
3:- another new String object with the value "Hello" placed in Heap memory.

10) Find the output of below program ?

 public class TestProgram {  
   public static void main(String a[]) {  
    StringBuffer str = "";  
   }  
 } 

Output:- Compile time error.

Reason:- In order to create a StringBuffer object ,we need to build an object explicitly like new StringBuffer(""); .whereas in case String we can directly assign the literal like String str="";

11) Find the output of below program ?

1:  public class TestProgram {  
2:    public static void main(String a[]) {  
3:     String str = "";  
4:     String str1="Hello";  
5:     System.out.println(str.length());  
6:     System.out.println(str1.length());  
7:     System.out.println(str1.charAt(0));  
8:     System.out.println(str1.charAt(5));  
9:    }  
10:  }  

Output:-  
 0  
 5  
 H  
 Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 5  
      at java.lang.String.charAt(Unknown Source)  
      at TestProgram.main(TestProgram.java:9)  


Reason:- At line number 8, it gives an StringIndexOutOfBoundsException because String index starts from 0 .

12) How many String objects created below ?

 public class TestProgram {    
   public static void main(String a[]) {  
    String s1="Hello";  
    String s2="Hello";  
    String s3="Hello";  
   }  
 } 

Answer:- 1

Reason:- "Hello" String literal object gets created in String pool and s1,s2,s3 refers to the same literal object.

13) Difference between StringBuffer and String?
 refer to this link what is the differnce between StringBuffer and String?

14) Difference between String literal and String Object?
refer to this link difference between String literal and String object?


All the best :)

Wednesday, 23 September 2015

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.

Tuesday, 15 September 2015

Count all possible paths from top left to bottom right of a m*n Matrix


A person starts from the uppermost, leftmost corner of a grid. Each cell of grid is 0,1,2,3,4,5,6 or 7. From any cell, he can only go to right cell if this cell is 1, he can only go to lower cell if this cell is 2, he can only go to its diagonally opposite cell if this cell is 3, he can go to right and lower cell if this cell is 4, he can go to right and diagonally opposite cell if this cell is 5, he can go to lower and diagonally opposite cell if this cell is 6, he can go to right and lower and diagonally opposite cell if this cell is 7 and he can not move from this cell if this cell is 0. The following figure shows each of these cases:

Person wants to go to the lowermost, rightmost corner of the grid. You have to find number of paths travelling on which he can reach at destination.

Input :
Input1: An Integer array having  two elements: m, n that depict rows and columns of the grid respectively
Input2: An Integer array containing m*n elements 

Output :
Output will be the number of ways to reach the ending position.

For Example:-
Input1: 4 6
Input2: 1 3 0 0 0 0 0 0 4 5 1 0 0 0 0 6 7 6 0 0 0 0 5 0

Output: 3

Input1: 3 4
Input2: 1 2 0 0 5 0 0 0 7

Output: 1

Note:Press Enter after each input for ex: after entering 4 press enter then enter 6 as scanner nextInt method is used for reading input.

Solution:

import java.util.Scanner;  
 public class MatrixPathProblem {  
      int m, n;  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           // TODO Auto-generated method stub  
           MatrixPathProblem obj = new MatrixPathProblem();  
           int a[] = new int[2];  
           Scanner s = new Scanner(System.in);  
           for (int i = 0; i < a.length; i++) {  
                a[i] = s.nextInt();  
           }  
           obj.m = a[0];  
           obj.n = a[1];  
           int b[] = new int[obj.m * obj.n];  
           for (int i = 0; i < b.length; i++) {  
                b[i] = s.nextInt();  
           }  
           int mat[][] = new int[obj.m][obj.n];  
           int k = 0;  
           for (int i = 0; i < obj.m; i++) {  
                for (int j = 0; j < obj.n; j++) {  
                     mat[i][j] = b[k];  
                     k++;  
                }  
           }  
           System.out.println(obj.path(mat, 0, 0));  
      }  
      private int path(int[][] a, int i, int j) {  
           if (i == m - 1 && j == n - 1)  
                return 1;  
           else if (i == m - 1) {  
                if (a[i][j] == 0)  
                     return 0;  
                else  
                     return 1;  
           } else if (j == n - 1) {  
                if (a[i][j] == 0)  
                     return 0;  
                else  
                     return 1;  
           } else if (a[i][j] == 0)  
                return 0;  
           else if (a[i][j] == 1)  
                return path(a, i, j + 1);  
           else if (a[i][j] == 2)  
                return path(a, i + 1, j);  
           else if (a[i][j] == 3)  
                return path(a, i + 1, j + 1);  
           else if (a[i][j] == 4)  
                return path(a, i + 1, j) + path(a, i, j + 1);  
           else if (a[i][j] == 5)  
                return path(a, i, j + 1) + path(a, i + 1, j + 1);  
           else if (a[i][j] == 6)  
                return path(a, i + 1, j) + path(a, i + 1, j + 1);  
           else if (a[i][j] == 7)  
                return path(a, i, j + 1) + path(a, i + 1, j + 1)  
                          + path(a, i + 1, j);  
           else  
                return 0;  
      }  
 }  

Tuesday, 8 September 2015

Java Program to Find Lexicographically Smallest and Largest substring of Length K


What is Lexicographic order?

Lexicographic order is an order in which words are displayed in alphabetical order using the appearance of letters in the word.It is also know as dictionary order or alphabetical order.For ex:-"Africa" is smaller than "Bangladesh" ,"He" is smaller than "he".

Sample program:-

 import java.util.ArrayList;  
 import java.util.Collections;  
 import java.util.List;  
 import java.util.Scanner;  
 /**  
  * @author Dixit  
  *   
  */  
 public class LexicographicExample {  
      public static void main(String a[]) {  
           Scanner sc = new Scanner(System.in);  
           System.out.println("Enter the String:-");  
           String str = sc.nextLine();  
           System.out.println("Enter the length");  
           int count = sc.nextInt();  
           List<String> list = new ArrayList<String>();  
           for (int i = 0; i < str.length(); i = i + 1) {  
                if (str.length() - i >= count) {  
                     list.add(str.substring(i, count + i));  
                }  
           }  
           Collections.sort(list);  
           System.out.println("Smallest subString:-" + list.get(0));  
           System.out.println("Largest subString:-" + list.get(list.size() - 1));  
      }  
 }  


 Output  
 Enter the String:-  
 helloworld  
 Enter the length  
 2  
 Smallest subString:-el  
 Largest subString:-wo  


Enjoy programming.

Tuesday, 1 September 2015

ListenerExecutorService and its Example



What is ListenerExecutorService ?
ListenerExecutorService is almost same as ExecutorService except  in ListenerExecutorService ,callback methods can be registered and that will be called once execution of task reach some defined state.ListenerExecutorService returns ListenableFuture instances.ListenableFuture instance allows to register callback methods which will get executed once the task gets completed.

In order to create ListenerExecutorService ,you need to use decorator which accepts ExecutorService as parameter
                MoreExecutors.listeningDecorator(ExecutorService);
You can use any of the ExecutorService (newFixedThreadPool(),newSingleThreadExecutor(),etc)


Sample Example:-


 import java.util.concurrent.Callable;  
 import java.util.concurrent.Executors;  
 import com.google.common.util.concurrent.FutureCallback;  
 import com.google.common.util.concurrent.Futures;  
 import com.google.common.util.concurrent.ListenableFuture;  
 import com.google.common.util.concurrent.ListeningExecutorService;  
 import com.google.common.util.concurrent.MoreExecutors;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class ListeningExecutorServiceExample {  
      @SuppressWarnings("unchecked")  
      public static void main(String a[]) {  
           ListeningExecutorService pool = MoreExecutors  
                     .listeningDecorator(Executors.newCachedThreadPool());  
           final ListenableFuture<String> future = pool.submit(new Callable() {  
                @Override  
                public String call() throws Exception {  
                     try {  
                          int a = 10 / 0;  
                     } catch (Exception e) {  
                          throw e;  
                     }  
                     return "done";  
                }  
           });  
           Futures.addCallback(future, new FutureCallback() {  
                @Override  
                public void onSuccess(Object object) {  
                     System.out.println("Success.");  
                }  
                public void onFailure(Throwable throwable) {  
                     System.out.println("Failure.");  
                }  
           });  
      }  
 }  


 Output  
 Failure.

So in this program ,the callback methods onSuccess and onFailure will be called once execution of the task is finished.In this case an arithmetic exception occurs which calls the callback method onFailure.You don't need to explicitly check the state of your ListenableFuture object ,as the registered callbacks will handle the states ,once the task is completed.

you need to download the guava jar ,here is the link http://www.java2s.com/Code/Jar/g/Downloadguavajar.htm

Enjoy programming