Showing posts with label Core Java. Show all posts
Showing posts with label Core Java. Show all posts

Sunday, December 20, 2015

Daily Hunt: Interview Questions #3

As I have been part of rat race to find another Job. It was my 3rd interview with Daily Hunt.. It was mix of data structures and Java. I was asked 3 questions on Data Structures and various other questions related to Java.

Question 1: It is related to Data Structure. You have been given list of integers in an array and an another integer X. It is known that multiplication of 2 integers in the array is equal to X. Find the numbers from the array.

Solution 1: Solution I provided was to have 2 separate arrays. One contains the input as received and another to keep integers as Binary Search Tree.

We will iterate through the array to find the first multiplier, and once we found it we will try to find the remaining multiplier in the BST array. If the number is found is the BST, we found the else otherwise move to another integer in the input array.

Question 2: This question is on the design patterns. Design the coffee vending machine?
Coffee Vending machine is simple machine which are part of offices now a day. If you have to implement the coffee building machine, how would you do it?

Coffee vending machine can have options for various tea and various coffees. So what would be the best approach to design a software for such a coffee vending machine.

Now we have various design patterns available with us. What would be the best one for you?

The answer for the problem is the Decorator Pattern. We would discuss the same in the upcoming post in the details. Though I answered it with Abstract Factory and Abstract Method pattern. :-(

Question 3: Interviewer again moves to DS. An application is receiving the stream of strings. String may contain anagram. Application would need to detect those anagrams in the stream.
It is required to check the stream again to figure out if application has already received the string earlier in the stream to report it to be duplicate. But based on the question, 2 strings are duplicate when both of them are anagram to each other.

Simple answer for the question would be to read the string from the stream and sort the character string. Save the string in the Set, to maintain unique strings. If application tries to add the string in the set and it is already added to the set, set does not add it to array and returns false. In this case, the string can be marked as DUPLICATE.

Let's look at the example:
String a is not duplicate of ton of trings.
[String] => Set will contain {ginrst}
[a] => Set {ginrst, a}
[is] => Set {ginrst, a, is}
[not] => Set {ginrst, a, is, not}
[duplicate] => Set {ginrst, a, is, not, acdeilptu}
[of] => Set {ginrst, a, is, not, acdeilptu, of}
[ton] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'not' already exists. It is considered as duplicate string.
[of] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'of' already exists. It is considered as duplicate string.
[trings] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'ginrst' already exists.

Question 4: So here comes a puzzle. 2 persons are landing on a straight line on a point A and B. Points A and B are not known to each of them. How would they find each other?
This one was interesting puzzle. I did not really have any clue about it. So I requested for the clue. Interviewer said that both the person can move in any direction. But it indicated that one of these two would move like a pendulum. So let's say that A moves but not B. So A moves to his left for half KM and later he moves to his right for 1Km. Next if could not find B yet, he moves to his left for 1.5KM, and so on.

Question 5: Here comes a DB cum Java question. An application has one table which contains only one column and one row. It maintains the user id of the users who are registering to the application. Database can only cater 10 update request per second, but number of user registering each second are 1000. How would you tackle the deadlock in this situation?
Now this was a tricky question. Initially I thought that it is required to look the solution at DB side, but rather the problem could have been solved at java side as well. My first thought was to think in terms of triggers. But triggers can not be the solution for this. Why did I think so? Trigger is a DB operation which will increase the count and save the count to database and return the value. In addition, triggers values are cached as well. It can also be a solution.

Java side we can fire the DB update after certain number of users have been created. So it is possible to maintain a static variable which will have the latest value.

I am now thinking, can we even use volatile or threadlocal variable in this? Please let me know if you have some better answer.

Question 6: What is serialization? Why do we use serialized version id for each class?
Serialization is to persist the Java memory object into file system in the form of file or database. readObject and writeObject methods are used to deserial and serial the object into the file file system.

To achieve serialization, it is required for class to implement Serializable interface.

serialVersionID is maintained to differentiate between 2 different version of classes. It helps loader to identify the class and deserial the specific object based on the version of the class. Serialization has been explained quite well in this blog.
http://exploreriddles.blogspot.in/2014/01/serialization-introduction.html

Question 7: On the deployed tomcat server, you have detected memory leak. How would you find the memory leak?
Okay, I assume that there is no fix to find the memory leak. In this case, we would need to first check in our application if something is possible leak. If it is not, it would be required to fetch the memory profile of the tomcat application and run through the profile to figure out the actual reason for the memory leak.
<!-- Notes to Me --> Learn more about Profiling.

Question 8: An application has a thread pool for 10 threads, but tasks provided to the threads are more than 10. How would you handle the situation programmatically?
Okay, I could not handle last 3 questions quite well. I was not to answer all simple questions of this interview. My assumption was that threadpool handles this scenario at it's own. As soon as, we submit a task to thread pool, it checks if there is any thread which is free. Threadpool assigns the task to the certain thread else if all threads are running, it send the task in the wait status to be notified once ny of the thread becomes free.

I am not an expert. I am also for the solution for the questions stated above. If you know some answers, let me know.

Wednesday, December 9, 2015

Oracle Interview - Telephonic Round - Continues

We did not solve the last problem that I was asked in the interview. So let's put together the solution for the same.
  • Algorithm Problem: A random string is provided to you, you must find the minimum number of elements to be inserted in the string to make it palindrome.
    • String is ABA, then method must return 0.
    • String is ABC, then method must return 2 to form ABCBA.
    • String ABCDA, then method must return 2 to form ABCDCBA.
    • String ASD3D5, then method must return 3 to form AS5D3D5SA.
It has been difficult for me to find the solutions for the problem within the specified timeframe as it requires quite a good understanding to achieve such an efficient answers.

When I first heard the question, I felt that this would round would not be difficult as I thought, as I could come up with the algorithm within some time. But I was wrong. It was not the case there.

First Solution
 public class Palindrome {  
      String element;  
      public Palindrome(final String elem) {  
           element = elem;  
      }  
      public int makePalindrome() {  
           if (element.length() <= 1) {  
                return 0;  
           } else {  
                char[] dst = new char[element.length()];  
                int endIndex = element.length() - 1;  
                int index = 0;  
                element.getChars(0, element.length(), dst, 0);  
                while (dst[index] == dst[endIndex]) {  
                     index++;  
                     endIndex--;  
                }  
                return endIndex - index;  
           }  
      }  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           Palindrome p = new Palindrome("ABCA");  
           System.out.println("Chars to be added are: " + p.makePalindrome());  
      }  
 }  

Oh wow, that's it. But it is really worth the question.

What I did?
I solved for ABA, and it would return 0 but it was not the smallest palindrome. After discussion with interview a bit more, I can to know that this code would really not work for "ASD3D5". It was true, the code did not really work as per the question. Hell broke lose here. Now interviewer is already agitated with the time that I have taken.

I have to rework the solution with the closed mind. Stupid mind was still contemplating me to write some code on the same line, and it was not able to think something different at that time. However I failed the interview at that time only, but it was required for me to find the answer for the questions that are asked.

I tried little more and found the following answer.

Solution 2
It is simple, we have to use the dynamic programming to solve the issue that we have in hand. First we cut the corners of the string. In case of ABCDA, we use string BCD for the dynamic programming. Now we find the maximum number of elements which matches between original string and reversed string. Count of minimum non matching characters are the solution for the puzzle.

1:  package com.oracle;  
2:  import java.util.Collections;  
3:  import java.util.List;  
4:  public class Palindrome {  
5:       String element;  
6:       public Palindrome(final String elem) {  
7:            element = elem;  
8:       }  
9:       public int makePalindrome() {  
10:            if (element.length() <= 1) {  
11:                 return 0;  
12:            } else {  
13:                 char[] dst = new char[element.length()];  
14:                 int endIndex = element.length() - 1;  
15:                 int index = 0;  
16:                 element.getChars(0, element.length(), dst, 0);  
17:                 while (dst[index] == dst[endIndex]) {  
18:                      index++;  
19:                      endIndex--;  
20:                 }  
21:                 String substring = element.substring(index, endIndex + 1);  
22:                 System.out.println("New String is: " + substring);  
23:                 return Math.min(substring.length(),  
24:                           minCharForPalindrome(substring.toCharArray(), 0));  
25:            }  
26:       }  
27:       private int minCharForPalindrome(char[] substringArray, int compare) {  
28:            if(compare > substringArray.length){  
29:                 return compare;  
30:            }  
31:            int count = 0;  
32:            for (int index = compare, last = substringArray.length - 1; 
                   index < substringArray.length; index++, last--) {  
33:                 if (substringArray[index] != substringArray[last]) {  
34:                      count++;  
35:                 }  
36:            }  
37:            count += compare;  
38:            System.out.println("When Compare = " + compare + " Count= " + count);  
39:            return Math.min(count,  minCharForPalindrome(substringArray, ++compare));  
40:       }  
41:       /**  
42:        * @param args  
43:        */  
44:       public static void main(String[] args) {  
45:            Palindrome p = new Palindrome("ABCDEFG");  
46:            System.out.println("Chars to be added are: " + p.makePalindrome());  
47:       }  
48:  }  

This solution is based on the dynamic programming where starting from the first point string is compared with the another string. The solution is general should take O(N*N) time to compute the result.
1:  New String is: ABCDEFG  
2:  When Compare = 0 Count= 6  
3:  When Compare = 1 Count= 7  
4:  When Compare = 2 Count= 6  
5:  When Compare = 3 Count= 7  
6:  When Compare = 4 Count= 6  
7:  When Compare = 5 Count= 7  
8:  When Compare = 6 Count= 6  
9:  When Compare = 7 Count= 7  
10:  Chars to be added are: 6  

1:  New String is: ASD3D5  
2:  When Compare = 0 Count= 6  
3:  When Compare = 1 Count= 3  
4:  When Compare = 2 Count= 6  
5:  When Compare = 3 Count= 5  
6:  When Compare = 4 Count= 6  
7:  When Compare = 5 Count= 5  
8:  When Compare = 6 Count= 6  
9:  Chars to be added are: 3  

Now the problem with the solution is the time complexity. Can we do anything better?

Okay few people says yes. There is one solution which uses Knuth-Morris-Pratt Algo to find the solutions more efficiently.I have not implemented it yet, but I would surely try to implement and understand it. If you have understood the same, please suggest me the same.

Links for the reference are as following:
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
http://stackoverflow.com/questions/18732020/add-the-least-amount-of-characters-to-make-a-palindrome

Hope it helps

Tuesday, December 8, 2015

Oracle Interview - Telephonic Round

It was a telephonic discussion session for the post of senior software developer. Though I could not clear the round yet it would be best place to share the questions so that I can discuss whether there can be other solutions for the problems asked.

  • What are the differences between JDK, JRE, and JVM?
JDK (Java Development Kit): Development Kit which is actually required for the developers. It is not required to run the Java dependent applications. It is rather required at the development.
JRE (Java Runtime Environment): Java Runtime environment is required to run the java application. It computer does not JRE, No Java application can run on it.
JVM (Java Virtual Machine): JVM is part of JRE, it reads byte code and execute them on the Hardware. It is the reason which causes JAVA applications to run on various platforms without changing much at the program level.
  • Design Problem: You have to build a data/class model for a website. It has users i.e. People and it has group. A User can belong to multiple groups and a Group can have multiple users. Each group maintains an individual account. All the transactions are saved with the person who made the expenses and each person's share is calculated on each transaction. Person vice credit/debit history should also be maintained. Build the data structure for the same.
Design problems are some problem when interviewer and interviewee both do not have same understanding of the requirement. Such problems must only be discussed when you are speaking face to face. It not only gives more confidence but also provides more error correction while writing the code.

For this specific design problem, I had assumed that group is the prime information that system has, whereas Interviewer was expecting that Person should be the prima facie of the complete system. Though it was not difficult both the ways, but it is planned in separate way for both entities.

First Design
Application would have four classes as following

1:   public class Group{  
2:   List<Person> members;  
3:   List<Transaction> transactions;  
4:   List<Share> shares;  
5:   double totalExpenditure;  
6:   //Methods  
7:   addPerson  
8:   addTransaction  
9:   settleAmount  
10:   getShare for a person  
11:   }  
12:   public class Person{  
13:   String name;  
14:   List<Group> groups;  
15:   double credit;  
16:   double debit;  
17:   //Method  
18:   addToCredit  
19:   addToDebit  
20:   addGroup  
21:   }  
22:   public class Share{  
23:   double credit;  
24:   double debit;  
25:   Person belongsTo;  
26:   //Changes with each transaction.  
27:   }  
28:   //Transaction once added, it would be required it to modify.  
29:   public final class Transaction{ //Immutable class  
30:   final String type;  
31:   final String expenseReason;  
32:   final double amount;  
33:   final Person spentBy;  
34:   public Transaction(final String t, final String r, final double amount, final Person p){  
35:    type = t;  
36:    expenseReason = r;  
37:    this.amount = amount;  
38:    spentBy = p;  
39:   }  
40:   }  
Now when the system is designed from group point of view, it is considered that group is self managed and everyone part of the group would really be part of all the transactions relevant to group.

All the classes are self explanatory. Why did I make Transaction as immutable? Transaction is once done, it can not be altered later. Though there can be people who would say that 'What if user inputs the wrong data?' Oh yes, user has rights to enter wrong data, but it would be atmost 1% times.

It is best to solve the problems which are essential rather increase the complexity of the system by solving trivial problems.

However interviewer wanted to run things with the user perspective. As per him, A group is an entity based on users. User may or may not be the part of group's particular transactions. So it was required to rewrite the classes again based on the following assumption.

  //Transaction once added, it would not be required to modify it.  
  public final class Transaction{  
  final String type;  
  final String expenseReason;  
  final double amount;  
  final Person spentBy;  
  final List<Person> sharedAmong;  
  public Transaction(final String t, final String r, final double amount, final Person p, final List<Person> shared){  
   type = t;  
   expenseReason = r;  
   this.amount = amount;  
   spentBy = p;  
   sharedAmong = Collections.unmodifiableList(shared);  
  }  
  }  

However when things are user's point, then it is required to provide administrative work to someone who can create group, assign group, and perform group related works. It is required to add few fields and methods in other classes as well.

  public class Group{  
  List<Person> admins;  
         .....  
  }  
  public class Person{  
         ....  
  createGroup  
  addAdminToTheGroup  
  invitePeople  
  }  

However we can add more to it, but till this point we discussed.
  • Algorithm Problem: A random string is provided to you, you must find the minimum number of elements to be inserted in the string to make it palindrome.
    • String is ABA, then method must return 0.
    • String is ABC, then method must return 2 to form ABCBA.
    • String ABCDA, then method must return 2 to form ABCDCBA.
    • String ASD3D5, then method must return 3 to form AS5D3D5SA.
It would be best to save to Algorithm Problem for the next blog. I could not solve the problem at the time of interview, but I have a solution with O(n*n) complexity. If there is solution available which is better than this, please suggest me.

If you think that above design problem can be designed better, please suggest.

Friday, January 17, 2014

Interview: Java along with Algorithm 3

First F2F was followed with another rounds of F2F. Though first round was 90 minutes long but this round did not last longer than 40 minutes.

  1. How to save key and list of Integers in the HashMap?
  2. How is it possible to reduce the size of this map?
  3. Implement HashMap?
  4. Implement LRU with the help of Map?
  5. Find all possible strings of a Given String?
I have got few more interviews lined up for next couple of days. So I will try to remember post those interview question.

In addition to posting new questions, I will surely post the answers these questions.

Interview: Java along with Algorithm 2

After clearing questions in the first round, I was asked to face the interviewer in F2F rounds. I was nervous to face the interviewers after a long long time.

It all started with the general introductory question and followed with the following questions.
  1. Difference between Restful and Soap web services?
  2. What is Soap WS?
  3. Which different XML parsers we have?
  4. Write code for stream parser?
  5. Tell me the class loader heirarchy?
  6. What is serialization?
  7. What is SerialVersionUID?
  8. How does Hashmap work?
  9. What are the differences between SynchronizedHashMap and ConcurrentHashMap?
  10. Implement stack using 2 queues?
  11. Implement stack using 1 queue?
  12. Sort an array containing numbers 0,1,2?
  13. Difference between abstraction and encapsulation?
  14. where will you categories the private method?
  15. How to stop subclass from serializing if super-class is serializable?
I will try to post answers to following question within some time.

Serialization: All about Persisting the Object

I was thinking to improve my java fundamentals, so I planned to make few notes for myself that will assist me in future (Obviously at the time of Interviews). Following questions and answers have been taken from stackoverflow.com or such other sites. This post is a sticky note post for me. Please do not use the answers for reference purpose.

I have heard lot of Serialization, but do I really know the real purpose of Serialization? When someone tells me that serialization is required to save data in DBs and files, then it confuses my small brain. Did I ever serialize a class explicitly? Let’s find some answers to our question.

What do you mean by Serialization?
Serialization is the conversion of an object to a series of bytes, so that the object can be easily saved to persistent storage or streamed across a communication link. The byte stream can then be deserialised - converted into a replica of the original object.

Objects to be stored and retrieved frequently refer to other objects. Those other objects must be stored and retrieved at the same time to maintain the relationships between the objects. When an object is stored, all of the objects that are reachable from that object are stored as well.

The goals for serializing JavaTM objects are to:
  •  Have a simple yet extensible mechanism.
  • Maintain the JavaTM object type and safety properties in the serialized form.
  • Be extensible to support marshaling and unmarshaling as needed for remote objects.
  •  Be extensible to support simple persistence of JavaTM objects.
  • Require per class implementation only for customization.
  • Allow the object to define its external format.
Understanding Serialization with an analogy
After hard work of many years, Earth's scientist developed a robot who can help them in daily work. But this robot was less featured than the robots which were developed by the scientist of Mars planet.
After a meeting between both planet's scientist, it is decided that mars will send their robots to earth. But a problem occurred. The cost of sending 100 robots to earth was $100 millions. And it takes around 60 days for traveling.
Finally, Mar's scientist decided to share their secret with Earth's scientists. This secret was about the structure of class/robot. Earth's scientists developed the same structure on earth itself. Mar's scientistsserialized the data of each robot and send it to earth. Earth's scientists deserialized the data and fed it into each robot accordingly.

This process saved the time in communicating mass amount of data.
Some of the robots were being used in some defensive work on Mars. So their scientists marked some crucial properties of those robots as transient before sending their data to Earth. Note that transient property is set to null(in case of reference) or to default value(in case of primitive type) when the object gets deserialized.

One more point which was noticed by Earth's scientists is that Mars's scientists ask them to create some static variables to keep environmental detail. This detail is used by some robots. But Mars's scientists dint share this detail because the environment on earth was different from Mars.

Understand Serialization with Real life example
  • Banking example: When the account holder tries to withdraw money from the server through ATM, the account holder information along with the withdrawl details will be serialized (marshalled/flattened to bytes) and sent to server where the details are deserialized (unmarshalled/rebuilt the bytes)and used to perform operations. This will reduce the network calls as we are serializing the whole object and sending to server and further request for information from client is not needed by the server.
  • Stock example: Lets say an user wants the stock updates immediately when he request for it. To achieve this, everytime we have an update, we can serialize it and save it in a file. When user requests the information, deserialize it from file and provide the information. This way we dont need to make the user wait for the information until we hit the database, perform computations and get the result.

Why should Serialization be used?
·         To persist data for future use. It is possible to persist data in DB server, file system or other mean which can hold it forever.
·         To send data to a remote computer using such client/server Java technologies as RMI or socket programming.
  • To "flatten" an object into array of bytes in memory.
  • To exchange data between applets and servlets.
  • To store user session in Web applications.
  • To activate/passivate enterprise java beans.
  • To send objects between the servers in a cluster.

Terms to understand serialization

Static fields
If you are a java programmer, static fields does not require any explanation here. You must remember that static fields are associated with the class instead the object, so while serializing the state of the object, these fields are not serialized with object data.

The serialization runtime associates with each serializable class a version number, called a serialVersionUID, which is used during deserialization to verify that the sender and receiver of a serialized object have loaded classes for that object that are compatible with respect to serialization. If the receiver has loaded a class for the object that has a different serialVersionUID than that of the corresponding sender's class, then deserialization will result in an InvalidClassException. A serializable class can declare its own serialVersionUID explicitly by declaring a field named "serialVersionUID" that must be static, final, and of type long:

ANY-ACCESS-MODIFIER static final long serialVersionUID = 42L;

If a serializable class does not explicitly declare a serialVersionUID, then the serialization runtime will calculate a default serialVersionUID value for that class based on various aspects of the class, as described in the Java(TM) Object Serialization Specification. However, it is strongly recommended that all serializable classes explicitly declare serialVersionUID values, since the default serialVersionUID computation is highly sensitive to class details that may vary depending on compiler implementations, and can thus result in unexpected InvalidClassExceptions during deserialization. Therefore, to guarantee a consistent serialVersionUID value across different java compiler implementations, a serializable class must declare an explicit serialVersionUID value. It is also strongly advised that explicit serialVersionUID declarations use the private modifier where possible, since such declarations apply only to the immediately declaring class--serialVersionUID fields are not useful as inherited members.


So serialVersionUID is used for following 2 scenarios
  • SerialVersionUID acts as meta-data for Serialization and Deserialization process.
  • SerialVersionUID is changed to reject unused serialized objects in future releases.


Variables may be marked transient to indicate that they are not part of the persistent state of an object.

The basic mechanism of Java serialization is simple to use, but there are some more things to know. As mentioned before, only objects marked Serializable can be persisted. The java.lang.Object class does not implement that interface. Therefore, not all the objects in Java can be persisted automatically. The good news is that most of them -- like AWT and Swing GUI components, strings, and arrays -- are serializable.

On the other hand, certain system-level classes such as Thread, OutputStream and its subclasses, and Socket are not serializable. Indeed, it would not make any sense if they were. For example, thread running in my JVM would be using my system's memory. Persisting it and trying to run it in your JVM would make no sense at all. Another important point about java.lang.Object not implementing the Serializable interface is that any class you create that extends only Object (and no other serializable classes) is not serializable unless you implement the interface yourself (as done with the previous example).

That situation presents a problem: what if we have a class that contains an instance of Thread? In that case, can we ever persist objects of that type? The answer is yes, as long as we tell the serialization mechanism our intentions by marking our class's Threadobject as transient.

Another reason to use transient is when your class does some kind of internal caching. If, for example, your class can do calculations and for performance reasons it caches the result of each calculation, then saving that cache might not be desirable (because recalculating it might be faster than restoring it, or because it's unlikely that old cached values are of any use). In this case you'd mark the caching fields as transient.

Let’s serialize a class
Java has provided 2 ways to serialize a class. Developer is allowed to use either default mechanism provided by java by implementing java.io.Serializable interface or custom mechanism by implementing java.io. java.io.Externalizable interface. Serializable is a marker interface/tag interface which defines a contract of serializability and suggests VM to serialize class whereas Externalizable contains two methods which should be implemented to serialize the object.

Let’s serialize the class with default implementation.

Create a class which implements java.io.Serializable interface.
List 1
import java.io.Serializable;
import java.util.Date;
public class Person implements Serializable {
      private static final long serialVersionUID = -8708626244864641161L;
      String name;
      Date dob;
      public String getName() {
            return name;
      }
      public void setName(String name) {
            this.name = name;
      }
      public Date getDob() {
            return dob;
      }
      public void setDob(Date dob) {
            this.dob = dob;
      }
}


Create OutputObjectStream by passing applicable OutputStream. E.g. to create File, one of the application output stream is FileOutputStream.

List 2
FileOutputStream fos = new FileOutputStream(new File("PersonDetail.ser"));
ObjectOutputStream oos = new ObjectOutputStream(fos);
Call writeObject method of ObjectOutputStream with the instance of the object you want to serialize.
List 3
outStream.writeObject(personInstance);

Let's club last 2 steps into one program.
List 4
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.Date;
public class DemoSerialization {
      public static void main(String[] args) throws IOException {
            Person per = new Person();
            per.setName("Vishal Jain");
            per.setDob(new Date(1971, 1, 1));//Let's forget that it is deprecated method.
            FileOutputStream fos = new FileOutputStream(new File("Person.ser"));
            ObjectOutputStream oos = new ObjectOutputStream(fos);
            oos.writeObject(per);
      }
}

On running this program, it will create a file Person.ser in current folder which contains content of the Object Person.

Let’s de-serialize the class with default implementation.
Create InputObjectStream by passing applicable InputStream. E.g. to create File, one of the application input stream is FileInputStream.
List 5
FileInputStream fis = new FileInputStream(new File("PersonDetail.ser"));
ObjectInputStream ois = new ObjectInputStream(fos);
Call readObject method of ObjectInputStream with the instance of the object you want to serialize.
List 6
(CAST_TO_PERSON)outStream.readObject();
Let's club last 2 steps into one program.
List 7
public class DemoSerialization { 
      public static void main(String[] args) throws IOException, ClassNotFoundException {
            FileInputStream fis = new FileInputStream(new File("Person.ser"));
            ObjectInputStream ois = new ObjectInputStream(fis);
            Person per = (Person)ois.readObject();
            System.out.println("Name:"  + per.getName() + " DOB:" + per.getDob());
      }
}

Output for the following program as follows:
List 8
Name:Vishal Jain DOB:Wed Feb 01 00:00:00 IST 3871

Let’s check the importance of serialVersionUID
Our application has person class with serialVersionUID, and client contains a persisted object. Another developer did not know the importance of serialVersionUID, so he changes the version UID as following.
List 9
import java.io.Serializable;
import java.util.Date;
public class Person implements Serializable {
      //Changing -8708626244864641161L to 8708626244864641161L.
      private static final long serialVersionUID = 8708626244864641161L;
      String name;
      Date dob;
      public String getName() {
            return name;
      }
      public void setName(String name) {
            this.name = name;
      }
      public Date getDob() {
            return dob;
      }
      public void setDob(Date dob) {
            this.dob = dob;
      }
}


On re-running the list 6 again with new Person (as per the list 7), following exception is encountered.
List 10
Exception in thread "main" java.io.InvalidClassException: Person; local class incompatible: stream classdesc serialVersionUID = -8708626244864641161, local class serialVersionUID = 8708626244864641161
      at java.io.ObjectStreamClass.initNonProxy(ObjectStreamClass.java:562)
      at java.io.ObjectInputStream.readNonProxyDesc(ObjectInputStream.java:1582)
      at java.io.ObjectInputStream.readClassDesc(ObjectInputStream.java:1495)
      at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:1731)
      at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1328)
      at java.io.ObjectInputStream.readObject(ObjectInputStream.java:350)
      at DemoSerialization.main(DemoSerialization.java:12)


Till now it looks that the serialization is quite simple but is it that simple as demonstrated till now? So let’s understand it with various cases.

When an object has a reference to other objects
In general all the classes are not simple to have only primitives. Most of the classes contains object of another Java class. So what happens when application tries to serialize such classes?
Let’s introduce Person’s address. To add Person’s address, application need to have Address class in the classpath.
List 11
package com.serial;
public class Address {
 int houseNo;
 String city;
 int pincode;
 public int getHouseNo() {
  return houseNo;
 }
 public void setHouseNo(int houseNo) {
  this.houseNo = houseNo;
 }
 public String getCity() {
  return city;
 }
 public void setCity(String city) {
  this.city = city;
 }
 public int getPincode() {
  return pincode;
 }
 public void setPincode(int pincode) {
  this.pincode = pincode;
 }
 public Address(int houseNo, String city, int pincode) {
  this.houseNo = houseNo;
  this.city = city;
  this.pincode = pincode;
 }
}
Let’s change the definition of Person class
List 12
package com.serial;
import java.io.Serializable;
public class Person implements Serializable {
 private static final long serialVersionUID = 100L;
 String name;
 Address office;
 Address home;
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 public Address getOffice() {
  return office;
 }
 public void setOffice(Address office) {
  this.office = office;
 }
 public Address getHome() {
  return home;
 }
 public void setHome(Address home) {
  this.home = home;
 }
}
Okay, stage is set to serialize the new version of Person class. Let’s serialize.
List 13
public class DemoSerialization {
      public static void main(String[] args) throws IOException {
            Person per = new Person();
            per.setName("Vishal Jain");
            Address home = new Address(100, "Noida", 201300);
            Address office = new Address(100, "Delhi", 101300);
            per.setHome(home);
            per.setOffice(office);
            FileOutputStream fos = new FileOutputStream(new File("Person.ser"));
            ObjectOutputStream oos = new ObjectOutputStream(fos);
            oos.writeObject(oos);
      }
}
After running the program, application threw exception mentioned below.
List 14
Exception in thread "main" java.io.NotSerializableException: com.serial.Address
 at java.io.ObjectOutputStream.writeObject0(Unknown Source)
 at java.io.ObjectOutputStream.defaultWriteFields(Unknown Source)
 at java.io.ObjectOutputStream.writeSerialData(Unknown Source)
 at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source)
 at java.io.ObjectOutputStream.wr iteObject0(Unknown Source)
 at java.io.ObjectOutputStream.writeObject(Unknown Source)
 at com.serial.DemoSerialization.main(DemoSerialization.java:16)
Oops, it was not expected. Is not it? As java says, to serialize a class it is required to implement java.io.Serializable interface, but address class do not implement this interface.
In the first version of Person class, String, still a java class, was used. Why did not application throw any exception? The answer is clear. String class implements java.io.Serializable, Comparable<String>, CharSequence interfaces, so it is possible to serialize classes having String fields.

Let’s implement the interface in Address class and rerun the program.
List 15
package com.serial;
import java.io.Serializable;
public class Address implements Serializable {
 private static final long serialVersionUID = 1000L;
 int houseNo;
 String city;
 int pincode;
 public int getHouseNo() {
  return houseNo;
 }
 public void setHouseNo(int houseNo) {
  this.houseNo = houseNo;
 }
 public String getCity() {
  return city;
 }
 public void setCity(String city) {
  this.city = city;
 }
 public int getPincode() {
  return pincode;
 }
 public void setPincode(int pincode) {
  this.pincode = pincode;
 }
 public Address(int houseNo, String city, int pincode) {
  this.houseNo = houseNo;
  this.city = city;
  this.pincode = pincode;
 }
}
After running the program, Person.ser file is created with serialized object.

Now let’s try to deserialize the content with the following code
List 16
public static void main(String[] args) throws IOException, ClassNotFoundException {
            FileInputStream fis = new FileInputStream(new File("Person.ser"));
            ObjectInputStream ois = new ObjectInputStream(fis);
            Person per = (Person)ois.readObject();
            System.out.println("Name:"  + per.getName() + " Home City:" + per.getHome().getCity()
              + " Office City:" + per.getOffice().getCity());
      }
  
}
Result is as followed:
List 17
Name:Vishal Jain Home City:Noida Office City:Delhi
Impact of Inheritance on Serialization
When a super class is implementing the Serializable interface, then all the classes extending the specific super class is serializable.

Subclass is serializable but superclass is not
Let’s change person class such that it does not implement Serializable interface anymore, and let’s define a constructor of the class, so that default construction is not allowed anymore.
List 18
public class Person{
.
.
.
 public Person(String name, Address office, Address home) {
  super();
  this.name = name;
  this.office = office;
  this.home = home;
 }
}
Create a subclass player that extends Person class.
List 19
package com.serial;
import java.io.Serializable;
public class Player extends Person implements Serializable {
 private static final long serialVersionUID = -154L;
 String academy;
 public Player(String name, Address office, Address home, String aced) {
  super(name, office, home);
  academy = aced;
 }
 public String getAcademy() {
  return academy;
 }
 public void setAcademy(String academy) {
  this.academy = academy;
 }
}
Serialize the Player class as following
List 20
public class DemoSerialization {
 public static void main(String[] args) throws IOException {
  Address home = new Address(100, "Noida", 201300);
  Address office = new Address(100, "Delhi", 101300);
  Player per = new Player("Vishal Jain", home, office, "SRT Aceds");
  FileOutputStream fos = new FileOutputStream(new File("Player.ser"));
  ObjectOutputStream oos = new ObjectOutputStream(fos);
  oos.writeObject(per);
 }
}
It creates a file called Player.ser which contains information about the primitives and fields that are part of Player class.
Let’s try to deserialize the object with the following code.
List 21
public class DemoDeSerialization {
      public static void main(String[] args) throws IOException, ClassNotFoundException {
            FileInputStream fis = new FileInputStream(new File("Player.ser"));
            ObjectInputStream ois = new ObjectInputStream(fis);
            Player per = (Player)ois.readObject();
            System.out.println("Academy:"  + per.getAcademy() );
      } 
}
On executing the application following exception is encountered.
List 22
Exception in thread "main" java.io.InvalidClassException: com.serial.Player; com.serial.Player; no valid constructor
 at java.io.ObjectStreamClass.checkDeserialize(Unknown Source)
 at java.io.ObjectInputStream.readOrdinaryObject(Unknown Source)
 at java.io.ObjectInputStream.readObject0(Unknown Source)
 at java.io.ObjectInputStream.readObject(Unknown Source)
 at com.serial.DemoDeSerialization.main(DemoDeSerialization.java:12)
Does not that mean that we are missing something? Yes we are. So add a default constructor is Person class and this program will work fine without any issues.
List 23
public class Person{
 .
 .
 .
 public Person() {
 }
}
It is quite clear that when a superclass is not serialized then application do not serialize the information about the class and at the time of Deserilizing the object is tries to create the object with default constructor. If constructor is not found, it throws the exception else creates default instance of super class.
Superclass is serializable but subclass should not be serializable
When superclass is serializable, but application does not want to store classes extending the superclass.
In this case subclass must implement readObject and writeObject methods and these methods must throw java.io.NotSerializableException.
List 24
public class Player extends Person {
 .
 .
 .
 private void writeObject(ObjectOutputStream os) throws IOException, ClassNotFoundException{
  throw new NotSerializableException();
 }
  private void readObject(ObjectInputStream is) throws IOException, ClassNotFoundException{
  throw new NotSerializableException();
 }
}
On running the program listed above, application throws following exception.
List 25
Exception in thread "main" java.io.NotSerializableException
 at com.serial.Player.writeObject(Player.java:23)
 at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
 at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
 at java.lang.reflect.Method.invoke(Unknown Source)
 at java.io.ObjectStreamClass.invokeWriteObject(Unknown Source)
 at java.io.ObjectOutputStream.writeSerialData(Unknown Source)
 at java.io.ObjectOutputStream.writeOrdinaryObject(Unknown Source)
 at java.io.ObjectOutputStream.writeObject0(Unknown Source)
 at java.io.ObjectOutputStream.writeObject(Unknown Source)
 at com.serial.DemoSerialization.main(DemoSerialization.java:13)
Serialize when source code is not available
There are instances when third party class/subclass must be serialized but vendor has not provided the source code. Then what options do the coder has?

Don’t Serialize the class
In case of composition, you can mark the variable/field transient, which will suggest compiler not to serial the object.
List 26
transient Address office;
Okay, Application cannot live without the object, and it is required to serialize
In this case, it is required to implement readObject and writeObject according to the requirement.
List 27
 private void writeObject(ObjectOutputStream oos) throws IOException, ClassNotFoundException {
  try {
   oos.defaultWriteObject();
   oos.writeInt(home.getHouseNo());
  }
  catch (Exception e) { 
   e.printStackTrace(); 
  }
 }
 private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {
  try {
   ois.defaultReadObject();
   home = new Address(ois.readInt(), "", 0);
  } catch (Exception e) { 
   e.printStackTrace(); 
  }
 }
Please maintain the same order of reading and writing, else serialized object will differ from the object de-serialized.


Enum constants are serialized differently than ordinary serializable or externalizable objects. The serialized form of an enum constant consists solely of its name; field values of the constant are not present in the form. To serialize an enum constant, ObjectOutputStream writes the value returned by the enum constant's name method. To deserialize an enum constant, ObjectInputStream reads the constant name from the stream; the deserialized constant is then obtained by calling the java.lang.Enum.valueOf method, passing the constant's enum type along with the received constant name as arguments. Like other serializable or externalizable objects, enum constants can function as the targets of back references appearing subsequently in the serialization stream.

The process by which enum constants are serialized cannot be customized: any class-specific writeObject, readObject, readObjectNoData, writeReplace, and readResolve methods defined by enum types are ignored during serialization and deserialization. Similarly, any serialPersistentFields or serialVersionUID field declarations are also ignored--all enum types have a fixed serialVersionUID of 0L. Documenting serializable fields and data for enum types is unnecessary, since there is no variation in the type of data sent.


When java has provided default and robust implementation of Serialization, then why it mandated developers to implement marker interface. Java could have provided serialization as default behavior of class.

Best explanation for java’s such decision is following

Serialization is fraught with pitfalls. Automatic serialization support of this form makes the class internals part of the public API (which is why javadoc gives you the persisted forms of classes).

For long-term persistence, the class must be able to decode this form, which restricts the changes you can make to class design. This breaks encapsulation.
Serialization can also lead to security problems. By being able to serialize any object it has a reference to, a class can access data it would not normally be able to (by parsing the resultant byte data).

There are other issues, such as the serialized form of inner classes not being well defined.
Making all classes serializable would exacerbate these problems. Check out Effective Java Second Edition, in particular Item 74: Implement Serializable judiciously.

Another reason, but it has it’s counter argument, for not providing default serialization can be following

Not everything is genuinely serializable. Take a network socket connection, for example. You could serialize the data/state of your socket object, but the essence of an active connection would be lost.

Default serialization is somewhat verbose, and assumes the widest possible usage scenario of the serialized object, and accordingly the default format (Serializable) annotates the resultant stream with information about the class of the serialized object.

Externalization give the producer of the object stream complete control over the precise class meta-data (if any) beyond the minimal required identification of the class (e.g. its name). This is clearly desirable in certain situations, such as closed environments, where producer of the object stream and its consumer (which reifies the object from the stream) are matched, and additional metadata about the class serves no purpose and degrades performance.

Additionally (as Uri point out) externalization also provides for complete control over the encoding of the data in the stream corresponding to Java types. For (a contrived) example, you may wish to record boolean true as 'Y' and false as 'N'. Externalization allows you to do that.

If you want to read more about serialization, you can browse following articles.


There are few more topics to cover on serialization, that we can take up sometime later.
Few of them are as following:
  • Content of Serialized Objects.
  • Performance of Serialized Objects.

Tuesday, January 7, 2014

Interview: Java along with Algorithm

Few days back, I faced a telephonic interview with a Product based company in Gurgaon. It was quite a quick interview round for me. Here I am mentioning the questions asked by interviewer.


So Linked list provides following two advantages over arrays
1)         Dynamic size
2)         Ease of insertion/deletion
Linked lists have following drawbacks:
1)         Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2)         Extra memory space for a pointer is required with each element of the list.
3)         Arrays have better cache locality that can make a pretty big difference in performance. 

Q3. Suggest the best possible data structure in these 2 conditions?
A. DS must have add, delete, search operations, where search is most used functions of the DS?
DS based on hashing technique.
B. DS must have add, delete, rangeSearch operations, where search is most used functions of the DS?
DS based on Tree technique.

Q4. What do you mean by Hashing?
Q5. What are the different algorithms to resolve hash collision?
Q6. Is it possible to call static method within a constructor?
Q7. What is synchronization?
Q8. What are the different ways of implementing Threads?

Q9. What is the difference between creating threads by implementing runnable Interface or extending thread class implementation?
Implements Runnable is the preferred way to do it, IMO. You're not really specializing the thread's behaviour. You're just giving it something to run. That means composition is the philosophically "purer" way to go.

In practical terms, it means you can implement Runnable and extend from another class as well.

Q10. What is the difference between Callable and Runnable interfaces?
The Callable interface is similar to Runnable, in that both are designed for classes whose instances are potentially executed by another thread. A Runnable, however, does not return a result and cannot throw a checked exception.

Q11. What is garbage collection?
Q12. What is the difference between notify and notifyAll()?

Q13. What are practical scenarios where notify and notifyAll work?

Generics: Bridge Method

I was thinking to improve my algorithmic fundamentals, so I planned to make few notes for myself that will assist me in future (Obviously at the time of Interviews). Following questions and answers have been taken from stackoverflow.com. This post is a sticky notes post for me. Please do not use the answers for reference purpose.

Generics were introduced in Java in 1.5. It provided a tool to handle the casting related problems at the time of run times. With the use of generics ClassCastException has been reduced.

Earlier versions of Java 5 did not impose such generic restrictions, so programmer used to face various casting related problems.

Java 1.4 and prior version were using following formats. There were 2 main issues with these formats.
List list = new ArrayList();//Any class extending Object can be added to list.
list.add("hello");
String s = (String) list.get(0);//Explicit type casting is required.


Java 5 introduced generics which used to type safe the collection objects.
List list = new ArrayList();//Type-safe, it is required to add strings only.
list.add("hello");
String s = list.get(0);   // no cast

What did Java introduce to deal with Generics?
Nothing, While creating the byte code, it removed all generic and replace them with actual classes. So byte code for Java 1.4 version and Java 5 version will remain same. This process called 'ERASUR'.
List list = new ArrayList();
list.add("hello");
String s = (String)list.get(0);

For both the versions following runtime code will execute.

Type Erasur can fail in some conditions, one of such condition is as follows. (Example is taken from Oracles docs)
public class Node {
    private T data;
    public Node(T data)
{ this.data = data; }

    public void setData(T data) {
        System.out.println("Node.setData");
        this.data = data;
    }
}

public class MyNode extends Node {
    public MyNode(Integer data) { super(data); }

    public void setData(Integer data) {
        System.out.println("MyNode.setData");
        super.setData(data);
    }
}

MyNode mn = new MyNode(5);
Node n = mn;            // A raw type - compiler throws an unchecked warning
n.setData("Hello");     // Causes a ClassCastException to be thrown.
Integer x = mn.data;

After Type Erasur code becomes as following.
MyNode mn = new MyNode(5);
Node n = (MyNode)mn;         // A raw type - compiler throws an unchecked warning
n.setData("Hello");
Integer x = (String)mn.data; // Causes a ClassCastException to be thrown.

Bridge Method?
When compiling a class or interface that extends a parameterized class or implements a parameterized interface, the compiler may need to create a synthetic method, called abridge method, as part of the type erasure process. You normally don't need to worry about bridge methods, but you might be puzzled if one appears in a stack trace.

After type erasure, the Node MyNode classes become:
public class Node {

    private Object data;

    public Node(Object data) { this.data = data; }

    public void setData(Object data) {
        System.out.println("Node.setData");
        this.data = data;
    }
}

public class MyNode extends Node {

    public MyNode(Integer data) { super(data); }

    public void setData(Integer data) {
        System.out.println(Integer data);
        super.setData(data);
    }
}

After type erasure, the method signatures do not not match. The Node method becomes setData(Object) and the MyNode method becomes setData(Integer). Therefore, the MyNode setData method does not override the Node setData method.
To solve this problem and preserve the polymorphism of generic types after type erasure, a Java compiler generates a bridge method to ensure that subtyping works as expected. For the MyNode class, the compiler generates the following bridge method for setData:
class MyNode extends Node {

    // Bridge method generated by the compiler
    //
    public void setData(Object data) {
        setData((Integer) data);
    }

    public void setData(Integer data) {
        System.out.println("MyNode.setData");
        super.setData(data);
    }

    // ...
}
As you can see, the bridge method, which has the same method signature as the Node class's setData method after type erasure, delegates to the original setData method.

Note: In this post everything is copied from Java Docs.