Java Memory Architecture and Garbage Collection Algorithms(Part 2)

Java Memory Model

The Java memory model specifies how the Java virtual machine works with the computer's memory (RAM). The Java virtual machine is a model of a whole computer so this model naturally includes a memory model - AKA the Java memory model.

It is very important to understand the Java memory model if you want to design correctly behaving concurrent programs. The Java memory model specifies how and when different threads can see values written to shared variables by other threads, and how to synchronize access to shared variables when necessary.

The original Java memory model was insufficient, so the Java memory model was revised in Java 1.5. This version of the Java memory model is still in use in Java 8.


The Architecture of the Java Virtual Machine

In the Java virtual machine specification, the behavior of a virtual machine instance is described in terms of subsystems, memory areas, data types, and instructions. These components describe an abstract inner architecture for the abstract Java virtual machine. The purpose of these components is not so much to dictate an inner architecture for implementations. It is more to provide a way to strictly define the external behavior of implementations. The specification defines the required behavior of any Java virtual machine implementation in terms of these abstract components and their interactions.

Figure shows a block diagram of the Java virtual machine that includes the major subsystems and memory areas described in the specification. As mentioned in previous chapters, each Java virtual machine has a class loader subsystem: a mechanism for loading types (classes and interfaces) given fully qualified names. Each Java virtual machine also has an execution engine: a mechanism responsible for executing the instructions contained in the methods of loaded classes.

When a Java virtual machine runs a program, it needs memory to store many things, including bytecodes and other information it extracts from loaded class files, objects the program instantiates, parameters to methods, return values, local variables, and intermediate results of computations. The Java virtual machine organizes the memory it needs to execute a program into several runtime data areas.

Although the same runtime data areas exist in some form in every Java virtual machine implementation, their specification is quite abstract. Many decisions about the structural details of the runtime data areas are left to the designers of individual implementations.

Different implementations of the virtual machine can have very different memory constraints. Some implementations may have a lot of memory in which to work, others may have very little. Some implementations may be able to take advantage of virtual memory, others may not. The abstract nature of the specification of the runtime data areas helps make it easier to implement the Java virtual machine on a wide variety of computers and devices.

Some runtime data areas are shared among all of an application's threads and others are unique to individual threads. Each instance of the Java virtual machine has one method area and one heap. These areas are shared by all threads running inside the virtual machine. When the virtual machine loads a class file, it parses information about a type from the binary data contained in the class file. It places this type information into the method area. As the program runs, the virtual machine places all objects the program instantiates onto the heap. See Figure 5-2 for a graphical depiction of these memory areas.

As each new thread comes into existence, it gets its own pc register (program counter) and Java stack. If the thread is executing a Java method (not a native method), the value of the pc register indicates the next instruction to execute. A thread's Java stack stores the state of Java (not native) method invocations for the thread. The state of a Java method invocation includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocations is stored in an implementation-dependent way in native method stacks, as well as possibly in registers or other implementation-dependent memory areas.

The Java stack is composed of stack frames (or frames). A stack frame contains the state of one Java method invocation. When a thread invokes a method, the Java virtual machine pushes a new frame onto that thread's Java stack. When the method completes, the virtual machine pops and discards the frame for that method.

The Java virtual machine has no registers to hold intermediate data values. The instruction set uses the Java stack for storage of intermediate data values. This approach was taken by Java's designers to keep the Java virtual machine's instruction set compact and to facilitate implementation on architectures with few or irregular general purpose registers. In addition, the stack-based architecture of the Java virtual machine's instruction set facilitates the code optimization work done by just-in-time and dynamic compilers that operate at run-time in some virtual machine implementations.

See Figure for a graphical depiction of the memory areas the Java virtual machine creates for each thread. These areas are private to the owning thread. No thread can access the pc register or Java stack of another thread.

Java Memory Architecture and Garbage Collection Algorithms(Part 1)

Java Memory Architecture and Garbage Collection Algorithms Peeling Concept

Understand the Java Memory Model for the heap, as well as garbage collection algorithms, and memory leak best practices all with diagrams and bite-sized descriptions.


The diagram below is the Java Memory Model for the Heap as well as the PermGen for any Java Application running in the Java Virtual Machine (JVM). The ratios are also provided to get a fair understanding of how the distribution of allowed memory is done across each of the generation types. All of the info is completely applicable up to Java 1.7 (inclusive). This diagram is also known as the 'Managed Area' of the memory model.


Java Memory Architecture (Java Memory Model)

In addition to the above, there is a Stack Area, which can be configured using the -Xss option. This area holds the references on the heap, native references, pc registers, code cache, and local variables for all threads. This is also known as the 'Native Area' of the memory model.


Managed Area of the Java Memory Model (Java Memory Architecture)

[Young Generation/Nursery] Eden Space

All new objects are first created in the Eden Space. As soon as it reaches an arbitrary threshold decided by the JVM, a minor garbage collection (Minor GC) kicks in. It first removes all the non-referenced objects and moves referenced objects from the 'eden' and 'from' into the 'to' survivor space. Once the GC is over, the 'from' and 'to' roles (names) are swapped.

[Young Generation/Nursery] Survivor 1 (From)

This is a part of the survivor space (You may think of this a role in the survivor space). This was the 'to' role during the previous garbage collection (GC).

[Young Generation/Nursery] Suvrivor 2 (To)

This is also a part of the survivor space (You may think of this as a role in the survivor space too). It is here, during the GC, that all the referenced objects are moved to, from 'from' and 'eden'.

[Old Generation] Tenured

Depending on the threshold limits, which can be checked by using -XX:+PrintTenuringDistribution, which shows the objects (space in bytes) by age, objects are moved from the 'to' Survivor space to the Tenured space. 'Age' is the number of times that it has moved within the survivor space.

There are other important flags like, -XX:InitialTenuringThreshold, -XX:MaxTenuringThreshold and -XX:TargetSurvivorRatio which lead to an optimum utilization of the tenured as well as the survivor spaces.

By setting -XX:InitialTenuringThreshold and -XX:MaxTenuringThreshold we allow an initial value and a maximum value for 'Age' while maintaining the percentage utilization in the 'Survivor (To)' as specified by the -XX:+NeverTenure and -XX:+AlwaysTenure, which encouraged never to be used to tenure an object (risky to use). The opposite usage is to always tenure, which means to always use the 'old generation'.

The garbage collection that happens here is the major garbage collection (Major GC). This is usually triggered when the heap is full or the old generation is full. This is usually a 'Stop-the-World' event or thread that takes over to perform the garbage collection. There is another type of GC named full garbage collection (Full GC) which involves other memory areas such as the permgen space.

Other important and interesting flags related to the overall heap are -XX:SurvivorRatio and -XX:NewRatio, which specify the eden space to the survivor space ratio and old generation to the new generation ratio.

[Permanent Generation] Permgen space

The 'Permgen' is used to store the following information: Constant Pool (Memory Pool), Field & Method Data and Code. Each of them related to the same specifics as their name suggests.

Garbage Collection Algorithms

Serial GC (-XX:UseSerialGC): GC on Young Generation and Old Generation

Use the simple mark-sweep-compact cycle for young and tenured generations. This is good for client systems and systems with low memory footprint and smaller CPU.

Parallel GC (-XX:UseParallelGC): GC on Young Generation and Old Generation

This uses N threads, which can be configured using -XX:ParallelGCThreads=N, here N is also the number of CPU cores for garbage collection. It uses these N threads for GC in the Young Generation but uses only one-thread in the Old Generation.

Parallel Old GC (-XX:UseParallelOldGC): GC on Young Generation and Old Generation

This is same as the Parallel GC, except that it uses N threads for GC in both Old and Young Generation.

Concurrent Mark and Sweep GC (-XX:ConcMarkSweepGC): GC on Old Generation

As the name suggests, the CMS GC minimizes the pauses that are required for GC. It is most useful when used to create highly responsive applications and it does GC only in the Old Generation. It creates multiple threads for GC that work concurrently with applications threads, which can be specified using the -XX:ParallelCMSThreads=n.

G1 GC (-XX:UseG1GC): GC on Young and Old Generation (By Dividing Heap into Equal Size Regions)

This is a parallel, concurrent, and incrementally compacting low-pause garbage collector. G1 was introduced in Java 7 with the ultimate vision to replace CMS GC. It divides the heap into multiple, equal sized regions and then performs GC, usually starting with the region that has less live data, hence "Garbage First".

Most Common Out of Memory Issues

The most common out of memory issues, which all Java developers should know, are as follows:

Exception in thread "main": java.lang.OutOfMemoryError:

Java heap space. This does not necessarily imply a memory leak — as it could be due to lesser space configured for the heap. Otherwise, in a long-lived application it could be due to an unintentional reference being mentioned to heap objects (memory leak). Even the APIs that are called by the application could be holding references to objects that are unwarranted. Also, in applications that make excessive use of finalizers, sometimes the objects are queued into a finalization queue. When such an application creates higher priority threads and that leads to more and more objects in the finalization queue, it can cause an Out-of-Memory.

Exception in thread "main": java.lang.OutOfMemoryError:

PermGen space. If there are many classes and methods loaded or if there are many string literals created, especially through the use of intern() (From JDK 7 on, interned strings are no longer part of the PermGen), then this type of error occurs. When this kind of error occurs, the text ClassLoader.defineClass might appear near the top of the stack trace that is printed.

Exception in thread "main": java.lang.OutOfMemoryError: 

Requested array size exceeds VM limit. This again happens when the requested array size is greater than the available heap size. It may usually occur due to programmatic errors during runtime if an incredibly large value is requested for an array size.

Exception in thread "main": java.lang.OutOfMemoryError: 

request <s> bytes for <r>. Out of swap space? It is often the root cause of a memory leak. It happens when either the Operating System does not have sufficient swap space or when Another Process hogs all the available memory resources on the system. In simple terms, it was unable to provide the request space from heap due to exhaustion of space. The message indicates the size 's' (in bytes) of the request that failed and the reason 'r' for the memory request. In most cases the <r> part of the message is the name of a source module reporting the allocation failure, although in some cases it indicates a reason.

Exception in thread "main": java.lang.OutOfMemoryError:<reason> <stack trace> (Native method). This indicates that a Native method has met with an allocation failure. The root cause was that the error occurred in JNI rather than in the code executing inside the JVM. When the native code does not check for memory allocation errors, then the application crashes instead of going out of memory.

Definition of Memory Leak 

Think of memory leakage as a disease and the OutOfMemoryError as a symptom. But not all OutOfMemoryErrors imply memory leaks, and not all memory leaks manifest themselves as OutOfMemoryErrors.

In Computer Science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory, which is no longer needed, is not released. In Object-Oriented Programming, a memory leak may happen when an object is stored in memory but cannot be accessed by the running code.

Common Definitions of Memory Leak in Java

A memory leak occurs when object references that are no longer needed are unnecessarily maintained.

Memory leak in Java is a situation where some objects are not used by application any more, but GC fails to recognize them as unused.

A Memory Leak appears when an object is no longer used in the program but is still referenced somewhere at a location that is not reachable. Thus, the garbage collector cannot delete it. The memory space used for this object will not be released and the total memory used for the program will grow. This will degrade performances over time and the JVM may run out of memory.

In a way, Memory Leak would occur when No Memory can be Allocated on the Tenured Space.Some of the most common causes of Memory Leaks are:

• ThreadLocal Variables
• Circular and Complex Bi-Directional References
• JNI Memory Leaks
• Static Fields that are Mutable (Most Common)

I recommend the usage of Visual VM bundled with the JDK to start debugging your memory leak issues.

Common Debugging of Memory Leaks

• NetBeans Profiler
• Using the jhat Utility
• Creating a Heap Dump
• Obtaining a Heap Histogram on a Running Process
• Obtaining a Heap Histogram at OutOfMemoryError
• Monitoring the Number of Objects Pending Finalization
• Third Party Memory Debuggers

The common strategies or steps for going about debugging memory leak issues include:

• Identify Symptoms
• Enable Verbose Garbage Collection
• Enable Profiling
• Analyze the Trace

Now let me simplify all the information that i have shared.continuing on Java Memory......

CountDownLatch in java example

CountDownLatch in Java:

It is used to make sure that a task waits for other threads before it starts. To understand its application, let us consider a server where the main task can only start when all the required services have started.

Working of CountDownLatch:

When we create an object of CountDownLatch, we specify the number if threads it should wait for, all such thread are required to do count down by calling CountDownLatch.countDown() once they are completed or ready to the job. As soon as count reaches zero, the waiting task starts running.

Sample Code:

import java.util.concurrent.CountDownLatch;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class CountDownLatchApp
{
/**
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException
{
// TODO Auto-generated method stub

CountDownLatch latch=new CountDownLatch(7);
Worker worker1=new Worker(1000, latch, "Worker-1");
Worker worker2=new Worker(1000, latch, "Worker-2");
Worker worker3=new Worker(1000, latch, "Worker-3");
Worker worker4=new Worker(1000, latch, "Worker-4");
Worker worker5=new Worker(1000, latch, "Worker-5");
Worker worker6=new Worker(1000, latch, "Worker-6");
Worker worker7=new Worker(1000, latch, "Worker-7");

worker1.start();
worker2.start();
worker3.start();
worker4.start();
worker5.start();
worker6.start();
worker7.start();

latch.await();
System.out.println(Thread.currentThread().getName() + "has finished.");

}
}

class Worker extends Thread
{
private int delay;
private CountDownLatch countDownLatch;

public Worker(int delay,CountDownLatch countDownLatch,String name)
{
super(name);

this.countDownLatch=countDownLatch;
this.delay=delay;
}

public void run()
{
try
{
Thread.sleep(delay);
countDownLatch.countDown();
System.out.println(Thread.currentThread().getName() + "Finished");
}
catch(Exception e)
{
e.printStackTrace();
}
}

}

Output:

Worker-1Finished
Worker-3Finished
Worker-7Finished
Worker-4Finished
Worker-5Finished
Worker-6Finished
Worker-2Finished
mainhas finished.


Important Points about CountDownLatch:

Creating an object of CountDownLatch by passing an int to its constructor (the count), is actually number of invited parties (threads) for an event.

The thread, which is dependent on other threads to start processing, waits on until every other thread has called count down. All threads, which are waiting on await() proceed together once count down reaches to zero.

countDown() method decrements the count and await() method blocks until count == 0

Garbage Collection in Java

All about Garbage Collection in Java/Android.


In other programming language, it is programmer’s responsibility to delete a dynamically allocated object if it is no longer in use.

In Java, the programmer need not to care for all those objects which are no longer in use. Garbage collector destroys these objects, but the garbage collector is not guaranteed to run at any specific time, it can be at any time once an object is eligible for garbage collection.


Following are some important points related to garbage collection:

The finalize () method:

Called by the garbage collector on an object when garbage collector determines that there are no more references to the object.

The finalize method is never invoked more than once by a Java virtual machine for any given object.
Our program must not rely on the finalize method because we never know if finalize will be executed or not.

Ways to make an object eligible for garbage collection:

Once the object is no longer used by the program, we can change the reference variable to a null, thus making the object which was referred by this variable eligible for garbage collection.
Please note that the object can not become a candidate for garbage collection until all references to it are discarded.

class Test
{
    public static void main(String[] args)
    {
        Test obj = new Test();

        /* obj being used for some purpose in program */

        /* When there is no more use of o1, make the object
           referred by o1 eligible for garbage collection */      
        obj = null;

        /* Rest of the program */
     }
}


gc() – request to JVM:

We can request to run the garbage collector using java.lang.System.gc() but it does not force garbage collection, the JVM will run garbage collection only when it wants to run it.

We may use system.gc() or runtime.gc()

import java.lang.*;
public class Test
{
    public static void main(String[] args)
    {
        int g1[] = { 0, 1, 2, 3, 4, 5 };
        System.out.println(g1[1] + " ");

        // Requesting Garbage Collector
        System.gc();
        System.out.println("Hey I just requested "+
                          "for Garbage Collection");
    }
}


I have a question?

What happens when group of object only refer to each other?

Ans: It is possible that a set of unused objects only refer to each other.For example, object o1 refers to object o2. Object o2 refers to o1. None of them is referenced by any other object. In this case both the objects o1 and o2 are eligible for garbage collection.All this process is called Island of Isolation.

eg: public class Test
{
    Test geek;
    public static void main(String [] args)
    {
        Test o1 = new Test();
        Test o2 = new Test();
        o1.geek = o2;
        o2.geek = o1;

        o1 = null;
        o2 = null;
       // both become eligible for garbage collection
    }
}

Collections.reverseOrder() in Java with Examples

Collections.reverseOrder() in Java with Examples

java.util.Collections.reverseOrder() method is a java.util.Collections class method.

// Returns a comparator that imposes the reverse of
// the natural ordering on a collection of objects
// that implement the Comparable interface.
// The natural ordering is the ordering imposed by
// the objects' own compareTo method

public static  Comparator reverseOrder()

We can the comparator returned by Collections.reverseOrder() to sort a list in descending order.

Sample Code:

import java.util.ArrayList;
import java.util.Collections;


/**
 * @author Abhinaw.Tripathi
 *
 */
public class ReverseOrderApp {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(30);
        al.add(20);
        al.add(10);
        al.add(40);
        al.add(50);

        /* Collections.sort method is sorting the
        elements of ArrayList in descending order. */
        Collections.sort(al, Collections.reverseOrder());

        // Let us print the sorted list
        System.out.println("List after the use of Collection.reverseOrder()"+
                           " and Collections.sort() :\n" + al);
}

}


Output:

List after the use of Collection.reverseOrder() and Collections.sort() :
[50, 40, 30, 20, 10]


We can use this method with Arrays.sort() also.

Sample Code:

import java.util.*;

public class Collectionsorting
{
    public static void main(String[] args)
    {
        // Create an array to be sorted in descending order.
        Integer [] arr = {30, 20, 40, 10};

        /* Collections.sort method is sorting the
        elements of arr[] in descending order. */
        Arrays.sort(arr, Collections.reverseOrder());

        // Let us print the sorted array
        System.out.println("Array after the use of Collection.reverseOrder()"+
                           " and Arrays.sort() :\n" + Arrays.toString(arr));
    }
}

Output:

Array after the use of Collection.reverseOrder() and Arrays.sort() :
[40, 30, 20, 10]



public static Comparator reverseOrder(Comparator c)


Sample Code:

It returns a Comparator that imposes reverse order of a passed Comparator object. We can use this method to sort a list in reverse order of user defined Comparator. For example, in the below program, we have created a reverse of user defined comparator to sort students in descending order of roll numbers.

// Java program to demonstrate working of
// reverseOrder(Comparator c) to sort students in descending
// order of roll numbers when there is a user defined comparator
// to do reverse.

import java.util.*;
import java.lang.*;
import java.io.*;

// A class to represent a student.
class Student
{
    int rollno;
    String name, address;

    // Constructor
    public Student(int rollno, String name,
                               String address)
    {
        this.rollno = rollno;
        this.name = name;
        this.address = address;
    }

    // Used to print student details in main()
    public String toString()
    {
        return this.rollno + " " + this.name +
                           " " + this.address;
    }
}

class Sortbyroll implements Comparator<Student>
{
    // Used for sorting in ascending order of
    // roll number
    public int compare(Student a, Student b)
    {
        return a.rollno - b.rollno;
    }
}

// Driver class
class Main
{
    public static void main (String[] args)
    {
        ArrayList<Student> ar = new ArrayList<Student>();
        ar.add(new Student(111, "bbbb", "london"));
        ar.add(new Student(131, "aaaa", "nyc"));
        ar.add(new Student(121, "cccc", "jaipur"));

        System.out.println("Unsorted");
        for (int i=0; i<ar.size(); i++)
            System.out.println(ar.get(i));

        // Sorting a list of students in descending order of
        // roll numbers using a Comparator that is reverse of
        // Sortbyroll()
        Comparator c = Collections.reverseOrder(new Sortbyroll());
        Collections.sort(ar, c);

        System.out.println("\nSorted by rollno");
        for (int i=0; i<ar.size(); i++)
            System.out.println(ar.get(i));
    }
}


Output :

Unsorted
111 bbbb london
131 aaaa nyc
121 cccc jaipur

Sorted by rollno
131 aaaa nyc
121 cccc jaipur
111 bbbb london

Collections.shuffle() in Java with Examples

Collections.shuffle() in Java with Examples

java.util.Collections.shuffle() is a java.util.Collections class method.

// Shuffles mylist

public static void shuffle(List mylist)

This method throws UnsupportedOperationException if the
given list or its list-iterator does not support
the set operation.

Sample Code:

import java.util.ArrayList;
import java.util.Collections;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class CollectionSuffleApp {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ArrayList<String> mylist =new ArrayList<>();
mylist.add("code");
        mylist.add("quiz");
        mylist.add("geeksforgeeks");
        mylist.add("quiz");
        mylist.add("practice");
        mylist.add("qa");
        System.out.println("Original List : \n" + mylist);
        Collections.shuffle(mylist);
        System.out.println("\nShuffled List : \n" + mylist);
}

}


Output:

 Original List : 
[code, quiz, geeksforgeeks, quiz, practice, qa]

Shuffled List : 
[qa, practice, geeksforgeeks, quiz, code, quiz]



It shuffles a given list using the user provided source of randomness.

// mylist is the list to be shuffled.
// rndm is source of randomness to shuffle the list.

public static void shuffle(List mylist, Random rndm)

It throws  UnsupportedOperationException if the specified list or
its list-iterator does not support the set operation.



Key Points:

This method works by randomly permuting the list elements
Runs in linear time. If the provided list does not implement the RandomAccess interface, like LinkedList and is large, it first copies the list into an array, then shuffles the array copy, and finally copies array back into the list. This makes sure that the time remains linear.
It traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the “current position”. Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

What is the difference between HTTP & HTTPS? What is SSL?

What is the difference between HTTP & HTTPS? What is SSL?

Ans:

HTTP stands for Hypertext Transfer Protocol responsible for exchange of Hypertext objects over the internet,

HTTPS stands for Hypertext Transfer Protocol Secure responsible for exchange of Hypertext objects over the internet in a secure manner.In HTTPS the Browser and requested Website interact securely by introducing encryption amongst themselves.Thus, the interaction becomes more secure.It utilizes the SSL(Secure Socket Layer),also called as TLS(Transport Layer Security),to introduce encryption link between the Browser and the Website.

Both HTTP and HTTPS are Application Layer protocol of the OSI(Open System Intercaonnection) Model.HTTPS is more widely used due to the newly introduced functionallty of communicating with the website in a secure manner with the help of SSL/TLS.

Microsoft Interview Question:Sort a list of 0's ,1's and 2's solution in java

Solution:

 Traverse the list and count the number of 0s, 1s and 2s.
 Let the counts be node1, node2 and node3 respectively.
 Traverse the list again, fill the first node1 nodes with 0, then node2 nodes with 1 and finally node3 nodes with 2 .

Sample code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class SortLinkedList
{
Node head;

class Node
{
int data;
Node next;

public Node(int d) {

this.data=d;
next=null;
}
}

void push(int new_data)
{
Node node=new Node(new_data);
node.next=head;
head=node;
}

void printList()
{
Node temp=head;
while(temp!=null)
{
System.out.println(temp.data + " ");
temp=temp.next;
}
System.out.println();
}

void sortList()
{
int count[]={0,0,0};
Node ptr=head;
while(ptr!=null)
{
count[ptr.data]++;
ptr=ptr.next;
}

int i=0;
ptr=head;

while(ptr!=null)
{
if(count[i]==0)
i++;
else
{
ptr.data=i;
   --count[i];
   ptr=ptr.next;
}
}

}

public static void main(String[] args) {
// TODO Auto-generated method stub

SortLinkedList list=new SortLinkedList();
list.push(0);
list.push(1);
list.push(0);
list.push(2);
        list.push(1);
        list.push(1);
        list.push(2);
        list.push(1);
        list.push(2);
       
        System.out.println("Linked List before sorting");
        list.printList();
       
        list.sortList();

        System.out.println("Linked List after sorting");
        list.printList();
}

}

Output:

Linked List before sorting

2 

1 

2 

1 

1 

2 

0 

1 

0 

Linked List after sorting

0 

0 

1 

1 

1 

1 

2 

2 

2 

Solution Complexity: 

Time Complexity: O(n) where n is number of nodes in linked list.

Auxiliary Space: O(1)

#### Android Application Design and Development Principles for Seamless Experience ####

## Android Application Design and Development Principles for Seamless Experience ###

  For any application,there are some if's and but's.i mean to say you should have to follow some coding and design guidelines for the seamless experience.
Specially, for developers.You should take care few points which i am going to discuss below:

  1) Do not try to inflict the whole application in any sort of MVC,MVP,MVVM .etc patterns.there are two things can happen.one is, it can make your application  in good shape or even worse that you will have to re-write your whole application which is very impossible kind of effort, specially in service based companies.my whole intent is the project complexity in terms of performance,UI Experience,Code Readability,Flexibility and specially OOP's concept implementation. So,i mean to say you should not inflict instead you try your own but make it more OOPS wise intact then maintain some general code standard of Java.that's it.i can give you assurance that it will be more reliable and maintainable code.now lets discuss about Android Application Development perspective:

  2) Even if your application is fast and responsive there are few points design decisions can still cause  problems for users:
 
    a)Unplanned Interaction with the other applications or dialogs

    b)carelessness about data

    c)Unintended Blocking

To avoid these problems,it helps to understand the context in which your applications run and the system interactions that can affect your application.In short, you should strive to develop an application that interacts seamlessly with the system and with other applications.you

3) Let me tell you a very common problem in android is when an application's background process.a service or broadcast receiver — pops up a dialog in response to some event. This may seem like harmless behavior, especially when you are building and testing your application in isolation, on the emulator. However, when your application is run on an actual device, your application may not have user focus at the time your background process displays the dialog. So it could end up that your application would display it's dialog behind the active application, or it could take focus from the current application and display the dialog in front of whatever the user was doing (such as dialing a phone call, for example). That behavior would not work for your application or for the user.
To avoid these problems, your application should use the proper system facility for notifying the user — the Notification classes. Using notifications, your application can signal the user that an event has taken place, by displaying an icon in the status bar rather than taking focus and interrupting the user.

4)Let me again come up with another seamlessness problem is when an activity inadvertently loses state or user data because it doesn't correctly implement the onPause() and other lifecycle methods. Or, if your application exposes data intended to be used by other applications, you should expose it via a ContentProvider, rather than (for example) doing so through a world-readable raw file or database.

What those examples have in common is that they involve cooperating nicely with the system and other applications. The Android system is designed to treat applications as a sort of federation of loosely-coupled components, rather than chunks of black-box code. This allows you as the developer to view the entire system as just an even-larger federation of these components. This benefits you by allowing you to integrate cleanly and seamlessly with other applications, and so you should design your own code to return the favor.

5)Don't Drop Data:  It is very obvious to say that and it's important to remember that another Activity can pop up over your own Activity at any moment. This will fire the onSaveInstanceState() and onPause() methods, then at any point your application can be killed.

If the user was editing data in your application when the other Activity appeared, your application will likely lose that data when your application is killed.
Unless,you save the work in progress first. The "Android Way" is to do just that: Android applications that accept or edit input should override the onSaveInstanceState() method and save their state in some appropriate fashion. When the user revisits the application, she should be able to retrieve her data.

A classic example of a good use of this behavior is a mail application. If the user was composing an email when another Activity started up, the application should save the in-process email as a draft.Always keep in mind that Android is a mobile platform.

6)Don't Expose Raw Data: 

Exposing raw data requires other applications to understand your data format; if you change that format, you'll break any other applications that aren't similarly updated.

The "Android Way" is to create a ContentProvider to expose your data to other applications via a clean, well-thought-out, and maintainable API. Using a ContentProvider is much like inserting a Java language interface to split up and componentize two tightly-coupled pieces of code. This means you'll be able to modify the internal format of your data without changing the interface exposed by the ContentProvider, and this without affecting other applications .

7)Don't Interrupt the User:If the user is running an application (such as the Phone application during a call) it's a pretty safe bet he did it on purpose. That's why you should avoid spawning activities except in direct response to user input from the current Activity.I mean to say that .That is, don't call startActivity() from BroadcastReceivers or Services running in the background. if you do that then whatever application is currently running, and result in an annoyed user. Perhaps even worse, your Activity may become a "keystroke bandit" and receive some of the input the user was in the middle of providing to the previous Activity. Depending on what your application does, this could be application crash or bad news for you.Instead of spawning Activity UIs directly from the background, you should instead use the NotificationManager to set Notifications. These will appear in the status bar, and the user can then click on them at his leisure, to see what your application has to show him.

8)Got a Lot to Do? Do it in a Thread: 

If your application needs to perform some expensive or long-running computation, you should probably move it to a thread. This will prevent the dreaded "Application Not Responding" dialog from being displayed to the user, with the ultimate result being the fiery demise of your application.

By default, all code in an Activity as well as all its Views run in the same thread. This is the same thread that also handles UI events. For example, when the user presses a key, a key-down event is added to the Activity's main thread's queue. The event handler system needs to dequeue and handle that event quickly; if it doesn't, the system concludes after a few seconds that the application is hung and offers to kill it for the user.

If you have long-running code, running it inline in your Activity will run it on the event handler thread, effectively blocking the event handler. This will delay input processing, and result in the ANR dialogs. To avoid this, move your computations to a thread.

Now i am goig to discuss the very importpart of the Application and i have seen 90% people does this mistake whiole android application development.


9)Don't Overload a Single Activity Screen:

Any application worth using will probably have several different screens. When designing the screens of your UI, be sure to make use of multiple Activity object instances.

Depending on your development background, you may interpret an Activity as similar to something like a Java Applet, in that it is the entry point for your application. However, that's not quite accurate: where an Applet subclass is the single entry point for a Java Applet, an Activity should be thought of as one of potentially several entry points to your application. The only difference between your "main" Activity and any others you might have is that the "main" one just happens to be the only one that expressed an interest in the "android.intent.action.MAIN" action in your AndroidManifest..xml file.

So, when designing your application, think of your application as a federation of Activity objects. This will make your code a lot more maintainable in the long run, and as a nice side effect also plays nicely with Android's application history and "backstack" model.

10) Assume the Network is Slow: Android devices will come with a variety of network-connectivity options. All will have some data-access provision, though some will be faster than others. The lowest common denominator, however, is GPRS, the non-3G data service for GSM networks. Even 3G-capable devices will spend lots of time on non-3G networks, so slow networks will remain a reality for quite a long time to come.

That's why you should always code your applications to minimize network accesses and bandwidth. You can't assume the network is fast, so you should always plan for it to be slow. If your users happen to be on faster networks, then that's great — their experience will only improve. You want to avoid the inverse case though: applications that are usable some of the time, but frustratingly slow the rest based on where the user is at any given moment are likely to be unpopular.

One potential gotcha here is that it's very easy to fall into this trap if you're using the emulator, since the emulator uses your desktop computer's network connection. That's almost guaranteed to be much faster than a cell network, so you'll want to change the settings on the emulator that simulate slower network speeds. You can do this in Android Studio via the AVD Manager or via a command-line option when starting the emulator.

11) Do Conserve the Device Battery:Two of the biggest consumers of battery power are the processor, and the radio; that's why it's important to write your applications to do as little work as possible, and use the network as infrequently as possible.

Minimizing the amount of processor time your application uses really comes down to writing efficient code. To minimize the power drain from using the radio, be sure to handle error conditions gracefully, and only fetch what you need. For example, don't constantly retry a network operation if one failed. If it failed once, it's likely because the user has no reception, so it's probably going to fail again if you try right away; all you'll do is waste battery power.

Users are pretty smart: if your program is power-hungry, you can count on them noticing. The only thing you can be sure of at that point is that your program won't stay installed very long.


So atlast i would like to conclude here that is if any developer follows thease simple steps for his application development then i can bet his or her application
would be not just seamless rather it would be fast,reliable,more battery conserve and will work great in the slow ans fast network.All together it will be
great experience.













      

Amazon Interview Question:Find the element that appears once in Java

 Question:  Find the element that appears once
 
   Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
   Output: 2

Explanation:

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.

Solution:

Before going to further discussion. first lets understand the XOR operation:

Lets see some XOR operation,

  1.   5 ^ 5     = 0101 ^ 0101 = 0000
  2.   1 ^ 1     = 0001 ^ 0001 = 0000
  3.   10 ^ 10 = 1010 ^ 1010 = 0000

From the above few operation, we can see that when a number is XOR with same number then result is 0.

Also XOR is Associative and Commutative, it means

Associative    = giving the same result regardless of grouping,

i.e. so that a*(b*c)=(a*b)*c

Commutative = independent of order;

as in e.g. "a x b = b x a"

1.  1 ^ 1 = 0
2.  1 ^ 1 ^ 2 ^ 2 = 0
3.  1 ^ 2 ^ 1 ^ 2 = 0

Irrespective of order, when a same number will be XOR twice then result will be 0.

We can use sorting to do it in O(nLogn) time. We can also use hashing, but the worst case time complexity of but hashing requires extra space.


The idea is to use bitwise operators for a solution that is O(n) time and uses O(1) extra space.
The solution is not easy like other XOR based solutions, because all elements appear odd number of times here. The idea is taken from here.

Run a loop for all elements in array. At the end of every iteration, maintain following two values.

ones: The bits that have appeared 1st time or 4th time or 7th time .. etc.

twos: The bits that have appeared 2nd time or 5th time or 8th time .. etc.

Finally, we return the value of ‘ones’

How to maintain the values of ‘ones’ and ‘twos’?

‘ones’ and ‘twos’ are initialized as 0.

For every new element in array, find out the common set bits in the new element and previous value of ‘ones’.
These common set bits are actually the bits that should be added to ‘twos’. So do bitwise OR of the common set bits with ‘twos’. ‘twos’ also gets some extra bits that appear third time. These extra bits are removed later.

Update ‘ones’ by doing XOR of new element with previous value of ‘ones’. There may be some bits which appear 3rd time. These extra bits are also removed later.

Both ‘ones’ and ‘twos’ contain those extra bits which appear 3rd time. Remove these extra bits by finding out common set bits in ‘ones’ and ‘twos’.

Sample Code:

import java.io.*;

class GFG
{
public static void main (String[] args)
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3};
                 System.out.println(findElementThatAppearOnce(arr));
}

private static int findElementThatAppearOnce(int arr[])
{
  int result = 0;
  for (int i=0; i<arr.length; i++)
  {
   result = result ^ arr[i];
  }
  return result;
 }
}

Output:

12

Time Complexity: O(n)
Auxiliary Space: O(1)