Java Concepts in Details
DS- Find Maximum element in Binary Tree(Not BST)
Finding Maximum in a binary tree can be done by below approach.
- data in current node.
- Find maximum in left subtree.
- Find maximum in right subtree.
Then Compare all three value to get maximum.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int findMax(Node node) {
if(node == null)
return Integer.MIN_VALUE;
int max = node.data;
int leftMax = findMax(node.left);
int rightMax = findMax(node.right);
if (leftMax > max)
max = leftMax;
if (rightMax > max)
max = rightMax;
return max;
}
|
Type Promotion
Type promotion happens in method calling.
A low type can be promoted to high type.
But type promotion not happens in case of Wrapper class like Integer, Long Double.
it always happens with primitive type like int, double, char, byte..etc
- Shot can be promoted to byte, int, long, float and double.
- byte can be promoted to int, long, float and double.
- char can be promoted to int, long, float and double.
- int can be promoted to long, float and double.
- long can be promoted to float and double.
- float can be promoted to double.
Below type promotion can place take when we call a method.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | package practice.problem;
public class TypePromition {
public static void test(long a) {
System.out.println("float " + a);
}
public static void test(double a) {
System.out.println("double " + a);
}
public static void main(String[] args) {
test('h'); // it will call the long method
test(13L); // it will also call the long method
test(13.4f); // it will call the double method
}
}
|
Garbage Collection
Garbage Collector is used to destroy the objects that are not in use or unreachable. So that heap memory can be object for application.
Its a daemon thread that runs periodically , and user don’t have to worry about running or executing it.
So if you have created any object without new, you can use finalize method to perform cleanup processing (destroying remaining objects).
This thread calls the finalize() method before object is garbage collected.
Mark & Sweep:-
It works in two steps:-
- Step 1: All currently running active objects are marked live.
- Step 2: Any object that is not marked live is removed
- In this approach first it defines some specific root objects (local variable and input parameters of the currently executing methods, active threads, static field of the loaded classes). Now GC travels whole object graph starting from root and marks all object live that are reachable or connected in that graph. And in second step it remove all object that are not marked as live. Disadvantage: While running this approach application thread need to be stopped, as GC can not traverse the graph if it keep changing.
- Concurrent Mark Sweep
- It is advanced version of Mark and Sweep. It uses multiple thread s for scanning the heap.
- Also it runs in parallel with application threads. So gives better performance than Mark & Sweep.
- Serial Garbage Collection
- This algorithm uses mark-copy for the Young Generation and mark-sweep-compact for the Old Generation. It works on a single thread.
- while executing it suspends all application threads until GC result has been concluded.
2.
Parallel Garbage Collection- Like Serial GC it also uses mark-copy for the Young Generation and mark-sweep-compact for the Old Generation.
- It works on multiple threads.
- We can configure the number of thread in JVM arguments.
3. G1 (Garbage First) Garbage Collection- This basically divides the entire heap in small small segments.
- and each segment is marked as either Young generation or odd generation.
- This is parallel, concurrent, incrementally compacting low pause algorithm. This keeps tracking of the amount of live data in each region or segment. This information is used in knowing that which region keeps the most garbage. and that region is collection first. that is why the name is garbage first.
The Garbage collector of JVM collects only those objects that are created by new keyword.
Garbage collection is performed by a daemon thread called Garbage Collector(GC).
Below are the algorithm used for GC.
Thread Local
ThreadLocal can be used to provide a copy of variable for each thread.
That means each thread works on their own copy of variable and they can not see other threads variable value.
We use Thread Local to achieve thread safety apart from writing immutable classes.
InheritableThreadLocal
The InheritableThreadLocal class is a subclass of ThreadLocal.
Instead of each thread having its own value inside a ThreadLocal, the InheritableThreadLocal grants access to values to a thread and all child threads created by that thread.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Client implements Runnable{
ThreadLocal<Long> threadLocal;
Long sleepTime;
Client(ThreadLocal<Long> threadLocal, Long sleepTime){
this.threadLocal = threadLocal;
this.sleepTime = sleepTime;
}
@Override
public void run() {
this.threadLocal.set(sleepTime);
try {
Thread.sleep(sleepTime);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + ": " +
threadLocal.get());
}
}
public class ThreadLocalExample {
public static void main(String args[]) {
ThreadLocal<Long> threadLocal = new ThreadLocal<Long>();
Client client1 = new Client(threadLocal, 10000L);
Client client2 = new Client(threadLocal, 5000L);
new Thread(client1).start();
new Thread(client2).start();
}
}
|
Exception Class Hierarchy
Reentrant V/S Synchronization
There are four major differences between Reentrant Lock & Synchronization.
- Reentrant can be fairness. By passing fairness value true we can make sure the longest waited thread get the lock first.
- On the other hand, Synchronization wont guarantee that which thread will acquire the lock first once it is released.
- Reentrant provides tryLock method so that if the lock is not free the current thread will not be blocked, Or it will wait for provided period
- of time. While in synchronization,all threads trying to acquire the lock will be block if the lock is not released.
- In reentrant a lock can be acquire in one method and it can be unlocked in another method. While in Synchronization there is no such way, and lock is put on a
- ReentrantLock also provides convenient method to get List of all threads waiting for lock.
Reentrant Lock, Cyclic Barrier, Count Down Latch
Fixed Thread Pool:
In Fixed thread pool a pool is created of fixed size.
And every time a new job comes, then a thread is pooled from the pool and assigned the job.
In some scenario when all thread are busy serving another request, the the new request/job has to wait in queue. As soon as a thread finishes its current request, it takes the new waiting request.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | /*
* Below pool a fixed size (5) threads pool, where only 5 threads will be there
*/
ExecutorService fixedThredPool = Executors.newFixedThreadPool(5);
for(int i =0; i<100; i++) {
fixedThredPool.execute(new Runnable() {
@Override
public void run() {
try {
Thread.sleep(1000);
System.out.println(Thread.currentThread().getName());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
}
|
Cashed Thread Pool:
Creates a thread pool that creates new threads as needed, but will reuse previously constructed threads when they are available. These pools will typically improve the performance of programs that execute many short-lived asynchronous tasks. Calls to execute will reuse previously constructed threads if available. If no existing thread is available, a new thread will be created and added to the pool. Threads that have not been used for sixty seconds are terminated and removed from the cache. Thus, a pool that remains idle for long enough will not consume any resources.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /*
* The below thread pool is cached thread pool.
* Here when a new job comes, a new thread is created and after completing its task that thread is kept in pool till 60 seconds.
* And if within 30 seconds a new job comes then the same thread is pooled out and assigned the job.
*/
ExecutorService cachedThredPool = Executors.newCachedThreadPool();
for(int i =0; i<100; i++) {
cachedThredPool.execute(new Runnable() {
@Override
public void run() {
try {
Thread.sleep(1000);
System.out.println(Thread.currentThread().getName());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
}
|
Returning Outcome:
We need to call submit method of ExecutorService when we want our thread to return some outcome. The submit method implements the Callable interface. The submit method is also capable of implementing the Runnable interface, but in that case it wont return any outcome.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | ExecutorService executor = Executors.newSingleThreadExecutor();
Future<Integer> outcome =
executor.submit(new Callable<Integer>() {
@Override
public Integer call() throws Exception {
return 10;
}
});
System.out.println("outcome: "+ outcome.get());
//Submit method implementing Runnable interface
executor.submit(new Runnable() {
@Override
public void run() {
System.out.println("No outcome thread...");
}
});
|
Threading- Print Even Odd Using two Threads
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 | /**
*
*/
package practice.problem;
/**
* @author chandan
*
*/
class PrintEvenOdd implements Runnable {
static volatile int val = 1;
@Override
public void run() {
while(val <= 10) {
print();
}
}
synchronized private void print() {
notify();
try {
if(Thread.currentThread().getName().equals("EvenThread")) {
if(val % 2 == 1)
return;
}
if(Thread.currentThread().getName().equals("OddThread")) {
if(val % 2 == 0)
return;
}
System.out.println(Thread.currentThread().getName() + " " + val++);
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class ThreadPrintEvenOdd {
public static void main(String args[]) {
PrintEvenOdd print = new PrintEvenOdd();
Thread even = new Thread(print, "EvenThread");
Thread odd = new Thread(print, "OddThread");
odd.start();
even.start();
}
}
|
Sorting a HashMap
A hash map can be sorted by using below approaches.
- Using a TreeMap (default sorting based on key).
- Sorting using Comparator (Functional Interface).
- Sorting using Lambda Expression.
- Sorting Using Java Stream API.
Please See the below example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171 | /**
*
*/
package practice.problem;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
/**
* @author chandan
*
*/
public class HashMapSorting {
public static void main(String args[]) {
HashMapSorting ob = new HashMapSorting();
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("Guvava", 3);
map.put("Orange", 5);
map.put("Apple", 1);
map.put("Grapes", 2);
map.put("Banana", 4);
ob.sortingUsingTreeMap(map);
ob.sortingUsingComparator(map);
ob.sortingUsingLambdaExpression(map);
ob.sortingUsingStream(map);
/*
*
* Now we will see how to sort a map using stream, when that map is having custom object as key
*/
Map<Fruite, Integer> fruiteMap = new HashMap<Fruite, Integer>();
Fruite guvava = new Fruite("Guvava", 3);
Fruite orange = new Fruite("Orange", 5);
Fruite apple = new Fruite("Apple", 1);
Fruite grapes = new Fruite("Grapes", 2);
Fruite banana = new Fruite("Banana", 4);
fruiteMap.put(guvava, 3);
fruiteMap.put(orange, 5);
fruiteMap.put(apple, 1);
fruiteMap.put(grapes, 2);
fruiteMap.put(banana, 4);
ob.sortingFruiteMapUsingStream(fruiteMap);
}
//Sorting using tree map
//This method sorts the map on key (default)
public void sortingUsingTreeMap(Map<String, Integer> map) {
Map<String, Integer> treeMap = new TreeMap<String, Integer>(map);
List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(treeMap.entrySet());
printMap(list, "Sorting Using Tree Map");
}
//Sorting using comparator
//This approach we can use to sort a map based on key or value
public void sortingUsingComparator(Map<String, Integer> map) {
List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>( map.entrySet());
//Sorting Based on Key
Collections.sort(list, new Comparator<Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> element1, Entry<String, Integer> element2) {
return element1.getKey().compareTo(element2.getKey());
}
});
printMap(list, "Sorting Usgin Comparator, Based on Key");
//Sorting based on value
Collections.sort(list, new Comparator<Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> element1, Entry<String, Integer> element2) {
return element1.getValue() - element2.getValue();
}
});
printMap(list, "Sorting Usgin Comparator, Based on Value");
}
/*
* Below method is lambda expression version of above method (sortingUsingComparator).
* Since Comparator is a function interface so we can use lambda expression also to sort a map.
*/
public void sortingUsingLambdaExpression(Map<String, Integer> map) {
List<Entry<String, Integer>> list = new LinkedList<>(map.entrySet());
//Sorting based on key
Collections.sort(list, (o1, o2) -> o1.getKey().compareTo(o2.getKey()));
printMap(list, "Sorting Usgin Lambda Expression, Based on Key");
//Sorting based on value
Collections.sort(list, (o1,o2) -> o1.getValue() - o2.getValue());
printMap(list, "Sorting Usgin Lambda Expression, Based on Value");
}
//Sorting using stream API
public void sortingUsingStream(Map<String, Integer> map) {
System.out.println("Sorting Usgin Stream API, Based on Key");
map.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(System.out::println);
System.out.println("Sorting Usgin Stream API, Based on Value");
map.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(System.out::println);
}
//Sorting custom object map using streamAPI
public void sortingFruiteMapUsingStream(Map<Fruite, Integer> fruiteMap) {
System.out.println("Sorting Custom Object Usgin Stream API, Based on Fruite Name");
fruiteMap.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.comparing(Fruite :: getName))).forEach(System.out::println);
System.out.println("Sorting Custom Object Usgin Stream API, Based on Fruite ID");
fruiteMap.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.comparing(Fruite:: getId))).forEach(System.out::println);
System.out.println("Sorting Custom Object Usgin Stream API, Based on Fruite ID in reverse order");
fruiteMap.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.comparing(Fruite:: getId).reversed())).forEach(System.out::println);
}
private void printMap(List<Entry<String, Integer>> entryList, String description) {
System.out.println(description);
for(Entry<String, Integer> entry: entryList) {
System.out.println("Key: " + entry.getKey() + "," + "Value: " + entry.getValue());;
}
}
}
class Fruite{
String name;
Integer id;
public Fruite(String name, Integer id) {
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
@Override
public String toString() {
return name + " " + id;
}
}
|
Sorting Algorithm Complexity
Exception Handling in Overriding
We can have following two cases in method overriding.
Case 1: Super class method does not declares/throws an exception.
In this case method in subclass can have below two choices.
- It may not declare/throw any exception.
- It can overridden method cannot declare the checked exception but it can declare unchecked exception (Runtime Exception).
In this case method in subclass can have below three choices.- It may not declare/throw any exception.
- It can declare/throw the same exception that super class method has.
- It can declare/throw sub exception of the exception that super class method has.
Case 2: Super class declares/throws an exception
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 | class SuperClass{
public void noExceptionMethod() {
System.out.println("This method does not throw any exception");
}
public void noExceptionMethod(Long orderNumber) {
System.out.println("This method does not throw any exception");
}
public void excpetionMethod(String accountNumber) throws RuntimeException{
if(accountNumber == null)
throw new RuntimeException("invalid account");
}
public void excpetionMethod(Long orderNumber) throws Exception{
if(orderNumber == null)
throw new RuntimeException("invalid order");
}
public void superExceptionMethod() throws RuntimeException{
}
}
class ChildClass extends SuperClass{
//No Error
@Override
public void noExceptionMethod() {
System.out.println("This method does not throw any exception");
}
//No error, it can throw runtime exception
@Override
public void noExceptionMethod(Long orderNumber) throws RuntimeException{
System.out.println("This method does not throw any exception");
}
// Below method gives "Exception Exception is not compatible with throws clause in SuperClass.noExceptionMethod(Long)"
//Error, This is not allowed
// @Override
// public void noExceptionMethod(Long orderNumber) throws Exception{
// System.out.println("This method does not throw any exception");
// }
//No Error
@Override
public void excpetionMethod(String accountNumber){
if(accountNumber == null)
throw new RuntimeException("invalid account");
System.out.println("This method does not throw any exception");
}
@Override
public void excpetionMethod(Long accountNumber) throws RuntimeException{
if(accountNumber == null)
throw new RuntimeException("invalid account");
System.out.println("This method does not throw any exception");
}
//Error, not allowed
// @Override
// public void superExceptionMethod() throws Exception{
//
// }
@Override
public void superExceptionMethod() throws RuntimeException{
}
}
|
Serilizable vs Externalizable
We implement java.io.Externalizable interface if we want to serialize/desrialize only some specific attributes from a class.
The main disadvantage of using java.io.Serializable interface is that it serialize/desrialize the complete class. That means if a class is having even thousand attributes then it will serialize/desrialize all thousand attributes. With Serializable we can not skip any attribute.
So to get control over serialize/desrialize, we need to implement java.io.Externalizable.
In the target class we override public void writeExternal(ObjectOutput out) and public void readExternal(ObjectInput in) method from java.io.Externalizable interface.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101 | /**
*
*/
package practice.problem;
import java.io.Externalizable;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
class Student implements Externalizable{
String fName;
String lName;
int roll;
boolean regular;
public Student(){
}
public Student(String fName, String lName, int roll, boolean r){
this.fName = fName;
this.lName = lName;
this.roll = roll;
this.regular = r;
}
@Override
public void writeExternal(ObjectOutput out) throws IOException {
out.writeChars(fName);
out.writeChars(lName);
out.writeInt(roll);
out.writeBoolean(regular);
}
@Override
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
fName = in.readLine();
lName = in.readLine();
roll = in.readInt();
regular = in.readBoolean();
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Student [fName=" + fName + ", lName=" + lName + ", roll=" + roll + ", regular=" + regular + "]";
}
}
public class ExternizableClient {
private static void writeStudent(Student student) throws IOException {
FileOutputStream fos = new FileOutputStream("student.txt");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(student);
oos.close();
}
private static Student readStudent() {
try(FileInputStream fis = new FileInputStream("student.txt")){
ObjectInputStream ois = new ObjectInputStream(fis);
Student student = (Student)ois.readObject();
return student;
} catch (IOException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
}
return null;
}
public static void main(String args[]) throws IOException {
Student newStudent = new Student("chandan", "Singh", 3088, true);
writeStudent(newStudent);
System.out.println(readStudent());
}
}
|