Memory Management in JAVA

One of the most important features of Java is its memory management. Since Java uses automatic memory management, it becomes superior to those languages that do rely on programmers for their memory management. Having said that, although Java automates its memory management, it is very important to understand the functionality so that we do not end up in a situation where we start blaming JAVA for any out of memory because of our coding issues.

When we say JAVA memory, we mean JVM memory. JVM primarily defines 5 run-time data areas which are used in program execution:

Method Area | Heap Memory | Stack | PC Registers | Native Method Stack

Let us try to understand each one of them and the linkage between them:

1. Method Area:

• All the class data is available in the method area. 
• Corresponding static variables associated with the class are also part of the Method Area.
• Its size can be customized as peruse.
• Apart from the class data, it also stores superclass name, interface name, and constructors information
• If the memory in the method area can not satisfy an allocation request, JVM throws an OutOfMemoryError.

2. Heap Area:

• All the object data is available in the Heap area.
• The instance variable will also be stored in Heap Area. 
• It is very important for a programmer to understand the Heap Area as all the object-level information is present here and garbage collection keeps a check for this area only.
• Its size can be customized as per need.
• Heap is further divided into few parts which we will be discussing in detail along with garbage collection in our next blog.
• If more heap is required for the storage management system, JVM throws an OutOfMemoryError.

3. Stack Area:

• For every thread, a separate run-time stack is created and is stored in Stack Area. 
• Thus, if we have "n" number of threads, "n" number of stacks will be created and will be stored in the stack area.
• Further, each entry in each stack contains three parts i.e. Local variable array, operand stack, and Frame data, and these three are collectively known as a stack frame.
• If more JVM stack memory is required than is permitted, JVM throws a StackOverflowError. On the other hand, if JVM tried to expand the Stack memory or if there is a shortage of memory during initial JVM stack creation for a new thread, JVM throws OutOfMemoryError.

Relation between Stack and Heap:

1	String s = new String("abc");

• In the above syntax, an object of type String and value "abc" will be created in the Heap area. 
• "s" will be created in Stack which will refer to the object created in the Heap area.

4. PC Registers:

• For each thread, a stack is created in the stack area and a PC register is created in PC Registers memory. 
• Thus, if we have "n" number of threads, then again "n" number of stacks will be created in the stack area, and "n" number of PC registers will also be created. 
• It holds the address of the currently executing instruction and it moves to the next instruction once the current instruction is executed.

Relation between Stack Area and PC Registers:

• For each thread created in Stack Area, a program counter is associated with it.
• PC register stores the address of the current running instruction.

5. Native Method Stack:

• It is similar to Stack Area but the difference is that the native methods of JAVA are stored in this area. 
• If we deep dive into the architecture of JVM, we will find that there is a JNI (Java Native Interface) which deals with all the native methods.
• If more JVM native stack memory is required than is permitted, JVM throws a StackOverflowError. On the other hand, if JVM tried to expand the native stack memory or if there is a shortage of memory during the initial creation for a new thread, JVM throws OutOfMemoryError.

Read More

Compile Time and Run Time Polymorphism | Method Overloading and Method Overriding

Polymorphism can be divide into poly + morphs which are greek words and means many forms. In Java, a concept via which we can perform the same job in different ways is known as polymorphism. It can be further divided into compile-time polymorphism and run-time polymorphism. Let us have a look at each of them:

1. Compile time polymorphism (Method Overloading):

Whenever the object is assigned the functionality at compile-time, it is known as compile-time polymorphism. It is achieved via Method overloading in java. Method overloading is a concept in which two methods of a class have the same signature but different parameters. For Example:

If we have a class called AutoPace, and we wanted to declare a method as 

public void study(String subject)

We can declare the "study" method only once with the argument as "String". But in case we need some additional functionality, say we need to pass the time duration for the study method as well, we can achieve it with method overloading by declaring another "study" method and changing the argument to: 

public void study(String subject, int duration)

The class will look something like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class AutoPace{ public static void study(String subject){ System.out.println("Lets study: " + subject); } public static void study(String subject, int duration){ System.out.println("Let's study : " + subject + " for next " + duration + " hours"); } public static void main(String args[]){ study("Java"); //Lets study: Java study("Java", 2); //"Let's study : Java for next 2 hours" } }

Few more conecpts of Compile Time Polymorphis when dealing with int -> long -> float -> double:

Next, let us have a look at few method calls and try to understand their output:

Case 1:

Let's assume we have couple of methods in a class say:

1 2 3 4 5 6 7

public int sum(int i, int j){ System.out.println("Integers arguments called") return i+j; }

and, 

1 2 3 4 5

public long sum(long i, long j){ System.out.println("Long arguments called") return i+j; }

This is a case of polymorphism as the arguments are different for the method "sum". In this case, if we call method sum from the main class, something like: 

sum(1,2) -> Since the arguments are integers, the first method will be called and the output will be printed as "Integers arguments called".

Case 2:

Next, let us assume that only one method is available i.e.

1 2 3 4 5 6 7

public long sum(long i, long j){ Systemout.println("long argument called"); return i+j; }

and let's make the same call as the first one i.e. sum(1,2) -> In this case, even if the passed parameters are (int,int) and the corresponding method is not available, it will pass on to the next method which will accept (long,long).

Note: The hierarchy followed in this case should be int -> long -> float -> double i.e. for any lower arguments passed as a parameter if the appropriate argument method is not available it will check for the higher-order argument.

Case 3:

Next, let's try to understand the behavior if we will try to write a couple of methods like:

1 2 3 4 5 6 7 8

public int sum(int i, int j){ return i+j; } public long sum(int i, int j){ return i+j; }

In this case, the method name and parameters are the same, but the return type is different. But, this is not a valid scenario as the method signature is the same and the return type doesn't play any role in method overloading. Hence, it will throw an error.

Case 4: 

Next, let us try to understand the behavior if we will try to write a couple of methods like:

1 2 3 4 5 6 7

public int sum(int i, long j){ return i+j; } public int sum(long i, int j){ return i+j; }

In this case, the method name is the same but the parameters are different as they are in a different order. One can argue that this is following method overloading, but since we are dealing with int and long type, this is an error. 

To understand it better, let us try to understand what happens if someone tries to call sum(1,2) from the main method. 

It will get confused between both the sum methods and will not be able to figure out which method to call and will throw an error stating that the method is ambiguous.

2. Run-Time Polymorphism (Run-Time Polymorphism):

Whenever the object is assigned the functionality at run-time, it is known as run-time polymorphism. It is achieved via Method overriding in java. Method overriding is a concept in which two methods can have the same signature but different definitions. It can be achieved by the use of the parent-child class relationship. For example:

If we have a class HatchBack with a method carSegment, something like:

1 2 3 4 5

public class HatchBack{ public void carSegment(){ System.out.println("This is a hatchback car") } }

But let's suppose there is a child class known as Maruti that wants to extend the HatchBack class for its hatchback segments of cars. In this case, they can override the carSegment and update the definition of the method by:

1 2 3 4 5 6

public class Maruti extends HatchBack{ @Override public void carSegment(){ System.out.println("This is a maruti hatchback car.") } }

In this case, the Maruti class has overridden the functionality of carSegment method and this polymorphism can be achieved at run-time as one can decide which object to instantiate during run-time. Complete implementation of Run-Time Polymorphism:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class HatchBack { public void carSegment() { System.out.println("This is a hatchback car"); } } public class Maruti extends HatchBack { public void carSegment() { System.out.println("This is a maruti hatchback car."); } // Main Code public static void main(String args[]) { HatchBack hatchBack = new Maruti(); hatchBack.carSegment(); //This is a maruti hatchback car. } }

Read More

Reverse Linked List

Each element of the linked list consists of two parameters i.e. the value of the element and the address of the next element in the linked list. When we talk about reversing the linked list, we mainly focus on manipulating the address of the next linked list for each element. 

If we observe the above figure while reversing the linked list, we didn't reverse the value of each element rather we reversed the address of the next element of each element in the linked list. 

To execute this, we can make use of three pointers, the main pointer will iterate throughout the linked list, and the other two pointers will help in reversing the address of the next element in the linked list. Let's have a look at the below logic to reverse the linked list:

1 2 3 4 5 6 7 8 9 10 11

ListElement main = head; ListElement prev = null; ListElement next = null; while (main != null) {     next = main.next; main.next = prev; prev = main; main = next; } head = prev; return head;

In the above logic, ListElement is the object for an element of the linked list which contains the value and the address of the next element. We will start by declaring three pointers, i.e. main, prev, and next.

Next, the while loop will help us to iterate through the list, let us have a look at the first iteration:

If we observe here, at step 3 of the iteration, the linkage between the first and second element became null and the prev pointer is pointing to the first element so that we can point back the second element to the first element in the second iteration and reverse the first two elements.  Let's have a look at the second iteration:

            

Again after the second iteration, the second element is pointing to the first element of the linked list, and the first two elements are reversed at Step 2. Also, while the second element starts pointing to the first element, the linkage between the second element and the third element became null and is set to reverse in the third iteration. Let's have a look at the third iteration:

            

After the third iteration, the second and third elements are reversed and the last element is pointing to null. This will eventually point to the third element in the fourth iteration with the help of the prev pointer. Let us have a look at the fourth iteration:

                

Eventually, after the fourth iteration, all the elements will point in the reverse direction and the next and main pointers will become null. Since the main pointer becomes null, the iterations will stop. The only thing left is to point the head correctly. Since the linked list is reversed, the head should point to the last element of the original linked list. This can be achieved with the help of the prev pointer again. We can simply assign head = prev after the iterations are completed and return the new head of the reversed link list.

The above logic will help in reversing the linked list.

Read More

Fast and Slow Pointer

We can extend two pointers approach and use them as fast and slow pointer as well to solve more complex problems. In slow and fast pointer, we mostly extend slow pointer by 1 index and fast pointer by 2 indexes. This algorithm is known as Floyd’s Cycle Detection Algorithm. Let us look at a few of the solutions to better understand this algorithm.

TO CHECK IF THE TAIL OF THE LINKED LIST IS POINTING BACK TO ANY ELEMENT IN THE LINKED LIST

The fast-slow pointer can help us figure out if the tail of the linked list is pointing to any of the elements in the linked list. We will assign both the slow and fast pointers to the head of the linked list and will increment the slow pointer by 1 and the fast pointer by 2 in every iteration. If the fast pointer matches the slow pointer, that means the fast pointer re-iterated and the tail is not pointing to null. In case the tail is pointing to null and since the fast pointer was getting increase by 2 and the slow pointer was getting increased by 1. The fast and slow pointer should never point to the same element in the linked lsit.

TO FIND THE MIDDLE ELEMENT OF THE LINKED LIST

We can make use of this algorithm to find the middle element of the linked list quickly. We can start by pointer both of our pointer to the head of the linked list and we will move the slow pointer by 1 index and fast pointer by 2 indexes. We need to continue this until the fast pointer points to null or the linked list's last element. We can understand this flow with the help of the below diagram:

If we will observe the flow, by the time the fast pointer reaches the end (in case an odd number of elements are present in the linked list) or points to null (in case of even number of elements are present in the linked list), the slow pointer reached the middle element.

TO CHECK IF THE LINKED LIST IS PALINDROME

We can make use of the fast-slow pointer to check if the linked list is palindrome or not. We can follow the below flow to check the palindrome:

1. Make use of a fast-slow pointer to iterate the slow pointer until the linked list's middle element.

2. While iterating, the slow pointer till the middle element, we will be reversing the linked list.

3. Once the linked list is reversed, we will be having two different links linked list just need to place our pointers again to the head of both the pointers and compare if the elements are equal or not. If they are equal, then it is a palindrome.

Two reverse a linked list, we need to use 3 pointers, which is discussed in detail in our blog Reverse Linked List. Since we need to reverse only half of the linked list, we will be adding one additional pointer to figure out the middle element. Hence, in this case, we will be using four-pointers. Two of them will be used to figure out the middle element and the other two will be used to reverse the linked list:

Next, we will be assigning the slow and fast pointer to the head of the linked list and previous and next pointers as null for start. Next, we will follow the below logic until we iterate till the middle of the linked list to iterate the first half of the linked list:

1 2 3 4 5 6 7 8 9

while(fast != null && fast.next != null){ fast = fast.next.next; next = slow.next; slow.next = previous; previous = slow; slow = next; }

Let us say that the linked list is 1->2->2->1, after the first iteration of the while loop:
- The fast pointer will be at the 3rd element of the linked list.  (Image 2)

- The next pointer will be at the 2nd element of the linked list. (Image 3)

- The slow.next will become null i.e. the first element will stop pointing to the second element. This is required as we need to reverse the point which will be completed in the second iteration of the loop. (Image 4)

- The previous pointer will be at the 1st element of the linked list. (Image 5)

- The slow pointer will be at the second element, the same as the next pointer. (Image 6)

After the second iteration is completed, we will reach out middle element and the first half of the linked list will be reversed.

Post the second iteration of the while loop:
- The fast pointer will be null, making sure it will be the last iteration. (Image 1)

- The next pointer will move to the 3rd element. (Image 2)

- The slow.next will point to the previous pointer element i.e. the first element in this case. At this step, the linking is reversed. (Image 3)

- The previous pointer will then move to the second element. (Image 4)

- The slow pointer will move to the 3rd element of the linked list (Image 5)

This will help us divide the linked list into two separate linked lists. Next, we need to get two pointers to point to the head of these separate linked lists.

1 2 3 4 5 6 7 8 9

//Initiating Fast pointer to second linked list head. if(fast == null){ fast = slow; } else { fast = slow.next; } //Initiating Slow pointer to first linked list head. slow = previous;

The above logic will help us to get the head of both the linked list. For the second linked list, we need to check if fast is null or not.
If the fast pointer is null, we can assign the slow pointer reference to the fast pointer directly as it will be the case of even elements in the complete linked list. Hence, the slow pointer will be referring to (number of elements/2 -1).  
In case fast is not null, it explains that the fast pointer is referring to the last element of the linked list which means that the number of elements in the linked list is odd and in this case, the slow pointer is exactly pointing to the middle element. Hence, we can assign slow.next to fast pointer as we need not check the middle element for palindrome in case of odd elements linked list.

Once we have the separate linked list, we can simply iterate it using the below logic and checking each value. If any of the values are incorrect, the linked list is not a palindrome.

1 2 3 4 5 6 7 8 9

while(slow != null && fast != null){ if(slow.val != fast.val){ return false; } slow = slow.next; fast = fast.next; } return true;

Read More

Two Pointers

Two Pointers is a technique of solving problems of linear data structure, especially arrays. It helps to solve problems with lesser time complexity and space complexity and simplifies our code. Let us have a look at a few of the basic problems solved using two-pointers to understand the concept better. Ideally, we point to the first and last index of an array or the first and second index of an array to iterate the array and then move the pointers accordingly. The approach followed in the below problems might help us in solving more complex problems with an easier approach.

TO FIND A SORTED ARRAY OF SQUARES OF A SORTED ARRAY

Let us assume that we need to figure out an array of squares of a sorted array in increasing order. For Example, we need to find a sorted array in increasing order for squares of the element of [-5,-3,-1,0,3,4,6]. 

One way to achieve this is to iterate every member of the given array, square it and store it in a result array. Next, we can sort the result array. If we follow this approach, the time complexity will include the time to iterate the array and the time to sort it. 

Two pointers can help us in this case to minimize the time complexity. Let's declare two integers to point to the first and last index of an array as shown in the below figure. We can then declare a result array and iterate it from last to end and for each iteration of the result array; we can check the square of the start and end pointer. Whichever, square value is greater can be filled in the result array and the pointer can be decreased if it was the end pointer or can be increased if it was the start pointer. This will help us in getting the desired result.

In the above figure, the pointers are placed at -5 and 6 and an empty result array is declared. Next, the square value of both the pointers is computed and it is determined that 36 Is bigger than 25. Hence, 36 is stored in the result array and the end pointer is decreased by 1. 

In the next step, we computed the square value of both the pointers again and determined that 25 is bigger than 16. Hence, 16 is placed in the result array and the start pointer is incremented by 1. 

Once we are done iterating all the elements of the result array, we will get the desired sorted result.

TO MOVE ALL THE ENTRIES OF A PARTICULAR VALUE AT THE END OF THE ARRAY

Next, we will try to move all the entries of a particular value to the end of the array. Let us try to move all the "1" from the array [1,1,0,3,2,8,1]. 

An easier way to solve this problem is to create a new array of the same size and insert all the non "1" entries from the original array to the new array by iterating the original array. Once the iteration is completed, we can add 1 to the remaining indexes of the new array to get the desired output.

An efficient way to solve this problem is via the two-pointers approach. Let us have a look at the diagram below to understand the execution flow:

To solve this problem, we can initiate two pointers at the start of the array only, and can execute a loop until the second pointer is less than the size of the array and follow the below logic:

• If the second pointer value is "1", increment the second pointer and continue the loop.
• If the second pointer value is not "1", check the first pointer value and second pointer value. If they are not the same, swap the values.
• Increment both first and second pointer.

This approach will help us save some space complexity as no new array creation will be required and is an efficient way to solve the problem.

HOW TO REVERSE A STRING USING TWO POINTERS

Let's try to reverse a string. The string is nothing but an array of char, we can apply the two-pointers approach to simplify the problem. Let's assume that we have been given a char array ['A','U','T','O','P','A','C','E'] and we need to get reverse the array and obtain ['E','C','A','P','O','T','U','A'].

Let us declare a start pointer and an end pointer in this case. We can run a loop until the start pointer is less than the end pointer and can follow the below logic:

• Swap the start pointer and end pointer values.
• Increase the start pointer by 1 and decrease the end pointer by 1.

The below diagram shows the complete execution for this problem:

The two pointers can be extended to be used as a fast-slow pointer which is explained in detail in our blog Fast-Slow Pointers.

Read More

Bitwise Operators

In this section, we will discuss different bitwise operators available and used in Java and then we will discuss some of the algorithms and tricks to solve problems using a bitwise operator. We will try to understand each operator with the help of examples.

1. AND Operator (&)

Let say there are two numbers x = 2 and y = 3. Then if we try to find  (x & y), it will return 2 i.e. (2 & 3) = 2. Now let's try to understand, how it becomes 2. 

If we will run AND(&) operator between two numbers then it checks its binary form and only returns 1 in case both the bits are 1, or else it will return 0, which means if we convert 2 and 3 to there binary form then it will return us 010 which is 2 in decimal form.
 

2	0	1	0
3	0	1	1
Result	0	1	0

If we will observe closely, it returned us 1 only when both the bits were 1, in every other case, it returned us 0.

2. OR Operator (|)

Next is the OR operator. Let us we have the two numbers again i.e. x = 2 and y = 3 and if we try to find (x | y), it will return us 3 i.e. (2 | 3) = 3.

If we run OR(|) operator for any two numbers then it checks each bit of the number in its binary form and returns 1 if any bit is 1. It only returns 0 in case both bits are 0. In this case, it will check each bit based on the below table and will return us 011 i.e. 3

2	0	1	0
3	0	1	1
Result	0	1	1

In this case, if we observe closely, it returned us 1 even if anyone bit is 1 and it only returned 0 when both the bits were 0.

3. COMPLEMENT Operator (~)

If we run complement operator on any number then it will reverse each bit of the number in its binary form i.e. if the binary form of any number is 10101 and if we have executed ~ operator then it will return us 01010. 

For Ex: If we have a number x = 2 the (~x) = 5 i.e. (~2) = 5. Let's try to understand this with the help of the below table:

2	0	1	0
Result	1	0	1

If we observe closely, then we will notice that all the bits which were 0 have been converted to 1 and all the bits which were 1 have been converted to 0 after running a complement operator.

4. XOR Operator (^)

This operator is executed between two numbers and it checks each bit of the binary form of the numbers and returns 0 if both the bits are same and 1 if both the bits are different.
For Example, if we have two numbers i.e. x = 2 and y = 3 then (x^y) = 1 i.e. (2^3) = 1. Lets try to understand with the help of below table:

2	0	1	0
3	0	1	1
Result	0	0	1

If we observe closely, the xor operator returned 1 when both the bits were different and return 0 when both the bits were same.

Some interesting observation for xor operator:

• x^0 = x
• x^y = y^x
• (x^y)^z = x^(y^z)
• x^x = 0

5. Right Shift Operator (>>)

This operator is executed between two numbers and the bits of the first number are right-shifted by the number of times the second number.

For Ex: If we have two numbers i.e. x = 5 (101) and k = 2. Then if we try to find (x>>k), we need to right shift bits of x by k positions i.e. (101) will become (1) which means the last two bits (01) of x were dropped.

Observation: If we right shift x by k i.e. (x>>k) then the result will be equivalent to x/2^k

6. Left Shift Operator (<<)

<sup>This operator is again executed between two numbers and the bits of the first number are left-shifted by the number of times the second number.
For Ex: If we have two numbers i.e. x = 5 (00101) and k = 2. Then if we try to find (x<<k), we need to left-shift bits of x by k positions i.e. (...0000101), will become (10100) = 20 which means the last two bits (00) of x were shifted to the right.
In this case, we have taken  5 as ...0000101 in binary form and not 101 as in this case the left digits matter to us as we need to shift it by k positions.

Observation: If we left shift x by k i.e. (x<<k) then the result will be equivalent to x*2k</sup>

Some tricks which can help in problem-solving:

1. If we need to generate a number with the only kth bit set as 1 and rest all bit as 0, then we can use the below formula: 

(1 << (k-1))

2. If we have a number n and need to calculate 2n, then we can use the below formula:

1 << n

3. If we need to check if any number n is the power of 2 or not then we can use the below formula:

(n & (n-1))

If the above expression returns 0, then it is the power of 2, or else it is not the power of 2.
The above expression is also used in Brian Kernighan's Algorithm to check the number of set bits. Check it out on the web.

Read More

Prime Numbers

We will discuss three approaches for determining if a number is prime or not. We will start with the worst time complexity approach to the best time complexity approach.

Approach 1:

A number is a prime number if it has no other factors other than 1 and the number itself. For Ex: 11 is a  prime number because it is not divisible by any other number than 1 and 11. To determine if any number (N) is prime or not, we need to iterate each number (except 1 and N) before N and have to check if the modulus of that number with N is 0 or not, because if the modulus if 0 then that means that number is a factor of N and in that case, N is not a prime number.

1 2 3 4 5 6 7 8 9 10

public static boolean isPrimeWorst(int N) { if (N <= 1) { return false; } for (int i = 2; i < N; i++) { if (N % i == 0) return false; } return true; }

Approach 2:

The issue with the first approach is that we need to iterate each and every number before N to determine if N is prime or not and say if N is a big number then it will take a lot of time to execute the programme.

If we observe closely, we will get to know that if we do not have any factors of N till the square root of N, then definitely there will be no factors after that. In that case what we can do is we can check for each number till Math.sqrt(N) to check if any number is divisible by N of not, and then we can determine if N is prime or not.

1 2 3 4 5 6 7 8 9

public static boolean isPrimeMedium(int N) { if (N <= 1) return false; for (int i = 2; i <= Math.sqrt(N); i++) { if (N % i == 0) return false; } return true; }

Approach 3:

While the second approach is better than the first one, we can still improve our solution.

One rule of Mathematics is every prime number can be written in the form of 6K+1 or 6K-1 except 2 and 3. Which means we can break each prime number in the form of 6K+1 or 6K-1. For Example, 5 can be written as [6*1 – 1] or 17 can be written as [6*3 – 1]. But the vice versa is not true.

Taking this rule into consideration we can use the below code to find if a number is prime or not.

1 2 3 4 5 6 7 8 9 10 11 12 13

public static boolean isPrimeBest(int N) { if (N <= 1) return false; if (N <= 3) return true; if (N % 2 == 0 || N % 3 == 0) return false; for (int i = 5; i <= Math.sqrt(N); i = i + 6) { if (N % i == 0 || N % (i + 2) == 0) return false; } return true; }

In here, what we are doing is we are returning false if number is 1 and we are returning true if number is 2 or 3 in the first two if conditions.

Further, if any number is divisible by 2 or 3 (except 2 and 3 as if N is 2 or 3, we have already returned true in line 5) then it is definitely not prime. Hence we will return false.

Now for the rest terms, we can run a loop starting 5 till square root of N, and every time we can increase the loop by 6 times. This will reduce the number of checks to a great extent.

Read More