Swap 2 numbers without using temp variable

Swapping two numbers has been a very common problem in day to day use. Usually people use the approach of a temp variable where they store the value in a temp variable, do the assignment of other variable and restore second variable from temp.

Swap using a temp variable:
swap(int a, int b) {
      int temp = a;
      a = b;
      b = temp;
}

Swap with no temp variable: This approach uses XOR bitwise operation to swap the variables.

swap(int a, int b) {
      a = a ^ b;
      a = a ^ b;
      a = a ^ b; 
}

Swap with no temp variable: This approach uses addition substraction.

swap(int a, int b) {
      a=a+b; //a=15 (5+10)
      b=a-b; //b=5 (15-10)
      a=a-b; //a=10 (15-5)
}

Abstract Class in Java

Question

What is an abstract class, and when should it be used?

Answer

Abstract classes are classes that contain one or more abstract methods. An abstract method is a method that is declared, but contains no implementation. Abstract classes may not be instantiated, and require subclasses to provide implementations for the abstract methods. Let's look at an example of an abstract class, and an abstract method.
Suppose we were modeling the behavior of animals, by creating a class hierarchy that started with a base class called Animal. Animals are capable of doing different things like flying, digging and walking, but there are some common operations as well like eating and sleeping. Some common operations are performed by all animals, but in a different way as well. When an operation is performed in a different way, it is a good candidate for an abstract method (forcing subclasses to provide a custom implementation). Let's look at a very primitive Animal base class, which defines an abstract method for making a sound (such as a dog barking, a cow mooing, or a pig oinking). 

public abstract Animal

{

   public void eat(Food food)

   {

        // do something with food.... 

   }

   public void sleep(int hours)

   {

        try

        {

               // 1000 milliseconds * 60 seconds * 60 minutes * hours

               Thread.sleep ( 1000 * 60 * 60 * hours);

        }

        catch (InterruptedException ie) { /* ignore */ } 

   }

   public abstract void makeNoise();

}

Note that the abstract keyword is used to denote both an abstract method, and an abstract class. Now, any animal that wants to be instantiated (like a dog or cow) must implement the makeNoise method - otherwise it is impossible to create an instance of that class. Let's look at a Dog and Cow subclass that extends the Animal class.

public Dog extends Animal

{

   public void makeNoise() { System.out.println ("Bark! Bark!"); }

}

public Cow extends Animal

{

   public void makeNoise() { System.out.println ("Moo! Moo!"); }

}

Now you may be wondering why not declare an abstract class as an interface, and have the Dog and Cow implement the interface. Sure you could - but you'd also need to implement the eat and sleep methods. By using abstract classes, you can inherit the implementation of other (non-abstract) methods. You can't do that with interfaces - an interface cannot provide any method implementations.

Abstract class ia a base class that provides some invariant functionality but leaves implementation of other members to inheriting classes. You can accomplish this through the use of abstract classes which are classes that must be inherited.

Abstract classes are similar to interfaces but share many features with classes. An abstract class cannot be instantiated on its own; it must be inherited first. Abstract classes can provide all some or none of the actual implementation of a class. Like interfaces they can specify members that must be implemented in inheriting

Search for a value in a binary search tree (BST)

Java Solution:

public class SearchInBST {

    public static void main(String[] args) {
        Node root = new Node(5);
        Node node2 = new Node(2);
        Node node3 = new Node(7);
        root.left = node2;
        root.right = node3;
        Node node4 = new Node(1);
        Node node5 = new Node(3);
        node2.left = node4;
        node2.right = node5;
        Node node6 = new Node(6);
        Node node7 = new Node(8);
        node3.left = node6;
        node3.right = node7;
        Node foundElement = find(root, 3);
        if(foundElement != null){
            System.out.println("Element found");
        }else {
            System.out.println("Element not found");
        }
        System.out.println();
    }

    private static Node find(Node root, int key){
        if(root == null){
            return root;
        }
        if(root.data == key){
            return root;
        }else if(key < root.data){
            return find(root.left, key);
        }else {
            return find(root.right, key);
        }
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }
}

Simple blocking queue in Java using wait and notify

Simple blocking queue in Java using wait and notify

package sample;

import java.util.LinkedList;
import java.util.List;

/**
 * A Queue Implementation
 * A Blocking Queue is a queue in which enQueue(insertion) and deQueue (removal) will wait and will be synchnronized.
 * This is used mostly in Producer/ Consumer problem where we generally use a ArrayBlockingQueue or LinkedBlockingQueue.
 *
 * @param <T>
 */

public class BlockingQueue<T> {
    private final List<T> queueList;   // Kept final
    private final int size;

    public BlockingQueue(int limit) {
        queueList = new LinkedList<T>();
        size = limit;
    }

    public synchronized void enqueue(T item) throws InterruptedException {
        while (size == queueList.size()) {  // if full waiting
            wait();
        }
        if (queueList.size() == 0) {   // if empty notifying others
            notifyAll();
        }
        queueList.add(item);     // adding the element
    }


    public synchronized T dequeue() throws InterruptedException {
        while (queueList.size() == 0) {  // If empty waiting...
            wait();
        }
        if (size == queueList.size()) {  // if full notifying others
            notifyAll();
        }
        return queueList.remove(0);   // Removing the element
    }
}

Java Interview Questions on OOPS

What are the principle concepts of OOPS?

There are four principle concepts upon which object oriented design and programming rest. They are:

*     Abstraction
*     Polymorphism
*     Inheritance
*     Encapsulation (i.e. easily remembered as A-PIE).


What is Abstraction?

Abstraction refers to the act of representing essential features without including the background details or explanations.


What is Encapsulation?

Encapsulation is a technique used for hiding the properties and behaviors of an object and allowing outside access only as appropriate. It prevents other objects from directly altering or accessing the properties or methods of the encapsulated object.



What is Inheritance?

*     Inheritance is the process by which objects of one class acquire the properties of objects of another class.

*     A class that is inherited is called a superclass.

*     The class that does the inheriting is called a subclass.

*     Inheritance is done by using the keyword extends.

*     The two most common reasons to use inheritance are:

*   To promote code reuse

*   To use polymorphism



What is Polymorphism?

Polymorphism is briefly described as "one interface, many implementations." Polymorphism is a characteristic of being able to assign a different meaning or usage to something in different contexts - specifically, to allow an entity such as a variable, a function, or an object to have more than one form.


Explain the different forms of Polymorphism.

There are two types of polymorphism one is Compile time polymorphism and the other is run time polymorphism. Compile time polymorphism is method overloading. Runtime time polymorphism is done using inheritance and interface.
Note: From a practical programming viewpoint, polymorphism manifests itself in three distinct forms in Java:



*     Method overloading
*     Method overriding through inheritance
*     Method overriding through the Java interface


What is method overloading?

Method Overloading means to have two or more methods with same name in the same class with different arguments. The benefit of method overloading is that it allows you to implement methods that support the same semantic operation but differ by argument number or type.
Note:



*     Overloaded methods MUST change the argument list
*     Overloaded methods CAN change the return type
*     Overloaded methods CAN change the access modifier
*     Overloaded methods CAN declare new or broader checked exceptions
*     A method can be overloaded in the same class or in a subclass


What is method overriding?

Method overriding occurs when sub class declares a method that has the same type arguments as a method declared by one of its superclass. The key benefit of overriding is the ability to define behavior that’s specific to a particular subclass type.
Note:



*     The overriding method cannot have a more restrictive access modifier than the method being overridden (Ex: You can’t override a method marked public and make it protected).
*     You cannot override a method marked final
*     You cannot override a method marked static


What is an abstract class?

Abstract classes are classes that contain one or more abstract methods. An abstract method is a method that is declared, but contains no implementation.
Note:



*     If even a single method is abstract, the whole class must be declared abstract.
*     Abstract classes may not be instantiated, and require subclasses to provide implementations for the abstract methods.

Sort 3 number using only if

We are trying to sort three numbers using If-Else only and no sorting algorithm.
There are couple of possibilities but the easiest one with minimum comparison is presented here.

C++ Code

       
#include <iostream>

using namespace std;

void smallSort(int &a, int &b, int &c) {
    if(a > b) { // if a is greater than b, swap them        
        int temp = a;
        a = b;
        b = temp;
    }

    if(a > c) { // if a is greater than c, swap them        
        int temp = a;
        a = c;
        c = temp;
    }

    // Now A is the smallest. We just need to compare B and C and swap if needed.    
    if(b > c) {
        int temp = b;
        b = c;
        c = temp;
    }
}

int main(){
    int a = 14;
    int b = -90;
    int c = 2;
    smallSort(a, b, c);
    cout << a << ", " << b << ", " << c << endl;

    return 0;
}



 

Heap sort

A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.

The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than its left child and its right child. In a descending heap, the root should be the highest and given any other node i, that node should be greater than its left child and right child.

To sort the elements, one should create the heap first. Once the heap is created, the root has the highest value. Now we need to sort the elements in ascending order. The root can not be exchanged with the nth element so that the item in the nth position is sorted. Now, sort the remaining (n-1) elements. This can be achieved by reconstructing the heap for (n-1) elements.

Following is the java code which sorts an array in ascending order using Heap Sort:
(Time Complexity of the algorithm is - O(nlogn))

public class HeapSort {

    private static int getLeft(int i){
        return 2*i+1;
    }

    private static int getRight(int i){
        return 2*i+2;
    }

    private static void buildHeap(int[] arr){
        for(int i=(arr.length-2)/2; i>=0; i--){
           heapify(arr, arr.length, i);
        }
    }

    private static void heapify(int[] arr, int heapSize, int k){
        int leftChild = -1;
        if(k >= heapSize){
            return;
        }
        if(getLeft(k) < heapSize){
            leftChild = arr[getLeft(k)];
        }

        int rightChild = -1;
        if(getRight(k) < heapSize){
            rightChild = arr[getRight(k)];
        }

        if(arr[k] > leftChild && arr[k] > rightChild){
            return;
        }

        if(leftChild < rightChild){
            swap(arr, k, getRight(k));
            heapify(arr, heapSize, getRight(k));
        }else {
            swap(arr, k, getLeft(k));
            heapify(arr, heapSize, getLeft(k));
        }

    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int x[] = new int[]{9,3,1,10,15,16,8,7,4,5,89};
        buildHeap(x);
        int heapSize = x.length;
        for(int i = x.length-1; i>=0; i--){
            swap(x, 0, heapSize-1);
            --heapSize;
            heapify(x, heapSize, 0);
        }

        System.out.println(Arrays.toString(x));
    }
}

Reverse the bits in an integer

Coming Soon...

Count bits set in an integer

Coming Soon...

Threaded binary tree

Coming Soon...

New node to a Binary Search Tree

Coming Soon...

Implement Depth First Search (DFS)

Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors, which means that we're done. The recursion (stack) guides us through the graph. 

Implement Breadth First Search (BFS)

Breadth First Search (BFS) searches the graph one level (one edge away from the starting vertex) at a time. In this respect, it is very similar to the level order traversal that we discussed for trees. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then visit and process all of v's neighbors. Now that we've visited and processed all of v's neighbors, we need to visit and process all of v's neighbors neighbors. So we go to the first neighbor we visited and visit all of its neighbors, then the second neighbor we visited, and so on. We continue this process until we've visited all vertices in the graph. We don't use recursion in a BFS because we don't want to traverse recursively. We want to traverse one level at a time. So imagine that you visit a vertex v, and then you visit all of v's neighbors w. Now you need to visit each w's neighbors. How are you going to remember all of your w's so that you can go back and visit their neighbors? You're already marked and processed all of the w's. How are you going to find each w's neighbors if you don't remember where the w's are? After all, you're not using recursion, so there's no stack to keep track of them. To perform a BFS, we use a queue. Every time we visit vertex w's neighbors, we dequeue w and enqueue w's neighbors. In this way, we can keep track of which neighbors belong to which vertex. This is the same technique that we saw for the level-order traversal of a tree. The only new trick is that we need to make the vertices, so we don't visit them more than once -- and this isn't even new, since this technique was used for the blobs problem during our discussion of recursion. 

A full N-ary tree has M non-leaf nodes, how many leaf nodes does it have

M + (N ^ (n-1)) = (1 - (N ^ n)) / (1 - N)
Here (N ^ (n-1)) is the number of leaf-nodes.
Solving for this leads to the answer
Leaf nodes = M * (N - 1) + 1

Suppose you have a 3-ary tree

So, here M=4 and N=3.

So using the formula above, Leaf nodes = M * (N - 1) + 1 = 4 * (3 - 1) + 1 = 9 

How many different trees can be constructed using n nodes

Answer is 2^n - n

So, if there are 10 nodes, you will have (1024 - 10) = 1014 different trees! 

What is an AVL tree

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors Adelson-Velskii and Landis.

A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O (n) height and thus O(n) worst case insertion and lookup times.

AVL trees overcome this problem. An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.

Balance factor of each node = height of right subtree at that node - height of left subtree at that node.

Convert a tree into an array

Coming Soon...

Closest ancestor of two nodes in a tree

Coming Soon...

Construct a tree using postorder and preorder traversal

Coming Soon...

Count the number of leaves in a binary tree

Objective: Given the root pointer to a binary tree, find the number of leaves. In the binary tree given below, number of leaf nodes of 4.

Solution: Leaf has property that its left and right child both are null. Using this property we can recurse the tree from root node towards bottom moving to left and right branches and keep counting those nodes which has both the children as null. 

Time Complexity: O(n) where n is number of nodes in the tree.

Java Solution:

       
public class CountNoOfLeaves {

    public static void main(String[] args) throws Exception {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        node1.left = node2;
        node1.right = node3;
        node2.left = node7;
        node2.right = node9;
        node3.left = node5;
        node3.right = node4;
        System.out.println(numLeaves(node1));
    }


    private static int numLeaves(Node root){
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        return numLeaves(root.left) + numLeaves(root.right);
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

}


 

Delete a node from a Binary Search Tree

Coming Soon...

Level order traversal of a tree

Coming Soon...

Check if a binary tree is a binary search tree

Coming Soon...

Create a copy of a tree

Coming Soon.

Inorder traversal of a binary tree

Inorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then node and right subtree after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows inorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of Inorder traversal is - O(n)

Java Solution:

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void inorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        

        inorder(root.left);
        System.out.print(root.data + " ");
        //Traverse right subtree        

        inorder(root.right);
    }

    public static void main(String[] args) {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().inorder(node1);
    }
}

Postorder traversal of a binary tree

Postorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then right subtree and root node after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows postorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of postorder traversal is - O(n)

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void postorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        
        postorder(root.left);
        //Traverse right subtree        
        postorder(root.right);
        //Traverse root        
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().postorder(node1);
    }
}

Preorder traversal of a binary tree

Preorder tree traversal is a traversal method for binary tree where we traverse root first and then left subtree and right subtree after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows preorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of preorder traversal is - O(n)

Java Solution:

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void preorder(Node root){
        if(root == null){
            return;
        }
        //Traverse root        

        System.out.print(root.data + " ");
        //Traverse left subtree        

        preorder(root.left);
        //Traverse right subtree        

        preorder(root.right);
    }

    public static void main(String[] args) {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().preorder(node1);
    }
}

Create a mirror copy of a tree

Coming Soon...

Find the maximum depth in a tree

Coming Soon...

Find the minimum value in a binary search tree

Coming Soon...

Determine if two trees are identical

Coming Soon...

Delete a tree and free its nodes

Implementation of deletion of tree and its nodes is largely language dependent. If program is implemented using C/C++, it is program's duty to free up memory so code needs to traverse the tree in postorder fashion and keep freeing the nodes after visiting them.
If the program is implemented in Java, Java itself takes care of freeing up memory as long as object has no hard references pointing to it. Here is the Java solution for deleting a binary tree.

Java Solution:

public class DeleteTree {

    public static void main(String[] args) {
        //Build Tree        

        Node node1= new Node(1);
        Node node2= new Node(2);
        Node node3= new Node(3);
        Node node4= new Node(4);
        Node node5= new Node(5);
        Node node6= new Node(6);
        Node node7= new Node(7);
        Node node8= new Node(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node8;
        node5.left = node6;
        node6.right = node7;

        deleteTree(node1);
    }


    private static Node deleteTree(Node root){
        if(root == null){
            return null;
        }

        deleteTree(root.left);
        deleteTree(root.right);
        System.out.println("Deleting node:" + root.data);
        root.left = null;
        root.right = null;
        root = null;
        return root;
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data){
            this.data = data;
        }
    }
}

Determine the number of nodes in a binary tree

In order to find out number of nodes in a tree, we can traverse the tree using any of the traversal method - preorder, inorder and postorder and while traversing we can keep counting the nodes. Solution can be implemented using recursive approach as described earlier as well as using iterative method. In iterative method, we can use level order traversal and keep counting the nodes.
For example, number of nodes in the following binary tree is 9:

Time Complexity: O(n)

Java Recursive Solution:

public class NodeCount {
    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public int getNumberOfNodes(Node root){
        if(root == null){
            return 0;
        }

        return 1 + getNumberOfNodes(root.left) + getNumberOfNodes(root.right);
    }

    public static void main(String[] args) {
        //Build Tree

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("Number of nodes in tree are: " + new NodeCount().getNumberOfNodes(node1));
    }
}

Height of a binary tree

Height of a binary tree is 1+ number of edges between root node and a leaf node at longest distance from root node. Descendants of a node is one level deeper than that node. In other words, we need to find out distance from root node to deepest leaf node. Height of empty tree is 0. Height of tree in following tree is 4.

Ways to find out height:

1. Modified level order traversal: We can modify the level order traversal, where we are not just visiting the nodes level by level but we also keep track of level boundary. Total number of levels will be height of the tree.

2. Recursive method: 
In this method, we traverse the tree from root towards leaf recursively. We maintain a counter and increase the counter every time we move one level down. Final count is the height of the tree. Following the java solution for this. Height of the tree in this program is 5:

public class Height {

    public static void main(String[] args) throws Exception {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node7.right = node9;
        node9.left = node10;
        System.out.println(height(node1));
    }

    private static int height(Node root){
        if(root != null){
            return 1 + max(height(root.left), height(root.right));
        }

        return 0;
    }

    private static int max(int left, int right){
        if(left > right){
            return left;
        }

        return right;
    }
    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

}

Check If a String is a palindrome

Palindrome is a string which which reads the same backward as forward. For example: kayak, rotor, madam, radar, civic etc.

There are various ways to check whether String is a palindrome:

1. Reverse the string and compare: In this approach, we reverse the string and compare it with original string. If these two strings are same, it proves that string is palindrome. Time Complexity of this algorithm is still O(n) but it requires 2n operations (n for reverse and n for comparison)

2. Split the string from middle, reverse second half: In this approach, we form another string by splitting original string from middle to end. After split, we reverse this splitted string. Now, we run a loop to compare original list up to middle element with string formed by split and reverse. If comparison is successful, string is palindrome. It requires n operations (n/2 for split-reverse and n/2 for comparison)

3. Use two pointers: This is the most efficient method out of these three. We take two pointers - one from start of the string and another from end of the string. First pointer moves forward whereas second pointer moves backwards. At every iteration, we check if both the pointers have same character in the string. If both are same, first pointer is moved forward and second pointer is moved backwards. If values are not same, we terminate the loop and declare that string is not a palindrome.
Loop continues until second pointer index becomes lower than first pointer index.

Reverse a Linked List

Objective:
Reverse a linked list.  For example, resulting list after reversing the following list will have nodes in this order -  3, 2, 1.

To reverse a linked list, we need to maintain three pointers prev, current and next. Initially, prev will be pointing to null. We need to traverse through the list and move each pointer one node at a time. In each iteration, we need to unlink current.next from next and point to prev. We need to keep in mind that we need to move next first, so that we don't loose track of next node due to this unlinking. At the end, head will point to the last node in the chain and that way we'll reverse the whole linked list. This algorithm can implemented in iterative as well as recursive fashion.

Following java code gives solution for both the approaches:

Iterative Program:

public class LinkedList {

    Node head;
    Node lastNode;

    public static class Node {
        int data;
        Node next;

        public Node(int data){
            this.data = data;
            this.next = null;
        }
    }

    public void appendNode(int data){

        Node node = new Node(data);

        if(head == null){
            head = node;
            lastNode = head;
        }else {
            lastNode.next = node;
            lastNode = node;
        }
    }

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

public class ReverseLinkedList {

    private static LinkedList reverseList(LinkedList list) {
        LinkedList.Node prev = null;
        LinkedList.Node temp = list.head;

        while (temp != null) {
            LinkedList.Node current = temp;
            LinkedList.Node next = current.next;
            current.next = prev;
            temp = next;
            prev = current;
        }
        list.head = prev;

        return list;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList reverseList = reverseList(list);
        System.out.println();

        list.printList();
    }
}

Recursive Program:

public class ReverseLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList.Node newHead = recursiveReverse(list.head, null);
        list.head = newHead;
        System.out.println();

        list.printList();
    }


    private static LinkedList.Node recursiveReverse(LinkedList.Node head, 

                                                                LinkedList.Node prev) {
        if(head == null){
            return prev;
        }
        LinkedList.Node tmp = head.next;
        head.next = prev;
        return recursiveReverse(tmp, head);
    }
}

Find Loop in a Linked List

While traversing a linked list, when we reach already visited node again it is considered to be a loop in a linked list. We can't reach end of the linked list in case linked list has a loop.
Following diagram shows a linked list with loop. In this diagram, node 6 points back to node 3 which was already visited:

There are various ways to solve this problem:
1. Using HashSet
2. Tortoise Hare algorithm

1. Using HashSet: 

    While traversing the linked list, we insert the node in a HashSet. Every time we visit a node, we check if this node exists in the HashSet. if HashSet already contains this node that means we are visiting this node second time and that proves a cycle in the linked list. Time Complexity of searching in a HashSet is O(1), so time complexity of this algorithm remains O(n) only but it requires O(n) of additional space as well. For a linked list with huge number of nodes, this algorithm is not recommended due to memory requirements.

2. Using Tortoise Hare Algorithm:

This is also known as Floyd's cycle finding algorithm. This is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. 

Following diagram illustrates this algorithm:

In this algorithm, we maintain two pointers - one is slow pointer and another is fast pointer. Slow pointer is analogy for tortoise and fast pointer is analogous to a hare, that's why algorithm has this name. We start from head node towards the tail. Slow pointer moves one node at a time whereas fast pointer moves two nodes at a time. If there is no loop/cycle in the list, these pointer would never meet. But in case of a cycle, these pointers meet on some node. If these pointers meet it proves a cycle in the list else there is no cycle in the list.

Java Solution:

In this program, we have used three element linked list having nodes 1, 2 and 3. Node 3 points back to node 2.

public class DetectCycle {

    private static void detectLoop(LinkedList.Node head) {
        LinkedList.Node slow = head;
        LinkedList.Node fast = head;

        if (head.next == null) {
            System.out.println("Empty List");
        }

        while (fast != null && slow != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            }
            if (slow == fast) {
                System.out.println("Cycle found in the list");
                return;
            }
        }
        System.out.println("No Cycle found in the list");
    }

    public static void main(String[] args) {
        LinkedList.Node list = getLinkedList();
        detectLoop(list);
    }

    private static LinkedList.Node getLinkedList() {
        LinkedList.Node dummy = new LinkedList.Node(-9999);
        LinkedList.Node head = dummy;
        LinkedList.Node node1 = new LinkedList.Node(1);
        head.next = node1;
        head = head.next;
        LinkedList.Node node2 = new LinkedList.Node(2);
        head.next = node2;
        head = head.next;
        LinkedList.Node node3 = new LinkedList.Node(3);
        node3.next = node2;
        head.next = node3;
        return dummy.next;
    }

    static class LinkedList {
        Node head;

        public static class Node {
            int data;
            Node next;

            public Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
    }
}