Program to find frequency of elements in a String array.

One of the common interview questions is "Find how frequently a particular String element occurs in a String array".
Through this question the interviewers try to test your knowledge of Collections API.

The algorithm that we will try to use is as follows:

1. Initialize the string array
          String strArray[] = {"Amit","Suresh","Suyash","Vimal","Amit","Amit","Suyash","Amit","amit"};

2. Initialize a TreeMap
          Map<String, Integer> map = new TreeMap<String,Integer>();

    There must be one question popping in ur head- Why the hell does he want to use a MAP ????
    Well !!!
    I want to use Map because Map allows you to store key value pairs. I will store the String as key and           its frequency as the value. Well you also do the other way round- store String as value and its frequency       as key. But you won't succeed because Java doesn't allow you to modify keys in a Map.

3. You can search if a particular String is present in the Map
    To do that you will have to iterate over the Map.
    But Map interface doesn't provide you with an Iterator. Don't worry !!! There is workaround. We can           convert Map to a Set of Entries(that contain key value pairs).
                Set<Entry<String,Integer>> entrySet = map.entrySet();

   Then obtain the iterator over the set. I have obtained an Iterator object that iterates over                                 Entry<String,Integer>.
                Iterator<Entry<String,Integer>> it = entrySet.iterator();

    If it is present then increment its frequency. If  it is not already there then simply add it to the Map and set       its frequency as 1 as it has occurred for the first time.

4. Print the Map.
        System.out.println(map);


Program in Java
package mypackage;

import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class Test5 {

public static void main(String[] args) {

//Program to count the frequency of a word in an array
//Initialize the array
String strArray[] = {"Amit","Suresh","Suyash","Vimal","Amit","Amit","Suyash","Amit","amit"};
Map<String, Integer> map = new TreeMap<String,Integer>();
for (String string : strArray) {
if(map.containsKey(string)){
Set<Entry<String,Integer>> entrySet = map.entrySet();
Iterator<Entry<String,Integer>> it = entrySet.iterator();
while (it.hasNext()) {
Entry<String,Integer> entry = (Entry<String,Integer>) it.next();
if(entry.getKey().equals(string)){
int value = (int) entry.getValue();
entry.setValue(++value);
}
} //while ends
} //if ends

else
map.put(string,1);
} //for ends

System.out.println(map);
}//main ends
}//class ends

Output:

{Amit=4, Suresh=1, Suyash=2, Vimal=1, amit=1}

Note you can also use a HashMap. The program I have shown will  work for both TreeMap as well       as HashMap. If you use HashMap you will get the following output.

{Suresh=1, Vimal=1, Amit=4, Suyash=2, amit=1}

The only difference in output is the order in which map elements are printed. In TreeMap the keys were sorted in the ascending order while in HashMap there is no such sorting based on key values. 

Thats it guys. Signing off for today. Happy Learning.

Zycus Java Interview for Experienced Professionals. Sharing my experience

Hey guys, yesterday I went for an interview in Zycus (a product based company in Mumbai) for the post of Java developer. I want to share my experience with you.

It was a walk-in. Any one with 1.5 to 4 years of experience in Java development could go.
It had 4 rounds.
The first was general aptitude. Consisted of 10 questions. Total 30 minutes were given. So that comes to 3 minutes per question. The questions were very easy. But since I had no practice of Aptitude type questions I took time. But eventually I got all answers correct. :)
Questions were mostly mathematics based like 1 train-platform question, 1 question on average, 1 on percentage. Few were based on blood relations, series, etc.
We were divided into groups of 5 and asked to solve the first round of general aptitude. All the guys in my group cleared it.

Then the second round. Written Technical Test. I failed in that round!!!!  :'(
There were 2 questions in that round. One was based on applying the algorithm and the second one on coding the algorithm. Total 60 minutes were given which in my opinion are sufficient.
I want you people to be aware of what kind of questions can be asked so that your better prepared. I think I failed because I had appeared on another Java Interview on the same day in another company and I was just too tired. You better be prepared to put full effort and avoid being lazy like I was. :)
The first step to solve the problem is understand it. Think in your mind how to solve it. Prepare a rough pseudo code for the problem before you start writing actual code. Writing Pseudo code first is a very good practice as it gives you a feeling that you can solve the problem, gives you an estimates of time required to write the code, helps you establish the boundary values of indexes for arrays,etc.
I came home and tried to write a program for that and I succeeded this time.
I have commented out few things in the program that were helpful for me to debug it.
Try to copy the code in Eclipse/NetBeans.
Run it as a Java Application.
Understand its logic.
Read the problem statement twice thrice....until you understand it completely.

package mypackage;

/*Problem Statement
 * There is  a grid of size 5 by 5.
 * Each cell in the grid can be alive or dead.
 * An alive cell has a value 1 while a dead cell has a value 0.
 * A first generation of the grid is generated using the following rules.
 *  1.  If an alive cell has less than 2 alive neighbors then it dies as if by starvation.
 *  2.  If an alive cell has 2 or 3 alive neighbors then it survives.
 *  3.  If an alive cell has more than 3 alive neighbors then it dies as if by overcrowding.
 *  4.  If a dead cell has exactly 3 alive neighbors then it lives as if by reproduction.
 *
 *  Second generation of the grid is generated using the same rules as that used for generating        *  first one.
 *  Question 1. Generate first and second generation of grid on paper
 *  Question 2. Generate first and second generation of grid using a program in C/C++/Java.
 * */

(The dark cells are the live ones)
Answer 1.

Answer 2.
public class Test3 {

public static void main(String[] args) {
int inputGrid[][] = {{0,0,0,0,0},{0,1,1,0,0},{0,1,1,0,0},{0,0,1,1,0},{0,0,1,1,0}};
Test3 test3 = new Test3();
int outputGrid[][] = test3. getNextGeneration(inputGrid);
System.out.println("First Generation output");
test3.displayGrid(outputGrid);
outputGrid = test3. getNextGeneration(outputGrid);
System.out.println("Second Generation output");
test3.displayGrid(outputGrid);
}

public int[][] getNextGeneration(int[][] inputGrid){
int row = inputGrid.length;
int column = inputGrid[0].length;
int[][] outputGrid = new int[row][column];
int activeCount = 0;
//System.out.println("Active count.");
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
if(inputGrid[i][j] == 1){    //If the cell is alive.
activeCount = getActiveCount(inputGrid,i,j);
if(activeCount == 2 || activeCount == 3)
outputGrid[i][j] = 1;
}
else{                                 //If the cell is dead.
activeCount = getActiveCount(inputGrid,i,j);
if(activeCount == 3)
outputGrid[i][j] = 1;
}
//System.out.print("i=" + i + " j=" + j);
}
//System.out.println();
}

return outputGrid;
}

//Display the outputGrid.
public void displayGrid(int[][] inputGrid){
int row = inputGrid.length;
int column = inputGrid[0].length;
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
System.out.print(inputGrid[i][j]);
}
System.out.println();
}
}

       //Counts the number of active neighbors.
public int getActiveCount(int[][] inputGrid,int i,int j){
int activeCount = 0;
int noOfIter = 0;
for(int m=-1; m <= 1; m++){
for(int n = -1; n <= 1; n++){
                               //If the array indexes go out of boundary skip the remaining loop and continue to the                                      //next iteration.
if((m == 0 && n == 0) || (m+i) < 0 || (m+i) > 4 || (n+j) < 0 || (n+j) > 4)
continue;
if(inputGrid[m+i][n+j] == 1)
activeCount++;
//noOfIter++;
//System.out.print(" m+i" + (m+i) + " n+j" + (n+j));
}
//System.out.println();
}
//System.out.println("No of iterations:"+ noOfIter);
//System.out.println("Active Count"+ activeCount);
return activeCount;
}
}

If you have a better or more efficient program for the same problem then please add it in comments. It will be added to this blog post along with your name.

After the Written Technical Test comes the third round which is Technical Interview(TI). Although I couldn't qualify for that, got some info from my friend who went through it.
He had to wait for some 4 hours for his turn to come for TI. It lasted for 45 minutes. They started with core Java. The questions were not general. They were tough and demanded thorough knowledge and application of Java concepts. For everything the interviewer wanted a program. They asked to write a program to find the frequency of a string in a string array. My friend used a Map. Added the string as key and its frequency as value. Used the contains() method to find if the map contained the string. If it already contained then he used Object setValue(Object key) method to increment the frequency of the string. If it didn't then he added the key value pair to the map using the  method Object add(Object key ,Object value) keeping the value (frequency ) as 1.

Some useful code for the same program has been suggested by my friend - Sheshadri Talla. Thanks man!!!
Posting it here.

Same output using traditional coding style(without using collections framework)
String strArray[] = {"Amit","Suresh","Suyash","Vimal","Amit","Amit","Suyash","Amit","amit"};
System.out.print("{");
for(int i=0; i=0; j--){
if(temp.equals(strArray[j])){
skip=true;

}

}
for(int k=i+1; k<strArray.length; k++){

if(temp.equals(strArray[k]) && !skip){
count++;
}
}
if(!skip){
System.out.print(temp+"="+count+", ");
}

}
System.out.print("}");

Hope this was helpful. Signing off for today.

How does Polymorphism works with Generics References.

In this tutorial we will see what happens when you apply the concepts of Polymorphism to Generics.

Just to brush up few concepts.

What is Polymorphism?

It is the ability of an object to take many forms. The most common use of Polymorphism occurs when a superclass reference points to a subclass object.

Example 1.

class Parent{

public void sayHello(){

System.out.println("Hello Parent");

}

}

class Child extends Parent{

public void sayHello(){

System.out.println("Hello Child");

}

}

public class Test2 {

         public static void main(String[] args) {

       Parent ref = new Child();                                                          //Line 1.

ref.sayHello();                                                                        //Line 2.

         }

}

Output: 

Hello Child

Notice how at line 1 the reference variable "ref" of type Parent (supertype or superclass type) is used to point to an object of type Child (subtype or subclass type). 

See how at line 2 when sayHello method is invoked, the JVM figures out what object the reference (ref) is pointing to. ref is pointing to Child() object and hence sayHello() method of Child is invoked. 

Although polymorphism is not just limited to this scenario this is just a common situation encountered in Java Programming.

What is Generics?

Generics is a feature introduced in Java 5 which allows a type or method to operate on a type while providing compile time safety.

Example 2.

ArrayList<String> myList = new ArrayList<String>();

myList.add(new Integer(1));                                                                  //Line 1-throws a compile time error

myList.add("John");                                                                               //Line 2-works perfectly fine.

The declaration ArrayList<String> myList = new ArrayList<String>() says that myList can only hold objects of type String. If you add any other type of objects to the list. The compiler will throw an error.

You must be wondering why do you want to add a single type of object to myList. Here is the example.

Example 3.

public class Test2 {

         public static void main(String[] args) {

                    List list = new ArrayList();

                    list.add(new Integer(2));

                    String name = (String)list.get(0);

         }

}

Output:

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String

Here is the explanation.

Imagine we are not using generics. A list can hold any object. When you read the contents of the list you will always get an Object type.

public Object get(int index)      ->Signature of get method.

 So you will have to typecast it.

String name = (String)myList.get(0);

Since in this example we are not using generics we could add even an Integer object to List. 

So myList.get(0) would return an Integer. An Integer typecasted to String would give you a ClassCastException.

Huff Enough of revision. Lets get to the point of this tutorial. What happens when you apply the concepts of Polymorphism to Generics.

As we have seen in Example 1, Line 1

Parent ref = new Child();      

is perfectly OK. i.e. a parent class reference can point to a subclass object.

So what about this

List myList<Object> = new ArrayList<String>();

List myList<Number> = new ArrayList<Integer>();

This should work fine isn't it?

But IT DOESN'T.

Burn into your brain a rule of generics.

"Generic type of the reference and the generic type of the 

object must be exactly identical"

Polymorphism applies only to the base type (in this example, the collections List and ArrayList).

If the generic type of the reference is Number then it can point to only objects whose generic type is Number, neither a subtype of Number nor a supertype of Number. Only and only Number.

So the following lines are perfectly fine.

List myList<Object> = new ArrayList<Object>();                                          //Fine

List myList<Number> = new ArrayList<Number>();                                     //Fine

Set mySet<Parent> = new HashSet<Parent>();                                              //Fine

When working with generics type a cast is not required when extracting elements form  the collection. While for non-generic types an explicit cast is required.

Example 4.

List<String> myList = new ArrayList<String>();

myList.add("Vicky");

myList.add("John");

String name = myList.get(0);                                                                //No cast was required

List list = new ArrayList();

list.add("Sunny");

name = (String)list.get(0);                                                                     //An explicit cast was required.

In Example 4 we were dealing with Strings, now what would happen if we were dealing with Integers. One would expect that Unboxing would be done for us even when using Pre-Java 5 non type safe code and we won't have to type cast. But that is WRONG. Autoboxing only converts from a Wrapper class(Integer or Long or Short etc.) to a primitive. It cannot convert from an Object type to a primitive.
Following example illustrates it.

Example 5.
List<Integer> listOfTypeSafeIntegers = new ArrayList<Integer>();
/*Declaring type safe list of Integers. You can only add Integers to it.*/                                              listOfTypeSafeIntegers.add(100);
listOfTypeSafeIntegers.add(200);
listOfTypeSafeIntegers.add(300);
i = listOfTypeSafeIntegers.get(0);      
/*Typecast not necessary as get(int) method returns an Integer. The compiler automatically performs the typecasting for us such that get(int) returns Integer instead of object. Unboxing converts that Integer wrapper to int.*/

List listOfIntegers= new ArrayList();       //Declaring raw list.Can contain any objects
listOfIntegers.add(100);                                                              
listOfIntegers.add(200);
listOfIntegers.add(300);
int i = (Integer)listOfIntegers.get(2);       
/*Typecast is necessary as get() method returns an Object and an Object cannot be unboxed to primitive*/

By now you might have become pretty much comfortable with Generics. We have seen its introduction, basic syntax, how it works with polymorphism and unboxing.
Few catches when declaring type safe code.
In the following example I am declaring reference of generic type Integer and the object as a raw type.
List<Integer> list = new ArrayList();   
//This line pops up a warning- Array List a raw type references to generic type ArrayList<> should //be parameterized. 

list.add(100);                //OK. I can add an Integer to it.
lists.add(new String());  //When I try to add a string compiler throws an error. 

From this we infer that even if reference is declared of a generic type say Integer, compiler restricts us from adding any other type say String.

So will I get an error at Line 1 in the below example?
List list = new ArrayList<Integer>();
list.add(100);

list.add(new String());    //Line 1

Strangely, there is no error. Compiler just sees the generic type of the reference. Since it was a raw type compiler assumes any type of object can be added to the list.

That's it in today's tutorial. Signing off for here. Will be back with a whole lot of new tutorials for you all. All doubts, suggestions for improvements, correction of mistakes are welcome. Hope this helps. Happy Learning!!!