Interview Code Questions


Interview Code Questions

Class invariant - Immutable Class
What's problem in the following immutable class? is it really immutable? Can client violate its immutablity, and make start date of an object greater than end date of it?
or ask interviewee to write a class represent time period, and guarantee its start time is less than its end time.
public class TimeInterval{
private final Date start;
private final Date end;
public TimeInterval(Date s, Date e) {
start = s;
end = e;
if (this.start.compareTo(this.end) > 0)
throw new IllegalArgumentException(start + " after " + end);
}
public Date getStart() {
return start;
}
public Date getEnd() {
return end;
}
}
Is it safe to use the clone method of Date to make a defensive copy in constructor?
What would happen if we use long to represent internal time?
Hints:
It is essential to make a defensive copy of each mutable parameter in constructor.
Defensive copies should be made before checking the validity of the parameters, and the validity check is performed on the copies rather than on the originals.
We can also use the primitive long returned by Date.getTime() as an internal time representation instead of using a Date reference, as long is immutable.


Resources:

Java Inner Class


Java Inner Class

An inner class is a class that is defined inside another class.
The advantages of inner class:
• It is a way of logically grouping classes that are only used in one place, it is a name-hiding and code organization scheme, Inner classes can be hidden from other classes in the same package.
• It increases encapsulation.
• Nested classes can lead to more readable and maintainable code.
• Inner class methods can access the data from the scope in which they are defined, including data that would otherwise be private.
• Anonymous inner classes are handy when you want to define callbacks without writing a lot of code.


The Inner Classes can be classified in four types:
Regular Inner Class or Instance Inner Class
The regular inner class is a full fledged member of the outer class, so it shares all the features of a member of a class. It is associated with an instance of its enclosing class and has direct access to that object's all methods and fields including private methods and fields.
Because an inner class is associated with an instance, it cannot define any static members itself.
Static methods can only be declared in a static or top level type.


An object of inner class has a link to the enclosing object that made it,
An instance of InnerClass can exist only within an instance of OuterClass, to instantiate an inner class, you must first instantiate the outer class. Then, create the inner object within the outer object like below:
OuterClass.InnerClass innerObject = outerObject.new InnerClass();


If you need to produce the reference to the outer-class object, you name the outer class
followed by a dot and this: OuterClass.this
Local Inner class
Local Inner class is created within a method or even an arbitrary scope.
Local inner classes are never declared with an access specifier (that is, public or private). Their scope is always restricted to the block in which they are declared.


Method Local Inner class is completely hidden from the outside world-not even outerclass.


They can not only access the fields of their outer classes, they can even access local variables! However, those local variables must be declared final.


final int[] counter = new int[1];
for (int i = 0; i < dates.length; i++)
dates[i] = new Date()
{
public int compareTo(Date other)
{
counter[0]++;
return super.compareTo(other);
}
};
The array variable is still declared as final, but that merely means that you can’t have it refer to a different array. You are free to mutate the array elements.
Anonymous Inner Classes
If you want to make only a single object of inner class, you don’t even need to give the class a name. Such a class is called an anonymous inner class.


In general, the syntax is
new SuperType(construction parameters)
{
inner class methods and data
}
SuperType can be an interface, then the inner class implements that interface. Or SuperType can be a class; then, the inner class extends that class.


An anonymous inner class cannot have constructors because the name of a constructor must be the same as the name of a class, and the class has no name. Instead, the construction parameters are given to the superclass constructor.


Anonymous inner class always extend a class or implement an interface, but not both. And if you do implement an interface, you can only implement one.
Static Inner Classes - Nested classes
If you don’t need a connection between the inner-class object and the outerclass object, then you can make the inner class static.


Only inner classes can be declared static. A static inner class is exactly like any other inner class, except that an object of a static inner class does not have a reference to the outer class object that generated it.


A static inner classs is analogous to a static method, it can only access static field and method of outer class, and can not access non-static outer-class fields or methods.
A static inner class can have static fields and methods.
Classes inside interfaces
Normally, you can’t put any code inside an interface, but a nested class can be part of an
interface.


Difference between outer class and Inner class
Outer classes can only be declared public or package private, a nested class can be declared private, public, protected, or package private and static.
Difference with C++ nested class
C++ has nested classes, the nesting is a relationship between classes, not objects.
The Java inner classes have an additional feature that makes them richer and more useful than nested classes in C++. An object that comes from an inner class has an implicit reference to the outer class object that instantiated it. Through this pointer, it gains access to the total state of the outer object.
In Java, static inner classes do not have this added pointer. They are the Java analog to nested classes in C++.


Resources:
Core Java(TM), Volume I--Fundamentals (8th Edition) Ch.6 Interfaces and Inner Classes
Thinking in Java (4th Edition) Ch.12 Thinking in Java (4th Edition)
Nested Classes http://java.sun.com/docs/books/tutorial/java/javaOO/nested.html
http://www.javaworld.com/javaworld/javaqa/2000-03/02-qa-innerclass.html
Types of Inner Class in Java

Algorithm - Numbers


Algorithm - Numbers

Bitwise Manipulation
Bitwise operators include ~(NOT), | (OR), & (AND), and ^ (XOR).
^: If the bits are the same, the result is 0. If the bits are different, the result is 1.
Left shift and right shift operation.

Use & to do modular operation, for instance: int & 0x1F means mod 32.
Optimizing with Shifts
The shift operators enable you to multiply and divide by powers of 2 very quickly.
Swap X and Y
x = x^y; y=x^y; x=x^y;
Number of Ones
Write a function that determines the number of 1 bit in the computer's internal representation of a given integer.
 public static int numOnesInBinary(int number) {  
 int numOnes = 0;  
 while (number != 0) {  
 if ((number & 1) == 1)  
 numOnes++;  
 number = number >>> 1;  
 }  
 return numOnes;  
 }  
This is O(n), where n is the size of bits.
Theory:
Consider what happens at the bit level when you subtract 1 from a number. Subtracting 1 produces a value that has all the same bits as the original integer except that all the low bits up to and including the lowest 1 are flipped.
If you apply the AND operation to the integer and the result of the subtraction, the result is a new number that is the same as the original integer except that the rightmost 1 is now a 0.
 public static int numOnesInBinary(int number) {  
 int numOnes = 0;  
 while (number != 0) {  
 number = number & (number - 1);  
 numOnes++;  
 }  
 return numOnes;  
 }  
This solution has a running time of O(m), where m is the number of 1's in the solution.
Or for integer limited in small bits, we can use space-time tradeoff algorithm, write a array to store the answer - number of one in bits, the complexity of this algorithm is O(1).
For two positive integers A, B(binary-coded), how many bits we have to change in order to convert A to B?
 public static int bitsChangeNeededFromAtoB(int a, int b)  
 {  
 int c = a ^ b;  
 return numOnesInBinary(c);  
 }  
In the decimal representation of N!, how many zeros there are at the end? For example, 10!=3 628 800, so the answer is 2.
This is to find out how many 5s and 2s in the product because a 5 and a 2 makes a 10 where you get a zero per pair. Because the number of 2s is sure to be much greater than that of 5s,this problem is to figure out how many 5s in the numbers from 1 to N.
 public static int numZerosInEndofOfFactoriaN(int n)  
 {  
 int result = 0;  
 int i, j;  
 for(i=1; i&lt;=n; i++)  
 {  
 j=i;  
 while(j%5==0)  
 {  
 result++;  
 j/=5;  
 }  
 }  
 return result;  
 }  
This question can continue to simplify to figure out the number z = [N/5] +[N/(5*5)] +[N/(5*5*5)] + ...
This is because each factor of 5 contributes one zero, and 25's contribute 2 factors of 5, contribute one more factor of 5.
 public static int numZerosInEndofFactoriaN(int n) {  
 int result = 0;  
 while(n>0)  
 {  
 result += n/5;  
 n /=5;  
 }  
 return result;  
 }  
Then in the binary-coded representation of N!, how many zeros there are at the end? For example, 3!= 6 = 1010, so the answer is 1.
This question is same as to figure out how many prime factors of 2 in factorial n.
 A = [N/2] +[N/(2*2)] +[N/(2*2*2)] + ...  
 public static int numZerosInEndOfBinaryofFactoriaN(int n) {  
 int result = 0;  
 while (n > 0) {  
 n >>= 1;  
 result += n;  
 }  
 return result;  
 }  
This tech can be used to find out many prime factors of x in factorial of n.
For a number n, figure out whether it is power of 2.
This is to find out in binary-coded representation of n, whether there are only one bit is 1, and the 1 is not at the last, whether x&(x-1)=0
 public static boolean powerof2(int n) {  
 boolean result = false;  
 if (n > 0) {  
 if ((n & (n - 1)) == 0)  
 result = true;  
 }  
 return result;  
 }  

Q. Determine the number of bits required to convert integer A to integer B.
xor A and B, Each 1 in the xor will represent one different bit between A and B.
Q. Swap odd and even bits in an integer with as few instructions as possible.
 public static int swapOddEvenBits(int x) {   
  return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) );   
 }  
Q. Give two 32-bit numbers, N and M, and two bit positions i and j(i<j), a="" all="" and="" between="" bits="" equal="" i="" in="" j="" m.<="" method="" n="" set="" span="" to="" write="">
1. Clear all bits in N between position i and j
2. ORing to put M in there.
 public static int updateBits(int n, int m, int i, int j) {  
  int max = ~0; /* All 1’s */  
  // 1’s through position j, then 0’s  
  int left = max - ((1 << j) - 1);  
  // 1’s after position i  
  int right = ((1 << i) - 1);   
  // 1’s, with 0s between i and j  
  int mask = left | right;   
  // Clear i through j, then put m in there   
  return (n & mask) | (m << i);   
 }  
Q. Given a decimal number that is passed in as a string, print the binary representation.
 public static String printBinary(String n)  
 {  
   int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));  
   double decPart = Double.parseDouble(n.substring(n.indexOf('.'), n.length()));  
   String int_string = "";  
   while (intPart > 0)  
   {  
     int r = intPart % 2;  
     intPart >>= 1;  
     int_string = r + int_string;  
   }  
   StringBuffer dec_string = new StringBuffer();  
   while (decPart > 0)  
   {  
     if (dec_string.length() > 32) return "ERROR";  
     if (decPart == 1)  
     { dec_string.append((int) decPart); break;}  
     double r = decPart * 2;  
     if (r >= 1)  
     { dec_string.append(1); decPart = r - 1;}  
     else  
     { dec_string.append(0); decPart = r; }  
   }  
   return int_string + "." + dec_string.toString();  
 }  
Q. An array A[1..n] contains all the integers from 0 to n except for one number which is missing. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]". 
Thoery: balance of 1s and 0s in the least signifcant bit.
 int fndMissing(ArrayList<BitInteger> array) {  
  return fndMissing(array, BitInteger.INTEGER_SIZE - 1);  
 }      
 int fndMissing(ArrayList<BitInteger> input, int column) {  
  if (column < 0) { // Base case and error condition  
    return 0;  
   }  
   ArrayList<BitInteger> oddIndices = new ArrayList<BitInteger>();  
  ArrayList<BitInteger> evenIndices = new ArrayList<BitInteger>();  
  for (BitInteger t : input) {  
   if (t.fetch(column) == 0) {  
    evenIndices.add(t);  
   } else {  
    oddIndices.add(t);  
   }  
  }  
  if (oddIndices.size() >= evenIndices.size()) {  
   return (fndMissing(evenIndices, column - 1)) << 1 | 0;  
  } else {  
   return (fndMissing(oddIndices, column - 1)) << 1 | 1;  
  }  
 }  
Q. Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
To get the next number:
1 Traverse from right to left. Once we’ve passed a 1, turn on the next 0.
2 Turn of the one that’s just to the right side of that.
3 Make the number as small as possible by rearranging all the 1s to be as far right as possible.
To get the previous number, we do the reverse:
1   Traverse from right to left. Once we’ve passed a zero, turn of the next 1.
2   Turn on the 0 that is directly to the right.
3   Make the number as big as possible by shifting all the ones as far to the left as possible.
Numbers Related Algorithms Questions
Greatest Common Divisor
 gcd(a,b)=gcd(a-b,b)=gcd(b,a%b)  
 gcd(a,b) = gcd(|a|,|b|)  
 public static long gcd( long a, long b )  
 {  
  if(a<0) a=-a;  
  if(b<0) b=-b;  
  if(a<b)  
  {  
   a=a^b;  
   b=a^b;  
   a=a^a;  
  }  
  return gcdImp(a,b);  
 }  
 private static long gcdImp( long a, long b )  
 {  
   if( b == 0 )  
     return a;  
   else  
     return gcd( b, a % b );  
 }  

Modular arithmetic
1. If A(mod N) = B(mod N), then for any C, (A+C)(mod N) = (B+C)(mod N), (AC)(mod N) = (BC)(mod N), (A^C)(mod N) = (B^C)(mod N).
Compuete the last digit in 3333^5555 = 3333^5555 (mod 10) = (3333 mod 10) ^5555(mod 10) = 3^5555(mod 10)
3^4 mod 10 = 1, so 3^ (4^1388) = 1, so 3^5555(mod 10)= 3^3 mod 10 = 7
Exponentiation - X^N
If N is even, X^N = (X*X)^(N/2) else X^N = X*(X*X)^(N/2).
Based on this, we can compute X^N in O(logN)
Modular Exponentiation - X^N mod p
If N is even, X^N = (X*X mod p)^(N/2) mod p else X^N = {X*[(X*X mod p)^(N/2) mod p]} mod p.
 public static long power(long x, long n, long p)  
 {  
   return doPower(x % p, n, p);  
 }  
 public static long doPower(long x, long n, long p)  
 {  
   if (n == 0) return 1;  
   long tmp = doPower((x * x) % p, n / 2, p);  
   if (n % 2 != 0) tmp = (tmp * x) % p;  
   return tmp;  
 }  
Find Nth fibonacci number in O(logN) time complexity.
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]
To find A^n, we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end.
Numbers are randomly generated and stored into an expanding array.
Q1. How to keep track of the median?
Maintain two heaps, the smallest half is kept in a max heap, contaning the smallest half of the elements, the biggest half is kept in a min heap. With these data structures, you have the potential median elements at the roots. If the heaps are no longer the same size, rebalance the heaps by popping an element of the one heap and pushing it onto the other.
Q2. How to find the kth largest element? (Same as above)

Q. Find out all primes between 1 and n.
 void gen_primes(int max)  
 {  
   int[] primes = new int[max];  
   int i, j;  
   for (i = 0; i < max; i++)  
     primes[i] = 1;  
   for (i = 2; i <= (int) Math.sqrt(max); i++)  
     if (primes[i] == 1) for (j = i; j * i < max; j++)  
       primes[i * j] = 0;  
   // i is prime if primes[i] is still 1.  
 }  
Q. Goldbach's Conjecture:
For any integer n (n 4) there exist two prime numbers p1 and p2 such that p1 + p2 = n. In a problem we might need to find the number of essentially different pairs (p1, p2).
 int FindSol(int n)   
 {   
   int i,res=0;   
   for(i=2;i<=n/2;i++)   
    if (primes[i] && primes[n-i]) res++;   
 }  
Q. Shuffle an array
 public static void shuffleArray(int[] a) {  
   int n = a.length;  
   Random random = new Random();  
   random.nextInt();  
   for (int i = 0; i < n; i++) {  
     int change = i + random.nextInt(n - i);  
     swap(a, i, change);  
   }  
 }  
Key point - int change = i + random.nextInt(n - i); swap(a, i, change);


Endianness
Endianness refers to the order in which a computer stores the bytes of a multibyte value.
In a big-endian machine the MSB has the lowest address; in a little-endian machine the
LSB has the lowest address.
JAVA virtual machine always used big-endian, Intel x86 used little-endian.
Java code to detect os endianness:
 ByteOrder b = ByteOrder.nativeOrder();  
 if(b.equals(ByteOrder.BIG_ENDIAN)) { System.out.println("Big-endian"); }  
 else { System.out.println("Little-endian"); }  
C code:

 bool isLitteEndian(){  
   int  testNum;  
   char *ptr;  
   testNum = 1;  
   ptr = (char *) &testNum;  
   return (*ptr); /* Returns the byte at the lowest address */  
 }  
 bool isLitteEndian(){  
   union {  
     int theInteger;  
     char singleByte;  
   } endianTest;  
   endianTest.theInteger = 1;  
   return endianTest.singleByte;  
 }  

 public final static int swabInt(int v) {  
  return (v >>> 24) | (v << 24) |   
   ((v << 8) & 0x00FF0000) | ((v >> 8) & 0x0000FF00);  
 }  

Resources

Java Serialization Code Examples


Java Serialization Code Examples

Evolving Classes when three are three machines invloved A <---> B <---> C

When java deserialize object, any field of the object that does not appear in the stream is set to its default value. Values that appear in the stream, but not in the object, are discarded.

This works fine in most cases.

But how about there are three machines when serialize and deserialize?

For example, we have a class User, and first in machine A we serialize it and transfer it to machine B, in machine B, we deserialize it and do do some operations then serialize it and transfer it to machine C. in machine C, we deserialize it and do whatever we want.

We will also need to return the object back, C to B, then to A.

A(User) <---> B(User) <---> C(User)


Now, we have to add some new fields - for instance property age - to the Class User.

Imagine that the class version on A is latest, on B old version, on C is newest.

On B, when it deserialize User, and it would discard age property in the stream, then B deserialize it and transfer to C, there would be no field age, so on machine C, Java set age field to default value 0.


In this process, the age value is missing due to the old version on B.


One solution to this problem is to save all fields of the logical state of the

object User in a map, then writeObject writes this map to ObjectOutputStream, readObject get every field value from this map.

public class User implements Serializable {

     private static final long serialVersionUID = 1L;

     private Map fieldsMap = new HashMap();

     private void writeObject(ObjectOutputStream out) throws IOException {

         fieldsMap.put("firstName", firstName);

         fieldsMap.put("age", age);

         out.writeUnshared(fieldsMap);

     }

     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {

         fieldsMap = (HashMap) in.readObject();

         firstName = (String) fieldsMap.remove("firstName");

         age = (Integer) fieldsMap.remove("age");

     }

}


Then if in B, its class definition doesn't include property age, its class looks like below:

public class User implements Serializable {

     private Map fieldsMap = new HashMap();

     private void writeObject(ObjectOutputStream out) throws IOException {

         fieldsMap.put("firstName", firstName);

         out.writeUnshared(fieldsMap);

     }

     private void readObject(ObjectInputStream in) throws IOException,ClassNotFoundException {

         fieldsMap = (HashMap) in.readObject();

         firstName = (String) fieldsMap.remove("firstName");

     }

}


Then in B, it doesn't modify age property in fieldsMap, so when deserialize this object,age property is still in fieldsMap, thus C can restore the original age value.


Changing type of an instance field

For example, we have a Class Inventory:

public class Inventory implements Serializable {

     private static final long serialVersionUID = 1L;

     private String name;

     private int amount;

}

Now we have to promote amount field from int to long in Class Inventory,

and meanwhile we need to ensure class compatibility, that is we must guarantee the new version

of class can deserialize an object saved by the earlier version of the class, and vice verse.


If we simply convert the int type to long, then when use the new version of class to deserialize an object saved by the earlier version, or vice verse, it would throw the following exception:

java.io.InvalidClassException: io.Inventory; incompatible types for field amount


We can use serialPersistentFields, readObject, writeObject to maintain backward compatibility with the serialization format.

public class Inventory implements Serializable {
    private static final long serialVersionUID = 1L;
    private String name;
    private long longAmount;
    private static final ObjectStreamField[] serialPersistentFields = {
            new ObjectStreamField("name", String.class),

            new ObjectStreamField("amount", int.class),
            new ObjectStreamField("longAmount", long.class), };
    private void writeObject(ObjectOutputStream out) throws IOException {
        ObjectOutputStream.PutField fields = out.putFields();
        fields.put("name", name);
        int intAmount;
        if (longAmount > Integer.MAX_VALUE)
            intAmount = Integer.MAX_VALUE;
        else
            intAmount = (int) longAmount;
        // or for short
         // intAmount = (int) ((longAmount > Integer.MAX_VALUE)? Integer.MAX_VALUE:longAmount);
        // For compatibility reason, we need to put the old values first.
        fields.put("amount", intAmount);
        fields.put("longAmount", longAmount);
        out.writeFields();
    }
    private void readObject(ObjectInputStream in) throws IOException,
            ClassNotFoundException {
        ObjectInputStream.GetField fields = in.readFields();
        name = (String) fields.get("name", "");
        // it there is no longAmount in the stream, then it is serialized by
        // older version, and use the int type amount
        if (fields.defaulted("longAmount")) {
            longAmount = fields.get("amount", (int) 0);
        } else {
            // long type - longAmount exists in this stream
            // the "(long)0" is a must, it tells java to read a field
            // named longAmount with a value of type long
            longAmount = fields.get("longAmount", (long) 0);
        }
        // or for short
        // longAmount = fields.defaulted("longAmount") ?
        //       fields.get("amount",(int) 0) : fields.get("longAmount", (long) 0);
    }

We have to run various kinds of tests to ensure class compatibility, first guarantee serialize and deserialize works when in same version, and then serialize an instance in the new release and deserialize it in old releases, and vice versa.


Distinguish default value from no-such-field case
    After add a field to existing class, when deserialize, we need to distinguish the case the response object doesn't include this field at all from that the field has default value.
    In the new class, directly setting the field to invalid value would not work, as when deserialize, If the stream doesn't include one field, Java would directly set the object to its default value, object to null, int to 0, etc.

public class User implements Serializable {
    private static final long serialVersionUID = 1L;
    private String firstName;
    // age field is added later, and need to distinguish its default value 0 from case response doesn't include this field
    // directly assigning age -1 would not work, when deserialize,
    // the stream doesn't include one field, Java would set the object to its default value, object to null, int to 0, etc.
    private int age;
    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        ObjectInputStream.GetField fields = in.readFields();
        firstName = (String) fields.get("firstName","");
        age = fields.defaulted("age") ?
                -1 : fields.get("age", (int) 0);
    }
    // we still need rewrite writeObject
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
    }

}

Miscs

public class SerializationUtils {
    public static Object deserialize(String filename)
            throws FileNotFoundException, IOException, ClassNotFoundException {
        Object object = null;
        FileInputStream fis = null;
        ObjectInputStream in = null;
        fis = new FileInputStream(filename);
        in = new ObjectInputStream(fis);
        object =  in.readObject();
        in.close();
        return object;
    }
    public static void serialize(String filename, Object object)
            throws FileNotFoundException, IOException {
        FileOutputStream fos = null;
        ObjectOutputStream out = null;
        fos = new FileOutputStream(filename);
        out = new ObjectOutputStream(fos);
        out.writeObject(object);
        out.flush();
        out.close();
    }
}

Read/Write object with ByteArrayInputStream/ByteArrayOutputStream

ByteArrayOutputStream bout = new ByteArrayOutputStream();
ObjectOutputStream oout = new ObjectOutputStream(bout);
oout.writeInt(20);
oout.flush();

byte[] bytes = bout.toByteArray();
ByteArrayInputStream bin = new ByteArrayInputStream(bytes);
ObjectInputStream oin = new ObjectInputStream(bin);
System.out.println(oin.readInt());


Resources:

Java I/O 2nd edition - Chapter 13. Object Serialization

Effective Java (2nd Edition) - Chapter 11 Serialization

Java Object Serialization Specification


Notes on Java Serialization


Notes on Java Serialization

Object serialization is the process of saving an object's state to a sequence of bytes, as well as the process of rebuilding those bytes into a live object at some future time.

Writing to an Object Stream

User time = new User();

FileOutputStream fos = null;

ObjectOutputStream out = null;

fos = new FileOutputStream(filename);

out = new ObjectOutputStream(fos);

out.writeObject(time);

out.flush(); out.close();

Reading from an Object Stream

User time = null;

FileInputStream fis = null;

ObjectInputStream in = null;

fis = new FileInputStream(filename);

in = new ObjectInputStream(fis);

time = (User) in.readObject();

in.close();

Implement Serializable judiciously

A major cost of implementing Serializable is that it decreases the flexibility to change a class’s implementation once it has been released.

When a class implements Serializable, its byte-stream encoding (or serialized form) becomes part of its exported API.

A second cost of implementing Serializable is that it increases the likelihood of bugs and security holes.

A third cost of implementing Serializable is that it increases the testing burden associated with releasing a new version of a class. When a serializable class is revised, it is important to check that it is possible to serialize an instance in the new release and deserialize it in old releases, and vice versa.

If a class that is designed for inheritance is not serializable, it may be impossible to write a serializable subclass. Specifically, it will be impossible if the superclass does not provide an accessible parameterless constructor. Therefore, you should consider providing a parameterless constructor on nonserializable classes designed for inheritance.

public abstract class AbstractFoo {}

    // Serializable subclass of nonserializable stateful class - Effective Java - Pages 293-294

    public class Foo extends AbstractFoo implements Serializable {

     private static final long serialVersionUID = 1L;

     private void readObject(ObjectInputStream s) throws IOException,ClassNotFoundException {

         s.defaultReadObject();

         // Manually deserialize and initialize superclass state

         int x = s.readInt();

         int y = s.readInt();

         initialize(x, y);

     }

     private void writeObject(ObjectOutputStream s) throws IOException {

         s.defaultWriteObject();

         // Manually serialize superclass state

         s.writeInt(getX());

         s.writeInt(getY());

     }

}

Inner classes should not implement Serializable. They use compiler-generated synthetic fields to store references to enclosing instances and to store values of local variables from enclosing scopes. How these fields correspond to the class definition is unspecified, as are the names of anonymous and local classes. Therefore, the default serialized form of an inner class is ill-defined. A static member class can, however, implement Serializable.

The Default Mechanism - implements java.io.Serializable interface

Serializable is a marker interface that does not declare any methods or fields, serves purely to indicate that a class may be serialized.

subclasses of a class that implements a particular interface also implement that interface. Thus,

many classes that do not explicitly declare that they implement Serializable are in fact serializable.

Rule #1: The object to be persisted must implement the Serializable interface or inherit that implementation from its object hierarchy

Rule #2: The object to be persisted must mark all nonserializable fields transient

Gotchas - Classes That Implement Serializable but Aren't

Problem 1: References to nonserializable objects

If object is not serializable, or its graph contains objects that do not implement

Serializable, then it would throw java.io.NotSerializableException when try to serialize the object.

Problem 2: Missing a no-argument constructor in superclass

If a superclass of the class is not serializable and does not contain a no-argument constructor, its subclass can not be deserialized.

When an object is deserialized, the no-argument constructor of the closest superclass that does not

implement Serializable is invoked to establish the state of the object's nonserializable superclasses. If that class does not have a no-argument constructor, the object cannot be deserialized.

This kind of class can be serialized, but it is un-deserialized, you can't get the object back again.

It would throws the following exception: java.io.InvalidClassException: no valid constructor

Locating the offending object

The detailMessage field of the

NotSerializableException contains the name of the unserializable class. This can be

retrieved with the getMessage( ) method of java.lang.Throwable or as part of the

string returned by toString( ):

catch (NotSerializableException ex) { System.err.println(ex.getMessage( ) + " could not be serialized");}

Making nonserializable fields transient

Turn serialization off - deliberate throwing of NotSerializableException

Sometimes for security or other reasons, you want to make a class or even a particular object not serializable, but in this case one of its superclasses does already implement Serializable. Since a subclass can't unimplement an interface implemented in its superclass, the subclass may choose to deliberately throw a NotSerializableException when you attempt to serialize it.

private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException { throw new NotSerializableException();}

private void writeObject(ObjectOutputStream ois) throws IOException { throw new NotSerializableException(); }

Versioning - SUIDs -Compatible and Incompatible Changes

To help identify compatible or incompatible classes, each serializable class has a stream unique identifier, SUID for short. When Java deserializes an object, it compares the SUID of the class found in the stream to the SUID of the class with the same name in the local classpath. If they match, Java assumes the two versions of the class are compatible., otherwise, it throws java.io.InvalidClassException: local class incompatible

By default, the SUID is calculated by hashing together all the pieces of a class's interface: the signature of the class, the signatures of the nonprivate methods in the class, the signatures of the fields, and so on. If any of these change, the SUID changes. By default, this is fairly strict. Even compatible changes that don't affect the serialized format such as adding a public method can prevent a serialized object from being deserialized against the newer version of the class.

Sometimes a normally incompatible change can be made compatible. For instance, if you add a new int field to a class, it may be OK for deserialization of old instances of that class to just set the field to 0. If you remove a field from a class, it may be OK for deserialization of old instances to ignore the value stored for that field. Java will do this, but only if the SUIDs of the two versions of the class match.

To tell Java that it's OK to ignore removed fields and use default values for added fields, as well as telling it that other changes don't matter, you can specify the SUID for a class rather than allow it to be calculated automatically.

private static final long serialVersionUID = 1;

However now it is your responsibility to make sure that the old and new versions of the class are indeed compatible. If you can't maintain forward and backward compatibility with the serialization format, you must change the serialVersionUID field to stop Java from deserializing old instances into the new class version and vice versa.

The serialver tool, included with the JDK, calculates an SUID that fits the class: % serialver User

You do not have to use the SUID values that serialver calculates. You can use your own version-numbering scheme. The simplest such scheme would be to give the first version of the class SUID 1, the next incompatible version SUID 2, and so forth.

Consider using a custom serialized form

Do not accept the default serialized form without first considering whether it is appropriate.

The default serialized form is likely to be appropriate if an object’s physical representation is identical to its logical content.

Even if you decide that the default serialized form is appropriate, you often must provide a readObject method to ensure invariants and security.

public final class StringList implements Serializable {

    private static final long serialVersionUID = 1L;

     private transient int size = 0;

     private transient Entry head = null;

     // No longer Serializable!

     private static class Entry {

         String data;

         Entry next;

         Entry previous; }

     private void writeObject(ObjectOutputStream s) throws IOException {

         s.defaultWriteObject();

         s.writeInt(size);

         // Write out all elements in the proper order.

         for (Entry e = head; e != null; e = e.next)

         s.writeObject(e.data);

     }

     private void readObject(ObjectInputStream s) throws IOException,ClassNotFoundException {

         s.defaultReadObject();

         int numElements = s.readInt();

         // Read in all elements and insert them in list

         for (int i = 0; i < numElements; i++)

         add((String) s.readObject());

     }

}

Note that the first thing writeObject does is to invoke defaultWriteObject, and the first thing readObject does is to invoke defaultReadObject.

Every instance field that can be made transient should be made so. This includes redundant fields, whose values can be computed from “primary data fields,” such as a cached hash value. Before deciding to make a field nontransient, convince yourself that its value is part of the logical state of the object.

If you are using the default serialized form and you have labeled one or more fields transient, remember that these fields will be initialized to their default values when an instance is deserialized, If these values are unacceptable for any transient fields, you must provide a readObject method that invokes the defaultReadObject method and then restores transient fields to acceptable values. Alternatively, these fields can be lazily initialized the first time they are used.

Regardless of what serialized form you choose, declare an explicit serial version UID in every serializable class you write. This eliminates the serial version UID as a potential source of incompatibility . There is also a small performance benefit. If no serial version UID is provided, an expensive computation is required to generate one at runtime.

private static final long serialVersionUID = randomLongValue ;

If you write a new class, it doesn’t matter what value you choose for randomLongValue. You can generate the value by running the serialver utility on the class, but it’s also fine to pick a number out of thin air. If you modify an existing class that lacks a serial version UID, and you want the new version to accept existing serialized instances, you must use the value that was automatically generated for the old version. You can get this number by running the serialver utility on the old version of the class—the one for which serialized instances exist.

If you ever want to make a new version of a class that is incompatible with existing versions, merely change the value in the serial version UID declaration. This will cause attempts to deserialize serialized instances of previous versions to fail with an InvalidClassException.

Customizing the Serialization Format - readObject and writeObject

The simplest way to customize serialization is to declare certain fields transient. The values

of transient fields are not written onto the underlying output stream when an object in the

class is serialized.

The ObjectInputStream Class

The ObjectInputStream constructor calls readStreamHeader to read and verifies the header and version written by the corresponding ObjectOutputStream.writeStreamHeader method. The ObjectInputStream constructor blocks until it completes reading the serialization stream header. Code which waits for an ObjectInputStream to be constructed before creating the corresponding ObjectOutputStream for that stream will deadlock, since the ObjectInputStream constructor will block until a header is written to the stream, and the header will not be written to the stream until the ObjectOutputStream constructor executes.

This problem can be resolved by creating the ObjectOutputStream before the ObjectInputStream.

The defaultReadObject method is used to read the fields and object from the stream. Any field of the object that does not appear in the stream is set to its default value. Values that appear in the stream, but not in the object, are discarded.

This occurs primarily when a later version of a class has written additional fields that do not occur in the earlier version.

The readObject Method

Reading an object from the ObjectInputStream is analogous to creating a new object. Just as a new object's constructors are invoked in the order from the superclass to the subclass, an object being read from a stream is deserialized from superclass to subclass.

As constructors, calling an overridable method from within a readObject or readObjectNoData method may result in the unintentional invocation of a subclass method before the superclass has been fully initialized.

Write readObject methods defensively

Loosely speaking, readObject is a constructor that takes a byte stream as its sole parameter, Problem arises when readObject is presented with a byte stream that is artificially constructed to generate an object that violates the invariants of its class. so in readObject method, we must ensure class invariants, immutablity and security.

When an object is deserialized, it is critical to defensively copy any field containing an object reference that a client must not possess.

// Immutable class that uses defensive copying - Effective Java - Page 302

public final class Period implements Serializable {

     private static final long serialVersionUID = 1L;

     private Date start;

     private Date end;

     public Period(Date start, Date end) {

         this.start = new Date(start.getTime());

         this.end = new Date(end.getTime());

         checkInvariant(start, end);

     }

     public Date start() { return new Date(start.getTime()); }

     public Date end() { return new Date(end.getTime()); }

     // readObject method with defensive copying and validity checking - Page 306

     // This will defend against BogusPeriod and MutablePeriod attacks.

     private void readObject(ObjectInputStream s) throws IOException,ClassNotFoundException {

         s.defaultReadObject();

         // Defensively copy our mutable components

         start = new Date(start.getTime());

         end = new Date(end.getTime());

         checkInvariant(start, end);

     }

    // Check that our invariants are satisfied
    private void checkInvariant(Date start, Date end) throws InvalidObjectException {
        if (start.compareTo(end) > 0)
            throw new InvalidObjectException(start + " after " + end);
    }

}

Guidelines for writing a bulletproof readObject method:

• For classes with object reference fields that must remain private, defensively copy each object in such a field. Mutable components of immutable classes fall into this category.

• Check any invariants and throw an InvalidObjectException if a check fails. The checks should follow any defensive copying.

• If an entire object graph must be validated after it is deserialized, use the ObjectInputValidation interfac.

• Do not invoke any overridable methods in the class, directly or indirectly.

Item 78: Consider serialization proxies instead of serialized instances

The serialization proxy pattern is reasonably straightforward. First, design a private static nested class of the serializable class that concisely represents the logical state of an instance of the enclosing class. This nested class, known as the serialization proxy, should have a single constructor, whose parameter type is the enclosing class. This constructor merely copies the data from its argument: it need not do any consistency checking or defensive copying. By design, the default serialized form of the serialization proxy is the perfect serialized form of the enclosing class. Both the enclosing class and its serialization proxy must be declared to implement Serializable.

public final class Period implements Serializable {

     // Serialization proxy for Period class - page 312

     private static class SerializationProxy implements Serializable {

     private final Date start;

     private final Date end;

     SerializationProxy(Period p) {

         this.start = p.start;

     this.end = p.end;

     }

     // The presence of readResolve method causes the serialization system to translate the serialization proxy back

     // into an instance of the enclosing class upon deserialization.

     private Object readResolve() {

         return new Period(start, end); // Uses public constructor

         }

     }

     // The presence of this method causes the serialization system to emit a Serializa-

     // tionProxy instance instead of an instance of the enclosing class.

     private Object writeReplace() {

         return new SerializationProxy(this);

     }

     // With this writeReplace method in place, the serialization system will never

     // generate a serialized instance of the enclosing class, but an attacker might

     // fabricate one in an attempt to violate the class's invariants. To guarantee that such an

     // attack would fail, merely add this readObject method to the enclosing class:

     private void readObject(ObjectInputStream stream) throws InvalidObjectException {

     throw new InvalidObjectException("Proxy required");

     }

}

The defaultWriteObject() and defaultReadObject( ) Methods

Sometimes rather than changing the format of an object that's serialized, all you want to do is add some additional information, perhaps something that isn't normally serialized, like a static field. In this case, you can use ObjectOutputStream's defaultWriteObject( ) method to write the state of the object and then use ObjectInputStream's defaultReadObject ( ) method to read the state of the object. After this is done, you can perform any custom work you need to do on serialization or deserialization.

private void readObject(ObjectInputStream in)

throws IOException, ClassNotFoundException {

in.defaultReadObject( );

if (face < 1 || face > 6) { throw new InvalidObjectException("Illegal die value: " + this.face); }

}

The writeReplace Method

The writeReplace method allows a class of an object to nominate its own replacement in the stream before the object is written. By implementing the writeReplace method, a class can directly control the types and instances of its own instances being serialized.

The object returned should be either of the same type as the object passed in or an object that when read and resolved will result in an object of a type that is compatible with all references to the object.

The readResolve Method

For Serializable and Externalizable classes, the readResolve method allows a class to replace/resolve the object for the one created by readObject before it is returned to the caller.

ObjectInputStream checks whether the class of the object defines the readResolve method. If the method is defined, the readResolve method is called to allow the object in the stream to designate the object to be returned.

The object returned should be of a type that is compatible with all uses. If it is not compatible, a ClassCastException will be thrown when the type mismatch is discovered.

The accessibility of readResolve is significant.

If you depend on readResolve for instance control, all instance fields with object reference types must be declared transient. Otherwise, it is possible for a determined attacker to secure a reference to the deserialized object before its readResolve method is run.

// Serializable Singleton Class - Effective Java - Page 309

public class Elvis implements Serializable {

public static final Elvis INSTANCE = new Elvis();

private Elvis() { }

private Object readResolve() throws ObjectStreamException { return INSTANCE; }

}

Defining Serializable Fields for a Class - serialPersistentFields

The serializable fields of a class can be defined two different ways. Default serializable fields of a class are defined to be the non-transient and non-static fields, or we can explicitly specify which fields should and should not be serialized by listing them in a serialPersistentFields array in a private static field in the class. If such a field is present, only fields included in the array are serialized. All others are treated as if they were transient. In other words, transient marks fields not to serialize while serialPersistentFields marks fields to serialize.

The next trick is to use serialPersistentFields to declare fields that don't actually exist in the class. The writeObject( ) method then writes these phantom fields, and the readObject( ) method reads them back in. Typically this is done to maintain backward compatibility with old serialized versions after the implementation has changed. It's also important when different clients may have different versions of the library.

The advantage to using serialPersistentFields instead of merely customizing the readObject( ) and writeObject( ) methods is versioning. A class can be both forward and backward compatible as long as the SUIDs are the same, even if the old version did not have custom readObject( ) and writeObject( ) methods.

private static final ObjectStreamField[] serialPersistentFields = {

new ObjectStreamField("x", double.class),

new ObjectStreamField("y", double.class), };

private void writeObject(ObjectOutputStream out) throws IOException {

     // Convert to Cartesian coordinates

     ObjectOutputStream.PutField fields = out.putFields( );

     fields.put("x", radius * Math.cos(angle));

     fields.put("y", radius * Math.sin(angle));

     out.writeFields( );

}

private void readObject(ObjectInputStream in) throws ClassNotFoundException, IOException {

     ObjectInputStream.GetField fields = in.readFields( );

     double x = fields.get("x", 0.0);

     double y = fields.get("y", 0.0);

     // Convert to polar coordinates

     radius = Math.sqrt(x*x + y*y);

     angle = Math.atan2(y, x);

}

Serializable vs Externalizable

Sometimes customization requires you to manipulate the values stored for the superclass of an object as well as for the object's class. In these cases, you should implement the java.io.Externalizable interface instead of Serializable. Externalizable is a subinterface of Serializable:

public interface Externalizable extends Serializable

This interface declares two methods, readExternal( ) and writeExternal( ):

public void writeExternal(ObjectOutput out) throws IOException

public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException

The implementation of these methods is completely responsible for saving the object's state, including the state stored in its superclasses. This is the primary difference between implementing Externalizable and providing private readObject( ) and writeObject( ) methods.

Furthermore, externalizable objects are responsible for tracking their own versions; the virtual machine assumes that whatever version of the externalizable class is available when the object is deserialized is the correct one. It does not check the serialVersionUID field as it does for merely serializable objects. If you want to check for different versions of the class, you must write your own code to do the checks.

For client, there is no difference whether a class implements Serializable or Externalizable interface.

Validation

Most obviously, you may need to check the class invariants on an object you deserialize.

The registerValidation method can be called to request a callback when the entire graph has been restored but before the object is returned to the originalcaller of readObject. The order of validate callbacks can be controlled using the priority. Callbacks registered with higher values are called before those with lower values.

public class Person implements Serializable, ObjectInputValidation {

    static Map thePeople = new HashMap( );

    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {

        in.registerValidation(this, 5);

         in.defaultReadObject( ); }

    public void validateObject( ) throws InvalidObjectException {

         if (thePeople.containsKey(this.ss)) { throw new InvalidObjectException(this.name + " already exists"); }

         else { thePeople.put(this.ss, this.name); }

     }

}


Frequently Asked Questions Object Serialization

# If class A does not implement Serializable but a subclass B implements Serializable, will the fields of class A be serialized when B is serialized?
Only the fields of Serializable objects are written out and restored. The object may be restored only if it has a no-arg constructor that will initialize the fields of non-serializable supertypes. If the subclass has access to the state of the superclass it can implement writeObject and readObject to save and restore that state.

# Why is OutOfMemoryError thrown after writing a large number of objects into an ObjectOutputStream?
The ObjectOutputStream maintains a table mapping objects written into the stream to a handle. The first time an object is written to a stream, its contents are written into the stream; subsequent writes of the object result in a handle to the object being written into the stream. This table maintains references to objects that might otherwise be unreachable by an application, thus, resulting in an unexpected situation of running out of memory. A call to the ObjectOutputStream.reset() method resets the object/handle table to its initial state, allowing all previously written objects to be elgible for garbage collection. See handle.



Resources:

Java I/O 2nd edition - Chapter 13. Object Serialization

Effective Java (2nd Edition) - Chapter 11 Serialization

Java Object Serialization Specification

Discover the secrets of the Java Serialization API

Advanced Serialization

What are the writeReplace() and readResolve() methods used for?

Frequently Asked Questions Object Serialization

Selenium Examples


Selenium Examples

Today, one of my friends wanted to query his GCT(Graduate Candidate Test) scores,
and he knew his ID number, but he forgot his Admission Form No., it is easy to find out the first 11 digits assigned to his school,
but he just knew the range of last four digits, so he asked me to help to figure it out.

The first thought is to write a program and use HttpURLConnection to submit form and analyze response,
but it failed for some reason, and don't want the friend to wait for a long time, so I gave up my
first idea, and resort to Selenium.

1: start selenium server:
Download Selenium RC.
cd selenium-remote-control-1.0.1-dist\selenium-server-1.0.1
java -jar selenium-server.jar (to run the server in interactive mode execute java -jar selenium-server.jar -interactive)

2: Then write the following code:
import com.thoughtworks.selenium.SeleneseTestCase;
public class Scores extends SeleneseTestCase {
    public void setUp() throws Exception {
        setUp("http://**.edu.cn/", "*");
    }

    public void testScores() throws Exception {
        String idNo = "*******************";
        String admFormNoPrefix = "************";
        int admFormNoUnknownPartStart = 1000, admFormNoUnknownPartEnd = 3000;
        boolean notMatch = true;
        selenium.setTimeout("300000");
        for (int i = admFormNoUnknownPartStart; i < admFormNoUnknownPartEnd; i++) {
            selenium.open("/graduate/**.htm");
            selenium.type("zjhm", idNo);
            selenium.type("ksbh", admFormNoPrefix + i);
            selenium.click("B1");
            selenium.waitForPageToLoad("10000");
            notMatch = selenium.isTextPresent("Id No. and Admission Form No. don't match.");
            if (!notMatch) {
                System.out.println("Admission Form No.= " + admFormNoPrefix + i);
            }
            assertTrue(notMatch);
        }
    }
}
Then Run it as JUnit Test.
At last, problem resolved, and thanks, Selenium :)

Resources:
http://blog.taragana.com/index.php/archive/5-minute-guide-to-selenium-ide-and-selenium-rc-test-tools/
http://blog.taragana.com/index.php/archive/9-important-tips-for-selenium-remote-control-java-client-test-tool/

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)