Graph Data Structure And Algorithms

• A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as,A Graph consists of a finite set of vertices(or nodes) and set of Edges which connect a pair of nodes.
• In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.
• Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc.

Continue Reading

Java Serialization and Customized Serialisation

• Serialization
• Serialization is a mechanism of converting the state of an object into a byte stream. Deserialization is the reverse process where the byte stream is used to recreate the actual Java object in memory. This mechanism is used to persist the object.
• The byte stream created is platform independent. So, the object serialized on one platform can be deserialized on a different platform.
• To make a Java object serializable we implement the java.io.Serializable interface.
• The ObjectOutputStream class contains writeObject() method for serializing an Object.
• The ObjectInputStream class contains readObject() method for deserializing an object.
• readResolve()
• This ensures that nobody can create another instance by serializing and deserializing the singleton.
• Advantages of Serialization
• To travel an object across a network.

• To save/persist state of an object.
• 
• 
  
• Only the objects of those classes can be serialized which are implementing java.io.Serializable interface. Serializable is a marker interface (has no data member and method). It is used to “mark” java classes so that objects of these classes may get certain capability.
• Other examples of marker interfaces are:- Cloneable and Remote.
• Points to remember
•  If a parent class has implemented Serializable interface then child class doesn’t need to implement it but vice-versa is not true.
• Only non-static data members are saved via Serialization process.
• Static data members and transient data members are not saved via Serialization process.So, if you don’t want to save value of a non-static data member then make it transient.
•  Constructor of object is never called when an object is deserialized.
• SerialVersionUID
• The Serialization runtime associates a version number with each Serializable class called a SerialVersionUID, which is used during Deserialization to verify that sender and reciever of a serialized object have loaded classes for that object which are compatible with respect to serialization. 
• If the reciever has loaded a class for the object that has different UID than that of corresponding sender’s class, the Deserialization will result in an InvalidClassException. A Serializable class can declare its own UID explicitly by declaring a field name.
• Example
• // Java program to illustrate loss of information // because of transient keyword. import java.io.*; class GfgAccount implements Serializable { String username = "gfg_admin"; transient String pwd = "geeks"; } class CustomizedSerializationDemo { public static void main(String[] args) throws Exception { GfgAccount gfg_g1 = new GfgAccount(); System.out.println("Username : " + gfg_g1.username + " Password : " + gfg_g1.pwd); FileOutputStream fos = new FileOutputStream("abc.ser"); ObjectOutputStream oos = new ObjectOutputStream(fos); // writeObject() method present in GfgAccount class // will be automatically called by jvm oos.writeObject(gfg_g1); FileInputStream fis = new FileInputStream("abc.ser"); ObjectInputStream ois = new ObjectInputStream(fis); // readObject() method present GfgAccount class // will be automatically called by jvm GfgAccount gfg_g2 = (GfgAccount)ois.readObject(); System.out.println("Username : " + gfg_g2.username + " Password : " + gfg_g2.pwd); } } ############### OUTPUT ############### Username : gfg_admin Password : geeks Username : gfg_admin Password : null
• Customized Serialisation
• During serialization, there may be data loss if we use the ‘transient’ keyword. ‘Transient’ keyword is used on the variables which we don’t want to serialize. But sometimes, it is needed to serialize them in a different manner than the default serialization (such as encrypting before serializing etc.), in that case, we have to use custom serialization and deserialization.
• Customized serialization can be implemented using the following two methods:
• private void writeObject(ObjectOutputStream oos) throws Exception: 
• This method will be executed automatically by the jvm(also known as Callback Methods) at the time of serialization. Hence to perform any activity during serialization, it must be defined only in this method.
• private void readObject(ObjectInputStream ois) throws Exception:
•  This method will be executed automatically by the jvm(also known as Callback Methods) at the time of deserialization. Hence to perform any activity during deserialization, it must be defined only in this method.
• Example
• import java.io.*; class GfgAccount implements Serializable { String username = "gfg_admin"; transient String pwd = "geeks"; // Performing customized serialization using the below two methods: // this method is executed by jvm when writeObject() on // Account object reference in main method is // executed by jvm. private void writeObject(ObjectOutputStream oos) throws Exception { // to perform default serialization of Account object. oos.defaultWriteObject(); // epwd (encrypted password) String epwd = "123" + pwd; // writing encrypted password to the file oos.writeObject(epwd); } // this method is executed by jvm when readObject() on // Account object reference in main method is executed by jvm. private void readObject(ObjectInputStream ois) throws Exception { // performing default deserialization of Account object ois.defaultReadObject(); // deserializing the encrypted password from the file String epwd = (String)ois.readObject(); // decrypting it and saving it to the original password // string starting from 3rd index till the last index pwd = epwd.substring(3); } } class CustomizedSerializationDemo { public static void main(String[] args) throws Exception { GfgAccount gfg_g1 = new GfgAccount(); System.out.println("Username :" + gfg_g1.username + " Password :" + gfg_g1.pwd); FileOutputStream fos = new FileOutputStream("abc.ser"); ObjectOutputStream oos = new ObjectOutputStream(fos); // writeObject() method on Account class will // be automatically called by jvm oos.writeObject(gfg_g1); FileInputStream fis = new FileInputStream("abc.ser"); ObjectInputStream ois = new ObjectInputStream(fis); GfgAccount gfg_g2 = (GfgAccount)ois.readObject(); System.out.println("Username :" + gfg_g2.username + " Password :" + gfg_g2.pwd); } } ############### OUTPUT ############### Username :gfg_admin Password :geeks Username :gfg_admin Password :geeks

Continue Reading

Java Innerclass

• Inner class is a class defined inside other class and act like a member of the enclosing class.
• There are two main types of inner classes
• Static member class
• Inner class
• Member class
• Anonymous class
• Local class
• Static member class
• A static member class behaves much like an ordinary top-level class, except that it can access the static members of the outer. 
• Outer class can access all inner class fields by referring Inner Class.(InnerA.printAnimal()). But inner class can access all static outer class properties and methods directly.
• Both inner and outer classes can access others private properties and methods.
• The static nested class can be accessed as the other static members of the enclosing class without having an instance of the outer class.
•  The static class can contain non-static and static members and methods.
• InnerClassTest1.java
• public class InnerClassTest1 { private static int out = 1; public static class innerA { private static int number = 10; static void printAnimal(String animal) { System.out.println(out); System.out.println(animal); test(); } } private static void test() { System.out.println(innerA.number); } }
• App.java
• public class App { public static void main(String[] args) { InnerClassTest1.innerA.printAnimal("Tiger"); } }
• Member class
• Need to create Instance access properties and class out side the method.
• Need Outer class object to create inner class object.
• The member class can be declared as public, private, protected, final and abstract. E.g.
• InnerClassTest2.java
• public class InnerClassTest2 { private int out = 1; public class MemberClass { private void showName() { System.out.println("Sonu"); System.out.println(out); } } public void test() { MemberClass m = new MemberClass(); m.showName(); } }
• App.java
• public class App { public static void main(String[] args) { InnerClassTest2 o = new InnerClassTest2(); InnerClassTest2.MemberClass m = o.new MemberClass(); } }
• Local class
• It can be accessed only from same method.
• Local classes cannot be public, private, protected, or static. (No access modifiers)
• Local class can access all outer class properties and methods.
• local class can access local variables and parameters of the enclosing method that are effectively final.
• InnerClassTest3.java
• public class InnerClassTest3 { int outerNumber = 1; public void methodTest() { int methodNumber = 2; class MethodLocalClass { private void showName() { System.out.println("SONU"); System.out.println(outerNumber); System.out.println(methodNumber); test(); } } methodNumber = 2; //error outerNumber =3; //will work MethodLocalClass m = new MethodLocalClass(); m.showName(); } public void test() { System.out.println("TEST"); } }
• Anonymous class
• These are local classes which are automatically declared and instantiated in the middle of an expression. 
• Also, like local classes, anonymous classes cannot be public, private, protected, or static. 
• They can define in the  arguments to the constructor of the outerclass, but cannot otherwise have a constructor.
• They can implement only one interface or extend a class.
• Anonymous class cannot define any static fields, methods, or classes, except for static final constants.
• xxxx

Continue Reading

LinkedList and Index

1. They have a logical index, yes - effectively the number of times you need to iterate, starting from the head, before getting to that node.
2. it can't directly search using index of the object
3. Typically O(1) access by index is performed by using an array lookup, and in the case of a linked list there isn't an array - there's just a chain of nodes. To access a node with index N, you need to start at the head and walk along the chain N times... which is an O(N) operation.
4. import java.util.LinkedList; import java.util.List; import java.util.function.Supplier; import java.util.stream.Collectors; import java.util.stream.IntStream; public class LnkedListNthh { public static void main(String[] args) { LnkedListNthh app = new LnkedListNthh(); LinkedList list = app.createList(); app.nthElement(list, 2); app.SecondLastElement(list); } private void nthElement(LinkedList list, Integer n) { list.get(n); System.out.println(n + "th Element is " + list.get(n)); } private void SecondLastElement(LinkedList list) { System.out.println("SecondLastElement = " + list.get(list.size() - 1)); } private LinkedList createList() { LinkedList list = new LinkedList(); Supplier> supplier = () -> new LinkedList(); return (LinkedList) IntStream.range(2, 102).boxed().collect(Collectors.toCollection(supplier)); } }

Continue Reading

Java 8 New

1. Function Interface
1.  Java.util.function has special interface like bleow, it contains generic methods used as type for lambda expression with same type and signature.
2. An interface with exactly one abstract method is called Functional Interface.
3. @FunctionalInterface annotation is added so that we can mark an interface as functional interface.
4.  If  we try to have more than one abstract method, it throws compiler error.
5. The major benefit of java 8 functional interfaces is that we can use lambda expressions to instantiate them and avoid using bulky anonymous class implementation.
6. Java 8 has defined a lot of functional interfaces in java.util.function package. Some of the useful java 8 functional interfaces are Runnable, Consumer, Supplier, Function and Predicate
1. Custom
1. @FunctionalInterface public interface Square { public int calculate(int number); } // Custom Square sq = (i) -> (i * i); int result = sq.calculate(2); System.out.println(result);
2. Runnable
1. Thread t = new Thread(() -> { System.out.println("Thread Running"); }); t.start();
3. Predecate Interface
1. The Functional Interface PREDICATE is defined in the java.util.Function package.It improves manageability of code, helps in unit-testing them separately, and contain some methods like:
1. isEqual(Object targetRef) : Returns a predicate that tests if two arguments are equal according to Objects.equals(Object, Object).
2. and(Predicate other) : Returns a composed predicate that represents a short-circuiting logical AND of this predicate and another.
3. negate() : Returns a predicate that represents the logical negation of this predicate.
4. or(Predicate other) : Returns a composed predicate that represents a short-circuiting logical OR of this predicate and another.
5. test(T t) : Evaluates this predicate on the given argument.boolean test(T t)
2. // Simple Predicate Predicate lesserThan = (i) -> (i > 10); System.out.println(lesserThan.test(11)); // Predicate Chaining Predicate lessThan = (i) -> (i < 10); Predicate greaterThan = (i) -> (i > 5); boolean result = lesserThan.and(greaterThan).test(6); System.out.println(result); // negation boolean result2 = lesserThan.and(greaterThan).negate().test(6); System.out.println(result2); Predicate equals = (i) -> (i == 2); boolean result3 = equals.test(2); System.out.println(result3);
2. Static methods and Default methods
1. Default methods
1. Java 8 interface changes include static methods and default methods in interfaces. Prior to Java 8, we could have only method declarations in the interfaces. But from Java 8, we can have default methods and static methods in the interfaces.
2. For creating a default method in java interface, we need to use “default” keyword with the method signature. For example,
3. public interface Interface2 { void method2(); default void log(String str){ System.out.println("I2 logging::"+str); } }
2. Static methods 
1. Java interface static method is similar to default method except that we can’t override them in the implementation classes.
2. public interface MyData { default void print(String str) { if (!isNull(str)) System.out.println("MyData Print::" + str); } static boolean isNull(String str) { System.out.println("Interface Null Check"); return str == null ? true : "".equals(str) ? true : false; } }
3. Java interface static methods are good for providing utility methods, for example null check, collection sorting etc.
3. Abstract Class Needs
1. Abstract class can define constructor. They are more structured and can have a state associated with them. 
2. The constraint on the default method is that it can be implemented only in the terms of calls to other interface methods, with no reference to a particular implementation's state. So the main use case is higher-level and convenience methods.

Continue Reading

Inheritance and Conditions

1. When Parent throws Generic Exception and Child throws specific exception
1. Compiles and run successfully
2. public class Animal { public void eat() throws Exception { System.out.println("Animal Eating..."); } } public class Cat extends Animal { @Override public void eat() throws FileNotFoundException { System.out.println("Cat Eating ....."); } } public class App { public static void main(String[] args) throws Exception { Animal cat = new Cat(); cat.eat(); } } ######### RESULT ########## Cat Eating .....
2. When Parent throws specific exception and child throws generic exception
1. Compile time error
3. When Parent modifier is protected and child modifier is public
1. Compiles and run successfully
4. When Parent modifier is private and child modifier is public
1. Compile time error
5. When Parent modifier is public and child modifier is private
1. Compile time error

Continue Reading

Java clone object – cloning in java

• Java Object class comes with native clone() method that returns the copy of the existing instance.
• To use java object clone method, we have to implement the marker interface java.lang.Cloneable so that it won’t throw CloneNotSupportedException at runtime.
• Also Object clone is a protected method, so we will have to override it to use with other classes
• Student.java
• public class Student implements Cloneable { private int id; private String name; public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override protected Object clone() throws CloneNotSupportedException { return super.clone(); } }
• App.java
• public class App { public static void main(String[] args) throws CloneNotSupportedException { Student student1 = new Student(); student1.setId(1); student1.setName("Sonu"); Student student2 = (Student) student1.clone(); System.out.println(student2.getName()); if (student1.equals(student2)) { System.out.println("EQUAL"); } } }
• s1 == s2: false
• So s1 and s2 are two different object, not referring to same object. This is in agreement of the java clone object requirement.
• s1.name == s2.name: true
• So both s1 and s2 object variables refer to same object.
• Shallow copy
• Shallow copy is a bit-wise copy of an object. A new object is created that has an exact copy of the values in the original object. If any of the fields of the object are references to other objects, just the reference addresses are copied i.e., only the memory address is copied.
• Deep copy
• A deep copy copies all fields, and makes copies of dynamically allocated memory pointed to by the fields. A deep copy occurs when an object is copied along with the objects to which it refers.

Continue Reading

Structural design patterns

Structural design patterns are concerned with how classes and objects can be composed, to form larger structures.The structural design patterns simplifies the structure by identifying the relationships.These patterns focus on, how the classes inherit from each other and how they are composed from other classes.

• Adapter Pattern 
• An Adapter Pattern says that just "converts the interface of a class into another interface that a client wants".
• In other words, to provide the interface according to client requirement while using the services of a class with a different interface.
• The Adapter Pattern is also known as Wrapper.

Continue Reading

Java Objet and Object Reference Variable

• An object is chunk of memory , and the reference to the object is way to reach up to that object in the memory
• Object reference variable contains address of the object which is declared in the heap memory
• Class Box { double height; double width; double depth; } Box b1; //declare reference ..it will be null b1 = new Box(); //Create an instance assign to reference variable b1 Box b2 = b1; //Only creates reference to this object.. will not create object memory..use same object memory..
• Now I  am going to set some property in b1
• b1.height = 10; b1.width = 20; b1.depth = 30;
• Then I printed b2 properties
• System.out.println(b2.height); System.out.println(b2.width); System.out.println(b2.depth); //output 10 20 30
• I got same values for b2, because it using same memory but different reference

Continue Reading

Quick Sort in java

• This algorithm uses idea of divide and conquer.
• Find the element called pivot which divides the array into two halves
• Left side elements should be smaller than the pivot
• Right side elements are geater than the pivot
• Steps
• Bring the pivot to its appropriate position such that left of the pivot is smaller and right is greater.
• Quick sort left part
• Quick sort right part
• There are many different versions of quickSort that pick pivot in different ways.
• Always pick first element as pivot.
• Always pick last element as pivot (implemented below)
• Pick a random element as pivot.
• Pick median as pivot
• 
  
• Reference:

Continue Reading

Implement Producer Consumer Pattern using Semaphores

• Create shared Semaphore object , lock and unlock in consumer - producer  blocks by limiting thread accessible count to 1
• Output will be like produce 1 and consume 1 , produce 2 and consume 2 ...
• Producer.java
• public class Producer implements Runnable { private static List LIST; private static Semaphore semaphore; public Producer(List LISTv, Semaphore semaphoreV) { LIST = LISTv; semaphore = semaphoreV; } public void run() { produce(); } private static void produce() { try { int i = 1; while (true) { semaphore.acquire(); LIST.add(i); System.out.println(i + " Produced"); i++; semaphore.release(); if (i > 100) { break; } } } catch (Exception e) { e.printStackTrace(); } } }
• Consumer.java
• public class Consumer implements Runnable { private static List LIST; private static Semaphore semaphore; public Consumer(List LISTv, Semaphore semaphoreV) { LIST = LISTv; semaphore = semaphoreV; } public void run() { consume(); } private static void consume() { int index = 0; try { while (true) { semaphore.acquire(); index = LIST.size() - 1; System.out.println(LIST.get(index) + " Removed"); LIST.remove(index); semaphore.release(); } } catch (Exception e) { e.printStackTrace(); } } }
• App.java
• public class App { private static List LIST = new ArrayList(); private static Semaphore SEMAPHORE = new Semaphore(1, true); public static void main(String[] args) { Thread producer = new Thread(new Producer(LIST, SEMAPHORE)); Thread consumer = new Thread(new Consumer(LIST, SEMAPHORE)); producer.start(); consumer.start(); } }
• Output
• 1 Produced 1 Removed 2 Produced 2 Removed 3 Produced 3 Removed 4 Produced 4 Removed 5 Produced 5 Removed 6 Produced 6 Removed 7 Produced 7 Removed 8 Produced 8 Removed 9 Produced 9 Removed 10 Produced 10 Removed

Continue Reading

Implement Producer Consumer Pattern using Blocking Queue

• BlockingQueue amazingly simplifies implementation of Producer-Consumer design pattern by providing outofbox support of blocking on put() and take().
• No need of manual empty or full check, Blocking Queue handle it internally.
• Only put and take operation required
• Output is like one N produce and then consume like FIFO ordedr
• Producer.java
• public class Producer implements Runnable { private static BlockingQueue QUEUE; public Producer(BlockingQueue QUEUE_V) { QUEUE = QUEUE_V; } public void run() { try { int i = 1; while (true) { QUEUE.put(i); System.out.println(i + " Produced"); i++; } } catch (Exception e) { e.printStackTrace(); } } }

Consumer.java

• public class Consumer implements Runnable { private static BlockingQueue QUEUE; public Consumer(BlockingQueue QUEUE_V) { QUEUE = QUEUE_V; } public void run() { consumer(); } private static void consumer() { int item; try { Thread.sleep(1000); while (true) { item = QUEUE.take(); System.out.println(item + " Consumed"); } } catch (Exception e) { e.printStackTrace(); } } }

App.java

• private static BlockingQueue QUEUE = new ArrayBlockingQueue(10); public static void main(String[] args) { Thread producer = new Thread(new Producer(QUEUE)); Thread consumer = new Thread(new Consumer(QUEUE)); producer.start(); consumer.start(); }

Output

• 1 Produced 2 Produced 3 Produced 4 Produced 5 Produced 6 Produced 7 Produced 8 Produced 9 Produced 10 Produced 1 Consumed 11 Produced 2 Consumed 3 Consumed 4 Consumed 5 Consumed 12 Produced 6 Consumed 13 Produced 7 Consumed 14 Produced 8 Consumed 15 Produced 9 Consumed 16 Produced 10 Consumed 17 Produced 11 Consumed 18 Produced

Continue Reading

Producer Consumer Problem using Synchronized block

• If List is full then our PRODUCER thread waits until CONSUMER thread consume one item and make space in your queue and call notify() method to inform PRODUCER thread. Both wait() and notify() method are called on shared object which is List in our case.
• Need synchronised block
• Check for List size manually and wait for consumer and producer threads
• Since it is synchronised,
• Needs to wait till N production
• Needs to wait till N Consumption
• Producer.java
• public class Producer implements Runnable { private static List LIST; private static int SIZE; public Producer(List LIST_V, int SIZE_V) { LIST = LIST_V; SIZE = SIZE_V; } public void run() { producer(); } private static void producer() { try { int i = 1; while (true) { synchronized (LIST) { if (LIST.size() == SIZE) { System.out.println("Producer Waiting for consumer to consume object"); LIST.wait(); } LIST.add(i); System.out.println(i + " Produced"); LIST.notify(); } i++; if (i > 100) { break; } } } catch (Exception e) { e.printStackTrace(); } } }
• Consumer.java
• public class Consumer implements Runnable { private static List LIST; public Consumer(List LIST_V) { LIST = LIST_V; } public void run() { consumer(); } private static void consumer() { int index = 0; try { Thread.sleep(2000); while (true) { synchronized (LIST) { if (LIST.size() == 0) { System.out.println("Consumer is waiting for producer to produce"); LIST.wait(); } System.out.println(LIST.get(index) + " Consumed"); LIST.remove(index); LIST.notify(); } } } catch (Exception e) { e.printStackTrace(); } } }
• App.java
• public class App { private static List LIST = new ArrayList(); private static int SIZE = 10; public static void main(String[] args) { Thread producer = new Thread(new Producer(LIST, SIZE)); Thread consumer = new Thread(new Consumer(LIST)); producer.start(); consumer.start(); } }
• Output
• 1 Produced 2 Produced 3 Produced 4 Produced 5 Produced 6 Produced 7 Produced 8 Produced 9 Produced 10 Produced Producer Waiting for consumer to consume object 1 Consumed 2 Consumed 3 Consumed 4 Consumed 5 Consumed 6 Consumed 7 Consumed 8 Consumed 9 Consumed 10 Consumed Consumer is waiting for producer to produce 11 Produced 12 Produced 13 Produced

Continue Reading

LRU Cache Implementaion

• LRU Cache (Java) Design and implement a data structure for Least Recently Used (LRU) cache. 
• The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.
• Properties are,
• Fixed Size: Cache needs to have some bounds to limit memory usages.
• Fast Access: Cache Insert and lookup operation should be fast , preferably O(1) time.
• Replacement of Entry in case , Memory Limit is reached: A cache should have efficient algorithm to evict the entry when memory is full.
• When we think about O(1) lookup , obvious data structure comes in our mind is HashMap. HashMap provide O(1) insertion and lookup.
• but HashMap does not has mechanism of tracking which entry has been queried recently and which not.To track this we require another data-structure which provide fast insertion ,deletion and updation , in case of LRU we use Doubly Linkedlist . 
• Reason for choosing doubly LinkList is O(1) deletion , updation and insertion if we have the address of Node on which this operation has to perform.
•  HashMap will hold the keys and address of the Nodes of Doubly LinkedList . And Doubly LinkedList will hold the values of keys.
• As We need to keep track of Recently used entries, We will use a clever approach. We will remove element from bottom and add element on start of LinkedList and whenever any entry is accessed , it will be moved to top. so that recently used entries will be on Top and Least used will be on Bottom.

• package com.iwq.LRU.withhashmap; import java.util.HashMap; import java.util.Map; public class LRUcache { Map hashmap = new HashMap(); Entry start; Entry end; int LRU_SIZE = 4; public void put(int key, int value) { // if key already exists update value and move to top if (hashmap.containsKey(key)) // Key Already Exist, just update the value and move it to top { Entry entry = hashmap.get(key); entry.value = value; removeNode(entry); addAtTop(entry); } else { Entry newnode = new Entry(); newnode.left = null; newnode.right = null; newnode.value = value; newnode.key = key; if (hashmap.size() > LRU_SIZE) // We have reached maxium size so need to make room for new element. { hashmap.remove(end.key); removeNode(end); addAtTop(newnode); } else { addAtTop(newnode); } hashmap.put(key, newnode); } } public void removeNode(Entry node) { // remove from left and right nodes if (node.left != null) { node.left.right = node.right; } else { start = node.right; } if (node.right != null) { node.right.left = node.left; } else { end = node.left; } } public void addAtTop(Entry node) { // node.right = start; node.left = null; if (start != null) start.left = node; start = node; if (end == null) end = start; } }

Continue Reading

Java Memory Management

• Java Memory Management, with its built-in garbage collection, is one of the language's finest achievements
•  It allows developers to create new objects without worrying explicitly about memory allocation and deallocation, because the garbage collector automatically reclaims memory for reuse
• How Garbage Collection Really Works
• Many people think garbage collection collects and discards dead objects. In reality, Java garbage collection is doing the opposite! Live objects are tracked and everything else designated garbage.
• Object creation is faster because global synchronization with the operating system is not needed for every single object. An allocation simply claims some portion of a memory array and moves the offset pointer forward . The next allocation starts at this offset and claims the next portion of the array.
• When an object is no longer used, the garbage collector reclaims the underlying memory and reuses it for future object allocation. This means there is no explicit deletion and no memory is given back to the operating system.

• All objects are allocated on the heap area managed by the JVM. Every item that the developer uses is treated this way, including class objects, static variables, and even the code itself. As long as an object is being referenced, the JVM considers it alive. Once an object is no longer referenced and therefore is not reachable by the application code, the garbage collector removes it and reclaims the unused memory.
• There are four kinds of GC roots in Java:
• Local variables are kept alive by the stack of a thread. This is not a real object virtual reference and thus is not visible. For all intents and purposes, local variables are GC roots. 
• Active Java threads are always considered live objects and are therefore GC roots. This is especially important for thread local variables. 
• Static variables are referenced by their classes. This fact makes them de facto GC roots. Classes themselves can be garbage-collected, which would remove all referenced static variables. This is of special importance when we use application servers, OSGi containers or class loaders in general. We will discuss the related problems in the Problem Patterns section.
• JNI References are Java objects that the native code has created as part of a JNI call. Objects thus created are treated specially because the JVM does not know if it is being referenced by the native code or not. Such objects represent a very special form of GC root, which we will examine in more detail in the Problem Patterns section below.
• Marking and Sweeping Away Garbage
• To determine which objects are no longer in use, the JVM intermittently runs what is very aptly called a mark-and-sweep algorithm
• it's a straightforward, two-step process:
• The algorithm traverses all object references, starting with the GC roots, and marks every object found as alive.
• All of the heap memory that is not occupied by marked objects is reclaimed. It is simply marked as free, essentially swept free of unused objects.
• It's possible to have unused objects that are still reachable by an application because the developer simply forgot to dereference them. Such objects cannot be garbage-collected.
• 
  

Continue Reading

Core Java Interview Questions

1. Java 8  : How to Sort a List using lambdas?
1. Integer[] arr = { 1, 7, 3, 9, 4, 67, 100, 23, 26, 76, 8 }; List list = Arrays.asList(arr); list.sort((a1, a2) -> a1.compareTo(a2)); System.out.print(list);
2. Is singleton is lazy initialisation?
1. Yes. As in the below code singleton is lazy initialisation.
2. We will not initialise on static instance property. And initialise only on getInstance method, so it will initialise on required time only and lazy loading. If we need to make it as eager initialise instance on static field, then it will initialise on the time of class loading.
3. public class Singleton { private static Singleton instance; private LazyInitializedSingleton(){ } public static Singleton getInstance(){ if(instance == null){ synchronized (DclSingleton.class) { instance = new Singleton(); } } return instance; } }
3. How to find the nth element In QUEUE?
1. The fact that accessing elements by index is not part of the concept of a queue.If you need to access elements by index, you want a list, not a queue.
4. What is a partially checked exception in Java?
1. A checked exception is said to be partially checked exception if and only if some of its child classes are unchecked 
1. Ex: Exception
2. The only possible partially checked exception in java are  
1. Exception 
2. Throwable 
5. String intern()?
1. The java string intern() method returns the interned string. It returns the canonical representation of string.
2. It can be used to return string from memory, if it is created by new keyword. It creates exact copy of heap string object in string constant pool.
3. public class InternExample{ public static void main(String args[]){ String s1=new String("hello"); String s2="hello"; String s3=s1.intern();//returns string from pool, now it will be same as s2 System.out.println(s1==s2);//false because reference variables are pointing to different instance System.out.println(s2==s3);//true because reference variables are pointing to same instance } }
6. Can an abstract class have main method and run it?
1. Yes. It have main method and run. But canot create its own object,.
2. public abstract class AbstractMainEx { public static void main(String[] args) { System.out.println("Hi"); } public abstract boolean test(); }
7. How to create a custom Exception?
1. To create you own exception extend the Exception class or any of its subclasses.
2. class New1Exception extends Exception { } // this will create Checked Exception class NewException extends IOException { } // this will create Checked exception class NewException extends NullPonterExcpetion { } // this will create UnChecked exception
8. Can we have private constructor for parent constructor in inheritance?
1. No
2. Implicit super constructor Animal() is not visible for default constructor. Must define an explicit 
    constructor
9. 
   

Continue Reading

Java Executor Framework

• It is the first concurrent utility framework in java and used for standardising invocation, scheduling, execution and control of asynchronous tasks in parallel threads.
• Executor implementation in java uses thread pools which consists of worker threads. The entire management of worker threads is handled by the framework. So the overhead in memory management is much reduced compared to earlier multithreading approaches.
• The Java Executor framework creates tasks by using instances of Runnable or Callable. In case of Runnable, the run () method does not return a value or throw any checked exception. But Callable is a more functional version in that area. It defines a call () method that allows the return of some computed value which can be used in future processing and it also throws an exception if necessary.
• The FutureTask class is another important component which is used to get future information about the processing. An instance of this class can wrap either a Callable or a Runnable. You can get an instance of this as the return value of submit () method of an ExecutorService. You can also manually wrap your task in a FutureTask before calling execute () method.
• Following are the functional steps to implement the Java ThreadPoolExecutor.
• Create an executor
•  Executor class has a number of static factory methods to create an ExecutorService depending upon the requirement of the application.
• The newFixedThreadPool () returns a ThreadPoolExecutor instance with an initialized and unbounded queue and a fixed number of threads.
• The newCachedThreadPool () returns a ThreadPoolExecutor instance initialized with an unbounded queue and unbounded number of threads
• newFixedThreadPool ()
• No extra thread is created during execution
• If there is no free thread available the task has to wait and then execute when one thread is free
• newCachedThreadPool ()
• Existing threads are reused if available. But if no free thread is available, a new one is created and added to the pool to complete the new task. Threads that have been idle for longer than a timeout period will be removed automatically from the pool.
• This is a fixed pool of 10 threads.
private static final Executor executor = Executors.newFixedThreadPool(10);
• This is a cached thread pool
private static ExecutorService exec = Executors.newCachedThreadPool();
• Following is an example of customized thread pool executor. The parameter values depend upon the application need. Here the core pool is having 8 threads which can run concurrently and the maximum number is 12. The queue is capable of keeping 250 tasks. Here one point should be remembered that the pool size should be kept on a higher side to accommodate all tasks. The idle time limit is kept as 5 ms.
private static final Executor executor = new ThreadPoolExecutor(5, 12, 50000L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue(250));
• Create one or more tasks and put in the queue
• After creating the executor now it’s time for creating tasks. Create one or more tasks to be performed as instances of either Runnable or Callable. In this framework, all the tasks are created and populated in a queue. After the task creation is complete the populated queue is submitted for concurrent execution.
• Submit the task to the Executor
• After creating the ExecutorService and proposed tasks, you need to submit the task to the executor by using either submit () or execute () method. Now as per your configuration the tasks will be picked up from the queue and run concurrently. For example if you have configured 5 concurrent executions, then 5 tasks will be picked up from the queue and run in parallel. This process will continue till all the tasks are finished from the queue.
• Execute the task
• Next the actual execution of the tasks will be managed by the framework. The Executor is responsible for managing the task’s execution, thread pool, synchronization and queue. If the pool has less than its configured number of minimum threads, new threads will be created as per requirement to handle queued tasks until that limit is reached. If the number is higher than the configured minimum, then the pool will not start any more threads. Instead, the task is queued until a thread is freed up to process the request. If the queue is full, then a new thread is started to handle it. But again it depends upon the type of constructor used during executor creation.
• Shutdown the Executor
• The termination is executed by invoking its shutdown () method. You can choose to terminate it gracefully, or abruptly.
• 
  

Continue Reading

Semaphore

• A Semaphore is a thread synchronization construct that can be used either to send signals between threads to avoid missed signals, or to guard a critical section like you would with a lock
• Simple Semaphore implementation:
• The take() method sends a signal which is stored internally in the Semaphore. The release() method waits for a signal. When received the signal flag is cleared again, and the release() method exited.
• // Prototype pattern public abstract class Prototype implements Cloneable { public Prototype clone() throws CloneNotSupportedException{ return (Prototype) super.clone(); } } public class ConcretePrototype1 extends Prototype { @Override public Prototype clone() throws CloneNotSupportedException { return (ConcretePrototype1)super.clone(); } } public class ConcretePrototype2 extends Prototype { @Override public Prototype clone() throws CloneNotSupportedException { return (ConcretePrototype2)super.clone(); } }
• Using a semaphore like this you can avoid missed signals. You will call take() instead of notify() and release() instead of wait().
• Using Semaphores for Signaling
• Here is a simplified example of two threads signaling each other using a Semaphore:
• MainApp.java
Semaphore semaphore = new Semaphore(); SendingThread sender = new SendingThread(semaphore); ReceivingThread receiver = new ReceivingThread(semaphore); receiver.start(); sender.start();
• SendingThread.java
public class SendingThread { Semaphore semaphore = null; public SendingThread(Semaphore semaphore){ this.semaphore = semaphore; } public void run(){ while(true){ //do something, then signal this.semaphore.take(); } } }
• RecevingThread.java
public class RecevingThread { Semaphore semaphore = null; public ReceivingThread(Semaphore semaphore){ this.semaphore = semaphore; } public void run(){ while(true){ this.semaphore.release(); //receive signal, then do something... } } }
• Semaphore to block threads
• 
  

Continue Reading

Multi-threading Interview Questions Java

1. How Volatile in Java works?
1. The Java volatile keyword cannot be used with method or class and it can only be used with a variable.
2. Java volatile keyword also guarantees visibility and ordering and write to any volatile variable happens before any read into the volatile variable.
3. Example: Singleton Class 
1. public class Singleton{ private static volatile Singleton _instance; //volatile variable public static Singleton getInstance(){ if(_instance == null){ synchronized(Singleton.class){ if(_instance == null) _instance = new Singleton(); } } return _instance; }
2. writer thread comes out of synchronized block, memory will not be synchronized and value of _instance will not be updated in main memory. With Volatile keyword in Java, this is handled by Java himself and such updates will be visible by all reader threads.
4. If a variable is not shared between multiple threads, you don't need to use volatile keyword with that variable.
5. Both T1 and T2 can refer to a class containing this variable. You can then make this variable volatile, and this means that changes to that variable are immeditately visible in both threads.
6. public class App { public static volatile boolean isEven = true; public static void main(String[] args) { Object mutex = new Object(); Thread odd = new Thread(new Runnable() { @Override public void run() { try { int i = 0; while (i < 20) { synchronized (mutex) { if (isEven) { mutex.wait(); } System.out.println("Odd"); isEven = true; mutex.notify(); } i++; } } catch (Exception e) { e.printStackTrace(); } } }); Thread even = new Thread(new Runnable() { @Override public void run() { try { int i = 0; while (i < 20) { synchronized (mutex) { if (!isEven) { mutex.wait(); } System.out.println("Even"); isEven = false; mutex.notify(); } i++; } } catch (Exception e) { e.printStackTrace(); } } }); odd.start(); even.start(); } }
7. Volatile keyword in Java guarantees that value of the volatile variable will always be read from main memory and not from Thread's local cache.
8. In Java reads and writes are atomic for all variables declared using Java volatile keyword (including long and double variables).
9. Using the volatile keyword in Java on variables reduces the risk of memory consistency errors because any write to a volatile variable in Java establishes a happens-before relationship with subsequent reads of that same variable.
10. Java volatile keyword doesn't mean atomic, its common misconception that after declaring volatile ++ will be atomic, to make the operation atomic you still need to ensure exclusive access using synchronized method or block in Java.
2. How is CountDownLatch used in Java Multithreading?
1. CountDownLatch works in latch principle, the main thread will wait until the gate is open. One thread waits for n threads, specified while creating the CountDownLatch.
2. Any thread, usually the main thread of the application, which calls CountDownLatch.await() will wait until count reaches zero or it's interrupted by another thread. 
3. All other threads are required to count down by calling CountDownLatch.countDown() once they are completed or ready.
4. As soon as count reaches zero, the waiting thread continues. One of the disadvantages/advantages of CountDownLatch is that it's not reusable: once count reaches zero you cannot use CountDownLatch any more.
3. can we make array volatile in java?
1. Yes, you can make an array (both primitive and reference type array e.g. an int array and String array) volatile in Java
2. But declaring an array volatile does NOT give volatile access to it's fields. you're declaring the reference itself volatile, not it's elements.
2. protected volatile int[] primes = new int[10];
1. then if you assign a new array to primes variable, change will be visible to all threads, but changes to individual indices will not be covered under volatile guarantee i.e
3. primes = new int[20];
1. will follow the "happens-before" rule and cause memory barrier refresh visible to all threads
4. primes[0] = 10;
1.  will not visible changes in all threads
3. Same for collections also
4. In other words you're declaring a volatile set of elements, not a set of volatile elements. The solution here is to use AtomicIntegerArray in case you want to use integers
4.  Thread Local?
1. The ThreadLocal class in Java enables you to create variables that can only be read and writte by the same thread. 
2. private ThreadLocal myThreadLocal = new ThreadLocal();
3. Now you can only store strings in the ThreadLocal instance.
4. myThreadLocal.set("Hello ThreadLocal"); String threadLocalValue = myThreadLocal.get();
5. How immutable objects manage memory ?
1. The advantage we get with String is that a common pool of string literals is kept by the virtual machine stopping the Heap getting filled up . The reasoning behind this is that much of the memory of a program can be taken up with storing commonly used strings.
6. How to throw exceptions from Runnable.run?
1. Do not use Runnable interface from Thread library, but instead create your own interface with the modified signature that allows checked exception to be thrown
2. public interface MyRunnable { void myRun ( ) throws MyException; }
3. You may even create an adapter that converts this interface to real Runnable ( by handling checked exception ) suitable for use in Thread framework.
7. Difference Between Daemon and User Threads?
1. Java offers two types of threads: user threads and daemon threads.
2. JVM will wait for all active user threads to finish their execution before it shutdown itself.
3. Daemon thread doesn't get that preference, JVM will exit and close the Java program even if there is a daemon thread running in the background
4.  Daemon threads are low-priority threads whose only role is to provide services to user threads..
5. A daemon thread is a thread that does not prevent the JVM from exiting when the user thread finishes but the thread is still running. An example for a daemon thread is the garbage collection.
6. That’s why infinite loops, which typically exist in daemon threads, will not cause problems, because any code, including the finally blocks, won’t be executed once all user threads have finished their execution. For this reason, daemon threads are not recommended for I/O tasks.
7. // Java program to demonstrate the usage of // setDaemon() and isDaemon() method. public class DaemonThread extends Thread { public DaemonThread(String name){ super(name); } public void run() { // Checking whether the thread is Daemon or not if(Thread.currentThread().isDaemon()) { System.out.println(getName() + " is Daemon thread"); } else { System.out.println(getName() + " is User thread"); } } public static void main(String[] args) { DaemonThread t1 = new DaemonThread("t1"); DaemonThread t2 = new DaemonThread("t2"); DaemonThread t3 = new DaemonThread("t3"); // Setting user thread t1 to Daemon t1.setDaemon(true); // starting first 2 threads t1.start(); t2.start(); // Setting user thread t3 to Daemon t3.setDaemon(true); t3.start(); } } ######OUT PUT#### t1 is Daemon thread t2 is User thread

Continue Reading

Synchronization in Java

• If your code is executing in a multi-threaded environment, you need synchronization for objects, which are shared among multiple threads, to avoid any corruption of state or any kind of unexpected behavior.
• Synchronization in Java will only be needed if shared object is mutable.
• JVM guarantees that Java synchronized code will only be executed by one thread at a time. 
• we can not have synchronized variable in java. Using synchronized keyword with a variable is illegal and will result in compilation error. You can use java synchronized keyword only on synchronized method or synchronized block.
• we need to take care is that static synchronized method locked on class object lock and nonstatic synchronized method locks on current object (this). So it’s possible that both static and nonstatic java synchronized method running in parallel. 
• public class Counter{ private static int count = 0; public static synchronized int getCount(){ return count; } public synchoronized setCount(int count){ this.count = count; } }
• In this example of Java, the synchronization code is not properly synchronized because both getCount() and setCount() are not getting locked on the same object and can run in parallel which may result in the incorrect count.
• Whenever a thread enters into java synchronized method or blocks it acquires a lock and whenever it leaves java synchronized method or block it releases the lock. The lock is released even if thread leaves synchronized method after completion or due to any Error or Exception.
• Object level lock
•  Java Thread acquires an object level lock when it enters into an instance synchronized java method 
• Class level lock 
• Acquires a class level lock when it enters into static synchronized java method.
• Re-entrant Lock
•  if a java synchronized method calls another synchronized method which requires the same lock then the current thread which is holding lock can enter into that method without acquiring the lock.
• Locks
• One Major disadvantage of Java synchronized keyword is that it doesn't allow concurrent read, which can potentially limit scalability. 
• By using the concept of lock stripping and using different locks for reading and writing, you can overcome this limitation of synchronized in Java. You will be glad to know that java.util.concurrent.locks.ReentrantReadWriteLock provides ready-made implementation of ReadWriteLock in Java.
• One more limitation of java synchronized keyword is that it can only be used to control access to a shared object within the same JVM. If you have more than one JVM and need to synchronize access to a shared file system or database, the Java synchronized keyword is not at all sufficient. You need to implement a kind of global lock for that.
• Java synchronized block is better than java synchronized method in Java because by using synchronized block you can only lock critical section of code and avoid locking the whole method which can possibly degrade performance.
• Do not synchronize on the non-final field on synchronized block in Java. because the reference of the non-final field may change anytime and then different thread might synchronizing on different objects i.e. no synchronization at all.
• Locks vs Synchronisation
• Synchronisation
• One thread at a time and other threads waiting
• Cannot do multi read even no write happening
• Cannot interrupt any thread which is waiting for acquire lock
• Cannot change priority of threads
• Locks
• Lock comes under java.util.concurrent.Lock
• One thread at a time and other threads waiting
• ReetantReadWriteLock.readLock
• ReetantReadWriteLock.writeLock
• Allows multiple reads as long as no write happens
• tryLock ->if lock available lock it 
• Fairness Policy
• Longest waiting will get higher priority
• Able interrupt thread

Continue Reading