Space Complexity

Space Complexity:

Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Space complexity includes both Auxiliary space and space used by input.

Space complexity = Auxiliary space + space used by input

For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be better criteria than Space Complexity.

Merge Sort uses O(n) auxiliary space (extra space), Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.

Hash, Hashing, Hashtable

Hash/hash value can be used to uniquely identify secret information. This requires that the hash function is collision resistant, which means that it is very hard to find data that generate the same hash value.

Hash function is any function that can be used to map data of arbitrary size to data of fixed size. The values returned by a hash function are called hash values/hash codes/ hashes.

Hash functions accelerate table or database lookup by detecting duplicated records in a large file.

                             

                                  

Majorly used hash function: Division

The hash function is:  f_D (x) = x % M   This gives bucket address that range from 0 to M-1, where M = the table size.

Hashing

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection.

Loading density

The identifier density of a hash table is the ratio n/T, where n is the number of identifiers in the table.  The loading density or loading factor of a hash table is a=n /(sb).

Collision:

When hash function generates same hash for two different values is known as collision. Because when be store the data in bucket than there will be more than one value in bucket.

Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.

                    

stepSize = probes.

newLocation = (startingValue + stepSize) % arraySize

Linear probing function (H(x, i)):

H(x, i) = (H(x) + i) (mod n), Here ordinary hash function H(x).

Here H(x) is the starting value, n the size of the hash table, and the stepsize is i in this case.

Often, the step size is one; that is, the array cells that are probed are consecutive in the hash table. Double hashing is a variant of the same method in which the step size is itself computed by a hash function.

Chained Hashing/Chaining

Instead of storing the data item directly in the hashtable, each hashtable entry contains a reference to a datastructure, e.g. a linked list (chain), or a balanced search tree. We compute the hash value  v of the data item d and then store d in the data structure referred to from the hashtable entry  at index  v.

Chaining using linked list:

                      

                                  

Hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket. Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

                             

	Average	Worst case
Space	O(n)	O(n)
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

Runtime.getRuntime().gc() and System.gc()

Garbage Collection in Java is carried by a daemon thread called Garbage Collector. Before removing an object from memory garbage collection thread invokes finalize() method of that object and gives an opportunity to perform required cleanups.

We cannot force garbage collection in Java. It will only trigger if JVM thinks it needs a garbage collection based on Java heap size.

System.gc() and Runtime.gc() are the methods which can be used to send request of Garbage collection to JVM but it’s not guaranteed that garbage collection will happen.

Runtime.gc()

void java.lang.Runtime.gc()

Calling this method suggests that the JVM expend effort toward recycling unused objects in order to make the memory they currently occupy available for quick reuse. When control returns from the method call, the JVM has made its best effort to recycle all discarded objects.

The virtual machine performs this recycling process automatically as needed, in a separate thread, even if the gc() method is not invoked explicitly.

The method System.gc() is the conventional and convenient means of invoking this method.

public native void gc();

How to call Runtime.gc()?

Runtime.getRuntime().gc();

Runtime is Singleton Class and getRuntime() returns the instance of this class.

System.gc()

void java.lang.System.gc()

Calling of System.gc() is effectively equivalent to call Runtime.getRuntime().gc();

System.gc() implementation

public static void gc() {

Runtime.getRuntime().gc();

}

System.gc() internally calls the  Runtime.gc().

We don't need to call garbage collection (calling System.gc()) manually because in most circumstances it is harmful for application performance.

When should use System.gc()?

If the application knows it is going into a phase where it has nothing else to do AND the user is unlikely to notice a garbage collection, then maybe it is OK call to System.gc() in an effort to stop the user experiencing GC pauses in the future.

The downsides include:

Calling System.gc() typically triggers a full GC which takes significantly longer than a GC of the 'new space'.

By forcing the GC, you are causing the JVM to use extra CPU cycles, etc. which may potentially interfere with other things that the user is doing on his machine.

Template Method Pattern

Template method defines the steps to execute an algorithm and it can provide default implementation that might be common for all or some of the subclasses.

package oops.design.patterns.template;

public abstract class InterviewProcess {

       abstract void written();

       abstract void technical();

       abstract void manager();

       abstract void hrRounds();

       // Template method - Sequence of processes.

       public final void judgeCandidate() {

              written();

              technical();

              manager();

              hrRounds();

       }

}

package oops.design.patterns.template;

public class OrangeInterview extends InterviewProcess {

       @Override

       void written() {

              System.out.println("written : Orange!");

       }

       @Override

       void technical() {

              System.out.println("technical : Orange!");

       }

       @Override

       void manager() {

              System.out.println("manager : Orange!");

       }

       @Override

       void hrRounds() {

              System.out.println("hr rounds : Orange!");

       }

}

package oops.design.patterns.template;

public class ExpediaInterview extends InterviewProcess {

       @Override

       void written() {

              System.out.println("written : Expedia!");

       }

       @Override

       void technical() {

              System.out.println("technical : Expedia!");

       }

       @Override

       void manager() {

              System.out.println("manager : Expedia!");

       }

       @Override

       void hrRounds() {

              System.out.println("hr rounds : Expedia!");

       }

}

package oops.design.patterns.template;

public class TestCandidate {

       public static void main(String[] args) {

              InterviewProcess orangeInterview = new OrangeInterview();

              orangeInterview.judgeCandidate();

             

              System.out.println("\n");

             

              InterviewProcess expediaInterview = new ExpediaInterview();

              expediaInterview.judgeCandidate();

       }

}

Output:

written : Orange!

technical : Orange!

manager : Orange!

hr rounds : Orange!

written : Expedia!

technical : Expedia!

manager : Expedia!

hr rounds : Expedia!

                                         

Template Method Pattern in JDK

1.All non-abstract methods of java.io.InputStream, java.io.OutputStream, java.io.Reader and java.io.Writer.

2.All non-abstract methods of java.util.AbstractList, java.util.AbstractSet and java.util.AbstractMap.

Things to remember

1.Template method should be final.

2.Template method should consist of certain steps whose order is fixed and for some of the methods; implementation differs from base class to subclass.

3.Most of the times, subclasses calls methods from super class however in template pattern, superclass template method calls methods from subclasses.