Data Structure questions for Java developer

'Data Structure questions' or 'Java Algorithm questions' is covered in this topic. These questions are always asked by interviewer if they are from CS background. This is very useful to understand java collection sorting and searching algorithm so that we can use correct collection type in our application. It help us to understand how indexes work in database and how the data retrievals become so fast due to B Tree data structure.

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Example -- 8 6 7
Compare 8 and 6 and re arrange to 6,8,7
Next number compare 8 and 7 and rearrange 6,7,8
This process continues till there is no swaping
Output : 6,7,8

Average : n^2 and 

worst case  n lon(n)

Quick Sort: Pivot

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.

2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3.  Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Average:  n log n

Worst : n^2

Merge Sort

a merge sort works as follows

1.   Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2.   Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

Example 4 8 9 0

Devide till single element :   4  ||  8 ||  9  || 0

Group into 2 :                        4 8  ||  0  9

Merge these 2 list :             0 4 8 9

Avg case :  n ( log n )

Worst case: n long (n)

Binary Search tree:

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

· The left subtree of a node contains only nodes with keys less than the node's key.

· The right subtree of a node contains only nodes with keys greater than the node's key.

· Both the left and right subtrees must also be binary search trees.

· There must be no duplicate nodes.

Best case :  O (1)
Avg case : O (log n )

Worst case : O (log n)

SkipList:

  A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in lists.A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. 

         If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/p, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total expected cost of a search is which is when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.

                           

Java Cache : Static data loading

Application performance highly depends on how the data is loaded into memory and how it is reused during application processing. If our application does database query for each static \client data which is rarely changing then we need to consider putting this static data in memory\cache. The application performance increase drastically if we reuse this static data from memory. In the market we have lots of open source cache implementation available like ehCache, osCache[Terracota], Guava library etc. In some cases these open source implementation can be more complicated compare to application requirement. After java 1.5 concurrent collections it is become very handy to write own cache. In static data cache we always want to control memory foot print and we use LRU [ Least recently Used] idiom to do this. We fix the size of cache and clear the oldest cache data if the cache needs to be refreshed behind its size. Here is example of LRU cache which is backed by ConcurrentHashMap and controlled by ConcurrentLinkedQueue.

Cache simply means loading the data by some key and it should be in memory. If we are running our application in clustered mode then available implémentation is Coherence which can isolated interaction with DB and provided fail over and syncronization between multiple application cache.

Here is example how we can build LRU cache in java using concurrent package. This implementation will be fragile and blocking if we would have implemented cache using old synchronize idiom. Cache data is backed up by ConcurrentHashMap so that reading from cache is not blocked and writing to cache will have concurrent effect, it means only the buckets will be locked during write operation.

Caching Implementation without concurrency using wait() and notify()

Java 1.7 features

'Java latest changes' or' 'Java 1.7 changes' are covered in this topic. Java 1.7 [ Dolphin] is major update after java 1.5 tiger release. It is done on 2011-07-28 after around 5 years of java release 1.6 [Mustang]. These are major changes in java 1.7 release and most important is definitely 'Auto closeable' of resources.

1) Autocloseable Try Statement defining Resources – Java 1.7 introduces all new try-with-resources statement using which declaration and initialization of one or more resources can happen. But only the resources that implement the interface “java.lang.AutoCloseable” can be declared. Example:

      try (BufferedReader bufferedReader = new BufferedReader( FileReader(path)))

         {             return bufferedReader.readLine();  

         }

  In this code snippet, sampleBufferedReader instance is created within the try statement. Note that the example does not include a finally block that contains a code to close sampleBufferedReader as in Java 1.6 or earlier versions. Java 1.7 automatically closes the resources that are instantiated within the try-with-resources statement as shown above.

2) Catch Block Handling Multiple Exceptions – In Java 1.5 and Java 1.6, a catch block can handle only one type of exception. But in Java 1.7 and later versions, a single catch block can handle multiple exceptions. Here is an example showing catch blocks in Java 1.6:

     try {    }

      catch(SQLException exp1)

      {     throw exp1;    }

       catch(IOException exp2)

       {    throw exp2;   }

The same code snippet can be modified in Java 1.7 as:

      try  {….      }

      catch(SQLException | IOException |ArrayIndexOutofBoundsException exp1)

      {     throw exp1;   }

3) String Object as Expression in Switch Statement – So far only integral types are used as expressions in switch statement. But Java 1.7 permits usage of String object as a valid expression. Example:

   example:           

                            case "CASE1":

                                     System.out.println(“CASE1”);

                                     break;

4) JDBC in Java 1.7

JDBC contained in Java 1.7 / Java SE 7 is JDBC 4.1 that is newly getting introduced. JDBC 4.1 is more efficient when compared to JDBC 4.0.

5) Language Enhancements in JDBC 1.7

Java 1.7 introduces many language enhancements:

  Integral Types as Binary Literals – In Java 1.7 / Java SE 7, the integral types namely byte, short, int and long can also be expressed with the binary number system. To specify these integral types as binary literals, add the prefix 0B or 0b to number. For example, here is a byte literal represented as 8-bit binary number:

     byte sampleByte = (byte)0b01001101;

   

  Underscores Between Digits in Numeric Literal – In Java 1.7 and all later versions, “_” can be used in-between digits in any numeric literal. “_” can be used to group the digits similar to what “,” does when a bigger number is specified. But “_” can be specified only between digits and not in the beginning or end of the number. Example:

long NUMBER = 444_67_3459L;

In this example, the switch expression contains a string called sampleString.  The value of this string is matched with every case label and when the string content matches with case label then the corresponding case gets executed. 

  Automatic Type Inference during the Generic Instance Creation – In Java 1.7 while creating a generic instance, empty parameters namely <> can be specified instead of specifying the exact type arguments. However, this is permitted only in cases where the compiler can infer the appropriate type arguments. For example, in Java 1.7 you can specify:

      sampleMap = new HashMap<>();

Thus HashMap<> can be specified instead of HashMap>;. This <>; empty parameters of Java 1.7 are named as diamond operator.

6) Suppress Warnings - When declaring varargs method that includes parameterized types, if the body of the varargs method does not throw any exceptions like ClassCastException (which occurs due to improper handling of the varargs formal parameter) then the warnings can be suppressed in Java 1.7 by three different ways: 

(1) Add annotation @SafeVarargs to static method declarations and non constructor method declarations 

(2) Add annotation @SuppressWarnings({"unchecked", "varargs"}) to varargs method declaration 

(3) Directly use compiler option “-Xlint:varargs.

By suppressing the warnings in varargs method, occurrence of unchecked warnings can be prevented at compile time thus preventing Heap Pollution.

7) Java Virtual Machine Enhancements in Java 1.7

Java SE 7 / Java 1.7 newly introduce a JVM instruction called “invokedynamic” instruction.  Using “invokedynamic” instruction, the dynamic types programming language implementation becomes simpler. Thus Java 1.7 enables JVM support for the non-java languages.  

Java Memory Management We are covering here -'Java garbage collection interview questions' or 'Java memory interview questions' in d...

Java util.collections is one of the most important package in java and the important of this package can be understand by...

Java Concurrency Java Concurrency interview question - In year 2004 when technology gurus said innovation in Java is gone down and Sun Microsystems [Now Or...

Design Pattern in Java : Part 1 'Java investment bank interview' generally contains 'Java Design Pattern' questions. If you want to be a professional Java ...

Java Producer and Consumer Implementation using Blocking Queue

'Java Consumer Producer' example - This is one of frequently asked questions to senior core java developer. Java concurrency producer and consumer solution is demonstrated below. 
Java Concurrency Queuing options:
 The java concurrent executors and task holding queues can be configured in three ways-

Direct handoffs :  A good default choice for a work queue is a SynchronousQueue that hands off tasks to threads without otherwise holding them. Here, an attempt to queue a task will fail if no threads are immediately available to run it, so a new thread will be constructed. This policy avoids lockups when handling sets of requests that might have internal dependencies. Direct handoffs generally require unbounded maximumPoolSizes to avoid rejection of new submitted tasks. This in turn admits the possibility of unbounded thread growth when commands continue to arrive on average faster than they can be processed.

Unbounded queues : Using an unbounded queue (for example a LinkedBlockingQueue without a predefined capacity) will cause new tasks to wait in the queue when all corePoolSize threads are busy. Thus, no more than corePoolSize threads will ever be created. (And the value of the maximumPoolSize therefore doesn't have any effect.) This may be appropriate when each task is completely independent of others, so tasks cannot affect each others execution; for example, in a web page server. While this style of queuing can be useful in smoothing out transient bursts of requests, it admits the possibility of unbounded work queue growth when commands continue to arrive on average faster than they can be processed.

Bounded queues : A bounded queue (for example, an ArrayBlockingQueue) helps prevent resource exhaustion when used with finite maximumPoolSizes, but can be more difficult to tune and control. Queue sizes and maximum pool sizes may be traded off for each other: Using large queues and small pools minimizes CPU usage, OS resources, and context-switching overhead, but can lead to artificially low throughput. If tasks frequently block (for example if they are I/O bound), a system may be able to schedule time for more threads than you otherwise allow. Use of small queues generally requires larger pool sizes, which keeps CPUs busier but may encounter unacceptable scheduling overhead, which also decreases throughput.

   Example of PriorityBlockingQueue and see how the comparable is used with priority of task which depends on implementation of compare method in task.
From Java Docs-

The Blocking queue here is bounded with 11 as initial capacity as default constructor.  The queue is based on priority and least priority data is processed 
" An unbounded blocking queue that uses the same ordering rules as class PriorityQueue and supplies blocking retrieval operations. While this queue is logically unbounded, attempted additions may fail due to resource exhaustion (causing OutOfMemoryError). This class does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so results in ClassCastException).
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityBlockingQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()). Also, methoddrainTo can be used to remove some or all elements in priority order and place them in another collection."

Output
 Consumed Data [number=2, name=two]
 producer 0
 Consumed Data [number=10, name=ten]
 producer 1
 Consumed Data [number=20, name=twenty]
 producer 2
 Consumed Data [number=0, name=0]
 producer 3
 Consumed Data [number=1, name=1]
 producer 4
 Consumed Data [number=2, name=2]
 producer 5
 Consumed Data [number=3, name=3]

Consumer Producer Solution with Synchronisation:

This implementation with Synchronisation needs great care and it is more complicated in implementation:

Output 

The output will confim that there is no concurrency issue on putting data into same queue and wait() and notify() works perfectly fine.
 Got: 53613
 Put: 53614
 Got: 53614
 Put: 53615
 Got: 53615
 Put: 53616
 Got: 53616
 Put: 53617
 Got: 53617

Design Pattern in Java : Part 1

'Java investment bank interview' generally contains 'Java Design Pattern' questions. If you want to be a professional Java developer, you should know popular solutions for common\standard coding problems. Such solutions have been proved efficient and effective and always used by experienced developers. These solutions are described as so-called design patterns. Learning design patterns speeds up your experience accumulation in OOA/OOD. Once you grasped them, you would be benefit from them for all your life and jump up yourselves to be a master of designing and developing. Furthermore, you will be able to use these terms to communicate with your fellows more effectively.

Many programmers with many years of experience don't know how to use design patterns, but as an Object-Oriented programmer, you have to know them well, especially for new Java programmers. Actually, when you solved a coding problem, you have used one of the design pattern. 

        You may not use a popular name to describe it or may not choose an effective way to better intellectually control over what you built. Learning how the experienced developers to solve the coding problems and trying to use them in your project are a best way to earn your experience. We have mainly 3 type of design patterns and they are Creational, Structural and Behavioural. Behavioural pattern is explained in next blog - Design Pattern - part 2.

There are frequently asked question in design pattern, and these were asked to me in java interviews:
1) Explain Singleton Design pattern and How to solve Double Check locking?
2) What is Abstract Factory Pattern?
3) What is Adapter pattern?
4) What is Decorator Design Pattern?
5) Where we should use Facade in application?
6) What is Proxy and Composite?
7) What is Observer Pattern? 

Creational Patterns
[Details are from taken out from wiki description]

Factory:

The factory pattern \ factory method pattern is an object-oriented creational design pattern to implement the concept of factories and deals with the problem of creating objects (products) without specifying the exact class of object that will be created. The essence of this pattern is to "Define an interface for creating an object, but let the classes that implement the interface decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses."

Creating an object often requires complex processes not appropriate to include within a composing object. The object's creation may lead to a significant duplication of code, may require information not accessible to the composing object, may not provide a sufficient level of abstraction, or may otherwise not be part of the composing object's concerns. The factory method design pattern handles these problems by defining a separate method for creating the objects, which subclasses can then override to specify the derived type of product that will be created.

The factory pattern relies on inheritance, as object creation is delegated to subclasses that implement the factory method to create objects. 

Example : Static factory method provided with Collections class like 

Collections.synchronizedMap( new HashMap()); 

Abstract Factory:

The abstract factory pattern is a software creational design pattern that provides a way to encapsulate a group of individual factories that have a common theme without specifying their concrete classes. In normal usage, the client software creates a concrete implementation of the abstract factory and then uses the generic interfaces to create the concrete objects that are part of the theme. The client does not know (or care) which concrete objects it gets from each of these internal factories, since it uses only the generic interfaces of their products. This pattern separates the details of implementation of a set of objects from their general usage and relies on object composition, as object creation is implemented in methods exposed in the factory interface.

An example of this would be an abstract factory class DocumentCreator that provides interfaces to create a number of products (e.g. createLetter() andcreateResume()). The system would have any number of derived concrete versions of the DocumentCreator class like FancyDocumentCreator or ModernDocumentCreator, each with a different implementation of createLetter() and createResume() that would create a corresponding object like FancyLetter or ModernResume. Each of these products is derived from a simple abstract class like Letter or Resume of which the client is aware. The client code would get an appropriate instance of the DocumentCreator and call its factory methods. Each of the resulting objects would be created from the same DocumentCreator implementation and would share a common theme (they would all be fancy or modern objects).

Example : The best example will be configuring Database connection factory which hide underline Database type. We can configure Oracle, DB2 or Sybase Connection Factory in application.

    > java.util.Calendar#getInstance()
    > java.util.ResourceBundle#getBundle()
    > java.text.NumberFormat#getInstance()




Singleton:

The Singleton pattern is a design pattern that restricts the instantiation of a class to one object. This is useful when exactly one object is needed to coordinate actions across the system. The concept is sometimes generalized to systems that operate more efficiently when only one object exists, or that restrict the instantiation to a certain number of objects. The term comes from the mathematical concept of a singleton.

In the second edition of his book Effective Java, Joshua Bloch claims that "a single-element enum type is the best way to implement a singleton" for any Java that supports enums. The use of an enum is very easy to implement and has no drawbacks regarding serializable objects, which have to be circumvented in the other ways.

 Bill Pugh has written about the code issues underlying the Singleton pattern when implemented in Java. Pugh's efforts on the "Double-checked locking" idiom led to changes in the Java memory model in Java 5 and to what is generally regarded as the standard method to implement Singletons in Java. The technique known as the initialization on demand holder idiom, is as lazy as possible, and works in all known versions of Java. It takes advantage of language guarantees about class initialization, and will therefore work correctly in all Java-compliant compilers and virtual machines.

The nested class is referenced no earlier (and therefore loaded no earlier by the class loader) than the moment that getInstance() is called. Thus, this solution is thread-safe without requiring special language constructs (i.e. volatile or synchronized). More details on Singleton Pattern.
Example: Getting Runtime environment using Runtime class is example of Singleton design pattern -- java.lang.Runtime#getRuntime()

Builder:
The builder pattern is an object creation software design pattern. The intention is to abstract steps of construction of objects so that different implementations of these steps can construct different representations of objects. Often, the builder pattern is used to build products in accordance with the composite pattern.The intent of the Builder design pattern is to separate the construction of a complex object from its representation. By doing so, the same construction process can create different representations.

Builder

Abstract interface for creating objects (product).

Concrete Builder

     Provides implementation for Builder. It is an object able to construct other objects. Constructs and assembles parts to build the objects.
Example : Builder pattern is frequently used in Java classes where We need special purpose classes like StingBuilder and StringBuffer.

    > java.lang.StringBuilder#append() 
    > java.lang.StringBuffer#append() 
    > java.nio.ByteBuffer#put()

Prototype:

The prototype pattern is a creational design pattern used in software development when the type of objects to create is determined by a prototypical instance, which is cloned to produce new objects. This pattern is used to:

• avoid subclasses of an object creator in the client application, like the abstract factory pattern does.
• avoid the inherent cost of creating a new object in the standard way (e.g., using the 'new' keyword) when it is prohibitively expensive for a given application.

To implement the pattern, declare an abstract base class that specifies a pure virtual clone() method. Any class that needs a "polymorphic constructor" capability derives itself from the abstract base class, and implements the clone() operation.

The client, instead of writing code that invokes the "new" operator on a hard-coded class name, calls the clone() method on the prototype, calls a factory method with a parameter designating the particular concrete derived class desired, or invokes the clone() method through some mechanism provided by another design pattern.

Example: Best example will be Java.lang.Object#clone() method. Class has be implement Cloneable interface to use this.  

Design Pattern - part 2

Java Memory Management We are covering here -'Java garbage collection interview questions' or 'Java memory interview questions' in d...

Collection Interview Questions for Java Developers Java util.collections is one of the most important package in java and the important of this package can be understand by...

Java Concurrency Java Concurrency interview question - In year 2004 when technology gurus said innovation in Java is gone down and Sun Microsystems [Now Or...

Design Pattern in Java : Part 2 'Java investment bank interview' generally contains 'Java Design Pattern' questions. If you want to be a professional Java ...

Java Interviews Frequently Asked Puzzles

Interview puzzles is the best way to check person's analytical skills. In investment banking job you need analytical skill to perform day to day job. It is not only applicable to traders , but some level of analytical skills is required by people who are developing these systems for understand business. Now a days it is become common practice to ask 1-2 puzzles during investment bank interview to check the candidate's analytical skills. The best way to clear this round is practice common puzzles and understand the logic to solve them. 

1) Fibonacci in Java:

The input will be number n and the output should be sum for 0 to n. for example

for n =4 the result should be 0+1+2+3+4 = 10

2) String Reverse

The input String "abcde" should return "edcba".

3) Reversing a linked list in Java

Here is example of revering the linked list in java using recursive function:

4) Find the missing number in Java

You have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot?

Try it for practice. please suggest the answer .

[Trick sum of n numbers is n*(n+1)/2]

5) Write a substring function in Java

String test= "AA BB CC BB BB CC BB";

String[]{"BB", "CC", "AA"}

Result shd be BB=4; CC=2 and AA=1

Since B occurred 4 times C did 2 times and A only 1 time.

This basic problem can be asked in different ways like, You have multiple words in new paper and find out the frequency of words in one page of news paper?

6) Reverse a String in Java

Reverse the String by java function without recursion and with recursion

7) Find one string inside another in Java

We can use String.indexOf( subString ) and it will return the first index of substring;

for Last Index : lastIndexOf(String str)

8) Algo for finding largest number in Array of Integer

Easy one, Check the integer one by one and find the largest number.

9) Java Runtime method invocation question:

Example : Tell the output of this

Answer is : 20 .

10) Suppose you have a large file with lots of words. How would you find the unique words and their count? What kind of data structure u will use? What will be the time complexity and space complexity?

We need to take care of two things counting the words and second duplicate. the best performance will be using hash function.

11) A train is one mile long. It travels at the rate of one mile a minute through a tunnel which is also one mile long. Can you say how long it will take for the train to pass completely through the tunnel? 

Answer : 2 minutes

it will take two minutes if you count the time for it to completely pass through the tunnel. One minute to pass through the tunnel and another one minute to drag itself out of the tunnel completely so two minutes nice question though well logical.

12) Convert String = "98989" into an integer without using any library functions in java.

Give fastest way to do it and explain why your method is best.

// converting string to number using ascii code

13) Write a program to shuffle a deck of 52 cards and shuffle them equally to 4 players.

Answer this puzzle by comments.

Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time?

for example you have 4 stairs and you can climb like

1,1,1,1

1,1,2

1,2,1

2,1,1

2,2

so in overall 5 ways for 3 stairs.

Java Memory Management

We are covering here -'Java garbage collection interview questions' or 'Java memory interview questions' in details. The topic is always asked to senior java developers to verify the java memory model understanding. In bigger project taking care of VM memory becomes very important due to more memory required at peak time processing in application.  

In this topic frequently asked questions are:

• What is Garbage collection?
• How to do analysis of java memory issues?
• Explain Java memory model?
• What are garbage collectors?
• How to use java profilers?
• Have you worked in application performance improvement?
• What are the memory issues you have faced in your application?

Garbage Collection:

Garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program. Garbage collection was invented by John McCarthy around 1959 to solve problems in Lisp.

Garbage collection is often portrayed as the opposite of manual memory management, which requires the programmer to specify which objects to deallocate and return to the memory system. However, many systems use a combination of approaches, including other techniques such as stack allocation and region inference.

Resources other than memory, such as network sockets, database handles, user interaction windows, and file and device descriptors, are not typically handled by garbage collection. Methods used to manage such resources, particularly destructors, may suffice to manage memory as well, leaving no need for GC. Some GC systems allow such other resources to be associated with a region of memory that, when collected, causes the other resource to be reclaimed; this is called finalization. Finalization may introduce complications limiting its usability, such as intolerable latency between disuse and reclaim of especially limited resources, or a lack of control over which thread performs the work of reclaiming.

Memory is divided in mainly 3 areas:

•  Young\Eden Generation : for newly created objects.
•  Tenured Generation : for old objects which are survived after minor gc.
•  Perm Space : for class definition, meta data and string pools.

At initialization, a maximum address space is virtually reserved but not allocated to physical memory unless it is needed. The complete address space reserved for object memory can be divided into the young and tenured generations.The young generation consists of eden and two survivor spaces. Most objects are initially allocated in eden. One survivor space is empty at any time, and serves as the destination of any live objects in eden and the other survivor space during the next copying collection. Objects are copied between survivor spaces in this way until they are old enough to be tenured (copied to the tenured generation). A third generation closely related to the tenured generation is the permanent generation which holds data needed by the virtual machine to describe objects that do not have an equivalence at the Java language level.

Java objects are created in Heap and Heap is divided into three parts or generations of garbage collection in Java as mentioned above. New Generation is divided into three parts known as 

•   Eden space
•   Survivor 1 
•   Survivor 2 space. 

When an object first created in heap its gets created in new generation inside Eden space and after subsequent Minor Garbage collection if object survives its gets moved to survivor 1 and then Survivor 2 before Major Garbage collection moved that object to Old or tenured generation.

Permanent generation of Heap or Perm Area of Heap is special and it is used to stores String pool,  Meta data related to classes and method in JVM.

Out Of Memory / OOM :

   If it happens in your application take it is opportunity to display your technical skills. In technical term it means the JVM does not have space to put objects in tenured space which are survived in minor collection and it stops working or responding due to no memory to do further processing.

These are terms used in context of java memory management:

• Throughput is the percentage of total time not spent in garbage collection, considered over long periods of time. Throughput includes time spent in allocation (but tuning for speed of allocation is generally not needed).
• Pauses are the times when an application appears unresponsive because garbage collection is occurring.
• Footprint is the working set of a process, measured in pages and cache lines. On systems with limited physical memory or many processes, footprint may dictate scalability. 
• Promptness is the time between when an object becomes dead and when the memory becomes available, an important consideration for distributed systems, including remote method invocation (RMI).
• Heap Dump is a list of objects in the memory of JVM as well as the content of the memory occupied by those objects. It preserves the value of any attributes of the objects, including references to other objects. In other words, a heap dump gives you a complete picture of the memory.There are multiple tools that allow you to dump heap in a Java process:Some tools like VisualVM and memory profilers allow you to initiate a heap dump from the GUI, but you don’t need any fancy tools here—jmap will do just fine. As it provides the most general case, we'll use jmap in the next example.Before you dump heap, be sure to keep the following issues in mind:Note that the -F option, which will dump non-responsive programs, might be useful on UNIX systems, but is not available on Windows. Note also that JDK 6 includes the option +XX:+HeapDumpOnOutOfMemoryError that will dump heap whenever the OutOfMemoryError alert is encountered. This can be a useful option, but keep in mind that it has the potential to consume significant amounts of disk space.

The basic principles of garbage collection are:

1. Find data objects in a program that cannot be accessed in the future
2. Reclaim the resources used by those objects

   An object is considered garbage when it can no longer be reached from any pointer in the running program. The most straightforward garbage collection algorithms simply iterate over every reachable object. Any objects left over are then considered garbage. The time this approach takes is proportional to the number of live objects, which is prohibitive for large applications maintaining lots of live data.The blue area in the diagram below is a typical distribution for the lifetimes of objects. The X axis is object lifetimes measured in bytes allocated. The byte count on the Y axis is the total bytes in objects with the corresponding lifetime. The sharp peak at the left represents objects that can be reclaimed (i.e., have "died") shortly after being allocated. Iterator objects, for example, are often alive for the duration of a single loop.   

Application GC bytes allocation is shown in above picture. Majority of byte survival happens in Minor Collection and majority of objects are cleared in Major collections. Some objects do live longer, and so the distribution stretches out to the the right. For instance, there are typically some objects allocated at initialisation that live until the process exits. Between these two extremes are objects that live for the duration of some intermediate computation, seen here as the lump to the right of the initial peak. Some applications have very different looking distributions, but a surprisingly large number possess this general shape. Efficient collection is made possible by focusing on the fact that a majority of objects "die young".

Collectors

The Java HotSpot VM includes three different collectors, each with different performance characteristics.

• The serial collector uses a single thread to perform all garbage collection work, which makes it relatively efficient since there is no communication overhead between threads. It is best-suited to single processor machines, since it cannot take advantage of multiprocessor hardware, although it can be useful on multiprocessors for applications with small data sets (up to approximately 100MB). The serial collector is selected by default on certain hardware and operating system configurations, or can be explicitly enabled with the option -XX:+UseSerialGC.

• The parallel collector (also known as the throughput collector) performs minor collections in parallel, which can significantly reduce garbage collection overhead. It is intended for applications with medium- to large-sized data sets that are run on multiprocessor or multi-threaded hardware. The parallel collector is selected by default on certain hardware and operating system configurations, or can be explicitly enabled with the option -XX:+UseParallelGC.

• New: parallel compaction is a feature introduced in J2SE 5.0 update 6 and enhanced in Java SE 6 that allows the parallel collector to perform major collections in parallel. Without parallel compaction, major collections are performed using a single thread, which can significantly limit scalability. Parallel compaction is enabled by adding the option -XX:+UseParallelOldGC to the command line.

• The concurrent collector performs most of its work concurrently (i.e., while the application is still running) to keep garbage collection pauses short. It is designed for applications with medium- to large-sized data sets for which response time is more important than overall throughput, since the techniques used to minimize pauses can reduce application performance. The concurrent collector is enabled with the option -XX:+UseConcMarkSweepGC.

VM Options for GC details:

• -verbose:gc — prints basic information about GC to the standard output

• -XX:+PrintGCTimeStamps — prints the times that GC executes

• -XX:+PrintGCDetails — prints statistics about different regions of memory in the JVM

• -Xloggc: — logs the results of GC in the given file.

These Command line options are available via JMX to monitor VM memory-

• -Dcom.sun.management.jmxremote — enables JMX monitoring

• -Dcom.sun.management.jmxremote.port = — controls the port for JMX monitoring

• com.sun.management.jmxremote.ssl

• com.sun.management.jmxremote.authenticate

• If you're using JDK 6, you can use tool called jmap on any platform.

What is Garbage First Collector?

 Recently in one java interview, I was asked about Garbage First collector and Garbage First collector splits the heap up into fixed-size regions and tracks the live data in those regions. It keeps a set of pointers — the "remembered set" — into and out of the region. When a GC is deemed necessary, it collects the regions with less live data first (hence, "garbage first"). Often, this can mean collecting an entire region in one step: if the number of pointers into a region is zero, then it doesn't need to do a mark or sweep of that region.

    For each region, it tracks various metrics that describe how long it will take to collect them. You can give it a soft real-time constraint about pause times, and it then tries to collect as much garbage as it can in that constrained time.

Technical description

The G1 collector achieves high performance and pause time goals through several techniques.

The heap is partitioned into a set of equal-sized heap regions, each a contiguous range of virtual memory. G1 performs a concurrent global marking phase to determine the liveness of objects throughout the heap. After the mark phase completes, G1 knows which regions are mostly empty. It collects in these regions first, which usually yields a large amount of free space. This is why this method of garbage collection is called Garbage-First. As the name suggests, G1 concentrates its collection and compaction activity on the areas of the heap that are likely to be full of reclaimable objects, that is, garbage. G1 uses a pause prediction model to meet a user-defined pause time target and selects the number of regions to collect based on the specified pause time target.

The regions identified by G1 as ripe for reclamation are garbage collected using evacuation. G1 copies objects from one or more regions of the heap to a single region on the heap, and in the process both compacts and frees up memory. This evacuation is performed in parallel on multi-processors, to decrease pause times and increase throughput. Thus, with each garbage collection, G1 continuously works to reduce fragmentation, working within the user defined pause times. This is beyond the capability of both the previous methods. CMS (Concurrent Mark Sweep ) garbage collection does not do compaction. ParallelOld garbage collection performs only whole-heap compaction, which results in considerable pause times.

It is important to note that G1 is not a real-time collector. It meets the set pause time target with high probability but not absolute certainty. Based on data from previous collections, G1 does an estimate of how many regions can be collected within the user specified target time. Thus, the collector has a reasonably accurate model of the cost of collecting the regions, and it uses this model to determine which and how many regions to collect while staying within the pause time target.

Recommended Use Cases for G1

The first focus of G1 is to provide a solution for users running applications that require large heaps with limited GC latency. This means heap sizes of around 6GB or larger, and stable and predictable pause time below 0.5 seconds.

Applications running today with either the CMS or the ParallelOld garbage collector would benefit switching to G1 if the application has one or more of the following traits.
- More than 50% of the Java heap is occupied with live data.
- The rate of object allocation rate or promotion varies significantly.
- Undesired long garbage collection or compaction pauses (longer than 0.5 to 1 second)

Understanding Spring MVC We are covering here -'Java garbage collection interview questions' or 'Java memory interview questions' in d...

Database Interview Questions for Java Developers ' Java database questions ' or ' Database interview questions for java developer ' is covered in this blog. All ent...

Java Concurrency Java Concurrency interview question - In year 2004 when technology gurus said innovation in Java is gone down and Sun Microsystems [Now Or...

Design Pattern in Java : Part 1 'Java investment bank interview' generally contains 'Java Design Pattern' questions. If you want to be a professional Java ...