Monday 21 December 2015

Design a data structure that supports insert, delete, search and get random in constant time

Perform Insert/Delete/Search/Get Random operations in O(1)

No predefined data structure that satisfies all these requirements.
Insertion supported by most of data structure but Deletion and Get Random supported by few of Data structure.
To perform all operation in constant time, we have to use Hybrid of 2 or more data structures.

1. O(1) Insert
Stacks/Queues/Linked lists and hash tables support this operation, here BST, heap, Skip list, TRIE etc. are eliminated.

2. O(1) delete
Question doesn't clearly specify delete what? First element, last element or any element?
If we have to delete first element than we go for queues, if we have to delete last element we select stack, if we have to delete any element then we opt for hash.
So contenders in the list till now are - stack/Queues and Hash table.

3. O(1) search
At this step both stacks and queues are ruled out as search is not possible in O(1) and only hash table remains in the list. So at this step we are clear that one of the data structure should be hash table.

4. O(1) Get Random
Hash fails to fulfill this requirement, hash requires key to fetch any element and we have no way of generating random keys.

Which data structure satisfies O(1) random access?
There is only one Arrays.
Just give index + starting address and boom array gives you the result in O(1).



import java.util.*;
class FastestDS {

      // A resizable array used to get Random element at runtime
      ArrayList<Integer> array;

      // A hash where keys are array elements and values are indexes in arr[]
      HashMap<Integer, Integer>  hashMap;

      // Constructor (creates arr[] and hash)
      public FastestDS() {
            array = new ArrayList<Integer>();
            hashMap = new HashMap<Integer, Integer>();
      }

      // A Theta(1) function to add an element to FastestDS data structure
      void add(int x) {
            // If element is already present, then noting to do
            if (hashMap.get(x) != null) {
                  return;
            }

            // Else put element at the end of arr[]
            int s = array.size();
            array.add(x);

            // And put in hash also
            hashMap.put(x, s);
      }

      // A Theta(1) function to remove an element from FastestDS data structure
      void remove(int x) {
            // Check if element is present
            Integer index = hashMap.get(x);
            if (index == null) {
                  return;
            }
            // If present, then remove element from hash
            hashMap.remove(x);

            // Swap element with last element so that remove from
            // arr[] can be done in O(1) time
            int size = array.size();
            Integer last = array.get(size-1);
            Collections.swap(array, index,  size-1);

            // Remove last element (This is O(1))
            array.remove(size-1);

            // Update hash table for new index of last element
            hashMap.put(last, index);
      }

      // Returns a random element from FastestDS
      int getRandom() {
            // Find a random index from 0 to size - 1
            Random rand = new Random();
            int index = rand.nextInt(array.size());

            // Return element at randomly picked index
            return array.get(index);
      }

      // Returns index of element if element is present, otherwise null
      boolean contains(int x) {
            return hashMap.get(x)!=null?true:false;
      }
}

Sunday 13 December 2015

Generate serialVersionUID using Java Program

serialVersionUID can be generated by using getSerialVersionUID() method of the ObjectStreamClass class.

SerialiazedClass.java
package com.serial;
import java.io.Serializable;

class SerialiazedClass implements Serializable {
     String name;
     public void setName(String name) {
           this.name = name;
     }
}

GenerateSerialVerUID.java

import java.io.ObjectStreamClass;
public class GenerateSerialVerUID {
    
     public static void main(String[] args) {
          
           Class hashClass = SerialiazedClass.class;
          
           ObjectStreamClass osc = ObjectStreamClass.lookup(hashClass);
           long serialID = osc.getSerialVersionUID();

           System.out.println(serialID);
     }
}
Output:
1623809446810541828

Saturday 12 December 2015

How to generate serialVersionUID in Java?

Generate serialVersionUID of Employee class

import java.io.Serializable;
public class Employee implements Serializable {
     private String name;
     public Employee(String name) {
           this.name = name;
     }
     public String getName() {
           return name;
     }
}

1. serialver command
JDK has a build in command called “serialver” to generate the serialVersionUID automatically.


C:\Users\awadh\Desktop>javac Employee.java
C:\Users\awadh\Desktop>serialver Employee
Employee:  private static final long serialVersionUID = -6607742892470200720L;




2. serialver tool


Run command: serialver –show
C:\Users\awadh\Desktop>serialver -show
Put the class description in the tool and click on the show button.
private static final long serialVersionUID = -6607742892470200720L;



3. Using Eclipse IDE

Friday 11 December 2015

Why SerialVersionUID is static?


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 is 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.

The serialVersionUID determines compatibility between different versions of a class. Since the property is bound to the class, it has to be made static.


static variables are not serialized with the object.

However, serialVersionUID is a must in serialization process.


When an object is serialized, the serialVersionUID is serialized along with the other contents. This is one exception to the general serialization rule that, “static fields are not serialized”.

References:
http://docs.oracle.com/javase/6/docs/platform/serialization/spec/class.html#4100

Need externalizable when we already have serializable

When you serialize any object using serializable, apart from fields, all objects that belong to object map and that can be reached using instance variable will also be serialized.

For example:
  • If you have Employee class and its superclass is the person then it will serialize all superclass objects (such as the person) until it reaches "Object" class.
  • Similarly, if Employee has an instance variable of address class then it will serialize whole object map of address also.

Do you really want this much overhead when all you want to serialize is empId and empName.


JVM uses reflection when you use serializable which is quite slow.

While serializing, information about class description which includes the description of its superclass and instance variable associated with that class also get stored in the stream. Again this is also a performance issue.

Thursday 10 December 2015

What is the problem if I synchronized only setters to make an object Thread-safe?

Scenario

Make setters synchronized only

public class ThreadSafeObject {
    private int value;

    public int getValue() {
        return value;
    }
    public synchronized void setValue(int value) {
        this.value = value;
    }
}

Changes to the object may not be visible to any reading thread, because JVM will not ensure that the reading thread's memory (like, cache) is in sync with the writing thread.

So, reader thread may still get out-of-date (older) values from its thread's cache than new value set by writing thread.

Solution

1.Make getters and setters both synchronized: No dirty read

When getters are synchronized, there will be lock on the object which will not allow other threads to modify the object state.
And synchronized also help to read the object from Main memory (not from cache) i.e NO DIRTY READ.

2.Use volatile keyword to ensure that the value has been read from Main memory.
Related Posts Plugin for WordPress, Blogger...