Friday, December 25, 2015

Amazon Interview 1: Problem 2

Problem 2: Given two linked lists. Each node stores a single digit. Each linked list this way represents a decimal number, with number of digits = number of nodes in the list. You need to add them to produce a third list which represents the sum of the numbers.

Problem statement would be complete only if we know the how decimal numbers are represented in the list.


To represent .123 the list is 1 -> 2-> 3


To add 2 numbers, you must consider the following scenario:


List 1 = 4 -> 5 -> 6

List 2 = 6 -> 9

Returned list should be 1 -> 1 -> 4 -> 6 (Though if this is considered only decimal number, it would be incorrect) but for time being let's consider this as a solution.


Solution 1: Modify the shorter list to append the '0' (Zero) to make both the lists size equal. For each list reach to ith location (1 <= i <= N ) starting from the Size of the list and add both the lists. If sum is greater than one use carry to add (i - 1) position.


List 1 => 4 -> 5 -> 6

List 2 => 6 -> 9 -> 0

When I = 3 (Iteration to reach 3rd position = 3)

List 3 => 6
Carry = 0

When I = 2 (Iteration to reach 3rd position = 2)

List 3 => 4 -> 6
Carry  = 1

When I = 1 (Iteration to reach 3rd position = 1)

List 3 => 1 -> 4 -> 6
Carry = 1

Exit the loop and add carry to list 3

List 3 => 1 -> 1 -> 4 -> 6

Time Complexity: 3 + 2 + 1 (N = 3)

Time Complexity for N elements: N + (N-1) + .... + 1 = N(N+1)/2 = O(N*N)

Time complexity of the above solution is O(N*N)


Solution 2: You can even reverse the lists and add them simply. But reversing the list would also require O(N*N) time complexity, and you would change the original structure of the input which is not desirable.


Solution 3: Here is another idea which performs better in normal circumstances, whereas in worst case it has same O(N*N) time complexity.




Logic
 method add start
  input list1 and list2
  minLength = find the smaller length of both the list
  assign a boolean array of len = minLength
  create a node with sum of list1 and list 2 digit mod 10
  array[0] = assign true if sum is greater than zero
  repeatTill = array[0] == true? 0:-1;
  for element from 1 to min length
   create a node with sum of list1 and list 2 digit mod 10
   array[element] = assign true if sum is greater than zero  
   repeatTill = array[element] == true? element:repeatTill;
  end for
  assign the remaining elements of the longer list to new list
  call recursive method to update the carries
 end
 
 method updateCarries start
  input list3, boolean[] array, repeatTill
  if repeatTill is negative then
   return list3
  end if
  if array[0] is true then
   add Node with digit 1 at front of the list
  end if
  for element from 1 to repeatTill
   if array[element] is true then
    assign repeatTill if array[element-1] is true
    update values
   end if
  end for
  return call updateCarries
 end



This solution's best case is O(N) when there is no carry in these two digits. For Example when 123 and 234 are added. In this case, loop is iterated only once.

Whereas in the worst case it will run for O(N*N). That would be most unusual addition. For Example when 9999 and 0001 are added. In this case, N*(N+1)/2 elements are accessed.

Java code for the solution is as following:

Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problem: Given two linked lists. Each node stores a single digit. Each linked
 * list this way represents a decimal number, with number of digits = number of
 * nodes in the list. You need to add then to produce a third list which
 * represents the sum of the numbers.
 * 
 * E.G. LinkedList 1 -> 2 -> 6 LinkedList 3 -> 8
 * 
 *
 */
public class SumDecimal {

 /**
  * This method reads the input and prepares the array and call the relevant
  * method.
  * 
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  /**
   * N is the number of test cases.
   */
  int N = Integer.parseInt(line);
  for (int i = 0; i < N; i++) {
   String[] list1Values = br.readLine().split(" ");
   String[] list2Values = br.readLine().split(" ");
   Node list1 = null;
   for (int index = list1Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list1Values[index]));
    n.next = list1;
    list1 = n;
   }
   Node list2 = null;
   for (int index = list2Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list2Values[index]));
    n.next = list2;
    list2 = n;
   }
   Node list3 = add(list1, list2);
   System.out.println(list3);
  }
 }

 private static Node add(Node list1, Node list2) {
  int minLength = 1;
  Node l1 = list1;
  Node l2 = list2;
  while (l1.next != null && l2.next != null) {
   minLength++; // M or N whatever is smaller.
   l1 = l1.next;
   l2 = l2.next;
  }
  boolean[] carries = new boolean[minLength];
  Node list3 = new Node((list1.digit + list2.digit) % 10);
  Node list = list3;
  carries[0] = (list1.digit + list2.digit) / 10 == 0 ? false : true;
  int toMove = carries[0] ? 0 : -1;
  for (int index = 1; index < minLength; index++) {
   Node n = new Node((list1.next.digit + list2.next.digit) % 10);
   carries[index] = (list1.next.digit + list2.next.digit) / 10 == 0 ? false : true;
   list1 = list1.next;
   list2 = list2.next;
   list3.next = n;
   list3 = list3.next;
   toMove = carries[index] ? index : toMove;
  }
  if (list1.next != null) {
   list3.next = list1.next;
  } else {
   list3.next = list2.next;
  }
  list = updateCarries(list, carries, toMove);
  return list;
 }

 private static Node updateCarries(Node list3, boolean[] carries, int toMove) {
  if (toMove == -1)
   return list3;
  int nextMove = -1;
  Node list = list3;
  if (carries[0]) {
   Node n = new Node(1);
   n.next = list3;
   list = n;
   carries[0] = false;
  }
  for (int index = 1; index <= toMove; index++) {
   if (carries[index]) {
    int sum = list3.digit + 1;
    carries[index - 1] = sum == 10 ? true : false;
    list3.digit = sum % 10;
    carries[index] = false;
    nextMove = carries[index - 1] ? index - 1 : nextMove;
   }
   list3 = list3.next;
  }
  return updateCarries(list, carries, nextMove);
 }

 static class Node {
  int digit;
  Node next;

  Node(int digit) {
   this.digit = digit;
  }

  public String toString() {
   return (next == null) ? digit + "" : digit + " " + next.toString();
  }
 }

}



Input
7
1 2 3
2 3 4
3 4 5
3 4 5
9 9 9
0 0 1
9 0 0
1 9 9
9 8 1
1 2
1 2 6 8 9 6 7 8 9
9
1 2 6 8 9 6 7 8 9
9 8 4 2 1 4 3 8 7

Output
3 5 7
6 9 0
9 9 9
1 0 9 9
1 1 0 1
1 0 2 6 8 9 6 7 8 9
1 1 1 1 1 1 1 1 7 6

If you feel that something is not correct with the solution, let me know. I would try to fix the problem.

Thursday, December 24, 2015

Amazon Interview 1: Problem 1

This is not my interview question. It was conducted for my friend. He cleared his interview. Now I am sharing/solving all the questions asked to him.

Question 1: Given a sorted array of numbers, some of which may be repeating. Find the first occurrence of a given number.

Answer: In this case we use a binary search which is modified a bit to find min or max.

       If Binary search matches, get the minimum element in left subtree.
  Fetch Mid
  Check whether high is lower than low, return
  Element matches again, so check if next left subtree matches.
  Element does not matches, find if right subtree has the same element.
 Remaining is the binary search.

Following is the program for the solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problem: Given a sorted array of numbers, some of which may be repeating.
 * Find the first occurrence of a given number.
 * 
 * E.G. 1, 2, 2, 4, 8, 9, 10, 10, 10, 12
 * 
 * @author Praveen
 *
 */
public class FindFirstElement {

 /**
  * This method reads the input and prepares the array and call the relevant method.
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  /**
   * N is the number of test cases.
   */
  int N = Integer.parseInt(line);
  for (int i = 0; i < N; i++) {
   String[] values = br.readLine().split(" ");
   int[] array = new int[values.length];
   for (int index = 0; index < values.length; index++) {
    array[index] = Integer.parseInt(values[index]);
   }
   String find = br.readLine();
   int element = Integer.parseInt(find);
   System.out.println(findIndexForElement(array, element, 0, array.length - 1));
  }
 }

 /**
  * Solution is to use a modified binary search.
  * 1. If Binary search matches, get the minimum element in left subtree.
  * 2. Remaining is the binary search.
  * @param array
  * @param element
  * @param low
  * @param high
  * @return
  */
 private static int findIndexForElement(int[] array, int element, int low, int high) {
  if (low > high) {
   return -1;
  }
  int mid = (low + high) / 2;
  if (array[mid] == element) {
   return getMin(array, element, low, mid - 1);
  } else if (array[mid] > element) {
   return findIndexForElement(array, element, low, mid - 1);
  } else {
   return findIndexForElement(array, element, mid + 1, high);
  }
 }

 /**
  * Finds the element that it first in the array.
  * Solution:
  * 1. Fetch Mid
  * 2. Check whether high is lower than low, return
  * 3. Element matches again, so check if next left subtree matches.
  * 4. Element does not matches, find if right subtree has the same element.
  * @param array
  * @param element
  * @param low
  * @param high
  * @return
  */
 private static int getMin(int[] array, int element, int low, int high) {
  int mid = (low + high) / 2;
  if (low > high) {
   return high + 1;
  } else if (array[mid] == element) {
   return getMin(array, element, low, mid - 1);
  } else {
   return getMin(array, element, mid + 1, high);
  }
 }

}

This program has been tested with the following test cases:
15
1 2 2 4 8 9 10 10 10 12
12
1 2 2 4 8 9 10 10 10 12
16
1 2 2 4 8 9 10 10 10 12
10
1 2 2 4 8 9 10 10 10 12
2
1 2 2 4 8 9 10 10 10 12
1
1 2 2 4 8 9 10 10 10 12
0
1 2 2 4 8 9 10 10 10 12
9
1 2 2 4 8 9 10 10 12
12
1 2 2 4 8 9 10 10 12
16
1 2 2 4 8 9 10 10 12
10
1 2 2 4 8 9 10 10 12
2
1 2 2 4 8 9 10 10 12
1
1 2 2 4 8 9 10 10 12
0
1 2 2 4 8 9 10 10 12
9
1 2 2 4 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13
10

If you think that I have still missed something during testing. Suggest me.

Wednesday, December 23, 2015

Design Patterns: Coffee Vending Machine

The question was asked in an interview to design a coffee vending machine.

Most importantly it is required for us to create the object with the help of creational design patterns. We would try to go through all the creational patterns which are widely known to us.

Let's start with Builder design pattern.
Builder design pattern is applied when the object constructed is huge and application would want to split the responsibility of object creation to various different objects. It can even give you the flexibility to sneak in the different implementations of a certain object based on need.

Does this DP fit to design the coffee vending machine?
Let's look over at the requirement. Coffee vending machine dispatches only few basic things i.e. various tea, various coffees, and hot water. None of the objects are really complex in nature. So it would be waste to invest so much efforts to apply builder pattern for the given problem.

Okay, let's take up another pattern i.e. Singleton design pattern.
Singleton design patterns knowing or unknowing have been in use for us. The idea behind this pattern to allow only one instance across the application. One instance must serve the need of all object requirement.

Instead analyzing this overly, we can conclude that single instance can not serve our purpose in this case. So we can not apply singleton design pattern for our application.

Moving on to Factory Abstract design pattern. (during the interview, I was using this design pattern to implement coffee vending machine)
Factory abstract design application build various different objects based on the requirement. Application would not really not know the product yet, the object created would serve the purpose of the operation. In this case application would require one class/product for each type of product type.

Does this DP fit to design the coffee vending machine?
If vending machine is used to get hot water, an object of hot water class must be returned. In this where the options could be unlimited Factory Abstract limits these options. To add another option, application would always need to introduce new class and add the application's main object which returns the output.

Could Factory Method design pattern suffice the need for this?
Based on my understanding abstract factory and factory method are almost the same. The difference lies between the responsibility of object creation. In case of factory method, object creation responsibility is designated to a factory method.

So applying this method would also be difficult in our scenario.

Let's look at the last known creational DP i.e. Prototype DP. In this design pattern we maintain a registry of object at some place and clone the object as per the need. It is very similar to on demand object creation. So in this DP also we would need to create as many classes as the options in the vending machine. Again, we would be writing way too much code for our work.

As we could not achieve the best design pattern mechanism with the help of creational design pattern. Let's move to other side of design patterns.

Let's look at the requirement in a different way.

Coffee Vending machine is using Coffee, Tea, Water, Milk, and Sugar to create all the available options. It might be needed that option might be needed to add lemon in the water and sugar to create lemon tea. In this case, we can use mix of two patterns. One abstract factory pattern and another is decorator patterns to decorate the object based on need.

Utilization of Abstract Factory pattern. Create 3 separate classes for Water, Coffee, and Tea. These 3 are the main component of the vending machine.

Now decorate the Coffee object with milk to make it milk coffee. Coffee object in itself can be utilized for espresso. Whereas in case tea, we can add various style based on the need.

milkCoffee = new Coffee(new Milk());
milkTea = new Tea(new Milk(new Masala()))
gingerTea = new Tea(new Milk(new Ginger()))
gingerMasalaTea = new Tea(new Milk(new Ginger(new Masala())))

Styling the tea and coffee can be solved with decorator pattern.

Why did we use different objects for tea and coffee?
Tea, Coffee, and Water are different products. So based on usual product understanding, we kept them separate and added styles later which are ginger to tea, masala to tea, and so on. Though it is possible to add the styles to the water to create coffee and tea also.
milkCoffee = new Water(Coffee(new Milk()));

If you think that your understanding deviates from mine. Let me know. We can discuss that in details.

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.

Monday, January 5, 2015

Integrating a PostGreSql database to WAMP server

I am working with WAMP server for quite some time. For my production I have application compatible with PostGreSQL but WAMP was configured with MySQL. It was really a trouble some thing for me.

As I am quite new to PHP, so I was not aware about integrating PostGreSQL with WAMP server. But now I know that. Thanks to the post mentioned below, it helped me a lot to get it working.

http://toolkt.com/site/install-postgresql-and-phppgadmin-in-windows-with-wamp/

Sunday, January 19, 2014

Flipkart Interview 1: Data Structure and Algorithm

It was a telephonic discussion with Flipkart, as per its reputation, its interview throws questions to provide algorithms for them. In the first telecon, I was asked 2 questions (though the interviewer wanted to discuss 3), and those are following 2 questions.

A Binary tree is there, root of the binary tree is provided. It is asked to search a node and find all the nodes that are at a K distance from the tree.
Binary Tree - Not BST
 Consider the tree provided in the figure above.

Root of the tree is A, and it is required to find all the elements at distance 3 from Node D.
Answer should be C, J and K.

Root of the tree is A, and it is required to find all the elements at distance 2 from Node D.
Answer should be A, E, P, Q, R, and S.

Root of the tree is A, and it is required to find all the elements at distance 4 from Node D.
Answer should be T, U, V, F and G.

Solution
It is possible to create the graph where starting node of the graph is D as the starting node of the graph. Search Node along with its path. Create a graph with the help of path that was retained while searching the node, find all the nodes at distance K using BFS.

Algorithm for this as follows:
List 1
Find the element using recursion and store all the elements in a stack.
(Time complexity O(n))
Create the graph such that all the parents, catered in the stacks,
points in the other direction. i.e. D -> B-> A
(Time complexity O log(n) + Space Complexity o(Log n))
Now run the Breadth First Search algorithm to for iterations.
(Time complexity O(n))

Total time complexity for the solution is O(n + log n) = O(k*n) = O(n)
Space Complexity is O(log n). 

Let’s look at the alternative approach, as we have to change the linking, so it might not be feasible to change the DS.
List 2
Find the element using recursion and store all the elements in a stack, 
along with the side of the side of the traversal (Left or Right). 
(Time complexity O(n))
Find all downward elements that are at distance K from the node specified.
For each element pop the stack and maintain a count
From the node popped, find all the elements at (K – count) distance 
at the other side of tree.
End for each 

Let’s write a program for the method mentioned above.
We will need 2 classes for complete DS and solution.
Tree.java
class Tree {  
  char data;
  Tree left;
  Tree right;
  public Tree(char data) {
   this.data = data;
  }
  public char getData() {
   return data;
  }
  public void setData(char data) {
   this.data = data;
  }
  public Tree getLeft() {
   return left;
  }
  public void setLeft(Tree left) {
   this.left = left;
  }
  public Tree getRight() {
   return right;
  }
  public void setRight(Tree right) {
   this.right = right;
  }  
  public String toString(){
   return "" + data;
  }
 }

PathElement.java 
class PathElement {
  int direction;
  Tree node;
  public PathElement(Tree node, int dir) {
   this.node = node;
   direction = dir;
  }
  public int getDirection() {
   return direction;
  }
  public void setDirection(int direction) {
   this.direction = direction;
  }
  public Tree getNode() {
   return node;
  }
  public void setNode(Tree node) {
   this.node = node;
  }
  public String toString(){
   return ("Node:" + node.toString() + " Direction: " + direction  + "\n");
  }
 }
Search the path for element requested, and Keep the PathElement object with the stack.
List 3
 Stack path = new Stack();
 private boolean searchElement(Tree root, char search, int direction) {
  if( root == null ) return false;
  if( root.data == search ){
   path.push(new PathElement(root, direction));
   return true;
  }else{
   path.push(new PathElement(root, direction));
   boolean isInLeftTree = searchElement(root.getLeft(), search, 1);
   boolean isInRightTree = !isInLeftTree? searchElement(root.getRight(), search, 2) : false;
   if(!isInLeftTree && !isInRightTree ){
    path.pop();
    return false;
   }
   return true;
  }
 }
Read the downward element and create for these downward element.
List 4
 private List downwardElements(PathElement elem, int distance) {
  List chars = new LinkedList();
  return readElementAtDistanceK(chars, elem.node, distance);
  //Following method is listed further.
 }
Read the upward elements and add them to the list created above.
List 5
 private List upward(Stack path, PathElement pathElem, int distance) {
  PathElement prevElement = pathElem;
  PathElement element;
  int count = 1;
  List chars = new LinkedList();
  try{
   while( ( element = path.pop() ) != null){
    readElementsInDifferentDirection(chars, element, distance - count, prevElement.direction);
    prevElement = element;
    count++;
   }
  }catch(EmptyStackException ese){
  }
  return chars;
 }

 private List readElementsInDifferentDirection(List chars, PathElement element, int i, int direction) {
  Tree root = element.node;
  if( i == 0 ){
   chars.add(root.data);
  }
  if( direction == 1 ){
   readElementAtDistanceK(chars, root.right, i - 1 );
  }else{
   readElementAtDistanceK(chars, root.left, i - 1 );
  }
  return chars;
 }
Module to Read all the elements at a distance K from a node.
List 6
 private List readElementAtDistanceK(List chars, Tree root, int distance) {
  if( root == null ) return chars;
  if( distance == 0 ){
   chars.add(root.data);
   return chars;
  }
  readElementAtDistanceK(chars, root.left, distance - 1 );
  readElementAtDistanceK(chars, root.right, distance - 1 );
  return chars;
 }
Java representation to call the module is as followed.
List 7
  tp.searchElement(root, search, 0);
  PathElement pathElem = tp.path.pop();
  List<Character> chars = tp.downwardElements(pathElem, distance);
  chars.addAll(tp.upward(tp.path, pathElem, distance));  
  System.out.println("All the Characters:" + chars);
It will contain few generic related warnings and errors, please modify them to compile and run the program.

This approach has space complexity of log(n) and time complexity as defined below.
Search the node and path = O(n) //Worst case scenario.
Search the downward and upward elements = O(n) //Worst case scenario.
Time complexity of algorithm is O(n).

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.