Algorithm Interview – Java2Blog

Rotate Matrix by 90 degrees in java

Vijay Sinha — Wed, 19 May 2021 18:36:39 +0000

In this article, we will look into another interesting problem related to 2D Arrays. Given a Matrix of N X N Dimension we have to Rotate matrix by 90 degrees. We will perform Rotation both Clockwise i.e. Right Rotation and Anti-Clockwise i.e. Left Rotation respectively. We will discuss each operation in detail along with a hint to perform Rotation of Matrix K times.

Note: To Perform Any type of Rotation, The Matrix should have equal dimensions (N X N) i.e. No. of Rows in Matrix = No. of Columns in Matrix.

Clockwise or Right Rotate a Matrix

In this type, we need to Right Rotate the given N X N Matrix by 90 degrees. Let us understand this with an example:

Basically, we need to start from the last row in the Original Matrix and need to make each row as a column to rotate the matrix in Clockwise direction.

So, let us look at the approach to do this :

We will first transpose of given matrix or 2D Array. By Transpose, we mean each Row of the matrix becomes a Column and vice-versa. In simple words, each Element in i^th row is replaced by corresponding element in the i^th column. We will do this in code by Swapping the elements at the i^th row and column respectively. So, considering the above matrix the Transpose will be:

After doing transpose, we need to just reverse the contents/elements of each row. Since each Row of the matrix is a 1D Array itself, we just reverse each array or row after that we would have the Right Rotated Matrix. So after reversing the Transpose Matrix we get the result.

Implementation in Java

Now, let us look at the code to cover this approach considering the same example as discussed above.

public class RotateMatrix
{
  // Takes Matrix and Size of Matrix and performs Clockwise or Right Rotation by 90 degrees.    
  static void rightRotate(int matrix[][],int n)
  {
      
      //At first we perform transpose of the matrix
      //by swapping elements of every i'th row with j'th column
      for(int i=0;i



Output:



The Original Matrix is: 
1 2 3 
4 5 6 
7 8 9 
The Right Rotated Matrix is: 
7 4 1 
8 5 2 
9 6 3



Time Complexity: The time complexity of performing rotation is O(n²) as we traverse all the elements of the matrix while interchanging them.




Further reading:



Matrix multiplication in java

			Read more →
		



Find transpose of matrix in java

		Read more →
	





Anti-Clockwise or Left Rotate a Matrix



In this type, we need to Left Rotate the given N X N Matrix by 90 degrees. Let us understand this with an example:







Basically, we need to start from the last row in the Original Matrix and need to make each column as a row to rotate the matrix in anti clockwise direction.



So, let us look at the approach to do this :



Like the approach we followed above in Right Rotate, we will first transpose the given Matrix or 2D Array. We convert elements of each Row of the matrix becomes a Column and vice-versa. So, considering the above matrix the Transpose will be:







After getting the transpose, Instead of reversing the Rows like we did in Right Rotate, Here we reverse contents of each Column in the Matrix. After doing this, we will have our resultant Left Rotated Matrix:







Now let us look at the implementation in code:



public class RotateMatrix
{
  // Takes Matrix and Size of Matrix and performs Anti - Clockwise Rotation by 90 degrees.    
  static void leftRotate(int matrix[][],int n)
  {
      
      //At first we perform transpose of the matrix
      //by swapping elements of every i'th row with j'th column
      for(int i=0;i



Output:



The Original Matrix is: 
1 2 3 
4 5 6 
7 8 9 
The Left Rotated Matrix is: 
3 6 9 
2 5 8 
1 4 7



Time Complexity: The time complexity for this type is also O(n²).



How to Rotate Matrix K Times?



Now if we want to Rotate a matrix K times, Depending on the type of rotation just call the rightRotate() or leftRotate() method inside a loop K times and print the matrix once like this:



int k = 3;
while(k>0)
{
  leftRotate(matrix,n);   // Remove Print logic from the method before calling
  k--;
}
//Then Print Matrix



So that’s all about how to Rotate Matrix by 90 degrees in java. You can try out the code with different examples and let us know your queries.

Data Structures in java

Java2blog — Fri, 16 Apr 2021 05:02:56 +0000

In this post, we will see about various data structures in java.

Data structure is a way of storing and organizing data. Data structure provide a way to process and store data efficiently.

For example:

Imagine you have pile of books on the table and you are going to read these books one by one from the top. Can you think of any data structure which can simulate with this?
Yes, you can simply use stack to store the books, so it can be accessed in Last in first out fashion.

In this post, I am going to cover list of all important data structures in java which you can easily implement.

Array

Array is linear data structure which stores fixed number of similar elements. Array can store primitive data types as well as object but it should be of same kind. This is one of most used data structures in java.

Declare and initialize array in java

You can declare a String array as below:

String[] strArr=new String[10];

Here,
String is data type
strArr is variable name
10 is size of the array

You can also initialize array as below:

String[] strArr={"One","Two","Three"};

Advantages of array

You can randomly access array elements using index
It can represent multiple elements of same type with single name
You can implement various data strucures such as LinkedList, Stack and Queue using Array

Disadvantages of array

You need to know number of elements in advance.
You can not modify array once its size is defined
Insertion and deletion are quite costly operation in array as you need to shift elements.

Example

Here is an example program of an array.

package org.arpit.java2blog;

import java.util.Arrays;
public class StringArrayMain {

    public static void main(String[] args) {
        String[] strArr = {"One","Two","Three"};

        System.out.println("Array elements are:");
        // Iterate over array
        for (int i=0;i
Output:

Array elements are:

One

Two

Three

====================

Printing array elements using Arrays.toString():

====================

[One, Two, Three]



        

          import_contacts

        
Array practice programs

There are many java tricky  interview programs that can be asked in interview.
You should practice these java interview programs on array.

Find smallest and largest element in array
Find second largest number in array
Find missing number in an array
Separate 0’s and 1’s in array
Separate odd even numbers in java
Sort array of 0’s, 1’s and 2’s in java
Find number occurring odd number of times in array
Minimum numbers of platforms required for railway station in java
Find pair whose sum is closest to zero in array in java
Find pair whose sum is closest to X in array in java
Find all pairs of elements whose sum is equal to given number
Search element in row wise and column wise sorted matrix
Stock buy and sell to maximize profit.
Find local minima in array
Find leader in array
Find subarray with given sum
Sliding window maximum
Find peak element in array
Permutations of array in java
Subsets of set
Rotate array by K positions
Largest sum contiguous subarray
search an element in a sorted and rotated arraybinary in java
Minimum element in a sorted and ratated array in java
Minimum jumps required to reach end of array


Stack
Stack is abstract data type which depicts Last in first out (LIFO) behavior.

Stack implementation using Array
package org.arpit.java2blog.datastructures;

/**
 * @author Arpit Mandliya
 */
public class MyStack {
    int size;
    int arr[];
    int top;

    MyStack(int size) {
        this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }

    public void push(int element) {
        if (!isFull()) {
            top++;
            arr[top] = element;
            System.out.println("Pushed element:" + element);
        } else {
            System.out.println("Stack is full !");
        }
    }

    public int pop() {
        if (!isEmpty()) {
            int topElement = top;
            top--;
            System.out.println("Popped element :" + arr[topElement]);
            return arr[topElement];

        } else {
            System.out.println("Stack is empty !");
            return -1;
        }
    }

    public int peek() {
        if(!this.isEmpty())
            return arr[top];
        else
        {
            System.out.println("Stack is Empty");
            return -1;
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (size - 1 == top);
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack(5);
        myStack.pop();
        System.out.println("=================");
        myStack.push(100);
        myStack.push(90);
        myStack.push(10);
        myStack.push(50);
        System.out.println("=================");
        myStack.pop();
        myStack.pop();
        myStack.pop();
        System.out.println("=================");
    }
}

Output:

Stack is empty !

=================

Pushed element:100

Pushed element:90

Pushed element:10

Pushed element:50

=================

Popped element :50

Popped element :10

Popped element :90

=================

Stack implementation using LinkedList
package org.arpit.java2blog.datastructures;

public class StackUsingLinkedList {
    private Node head; // the first node

    // nest class to define linkedlist node
    private class Node {
        int value;
        Node next;
    }

    public StackUsingLinkedList() {
        head = null;
    }

    // Remove value from the beginning of the list to simulate stack
    public int pop() throws LinkedListEmptyException {
        if (head == null) {
            throw new LinkedListEmptyException();
        }
        int value = head.value;
        head = head.next;
        return value;
    }

    // Add value to the beginning of the list to simulate stack
    public void push(int value) {
        Node prevHead = head;
        head = new Node();
        head.value = value;
        head.next = prevHead;
    }

    public static void main(String args[])
    {
        StackUsingLinkedList sll=new StackUsingLinkedList();
        sll.push(200);
        sll.push(150);
        sll.push(80);
        sll.push(90);
        sll.push(600);
        sll.push(175);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        System.out.println("Removed element from LinkedList: "+sll.pop());
        sll.push(100);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        printList(sll.head);
    }
    public static void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
}

/**
 *
 * Throw LinkedListEmptyException if LinkedList is empty
 */

class LinkedListEmptyException extends RuntimeException {
    private static final long serialVersionUID = 1L;

    public LinkedListEmptyException() {
        super();
    }

    public LinkedListEmptyException(String message) {
        super(message);
    }
}

Output:

Removed element from LinkedList: 175

Removed element from LinkedList: 600

Removed element from LinkedList: 100

90 80 150 200

Implementation

 Java Program to implement stack using array.
Java Program to implement stack using Linked List
 Java Program to implement stack using two queues

Practice Programs
Sort a stack using another stack.
Queue
Queue is abstract data type which depicts First in first out (FIFO) behavior.

Queue implementation using array
package org.arpit.java2blog.datastructures;

public class MyQueue {

    private int capacity;
    int queueArr[];
    int front;
    int rear;
    int currentSize = 0;

    public MyQueue(int size) {
        this.capacity = size;
        front = 0;
        rear = -1;
        queueArr = new int[this.capacity];
    }

    /**
     * Method for adding element in the queue
     *
     * @param data
     */
    public void enqueue(int data) {
        if (isFull()) {
            System.out.println("Queue is full!! Can not add more elements");
        } else {
            rear++;
            if (rear == capacity - 1) {
                rear = 0;
            }
            queueArr[rear] = data;
            currentSize++;
            System.out.println(data + " added to the queue");
        }
    }

    /**
     * This method removes an element from the front of the queue
     */
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty!! Can not dequeue element");
        } else {
            front++;
            if (front == capacity - 1) {
                System.out.println(queueArr[front - 1] + " removed from the queue");
                front = 0;
            } else {
                System.out.println(queueArr[front - 1] + " removed from the queue");
            }
            currentSize--;
        }
    }

    /**
     * Method for checking if Queue is full
     *
     * @return
     */
    public boolean isFull() {
        if (currentSize == capacity) {
            return true;
        }
        return false;
    }

    /**
     * Method for checking if Queue is empty
     *
     * @return
     */
    public boolean isEmpty() {

        if (currentSize == 0) {
            return true;
        }
        return false;
    }

    public static void main(String a[]) {

        MyQueue myQueue = new MyQueue(6);
        myQueue.enqueue(1);
        myQueue.dequeue();
        myQueue.enqueue(30);
        myQueue.enqueue(44);
        myQueue.enqueue(32);
        myQueue.dequeue();
        myQueue.enqueue(98);
        myQueue.dequeue();
        myQueue.enqueue(70);
        myQueue.enqueue(22);
        myQueue.dequeue();
        myQueue.enqueue(67);
        myQueue.enqueue(23);
    }
}

Output:

1 added to the queue

1 removed from the queue

30 added to the queue

44 added to the queue

32 added to the queue

30 removed from the queue

98 added to the queue

44 removed from the queue

70 added to the queue

22 added to the queue

32 removed from the queue

67 added to the queue

23 added to the queue

Queue implementation using LinkedList
package org.arpit.java2blog.datastructures;

public class QueueUsingLinkedList
{
    private Node front, rear;
    private int currentSize; // size

    //Node data structure
    private class Node
    {
        int data;
        Node next;
    }

    //constructor
    public QueueUsingLinkedList()
    {
        front = null;
        rear = null;
        currentSize = 0;
    }

    public boolean isEmpty()
    {
        return (currentSize == 0);
    }

    //Remove item from the beginning of the list to simulate Queue
    public int dequeue()
    {
        int data = front.data;
        front = front.next;
        if (isEmpty())
        {
            rear = null;
        }
        currentSize--;
        System.out.println(data+ " removed from the queue");
        return data;
    }

    //Add data to the end of the list to simulate Queue
    public void enqueue(int data)
    {
        Node oldRear = rear;
        rear = new Node();
        rear.data = data;
        rear.next = null;
        if (isEmpty())
        {
            front = rear;
        }
        else
        {
            oldRear.next = rear;
        }
        currentSize++;
        System.out.println(data+ " added to the queue");
    }
    public static void main(String a[]){

        QueueUsingLinkedList queueUsingLinkedList = new QueueUsingLinkedList();
        queueUsingLinkedList.enqueue(60);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(10);
        queueUsingLinkedList.enqueue(20);
        queueUsingLinkedList.enqueue(40);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(70);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(80);
        queueUsingLinkedList.enqueue(100);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(150);
        queueUsingLinkedList.enqueue(50);
    }
}

Output:

60 added to the queue

60 removed from the queue

10 added to the queue

20 added to the queue

40 added to the queue

10 removed from the queue

70 added to the queue

20 removed from the queue

80 added to the queue

100 added to the queue

40 removed from the queue

150 added to the queue

50 added to the queue

Implementation

 Implement queue using arrays
 Implement queue using linked list

LinkedList
Singly LinkedList

In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate over linked list by using this condition.
package org.arpit.java2blog.datastructures;

class Node {
    public int data;
    public Node next;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

public class MyLinkedList {
    private Node head;

    public boolean isEmpty() {
        return (head == null);
    }

    // Method for inserting node at the start of linked list
    public void insertFirst(int data) {
        Node newHead = new Node();
        newHead.data = data;
        newHead.next = head;
        head = newHead;
    }

    // Method for deleting node from start of linked list
    public Node deleteFirst() {
        Node temp = head;
        head = head.next;
        return temp;
    }

    // Method used to delete node after provided node
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next = temp.next.next;
    }

    // Method used to insert at end of LinkedList
    public void insertLast(int data) {
        Node current = head;
        while (current.next != null) {
            current = current.next; // we'll loop until current.next is null
        }
        Node newNode = new Node();
        newNode.data = data;
        current.next = newNode;
    }

    // Method for printing Linked List
    public void printLinkedList() {
        System.out.println("Printing LinkedList (head --> last) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        MyLinkedList myLinkedlist = new MyLinkedList();
        myLinkedlist.insertFirst(50);
        myLinkedlist.insertFirst(60);
        myLinkedlist.insertFirst(70);
        myLinkedlist.insertFirst(10);
        myLinkedlist.insertLast(20);
        myLinkedlist.printLinkedList();
        // Linked list will be
        // 10 -> 70 ->  60 -> 50 -> 20

        System.out.println("=========================");
        System.out.println("Delete node after Node 60");
        Node node=new Node();
        node.data=60;
        myLinkedlist.deleteAfter(node);
        // After deleting node after 1,Linked list will be
        // 10 -> 70 -> 60 -> 20

        System.out.println("=========================");
        myLinkedlist.printLinkedList();
    }
}

Output:

Printing LinkedList (head –> last)

{ 10 }

{ 70 }

{ 60 }

{ 50 }

{ 20 } 
=========================

Delete node after Node 60

=========================

Printing LinkedList (head –> last)

{ 10 }

{ 70 }

{ 60 }

{ 20 }

Doubly LinkedList

In doubly linked list, Node has data and pointers to next node and previous node.You can iterate over linkedlist either in forward or backward direction as it has pointers to prev node and next node. This is one of most used data structures in java.
package org.arpit.java2blog.datastructures;

class Node {
    public int data;
    public Node next;
    public Node prev;

    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}

public class MyDoublyLinkedList {

    private Node head;
    private Node tail;
    int size;

    public boolean isEmpty() {
        return (head == null);
    }

    // Method to insert a node at the start of linked list
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        newNode.prev=null;
        if(head!=null)
            head.prev=newNode;
        head = newNode;
        if(tail==null)
            tail=newNode;
        size++;
    }

    // Method to insert a node at the start of linked list
    public void insertLast(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = null;
        newNode.prev=tail;
        if(tail!=null)
            tail.next=newNode;
        tail = newNode;
        if(head==null)
            head=newNode;
        size++;
    }
    // used to delete node from start of Doubly linked list
    public Node deleteFirst() {

        if (size == 0)
            throw new RuntimeException("Doubly linked list is already empty");
        Node temp = head;
        head = head.next;
        head.prev = null;
        size--;
        return temp;
    }

    // Method to delete node from last of Doubly linked list
    public Node deleteLast() {

        Node temp = tail;
        tail = tail.prev;
        tail.next=null;
        size--;
        return temp;
    }

    // Method to delete node after particular node
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next.next.prev=temp;
        temp.next = temp.next.next;

    }

    // Method to print Doubly Linked List forward
    public void printLinkedListForward() {
        System.out.println("Printing Doubly LinkedList (head --> tail) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }

    // Method to print Doubly Linked List forward
    public void printLinkedListBackward() {
        System.out.println("Printing Doubly LinkedList (tail --> head) ");
        Node current = tail;
        while (current != null) {
            current.displayNodeData();
            current = current.prev;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        MyDoublyLinkedList mdll = new MyDoublyLinkedList();
        mdll.insertFirst(50);
        mdll.insertFirst(60);
        mdll.insertFirst(70);
        mdll.insertFirst(10);
        mdll.insertLast(20);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();

        System.out.println("================");
        // Doubly Linked list will be
        // 10 ->  70 -> 60 -> 50 -> 20

        Node node=new Node();
        node.data=10;
        mdll.deleteAfter(node);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
        // After deleting node after 1,doubly Linked list will be
        // 20 -> 10 -> 60-> 50
        System.out.println("================");
        mdll.deleteFirst();
        mdll.deleteLast();

        // After performing above operation, doubly Linked list will be
        //  60 -> 50
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
    }
}

Output:

Printing Doubly LinkedList (head –> tail)

{ 10 }

{ 70 }

{ 60 }

{ 50 }

{ 20 } 
Printing Doubly LinkedList (tail –> head)

{ 20 }

{ 50 }

{ 60 }

{ 70 }

{ 10 } 
================

Printing Doubly LinkedList (head –> tail)

{ 10 }

{ 60 }

{ 50 }

{ 20 } 
Printing Doubly LinkedList (tail –> head)

{ 20 }

{ 50 }

{ 60 }

{ 10 } 
================

Printing Doubly LinkedList (head –> tail)

{ 60 }

{ 50 } 
Printing Doubly LinkedList (tail –> head)

{ 50 }

{ 60 }

Implementation

Implement singly linked list in java
Implement Doubly linked list in java



        

          import_contacts

        
LinkedList Practice Programs


How to reverse a linked list in java
How to reverse a linked list in pairs
How to find middle element of linked list in java
How to detect a loop in linked list in java
Find start node of loop in linkedlist
How to find nth element from end of linked list
How to check if linked list is palindrome in java
Add two numbers represented by linked list in java
Find intersection of two Linked Lists


Binary tree
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Example of binary tree:

package org.arpit.java2blog.datastructures;

import java.util.Stack;

public class BinaryTree {

    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    public void preorder(Node root) {
        if(root !=  null) {
            //Pre order traversal
            System.out.printf("%d ",root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }

    // Iterative solution
    public void preorderIter(Node root) {

        if(root == null)
            return;

        Stack s = new Stack();
        s.push(root);

        while(!s.empty()){

            Node n = s.pop();
            System.out.printf("%s ",n.data);

            if(n.right != null){
                s.push(n.right);
            }
            if(n.left != null){
                s.push(n.left);
            }

        }

    }

    public static void main(String[] args)
    {
        BinaryTree bi=new BinaryTree();
        // Creating a binary tree
        Node rootNode=createBinaryTree();
        System.out.println("Using Recursive solution:");

        bi.preorder(rootNode);

        System.out.println();
        System.out.println("-------------------------");
        System.out.println("Using Iterative solution:");

        bi.preorderIter(rootNode);
    }

    public static Node createBinaryTree()
    {

        Node rootNode =new Node(30);
        Node node20=new Node(50);
        Node node10=new Node(60);
        Node node30=new Node(80);
        Node node60=new Node(90);
        Node node50=new Node(100);
        Node node70=new Node(110);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Output:

Using Recursive solution:

30 50 60 80 90 100 110

————————-

Using Iterative solution:

30 50 60 80 90 100 110

Implementation
Binary tree in java


        

          import_contacts

        
Binary tree practice programs


Binary tree in java
Binary tree preorder traversal
Binary tree postorder traversal
Binary tree inorder traversal
Binary tree level order traversal
Binary tree spiral order traversal
Binary tree reverse level order traversal
Binary tree boundary traversal
Print leaf nodes of binary tree
Count leaf nodes in binary tree
get maximum element in binary tree
Print all paths from root to leaf in binary tree
Print vertical sum of binary tree in java
Get level of node in binary tree in java
Lowest common ancestor(LCA) in binary tree in java


Binary Search tree
Binary search tree is a special type of binary tree which have following properties.

Nodes which are smaller than root will be in left subtree.
Nodes which are greater than root will be right subtree.
It should not have duplicate nodes
Both left and right subtree also should be binary search tree.


package org.arpit.java2blog.datastructures;

public class MyBinarySearchTree {
    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }

    public static boolean search(Node root, Node nodeToBeSearched)
    {
        if(root==null)
            return false;
        if(root.data== nodeToBeSearched.data)
        {
            return true;
        }
        boolean result=false;

        if(root.data > nodeToBeSearched.data)
            result=search(root.left,nodeToBeSearched);
        else if(root.data < nodeToBeSearched.data)
            result= search(root.right,nodeToBeSearched);

        return result;
    }

    public static Node insert(Node root, Node nodeToBeInserted)
    { if(root==null) {
        root=nodeToBeInserted; return root;
    } if(root.data > nodeToBeInserted.data)
    {
        if(root.left==null)
            root.left=nodeToBeInserted;
        else
            insert(root.left,nodeToBeInserted);
    }
    else if(root.data < nodeToBeInserted.data)
        if(root.right==null)
            root.right=nodeToBeInserted;
        else
            insert(root.right,nodeToBeInserted);
        return root;
    }

    public static void inOrder(Node root)
    {
        if(root==null)
            return;
        inOrder(root.left);
        System.out.print(root.data+" ");
        inOrder(root.right);
    }
    public static void main(String[] args)
    {
        // Create binary search tree
        Node rootNode=createBinarySearchTree();
        Node node55=new Node(55);
        boolean result=search(rootNode,node55);
        System.out.println("Searching for node 55 : "+result);
        System.out.println("---------------------------");
        Node node13=new Node(13);
        Node root=insert(rootNode,node13);
        System.out.println("Inorder traversal of binary tree after adding 13:");
        inOrder(root);

    }

    public static Node createBinarySearchTree()
    {
        Node rNode =new Node(40);
        Node node20=new Node(20);
        Node node10=new Node(10);
        Node node30=new Node(30);
        Node node60=new Node(60);
        Node node50=new Node(50);
        Node node70=new Node(70);
        Node node5=new Node(5);
        Node node55=new Node(55);

        insert(null,rNode);
        insert(rNode,node20);
        insert(rNode,node10);
        insert(rNode,node30);
        insert(rNode,node60);
        insert(rNode,node50);
        insert(rNode,node70);
        insert(rNode,node5);
        insert(rNode,node55);
        return rNode;
    }

}

Output:

Searching for node 55 : true

—————————

Inorder traversal of binary tree after adding 13:

5 10 13 20 30 40 50 55 60 70

Implementation
Binary search tree in java


        

          import_contacts

        
Binary search tree Practice programs


Binary search tree in java
Delete node from binary search tree
Minimum and maximum elements in binary search tree
LCA of binary search tree
inorder successor in binary search tre
Conver sorted array to balanced BST
Convert sorted Linked List to balanced BST
Convert sorted Linked List to balanced BST
Check if a binary tree is binary search tree or not in java


Trie
Trie is data structure which is used to store in such a way that data can be retrieved faster.

Some real time examples:

Trie can be used to implement Dictionary.
We can put words in Trie and its children linkedlist will have its child nodes.

Let’s say you want to insert do, deal , dear , he , hen , heat etc.
Here is the trie representation of the data:

package org.arpit.java2blog.datastructures;

/*
 *  Java Program to Implement Trie
 */

import java.util.*;

class TrieNode
{
    char data;
    boolean isEnd;
    int count;
    LinkedList childList;

    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList();
        isEnd = false;
        data = c;
        count = 0;
    }
    public TrieNode getChild(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.data == c)
                    return eachChild;
        return null;
    }
}

public class Trie
{
    private TrieNode root;

    /* Constructor */
    public Trie()
    {
        root = new TrieNode(' ');
    }
    /* Method for inserting words from trie*/
    public void insert(String word)
    {
        if (search(word) == true)
            return;
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child != null)
                tempCurr = child;
            else
            {
                // If child not present, adding it io the list
                tempCurr.childList.add(new TrieNode(ch));
                tempCurr = tempCurr.getChild(ch);
            }
            tempCurr.count++;
        }
        tempCurr.isEnd = true;
    }
    /* Method for searching words in Trie*/
    public boolean search(String word)
    {
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            if (tempCurr.getChild(ch) == null)
                return false;
            else
                tempCurr = tempCurr.getChild(ch);
        }
        if (tempCurr.isEnd == true)
            return true;
        return false;
    }
    /* Method for removing words from trie*/
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not present in trien");
            return;
        }
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray())
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child.count == 1)
            {
                tempCurr.childList.remove(child);
                return;
            }
            else
            {
                child.count--;
                tempCurr = child;
            }
        }
        tempCurr.isEnd = false;
    }

    public static void displayWordsInTrie(TrieNode root, String str)
    {
        TrieNode tempCurr = root;
        if(root.childList==null || root.childList.size()==0)
            return;
        Iterator iter=tempCurr.childList.iterator();
        while(iter.hasNext())
        {
            TrieNode trieNode= (TrieNode) iter.next();
            str+=trieNode.data;
            displayWordsInTrie(trieNode,str);
            if(trieNode.isEnd==true)
            {
                System.out.print(" "+str);
                str=str.substring(0,str.length()-1);
            }
            else
            {
                str=str.substring(0,str.length()-1);
            }
        }

    }
    public static void main(String[] args)
    {
        Trie t = new Trie();
        t.insert("apple");
        t.insert("ape");
        t.insert("goat");
        t.insert("goa");
        t.insert("apt");

        System.out.println("go present in trie : "+t.search("go"));
        System.out.println("goa present in trie : "+t.search("goa"));
        System.out.println("appl present in trie : "+t.search("ape"));
        System.out.println("========================");
        System.out.println("Displaying all word present in trie : ");
        displayWordsInTrie(t.root,"");
    }
}

Output:

go present in trie : false

goa present in trie : true

appl present in trie : true

========================

Displaying all word present in trie :

 apple ape apt goat goa

Implementation
Trie data structure in java
Heap
A min heap is complete binary tree based data structure in which value of root node is less than or equal to value of child nodes.

Implementation
package org.arpit.java2blog.datastructures;

import java.util.Arrays;
public class MinHeap
{
    int Heap[];
    int size;
    int capacity;

    public MinHeap(int size)
    {
        this.capacity = size;
        this.size = 0;
        Heap = new int[size];
    }

    int parent(int i)
    {
        return (i - 1)/2;     //returns the parent node index for ith node
    }

    int leftChild(int i)
    {
        return (2 * i) + 1;              //returns the left child index.
    }

    int rightChild(int i)
    {
        return (2 * i) + 2;              //return the right child index.
    }

    boolean isLeaf(int i)   //checks if ith node is leaf node or not.
    {
        if (rightChild(i) >= size || leftChild(i) >= size)
            return true;

        return false;
    }

    /* Method to insert node in MinHeap

     */
    void insert(int data)
    {
        if (size >= capacity)
            return;

        Heap[size] = data;
        int tempCurr = size;

        while (Heap[tempCurr] < Heap[parent(tempCurr)])
        {
            swap(tempCurr, parent(tempCurr));
            tempCurr = parent(tempCurr);
        }
        size++;
    }

    //removes and returns the minimum element or the root from the heap
    int extractMinimum()
    {
        int min = Heap[0];
        Heap[0] = Heap[--size];
        minHeapify(0);
        System.out.print("\nThe Min Heap after Removing node is :");

        for(int i=0;i Heap[leftChild(i)] || Heap[i] > Heap[rightChild(i)])
            {
                if(Heap[leftChild(i)] < Heap[rightChild(i)])
                {
                    swap(i, leftChild(i));
                    minHeapify(leftChild(i));
                }
                else
                {
                    swap(i, rightChild(i));
                    minHeapify(rightChild(i));
                }

            }
        }

    }

    // builds the min-heap using the minHeapify
    public void minHeap()
    {
        // we call until size/2 cause parent nodes present till that index.
        for (int i = (size-1)/2; i >= 0; i--)
        {
            minHeapify(i);
        }
    }

    //Prints the contents of heap
    public void printHeap()
    {
        for (int i = 0; i < (size / 2); i++)
        {
            if(i==0)
                System.out.print("Root : "+ Heap[i]);
            else
                System.out.print("Parent : " + Heap[i]);

            if (leftChild(i) < size)
                System.out.print(" Left : " + Heap[leftChild(i)]);

            if (rightChild(i) < size)
                System.out.print(" Right : " + Heap[rightChild(i)]);

            System.out.println();
        }
    }

    // swaps two nodes of the heap
    void swap(int x, int y)
    {
        int temp;
        temp = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = temp;
    }

    //Driver Code to test above methods.
    public static void main(String[] args)
    {

        // Creating a Min heap of capacity 6.
        MinHeap heap = new MinHeap(6);

        heap.insert(100);
        heap.insert(200);
        heap.insert(500);
        heap.insert(700);
        heap.insert(800);
        heap.insert(900);

        // then build the Min Heap
        heap.minHeap();
        System.out.println("The Min Heap is : "+     Arrays.toString(heap.Heap));

        // Get Minimum Operation
        System.out.println("\nThe Min Value in the heap : " + heap.getMinimum());
        System.out.println();

        heap.printHeap();

        // Extract Minimum Operation
        System.out.println("Extracted Minimum Node in the heap : " + heap.extractMinimum());
        System.out.println();

        // Finally print heap to check deleted item.
        heap.printHeap();

    }
}

Output:

The Min Heap is : [100, 200, 500, 700, 800, 900]
The Min Value in the heap : 100
Root : 100 Left : 200 Right : 500

Parent : 200 Left : 700 Right : 800

Parent : 500 Left : 900
The Min Heap after Removing node is :200 700 500 900 800

Extracted Minimum Node in the heap : 100
Root : 200 Left : 700 Right : 500

Parent : 700 Left : 900 Right : 800

Graph

 Graph is a data structure for storing connected data
 It contains group of vertices and edges
 Graph can be of two types: Directed and undirected
 It contains group of vertices and edges
 Graph can be disjoint or connected and there are various algorithms such as depth first search to find this out.


Implementation
package org.arpit.java2blog.datastructures;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class GraphMain
{

    static class Node
    {
        int data;
        boolean visited;
        List neighbours;

        Node(int data)
        {
            this.data=data;
            this.neighbours=new ArrayList<>();

        }
        public void addneighbours(Node neighbourNode)
        {
            this.neighbours.add(neighbourNode);
        }
        public List getNeighbours() {
            return neighbours;
        }
        public void setNeighbours(List neighbours) {
            this.neighbours = neighbours;
        }
    }

    // Recursive DFS
    public  void recursiveDFS(Node node)
    {
        System.out.print(node.data + " ");
        List neighbours=node.getNeighbours();
        node.visited=true;
        for (int i = 0; i < neighbours.size(); i++) {
            Node n=neighbours.get(i);
            if(n!=null && !n.visited)
            {
                recursiveDFS(n);
            }
        }
    }

    // Iterative DFS using stack
    public  void iterativeDFS(Node node)
    {
        Stack stack=new  Stack();
        stack.add(node);
        while (!stack.isEmpty())
        {
            Node element=stack.pop();
            if(!element.visited)
            {
                System.out.print(element.data + " ");
                element.visited=true;
            }

            List neighbours=element.getNeighbours();
            for (int i = 0; i < neighbours.size(); i++) {
                Node n=neighbours.get(i);
                if(n!=null && !n.visited)
                {
                    stack.add(n);
                }
            }
        }
    }

    public static void main(String arg[])
    {

        Node node40 =new Node(40);
        Node node10 =new Node(10);
        Node node20 =new Node(20);
        Node node30 =new Node(30);
        Node node60 =new Node(60);
        Node node50 =new Node(50);
        Node node70 =new Node(70);

        node40.addneighbours(node10);
        node40.addneighbours(node20);
        node10.addneighbours(node30);
        node20.addneighbours(node10);
        node20.addneighbours(node30);
        node20.addneighbours(node60);
        node20.addneighbours(node50);
        node30.addneighbours(node60);
        node60.addneighbours(node70);
        node50.addneighbours(node70);

        GraphMain gm = new GraphMain();

        System.out.println("Iterative DFS traversal ");
        gm.iterativeDFS(node40);

        System.out.println();

        // Resetting the visited flag for nodes
        node40.visited=false;
        node10.visited=false;
        node20.visited=false;
        node30.visited=false;
        node60.visited=false;
        node50.visited=false;
        node70.visited=false;

        System.out.println("Recursive DFS traversal ");
        gm.recursiveDFS(node40);
    }
}

Output:

Iterative DFS traversal

40 20 50 70 60 30 10

Recursive DFS traversal

40 10 30 60 70 20 50

 Inbuild data structures in java
There are lot of good data structures provided by Java language.
Here are few important ones:


        

          import_contacts

        
String

String is most used data structure in java. There are lot of java interview programs on String which can be asked in interview.

How to reverse String in java
How to check if two Strings are angrams
Find length of String without using java inbuilt length method
Find all substrings of String in java
Find First non repeated character in a String
Java Program to check Palindrome String
Why String is immutable in java
Find duplicate characters in String
Longest common prefix in array of Strings


HashMap

 HashMap is used to store key value pairs
 HashMap is neither synchronized nor thread safe.
 HashMap does not allow duplicate keys
 HashMap is unordered collection and does not give guarantee for specific order

package org.arpit.java2blog;

import java.util.HashMap;
public class HashMapMain {

    public static void main(String[] args) {
        HashMap map = new HashMap();
        // Putting key-values pairs in HashMap
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");

        System.out.println(map);
    }
}

Output:

{1=One, 3=Three, 2=Two, 4=Four}

LinkedHashMap

 LinkedHashMap implements Map interface and extends HashMap class
 LinkedHashMap maintains insertion order for key value pair
 LinkedHashMap does not allow duplicate keys
 LinkedHashMap uses double linked list to maintain insertion order

package org.arpit.java2blog;

import java.util.HashMap;
public class LinkedHashMapMain {

    public static void main(String[] args) {
        Map map = new LinkedHashMap();
        // Putting key-values pairs in HashMap
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");

        System.out.println(map);
    }
}

Output:

{1=One, 2=Two, 3=Three, 4=Four}

ArrayList

 ArrayList is resizable array which can dynamically grow 
 It uses array as internal data structure and increses its size by half when its size is increased
 ArrayList is not synchronized
 ArrayList implements List interface

package org.arpit.java2blog.datastructures;

import java.util.ArrayList;

public class ArrayListMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        System.out.println("ArrayList:");

        for (String str : list) {
            System.out.println(str);
        }
    }
}

Output:

ArrayList:

One

Two

Three

Four

LinkedList

 Java LinkedList class used doubly linked list to store the elements
 LinkedList maintains insertion order
 It is not synchronized
 Manipulation is quite fast in LinkedList as no shifting is required
 LinkedList can be Stack, Queue or LinkedList

import java.util.LinkedList;
import java.util.Iterator;

public class LinkedListMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");

        System.out.println("LinkedList:");

        Iterator it=list.iterator();  
        while(it.hasNext()){  
            System.out.println(it.next());  
        }  
    }
}

Output:

LinkedList:

One

Two

Three

Four

HashSet

 https://java2blog.com/how-hashset-works-in-java/ implements Set interface and it does not allow duplicate elements
 HashSet does not maintain insertion order
 It is not synchronized and not thread safe

package org.arpit.java2blog.datastructures;

import java.util.HashSet;
import java.util.Iterator;

public class HashSetMain {
    /*
     * @author : Arpit Mandliya
     */
    public static void main(String[] args) {
        HashSet set = new HashSet<>();
        set.add("One");
        set.add("Two");
        set.add("One");
        set.add("Three");
        set.add("Two");

        System.out.println("HashSet:");

        Iterator it=set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

Output:

HashSet:

One

Two

Three

As you can see, duplicate Strings are removed from the HashSet.

That’s all about Data structures in Java.

Top 100+ Java Coding Interview Questions

Java2blog — Sun, 29 Nov 2020 14:19:00 +0000

I have been posting data structure and coding interview questions on various topics such as Array, Queue, Stack, Binary tree, LinkedList, String, Number, ArrayList, etc. So I am consolidating a list of java coding interview questions to create an index post. I will keep adding links to this post whenever I will add new java coding interview question.

These are frequently asked java coding interview questions in 2025.

If you want to practice and improve data structure and algorithm programs, this post will be very helpful to you. I will recommend you to try it yourself first and then check the solution.

String

Question 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?

Solution: There are many ways to do it, some of them are:

Using for loop
Using recursion
Using StringBuffer

Please refer to the solution at reverse a String in java

Question 2 : Write a java program to check if two Strings are anagram in java?

Solution: Two string are anagrams if they have same characters but in different order. For example: Angel and Angle are anagrams
There are few ways to check if Strings are anagrams. Some of them are:

Using String methods
Using array.sort

Check solution at check if two Strings are anagram in java.

Question 3 : Write a program to check if String has all unique characters in java?

Solution: Here are some ways to check if String contains all unique characters

By using HashSet
Using indexOf and lastIndexOf methods of String
By Using ascii value of characters.

Please refer to complete solution at check if String has all unique characters.

Question 4 : How to check if one String is rotation of another String in java?

Solution: Let’s say you want to check whether str1 and str2 is rotation of one another or not.

Create a new String with str3= str1 + str1
Check if str3 contains str2 or not.
if str3 contains str2 then str2 is rotation of str1 else it is not

You can find complete solution at check if one String is rotation of another in java.

Question 5 : How to find duplicate characters in String in java?

Solution: Here is a solution to find duplicate characters in String.

Create a HashMap and character of String will be inserted as key and its count as value.
If Hashamap already contains char,increase its count by 1, else put char in HashMap.
If value of Char is more than 1, that means it is duplicate character in that String.

Please refer to solution at program to find duplicate characters in a String.

Question 6 : Find first non repeated character in String in java?

Solution: There are may ways to find it.
Some of them are:

Using LinkedHashMap
Using indexOf and lastIndexOf methods.

Please find complete solution at find first non repeated character in a String.

Question 7 : Find all substrings of String in java?

Solution: Java program to find all substrings of a String.
For example: If input is "abb" then output should be "a", "b","b", "ab", "bb", "abb"
We will use String class’s subString method to find all subString.
Please refer to complete solution at find all subStrings of String.

Question 8 : Find length of String without using any inbuilt method in java?

Solution: You can use try catch block for catching StringIndexOutOfBoundException and when this exception aries, you can simply return i(Index at which you will get the exception)
Please refer to complete solution at find length of String without inbuilt methods.

Question 9 : Write a program to print all permutations of String in java?

Solution: Take out first character of String and insert into different places of permutations of remaining String recursively. Please find complete solution at how to find all permutations of String in java.

Array

You may be asked lot of java coding interview questions on Array. You can practice following coding questions on Array to ace coding interview.

Question 10 : Write java Program to Find Smallest and Largest Element in an Array.

You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide an optimum solution to find the missing number. Number can not be repeated in the arry.
For example:

int[] arr1={7,5,6,1,4,2};
Missing numner : 3
int[] arr2={5,3,1,2};
Missing numner : 4

Solution : Java Program to Find Smallest and Largest Element in an Array

Question 11 : Find missing number in the array.

You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide optimum solution to find the missing number. Number cannot be repeated in the arry.
For example:

int[] arr1={7,5,6,1,4,2};
Missing numner : 3
int[] arr2={5,3,1,2};
Missing numner : 4

Solution : Find missing number in the array.

Question 12 : Search an element in rotated and sorted array.

You are given an sorted and rotated array as below:

int arr[]={16,19,21,25,3,5,8,10};

If you note that array is sorted and rotated. You need to search an element in above array in o(log n) time complexity.
Solution : Search element in rotated and sorted array

Question 13 : Find minimum element in a sorted and rotated array.

You are given an sorted and rotated array as below:

int arr[]={16,19,21,25,3,5,8,10};
Minimum element in the array : 3

If you note that array is sorted and rotated. You need to i an element in above array in o(log n) time complexity.
Solution : Find minimum element in a sorted and rotated array

Question 14: Find second largest number in an array

You are given an sorted and rotated array as below:
For example:

int[] arr1={7,5,6,1,4,2};
Second largest element in the array : 6

Solution : java program to find second largest number in an array.

Question 15 : Find the number occurring odd number of times in an array

You are given a array of integer. All numbers occur even number of times except one. You need to find the number which occurs odd number of time. You need to solve it with o(n) time complexity and o(1) space complexity.
For example:

int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is : 50

Solution : java program to find number occurring odd number of times in an array.

Question 16 : Find minimum number of platforms required for railway station

You are given arrival and departure time of trains reaching to a particular station. You need to find minimum number of platforms required to accommodate the trains at any point of time.

For example:

arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4

Please note that arrival time is in chronological order.

Solution : Find minimum number of platforms required for railway station.

Question 17 : Find a Pair Whose Sum is Closest to zero in Array

Given array of +ve and -ve integers ,we need to find a pair whose sum is closed to Zero in Array.
For example:

array[]={1,3,-5,7,8,20,-40,6};
The pair whose sum is closest to zero :  -5 and 6

Solution : Find a Pair Whose Sum is Closest to zero in Array in java.

Question 18 : Given a sorted array and a number x, find the pair in array whose sum is closest to x

Given a sorted array, we need to find a pair whose sum is closed to number X in Array.
For example:

array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5 :  1 and 3

Solution : Find a Pair Whose Sum is Closest to X in Array in java.

Question 19 : Find all pairs of elements from an array whose sum is equal to given number

Given a array,we need to find all pairs whose sum is equal to number X.
For example:

array[]={ -40, -5, 1, 3, 6, 7, 8, 20 };
Pair of elements whose sum is equal to 15 :  7, 8 and -5, 20

Solution : Find all pairs of elements from an array whose sum is equal to given number .

Question 20: Given an array of 0’s and 1’s in random order, you need to separate 0’s and 1’s in an array.

For example:

arr[] = {0,1,0,0,1,1,1,0,1}
Array after separating 0 and 1 numbers :
{0,0,0,0,1,1,1,1,1}

Solution : Separate 0s and 1s in array.

Question 21 : Separate odd and even numbers in an array

Given an array of integers, you need to segregate odd and even numbers in an array.
Please note: Order of elements can be changed.

For example:

arr[] = {12, 17, 70, 15, 22, 65, 21, 90}
Array after separating odd and even numbers :
{12, 90, 70, 22, 15, 65, 21, 17}

Solution : Separate 0s and 1s in array.

Question 22 : Given an array containing zeroes, ones and twos only. Write a function to sort the given array in O(n) time complexity.

For example:

Input :
[1, 2, 2, 0, 0, 1, 2, 2, 1]

Output :
[0, 0, 1, 1, 1, 2, 2, 2, 2]

Solution : Sort an array of 0s, 1s and 2s.

Question 23 : Find local minima in array

A local minima is less than its neighbours

For example:

Input :

int [] arr = {10, 5, 3, 6, 13, 16, 7};
Output: 2

int []arr = {11,12,13,14};
Output: 11

int []arr = {10};
Output: 10

int []arr = {8,6};
Output: 6

Question 24 : Sliding window maximum in java

Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K.

For example:

Input :
Input : int[] arr = {2,6,-1,2,4,1,-6,5}
int k = 3
output : 6,6,4,4,4,5

Solution : Find the local minima in array.

Question 25 : Count number of occurrences (or frequency) of each element in a sorted array

Given a Sorted Array of integers containing duplicates. Find the frequency of every unique element present in the array.
Frequency is defined as the number of occurrence of any element in the array.

For example :

Input :
Input:
int[] arr = {1, 1, 1, 3, 3, 4, 5, 5, 6, 6};
Output:
Frequency of 1 is : 3
Frequency of 3 is : 2
Frequency of 4 is : 1
Frequency of 5 is : 2
Frequency of 6 is : 2

Solution : Count number of occurrences (or frequency) of each element in a sorted array.

Question 26 : Find subarrays with given sum in an array.

Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
For example :

Input :
Input-int[] arr = {2, 3, 6, 4, 9, 0, 11};
int num = 9
Output-
starting index : 1, Ending index : 2
starting index : 5, Ending index : 5
starting index : 5, Ending index : 6

Solution : Find subarrays with given sum in an array.

Question 27 : Find peak element in the array.

Peak Element is the element of the array which is GREATER THAN / EQUAL TO its neighbours, that is, for an element at i th index, the neighbour elements at index i-1 & i+1 must be greater than equal to element at i th position.
Solution : Find peak element in the array.

Question 28 : Find leaders in an array.

We need to print all the leaders present in the array. Element is the leader if it is greater than right side of elements.

arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements

For example:
Solution : Find leaders in an array.

Question 29 : Count 1’s in sorted Binary Array.

Print number of 1’s in a given sorted Binary Array.
For example :

Input :
int[] arr = {0,0,0,1,1,1,1};
output : 4
int[] arr = {0,0,1};
output : 1

Solution : Count 1’s in sorted Binary Array.

Question 30 : Find first repeating element in an array of integers.

Find the first repeating element in array of integers.
For example :

Input :
Input: array[] = {10, 7, 8, 1, 8, 7, 6}
Output: 7 [7 is the first element actually repeats]

Solution : Find first repeating element in an array of integers.

Question 31 : Check if Array Elements are Consecutive.

Given an array, we need to check if array contains consecutive elements.
For example :

Input: array[] = {5, 3, 4, 1, 2}
Output: true
As array contains consecutive elements from 1 to 5
Input: array[] = {47, 43, 45, 44, 46}
Output: true
As array contains consecutive elements from 43 to 47
Input: array[] = {6, 7, 5, 6}
Output: false
As array does not contain consecutive elements.

Solution : Check if Array Elements are Consecutive.

Question 32 : Permutations of array in java.

Given array of distinct integers, print all permutations of the array.
For example :

array : [10, 20, 30]

Permuations are :

[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]

Solution : Permutations of array in java.

Question 33 : Rotate an array by K positions.

For example :

N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then rotated array will be  {5, 6, 1, 2,  3,  4}

Solution : Rotate an array by K positions.

Question 34 : Stock Buy Sell to Maximize Profit.

Given an array of integers representing stock price on single day, find max profit that can be earned by 1 transaction.
So you need to find pair (buyDay,sellDay) where buyDay < = sellDay and it should maximise the profit.
For example :

int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
Max profit can be gain by buying at 1th day(0 based indexing) and sell at 4th day.
Max profit = 99-12 =87

Solution : Stock Buy Sell to Maximize Profit.

Question 35 : Find maximum difference between two elements such that larger element appears after the smaller number.

Given array of integers, find Maximum difference between two elements such that larger element appears after the smaller number
For example :

int arr[]={14, 12, 70, 15, 95, 65, 22, 30};
Max Difference =95-12 = 83

Solution : Maximum difference between two elements such that larger element appears after the smaller number.

Question 36 : Search in a row wise and column wise sorted matrix.

Given row wise and column wise sorted matrix ,we need to search element with minimum time complexity.
Solution : Search in a row wise and column wise sorted matrix.

Question 37 : Largest sum contiguous subarray.

Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
For example :

for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6

Solution : Largest sum contiguous subarray.

Question 38 : Find the Contiguous Subarray with Sum to a Given Value in an array.

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example :

arr[]={14, 12, 70, 15, 99, 65, 21, 90};
X =97.
Sum found between index 1 to 3
Elements are 12, 17 and 15

Solution : Find the Contiguous Subarray with Sum to a Given Value in an array.

Question 39 : Longest Common Prefix in an array of Strings in java.

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example :

String[] strArr={"java2blog","javaworld","javabean","javatemp"};
So Longest common prefix in above String array will be “java” as all above string starts with “java”.

Solution : Longest Common Prefix in an array of Strings in java.

Question 40 : Find all subsets of set (power set) in java.

Given a set of distinct integers, arr, return all possible subsets (the power set).
For example :

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Solution : Find all subsets of set in java.

Stack

Question 41: Implement a stack using array.

You need to implement Stack using array. You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution : Java Program to implement stack using array.

Question 42: Implement a stack using Linked List.

You need to implement Stack using Linked List. You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution : Java Program to implement stack using Linked List

Question 43: Implement a stack using two queues.

You need to use two queues to implement stack behavior.You need to write push and pop methods to demonstrate Stack behavior(Last In First Out).
Solution : Java Program to implement stack using two queues

Question 44 : Sort an stack using another stack

You need to sort an stack using another stack. You can use push and pop operation of stack to do so,
Solution : Sort a stack using another stack.

Queue

Question 45: Implement Queue using Array in java.

You need to use array to implement queue.
Solution : Implement Queue using Array in java

Question 46: Implement a stack using two queues .

You need to use Linked list to implement queue.
Solution : Java Program to implement queue using linked list

Linked List

Question 47 : Implement singly linked list in java.

You need to implement singly linked list data structures.You need to write simple program to demonstrate insert , delete operations.

Solution : Java program to implement singly linked list in java.

Question 48: How to reverse linked list in java.

You need to write iterative and recursive solution to reverse linked list.
Solution : Java program to reverse linked list in java.

Question 49: How to find middle element of linked list.

You need to write java program to find middle element of linked list in most optimize way.

Solution : Java program to find middle element of linked list.

Question 50 : How to find nth element from end of linked list .

You need to write java program to find nth element of linked list in most optimize way.
In question 6, Node 7 is 3rd from last of linked list.
Solution : How to find nth element from end of linked list.

Question 51 : How to detect a loop in linked list. If linked list has loop, find the start node for the loop.

You need to write a java program to detect whether any loop exists in linked list and if loop exists , you need to find start node for the linked list.
Solution : How to detect loop in linked list.
How to find start node of loop in linked list.

Question 52: How to check if linked list is palindrome or not?

A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed. For example: 12121 is palindrome as it reads same forward or reversed. madam is also a palindrome . So we need write java programs to check if linked list is palindrome or not.
Solution : Java program to check if linked list is palindrome.

Question 53 : Find intersection of two linked lists?

Given two singly linked lists, find if two linked lists intersect. If they intersect, find intersection point.

Solution : Intersection of two linked list

Question 54 : How to reverse a linked list in pairs?

You need to write a java program to reverse linked list in pairs.

Solution : Java program to reverse linked list in pair.

Question 55 : Implement Doubly linked list in java?

You need to write a java program to implement doubly linked list in java.

Solution : Doubly Linked List in java

Binary Tree

Question 56 : How can you traverse binary tree?

There are three ways to traverse binary tree.

Question 57 : Write an algorithm to do level order traversal of binary tree?

You need to write java program to do level order traversal of binary tree. You can use queue data structure to do level order traversal.

Solution : Level order traversal of binary tree.

Question 58 : Write an algorithm to do spiral order traversal of binary tree?

You need to write java program to do spiral level order traversal of binary tree

Solution : Sprial order or zigzag traversal of binary tree.

Question 59 : How can you print leaf nodes of binary tree?

You need to write java program to print all leaf nodes of binary tree.

Leaf nodes for above binary tree will be 5 , 30 , 55 ,70
Solution : Print leaf nodes of binary tree.

Question 60 : How to count leaf nodes of binary tree.

You need to write java program to count leaf nodes of binary tree.
Count of Leaf nodes for binary tree used in Question 15 are 5.
Solution : Count leaf nodes of binary tree.

Question 61 : How to print all paths from root to leaf in binary tree.

You need to write a program to print all paths from root to leaf.

Solution : Print all paths from root to leaf in binary tree.

Question 62 : How to find level of node in binary tree

Given a node, you need to find level of a node. For example : Level of node will 3 for node 70 used in Question 14.
Solution: Find level of node in binary tree.

Question 63 : How to find maximum element in binary tree.

You need to write a java program to find maximum element in binary tree.
Solution : Find maximum element in binary tree.

Question 64 : How to find lowest common ancestor(LCA) in binary tree.

You need to write a program to find LCA in binary tree.

Solution: Program to find LCA in binary tree.

Question 65 : How to do boundary traversal of binary tree.

Write a java program to do boundary traversal of binary tree as shown in below image.

Solution : Boundary traversal of binary tree.

Question 66 : How to print vertical sum of binary tree?

You need to find sum of nodes which lies in same column.

Solution : How to print vertical sum of binary tree.

Question 67 : Count subtrees with Sum equal to target in binary tree?

Given a Binary tree and an integer. You need to find the number of subtrees having the sum of all of its nodes equal to given Integer, that is, Target sum.

Solution : Count subtrees with Sum equal to target in binary tree.

Binary Search tree

Question 68 : What is binary search tree?

Binary search tree is a special type of binary tree which have following properties.

Nodes which are smaller than root will be in left subtree.
Nodes which are greater than root will be right subtree.
It should not have duplicate nodes
Both left and right subtree also should be binary search tree.

Question 69 : Can you write algorithm to insert a node in binary search tree.

Solution : Insert node in binary search tree

Question 70 : Can you write algorithm to delete a node in binary search tree.

Solution : Delete node in binary search tree

Question 71 : How can you find minimum and maximum elements in binary search tree?

Solution : Leftmost and rightmost nodes of binary search tree are minimum and maximum nodes respectively
Minimum and maximum elements in binary search tree.

Question 72 : How to find lowest common ancestor(LCA) in binary search tree.

You need to write a program to find LCA in binary search tree.

Solution: Program to find LCA in binary search tree.

Question 73 : Find inorder successor in a Binary search Tree

You need to write a program to find inorder successor in a Binary search tree.

Solution: Inorder Successor in a Binary Search Tree

Sorting

Question 77 : Write an algorithm to implement bubble sort?

Solution : Bubble sort in java

Question 78 : Write an algorithm to implement insertion sort sort?

Solution : Insertion sort in java

Question 79 : Write an algorithm to implement selection sort sort?

Solution : Selection sort in java

Question 80 : Can you write algorithm for merge sort and also do you know complexity of merge sort?

Solution : Merge sort in java

Question 81 : Do you know how to implement Heap sort?

Solution : implement Heap sort in java

Question 82 : Implement quick sort in java?

Solution : implement Quick sort in java

Question 83 : Implement shell sort in java?

Solution : implement Shell sort in java

Question 84 : Implement Counting sort in java?

Solution : implement Counting sort in java

Question 85 : What is binary search? Can you write an algorithm to find an element in sorted array using binary search?

Solution :Binary search algorithm in java

Graph

Question 86 : Write algorithm to do depth first search in a graph.

Solution : Depth first search in java

Question 87 : Write algorithm to do breadth first search in a graph.

Solution : breadth first search in java

Question 88 : Explain Dijkstra algorithm from source to all other vertices.

Solution : Dijkstra’s algorithm in java

Question 89 : Explain Bellman Ford algorithm to find shortest distance

Solution : Bellman ford algorithm in java

Question 90 : Explain Kruskal’s algorithm for finding minimum spanning tree

Solution : Kruskal’s algorithm

Dynamic Programming

Question 91 : Given two String, find longest common substring.

Solution: Longest common substring in java.

Question 92 : Given two Strings A and B. Find the length of the Longest Common Subsequence (LCS) of the given Strings.

Solution: Longest common subsequence in java

Question 93 : Given a matrix, we need to count all paths from top left to bottom right of MxN matrix. You can either move down or right.

Solution: Count all paths in matrix

Question 94 : Edit Distance Problem in java

Given two strings string1 and string2, String1 is to be converted into String2 with the given operations available in the minimum number of steps. Using any one of the given operations contributes to the increment of steps by one.

Allowed Operations are :
(i) Remove : This operation allows the Removal any one character from String.
(ii) Insert : This operation allows the Insertion of one character at any spot in the String.
(iii) Replace : This operation allows the replacement of any one character in the string with
any other character.

Solution: Edit distance problem in java.

Question 95: Coin change problem in java

Given an Amount to be paid and the currencies to pay with. There is infinite supply of every currency using combination of which, the given amount is to be paid. Print the number of ways by which the amount can be paid.

Solution: Coin change problem in java

Question 96 : Minimum number of jumps to reach last index

Solution: Minimum number of jumps to reach last index.

Miscellaneous

Question 97 : What is an algorithm and how to calculate complexity of algorithms.

Solution : How to calculate Complexity of algorithm

Question 98 : Implement trie data structure in java.

Solution : Implement trie data structure in java.

Question 99 : Count Factorial Trailing Zeroes in java.

Solution : Count Factorial Trailing Zeroes in java

Question 100 : Largest Rectangular Area in a Histogram.

Solution : Count Largest Rectangular Area in a Histogram

Question 101 : Check for balanced parentheses in an expression in java.

Solution : check for balanced parentheses in an expression in java.

Question 102 : What is Memoization.

Solution :
Memoization ensures that method does not execute more than once for same inputs by storing the results in the data structure(Usually Hashtable or HashMap or Array).
Memoization example in java

This is all about java coding interview questions. Please do comment if you want to add any new questions to above list.
You may also like:

Minimum Number of Jumps to reach last Index

Java2blog — Thu, 18 Apr 2019 16:25:04 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find Minimum Number of Jumps to reach last Index.

Problem

Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can be made from this index. The length of a jump can vary from 1 to A[index].
If value on any index is zero, this means that you can not move forward from this index.
Find the minimum number of jumps required to reach the last index. If the answer is not possible for any case, print “Not Possible”.

Input :
int[] A = { 2, 3, 1, 1, 4 }
Output :
2

Input :
int[] A = { 2, 0, 0, 1, 4 }

Output :
Not Possible

Solution

APPROACH – I :
A basic brute force solution can be achieved by using a recursive approach and making calls to every possible reachable index from the current index.
Now, what does that mean?

We are given the array where each index contains the length of the maximum jumps that can be made from that index.
For eg if A[i] = x, this means that from index ‘i’ we can jump to index i+0, i+1, i+2 … i+x and obviously only if these indices are in bounds.
Here making a call is equivalent to a jump for which we need to keep a jump variable in the function call and increment it in every recursive call made.
The base case condition will be, when the current index in the function call is eventually the end index. In the base case we compare the number of jumps made to reach this end index with the global minimum variable update it if the current number of jumps made to reach end index is less than the previously global minimum jump and return from the current call. If the current index becomes greater than the last index, then return from the current call as this is not the result we are looking for.

Steps:

Start from index zero and initialize the number of jumps made variable to 0.
Now for every index that is, in every call, start a loop from 1 to value at current index in the given array indicating the lengths of jump to be made in the next call. Make the function call with current index incremented by the length of jump and number of jumps by 1.
When in base case, that is, when the current index in the call is equal to the last index, compare the number of jumps with the global min jumps variable, update it if the number of jumps made in this call is less than the previously global minimum jump and return from the current call.
Here we will be using reactive recursive calls, so when the current index in the call is greater than the last index, we simply return from the call without doing any comparisons.

Time Complexity Discussion:
For an array of length n, at every index ‘i’ we are making A[i] jumps which in the worst case can be equal to n. Hence, there can be a total of ‘n’ potential calls from all the ‘n’ indices, therefore the worst time complexity of this solution is O(n^n).

package Backtracking;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };
        /*current index and number of jumps are zero initially*/
        solve(0, A, 0);

        if(minJumps == (int) 1e9 + 1)
        {
            /*if the min jumps is still infinity, this means it has
             * never been updated that is, we did not reach the end
             * index even once, hence answer is not possible in this
             * case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(minJumps);
        }

    }

    /* global min variable to store the minimum number of
     * jumps required to reach last index.*/
    public static int minJumps = (int) 1e9 + 1;

    public static void solve(int currIdx, int[] a, int jumps) {
        /* base case : Case 1 - if current index is equal to last
         * index (destination) update the global min jumps if the
         * current number of jumps is lesser and return. 
         * Case 2 - if current index is greater than the last index,
         * simply return because this is not the result we are looking for*/
        if (currIdx >= a.length - 1) {
            if (currIdx == a.length - 1) {
                minJumps = Math.min(minJumps, jumps);
            }
            return;
        }
        /*maximum length of any jump that can be made from this index*/
        int reachableIdxs = a[currIdx];

        /* recursive calls for all lengths of jump varying from 1 to max
         * length and incrementing number of jumps by 1 in every call */
        for (int jumpLength = 1; jumpLength <= reachableIdxs; jumpLength++) {
            solve(currIdx + jumpLength, a, jumps + 1);
        }
    }

APPROACH 2 :

In the above recursive solution, we can clearly see a lot of redundant calls, therefore for the reduction of the number of calls and eventually for reduced time complexity, we can use Dynamic programming approach.

For any index ‘i’ we can actually store the minimum number of jumps required to reach this index and then from here we can calculate the same for all the reachable indices from this index ‘i’ (‘reachable indices’ term is explained in the previous approach).
Now for any current index, the minimum number of jumps required to reach any ‘reachable index’ from start(‘0’ th index) is minimum jumps required to reach this current ‘i’th index from start(‘0’ th index) + 1 (to reach index ‘i+x’ directly from index ‘i’) , that is,
minJumps[i+x] = minJumps[i] + 1
Where, x can be 1, 2, 3…A[i]
Possibly We will be reaching the same index more than once with different number of jumps, but we want the minimum value, therefore, we update any minJumps[i] only if the current number of jumps required to reach ‘i’ is less then the current value at minJumps[i]

Time Complexity Discussion :
Again in this approach, from any index ‘i’ we are calculating minimum number of jumps of all the reachable indices by visiting all the reachable indices from any index, which can be ‘n’ in a worst case, and we are doing this for all n indices.
Therefore, the time complexity of this algorithm is O(n^2).

import java.util.Arrays;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 0, 1, 1, 4 };

        int ans = solveDP(A);
        if(ans == Integer.MAX_VALUE)
        {
            /* if the min jumps for the last index is still infinity,
             * this means it has never been updated that is, we did
             * not reach the end index even once, hence answer is not
             * possible in this case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(ans);
        }

    }

    public static int solveDP(int[] a) {
        int[] minJumps = new int[a.length];
        /*
         * initialize min Jumps for every index to infinity
         * as the minimum value is to  be calculated for
         * every index
         */
        Arrays.fill(minJumps, Integer.MAX_VALUE);
        /* minimum jumps required to reach the very first index is zero */
        minJumps[0] = 0;

        /*calculating min jumps for every index */
        for (int i = 0; i < a.length; i++) {
            /* maximum length of jump from this index or the maximum
             * reachable index from this index*/
            int maxJump = a[i];
            for (int j = 1; j <= maxJump; j++) {
                /*visiting all the reachable index*/
                int reachableIdx = i + j;
                /* updating the minimum jumps required for every reachable
                 * index but only if the reachable index is in bounds and
                 * the intermediate index from which we are making jump to
                 * this reachable index must also be reachable from zeroth
                 * index*/
                if (reachableIdx < a.length && minJumps[i] != Integer.MAX_VALUE) {
                    /* min jumps for every reachable index is min jumps for this
                     * intermediate index 'i' + 1 ( for the jump from intermediate
                     * index to this reachable index) */
                minJumps[reachableIdx] = Math.min(minJumps[reachableIdx], minJumps[i] + 1);
                }
            }
        }
        /*finally return the minimum jumps required to reach last index*/
        return minJumps[a.length-1];
    }

Before moving on to the next approach, just think if we could do better by using a greedy approach and making greedy coices for next index to jump on, rather than exploring all the possibilities using Dynamic programming.

Approach – III :
Yes we can definitely solve the given problem more efficiently by adopting a greedy approach.

The basic strategy would be to keep the track of Maximum reachable index the whole time which will eventually be updated frequently as we move through the given array and as soon as we reach this Maximum reachable index, we increment our number of jumps.
For this, we maintain 2 variables which stores the value of current index and Maximum reachable index. The very first thing we do after reaching any index is update the value of Maximum reachable index by comparing it with current Index + A[current Index] (indicating the maximum length of any jump that can be made from here) and we upadate Maximum reachable index value if value of current Index + A[current Index] is greater than Maximum reachable index. That is,

MaxReachable = max( MaxReachable, current Index + A[current Index])

One point to reconsider is, What if after the updation of this Maximum reachable index its value is less than or equal to current Index?
Well, this the case where we can not move from this current position and hence we can never reach the end index, therefore, in this case we simply return -1, indicating that no answer is possible in this case.

Now, we need to think about the correctness of our greedy approach again.

Can simply incrementing number of jumps when the value of current index is equal to max reachable index, always yield the correct answer everytime?

The answer would be a No, as max reachable index is getting updated and incremented by a value of A[current index] every time, this way value of current index can never be equal to max reachable index except for the case when the answer for a case isn’t possible.

For making our approach perfect, we can take another variable which keeps the track of current reachable index, and instead of incrementing the value of jump when current index is equal to Max reachable index, we will increment jump when the current Index becomes equal to current reachable, and at this moment we update the current reachable to max reachable index also.

Time Complexity Discussion :
We visit every index exactly once and keep updating the declared variables as we traverse the given array having ‘n’ elements. Therefore, the worst time complexity of this algorithm is O(n) where n is the size of the given array.

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };

        int ans = jump(A);
        if(ans == -1)
        {
            System.out.println("Not Possible");
        }
        else {
            System.out.println("Minimum jumps required : " + ans);
        }

    }

    public static int jump(int[] a) {
        /*three variable as discussed in the editorial*/
        int maxReachable = 0;
        int jumps = 0;
        int currReachable = 0;
        /*exploring every index in the given array */
        for (int currIdx = 0; currIdx < a.length; currIdx++) {

            /*updating max reachable index every time we visit a new index*/
            maxReachable = Math.max(maxReachable, currIdx + a[currIdx]);

            /* as we have already considered the max jump length at this
             * index and if max reachable index is still equal to or
             * less than current index, then we can move forward from
             * this index therefore answer is not possible in this case*/
            if (maxReachable <= currIdx) {
                return -1;
            }

            /*if current index is equal to the current reachable, increment
             * jumps required and update current reachable*/
            if (currIdx == currReachable) {
                jumps++;
                currReachable = maxReachable;
            }
        }
        return jumps;
    }

That’s all about the Minimum Number of Jumps to reach last Index.

Inorder Successor in a Binary Search Tree

Java2blog — Wed, 20 Feb 2019 16:24:31 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find Inorder Successor in a Binary Search Tree.

Problem

Given a Binary Search Tree and a target node value. Find the Inorder successor of the given node value in the Binary Search tree given. Inorder successor of any node ‘x’ is basically the node which gets traversed immediately after ‘x’ in the Inorder traversal of a tree.
Also assume that the node can not be the rightmost node of the given BST as no Inorder successor can exist for such node as this would be the last node to get traversed in the Inorder traversal.

Inorder successor of 6 is 7 in this Binary Search Tree.

Solution

APPROACH – I :

A basic approach for finding inorder successor of any node in BST can be inspired by the fact that Inorder traversal of any Binary Search tree is sorted which means that Inorder successor of any node ‘x’ is the node having value greater than ‘x’ while being the smallest among all of these nodes having value greater than ‘x’

Let’s call this node as ‘next greater node’ which is actually the Inorder successor.
Now the problem boils down to finding this next greater node having value just greater than given target node.

So, for this, a simple preorder traversal would be enough, where at every node, we compare the node value with the target node and update our final answer if this current node has value greater than target node and lesser than final answer till now.

Time Complexity Discussion :
As we clearly need atleast a complete preorder or any traversal of the given Binary Search tree to explore all the nodes, hence, the worst time complexity of this approach for finding Inorder successor is O(n).

package BinaryTrees;

public class InorderSuccessor {

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

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

        public String toString() {
            return data + "";
        }
    }

    public static Node root;

    public static void main(String[] args) {

        root = new Node(6);
        root. left = new Node(4);
        root. right = new Node(10);
        root. left. left = new Node(1);
        root. left. right = new Node(5);
        root. right. right = new Node(12);
        root. right. left = new Node(8);
        root. right. left. left = new Node(7);
        root. right. left. right = new Node(9);

        /*for any rightmost node of a tree which is also the greatest
         * node in a tree, Inorder successor can not exist as it is
         * the very last node to get visited in the inorder */
        System.out.println(getJustLarger(root, 9));
    }

    public static int getJustLarger(Node node, int target) {
        /* return a maximum value in the basecase so that it
         * can not be able to update final answer to be returned */
        if (node == null)
            return Integer.MAX_VALUE;

        /* result of recursive call to left subtree*/
        int lr = getJustLarger(node.left, target);
        /* result of recursive call to left subtree*/
        int rr = getJustLarger(node.right, target);

        /*final answer to be returned*/
        int rv = Integer.MAX_VALUE;

        /* if the current node value is greater than target and
         * it is lesser than the greater values (greater than target
         * node value) explored till now, then update the final
         * answer to be returned*/
        if (node.data > target && node.data < rv) {
            rv = node.data;
        }

        /* if the result of Left recursive call is greater than target and
         * it is lesser than the greater values explored till now,
         * then update the final answer to be returned*/
        if (lr > target && lr < rv) {
            rv = lr;
        }
        /* if the result of Right recursive call is greater than target and
         * it is lesser than the greater values explored till now,
         * then update the final answer to be returned*/

        if (rr > target && rr < rv) {
            rv = rr;
        }
        return rv;

    }

Approach – II:

We know that Inorder successor of any element cannot lie in its left subtree as the Inorder successor of any node will definitely be greater than the target node and it is a property of binary search tree that no smaller value node can lie in the left subtree of any node.

Therefore, If a node has a right child, then its inorder successor should definitely be in the right subtree of that node.
Now, there can be two possibilities :

(i) If the target node has a right child :

As we know, inorder successor of any node is the next greater node in a Binary Search tree and next greater node of any node is the leftmost node in the right subtree of that node. In simpler terms, next greater node of any node ‘x’ must be the smallest node among all the nodes having value greater than ‘x’ and we know, right subtree in a Binary Search tree contains all the greater nodes. Now, smallest node among all these greater nodes will be leftmost node. Hence, If the target node has a right child then, its Inorder successor will be leftmost node in its right subtree.

(ii) If the target node does not have a right child :

Now, as there is no Right subtree belonging to the target node, therefore, now we need to find the next greater node in a traversal starting from root, but since we have a Binary search tree to work with hence we can find the next greater node efficiently.
How?
We always start the traversal from root node and compare the value of current node with the target node whose inorder successor has to be found and

if it is greater than target node value, then update the final answer and move to the left subtree, WHY? because there is no benefit in going to right subtree as we will only find nodes with values greater than this current node, and as this node itself is greater than target node, this means it can be a potential next greater node but nodes in its right subtree can certainly not.
if the current node is smaller than the target node, then move to the right subtree as we are looking for nodes having value greater than value of target node.

Time Complexity Discussion

Functions in both the cases (node with and without right child) traverse the tree in a linear path, that is, at every level we are either going to left subtree or the right subtree which makes the worst time complexity of this approach to O(height) and height of a tree is O(log n), where n is the number of nodes.

package BinaryTrees;

public class InorderSuccessor {

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

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

        public String toString() {
            return data + "";
        }
    }

    public static Node root;

    public static void main(String[] args) {

        root = new Node(6);
        root.left = new Node(4);
        root.right = new Node(10);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.right.right = new Node(12);
        root.right.left = new Node(8);
        root.right.left.left = new Node(7);
        root.right.left.right = new Node(9);

        /*for any rightmost node of a tree which is also the greatest
         * node in a tree, Inorder successor can not exist as it is
         * the very last node to get visited in the inorder*/
        System.out.println(getInsucc(5));

    }

    public static int getInsucc(int data) {

        /*find the object of the Node having data equal to given data */
        Node node = find(root, data);

        /* if the right child of the node whose inorder successor
         * is to be found is not null, then it means its inorder
         * successor will lie in the right side only having actual
         * value equal to smallest node in its right subtree*/
        if (node.right != null) {
            return rightsmallest(node).data;
        } else {
        /* if if the right child of the node whose inorder successor
         * is to be found is null, then we need to run an efficient
         * traversal starting from root looking for a value just greater
         * than given node */
            nextGreaterEfficient(root, data);
            return inSuc.data;
        }

    }

        public static Node find(Node node, int data) {
            /*negative basecase : if node is null, return null*/
        if (node == null) {
            return null;
        }
        /*positive basecase : node found*/
        if (node.data == data) {
            return node;
        }

        /* result of recursive call to left subtree*/
        Node lr = find(node.left, data);

        /* result of recursive call to left subtree*/
        Node rr = find(node.right, data);

        /*if left subtree result and right subtree result, both
         * are null, this means, node does not lie in either of
         * the subtree of current node, and hence return null*/
        if (lr == null && rr == null) {
            return null;
            /*if only one side is null. then node was found in
             * the other subtree and hence return the result of 
             * ecursive call to that subtree*/
        } else if (rr == null) {
            return lr;

            /*we have to have atleast one of either left result
             * or right result to be null, as a node can not be
             * present in both left and right subtree of any node*/
        } else {
            return rr;
        }
    }

    public static Node rightsmallest(Node node) {
        /* firstly, shift the current node to right child of the
         * current node. This can never lead to a null pointer
         * exception as we call this function only when we ensure
         * that the node has a right child*/
        Node curr = node.right;

        /* keep on shifting the current node to left, until we
         * find a node with no left child*/
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }

    public static Node inSuc = null;
    public static void nextGreaterEfficient(Node node, int target)
    {
        if(node==null)
        {
            return;
        }
        /* when we find a node having value greater than the target
         * node, then there is no point in going right side,
         * as we will only find nodes having value greater than this
         * node, therefore we update the final answer and move to left
         * subtree*/
        if(node.data > target)
        {
            inSuc = node;
            nextGreaterEfficient(node.left, target);
        }else {
            nextGreaterEfficient(node.right, target);
        }
    }

}

When you run above program, you will get below output:

That’s all about Inorder Successor in a Binary Search Tree.

LCA of a K-ary Tree in O(Sqrt(height))

Java2blog — Mon, 04 Feb 2019 18:25:23 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity.

Problem

Given a K-ary tree and its two nodes. Calculate the Lowest common ancestor of the nodes in the given tree efficiently in O(sqrt(height)).
Lowest Common Ancestor is the node which is the common ancestor for both the nodes which is closest to them or we can say, farthest from root.

INPUT FORMAT :-
In the first line, given n, the number of nodes, following that n-1 lines contains two integers, the first one representing parent, second one is the child.
After that, given two Integers, whose LCA is to be found.

INPUT :
61
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
5 11
6 12
7 13
7 14
8 15
9 16
10 17
11 18
11 19
12 20
14 21
14 22
16 23
16 24
17 25
18 26
19 27
20 28
20 29
22 30
22 31
24 32
25 33
25 34
27 35
27 36
29 37
30 38
32 39
32 40
34 41
35 42
35 43
36 44
37 45
37 46
39 47
39 48
39 49
43 50
43 51
46 52
49 53
49 54
51 55
51 56
52 57
53 58
53 59
53 60
53 61
23 61

OUTPUT :
16

Solution

The naive approach to find out LCA of two nodes would be keeping two pointers (i.e. one one each node) and keep jumping to the immediate parent of both the current nodes and reach to a point where both the pointers meet, that node will be our LCA for sure.

But this would surely take a time of O(height).

But we can definitely achieve the solution more efficiently in O(√(height)) time.
Instead of jumping one node at a time we can skip more number of nodes which are of no use to us and eventually reach to the required spot where both the nodes meet.
Now HOW do we achieve this?

We divide our tree in different blocks of Sqrt(h) size i.e each block will be having Sqrt(height) height.
Now if the total height, ‘h’ of the tree is a perfect square then we know total number of blocks will be sqrt(h), and
What if the height of the tree is not a perfect square? Still the block size will remain sqrt(h) but the number of blocks will vary in range [sqrt(h), sqrt(h)+2] which can be observed mathematically.
So Now instead of taking jump of one node, we will take jump of sqrt(h) nodes, which will help us achieve the worst time complexity of sqrt(h) size.

How?

We set the parent and more importantly the block parent for each node in pre processing itself. Whenever we are asked to find the LCA of two nodes and if they belong to different blocks, we first make their block parents same so that atleast they are in the same block, therefore, to achieve that we make the deeper node jump to its block parent until the blocks of both the nodes are same. Now in the worst case, one node will jump all the blocks, which can be sqrt(h) at max, hence the total time taken in this process would be sqrt(h).
Now after the blocks of both nodes are same, we jump to their immediate parent until the nodes eventually meet, and that meeting point will be the LCA of given nodes. Now at max one node can jump all the nodes in its block which can be sqrt(h) at max.
So the total time complexity of the algorithm will be : Sqrt(h) + Sqrt(h)
= 2*Sqrt(h)
= O(Sqrt(h))

Algorithm :

In the first DFS we set the parents, depths and more importantly find the height which helps us to define the size of each block.
After we find height of the tree, we define the block size of the tree.
Now once the block size is defined, we can set the block parent of each node in the tree.
For setting the block parent, we keep two things in mind,
- (i) if a node and the parent of that node lies in the same Block number, then they have the same block parent, that is, block parent of node = block parent of parent.
- (ii) if a node and the parent of that node lies in different Block numbers, then the block parent of node is the actual parent of the node, that is, block parent of node = parent.
Once the block parent is set we are done with pre processing and remaining is to process the query.

How to process the query?

If the nodes are in the different blocks, then make the deeper node jump to its block parent until they are in the same block number.
If the block number of both the nodes are same, then make the deeper node jump to its immediate parent until they actually meet. This node where the two nodes actually meet is the LCA.

package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.Scanner;

public class LCAsqrtdecomp {

    static ArrayList[] tree;
    static int[] parents;
    static int[] depths;
    static int[] blockParents;
    static int height;
    static int blockSize;

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);

        int nodes = scn.nextInt();
        int edges = nodes - 1;

        tree = new ArrayList[nodes + 1];

        // parents arr to store the parent of the ith node.
        parents = new int[nodes + 1];

        // blockParents arr to store the block parent of the ith node.
        blockParents = new int[nodes + 1];

        // depths to store the height of the current node
        depths = new int[nodes + 1];
        height = -1;

        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < edges; i++) {
            int parent = scn.nextInt();
            int child = scn.nextInt();

            // at the index of the parent node, we are adding its child
            tree[parent].add(child);
        }

        /* this dfs is to set the parents, depths, 
           and mainly to find the height of the
           tree given so that we can calculate our
           blocksize which will be sqrt(height).
        */
        dfs(1, 0, 0);

        /* incrementing the height by one, because the 
        height we calculated was started considering the
        root node at 0th level, but certainly root node also
        contributes to the total height of the tree.
         */
        blockSize = (int) Math.sqrt(++height);

        /* this is again a sort of DFS in which we are 
         setting the block parent for every node. we could 
         not do it in the previous dfs as before we didnt have
         our height precalculated for finding the blocksize
         */
        setBP(1);

        System.out.println("Output: "+getLCA(scn.nextInt(), scn.nextInt()));

    }

    public static void dfs(int node, int parent, int currDepth) {
        // setting parent and depth of the current node.
        parents[node] = parent;
        depths[node] = currDepth;
        // always updating Max Height as we move down 
        // in tree using preorder traversal. 
        height = Math.max(height, currDepth);

        for (int child : tree[node]) {
            // recurring for all the child nodes for which the 
            // current node will act as the parent .
            dfs(child, node, currDepth + 1);
        }

    }

    public static void setBP(int node) {

        int parent = parents[node];

        /* finding the block number of the current node and 
         its parent by diving the depth by blocksize.
        */
        int nodeBlock = depths[node] / blockSize;
        int parentBlock = depths[parent] / blockSize;

        /* if they both current node and the previous node lie in 
         the same block, then lie in the same block, then this means 
         that the block size of both nodes must be the same node, and 
         as we have already calculated the block parent of parent, so 
         the Block parent of current node will be the block parent of 
         the parent of current node.
         */

        if (nodeBlock == parentBlock) {
            blockParents[node] = blockParents[parent];
        } else {
            /* if the blocks of current node and its parent are  
             different then this means that the immediate parent  
             of the current node lies in the just the previous 
             block and hence the actual  parent of the current
                          node is also its block parent.
             */
            blockParents[node] = parents[node];
        }

        for (int child : tree[node]) {
            /* recurring for the child nodes, we do not really 
               need to send the parent in the call, a we have 
               already calculated  and stored them in the previous 
                           dfs.
            */
            setBP(child);
        }

    }

    public static int getLCA(int node1, int node2) {

        /* this is the part where all of our complexity reduction 
         * occurs, instead of jumping one be one, we directly 
         * take jumps of sqrt(height) size. if the block parent 
         * of both the nodes are different, then we jump to the 
         * block parent of the DEEPER node. we keep on doing the 
         * same until the block parent of both the nodes are equal.
         */
        while (blockParents[node1] != blockParents[node2]) {
            /*
             * this check takes care that we make the deeper node 
             * jump to its block parent, if this check was not 
             * there, there might be a case where both nodes
             * eventually reach to the block parent of the root node
             */
            if (depths[node1] > depths[node2]) {
                node1 = blockParents[node1];
            } else {
                node2 = blockParents[node2];
            }
        }

        /*
         * once the blocks of both the nodes are same, this 
         * means that the LCA of both the nodes must lie in 
         * the same block, therefore now we keep jumping to the
         * immediate parent of the nodes until the nodes actually 
         * meet, the point where they meet will be our LCA
         */
        while (node1 != node2) {

            if (depths[node1] > depths[node2]) {
                node1 = parents[node1];
            } else {
                node2 = parents[node2];
            }
        }

        // finally return the LCA of both the nodes
        return node1;
    }

}

That’s all about how to find Lowest Common Ancestor(LCA) of a K-ary Tree in O(Sqrt(height)).

Largest Rectangular Area in a Histogram

Java2blog — Sun, 03 Feb 2019 10:37:35 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about how to find largest rectangular area in a Histogram.

Problem

Given an Integer representing number of bars in a Histogram and an array of integers representing the height of the bars in the given Histogram. Find the maximum Rectangular area possible in the Histogram given when the width of each bar is considered to be one unit.

For example, Consider the histogram given below,

INPUT :
8
3 1 6 4 3 2 1 5
OUTPUT :
9

Solution

APPROACH – I

A very basic approach can be, considering every bar as a starting point of area.
We can one by one consider each bar as the starting point of area and then for each starting point consider every bar having index greater than the index of the starting bar to calculate area between them.
After calculation of area with every starting point we update the maximum possible rectangular area and finally return it after al starting points are exhausted.

Now, the maximum rectangular area between any two bars in a Histogram can be calculated by multiplying the number of bars in between starting bar and ending bar (both inclusive) by the height of the shortest bar.
This is because it is given, width of every bar is one.
That is, consider the indices of starting and ending bars to be x & y respectively, then,

Max rectangular area = [Min height bar (between x & y)] * [y – x + 1]

Time complexity Discussion :
As each bar is considered as starting point and for every starting point we are considering all bars as ending points (obviously with ending index greater than starting index) which clearly gives the idea of the worst time complexity of the order O(n^2), where n is the number of bars in the given Histogram.

package Algos;

import java.util.Scanner;

public class maxHistogramArea {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        /*input number of bars in the histogram*/   
        int n = scn.nextInt();
            long[] a = new long[n];
            /*input height of each bar*/
            for (int i = 0; i < a.length; i++) {
                a[i] = scn.nextLong();
            }

            System.out.println(solve(a));
    }

    public static long solve(long[] a) {
        /*final max rectangular area to be returned*/
        long ans = 0;

        /*considering every bar as a starting point of an area*/
        for (int i = 0; i < a.length; i++) {
            /*for keeping track of shortest bar encountered yet
             * when 'i' is chosen as the starting point of an area*/
            long min = Integer.MAX_VALUE;
            /* area when  when 'i' is chosen as the starting point
             * of an area*/
            long rv=0;
            for (int j = i; j < a.length; j++) {
                /*current area will be the height of the shortest
                 * bar multiplied with the number of bars*/
                min = Math.min(min, a[j]);
                rv = Math.max(rv, min * (j - i+1));
            }
            /*updating overall max with the current max*/
            ans = Math.max(ans, rv);
        }
        return ans;
    }

}

APPROACH – II (RECURSIVE):

This problem can be solved recursively using Divide and Conquer technique in which we divide the problem into two parts, that is, we divide the area to work with in array into two independent problems, whose result can be combined to give the result of bigger problem.

Now the point of division of any problem into two subproblems will be the index of the bar with minimum height in that particular area of the array of any current problem and not the complete array (just like in all other Divide and conquer approaches for example in mergesort and quicksort).

Now the maximum area for the current problem will be the maximum of :
(i) Current Maximum area including all the bars : This will be the maximum possible rectangular area in the current subproblem which will be calculated by Multiplying the height of the shortest bar with the Number of bars in a particular area (current subproblem).
(ii) Maximum possible rectangular area on the left side of the minimum height bar which will be calculated recursively.
(iii) Maximum possible rectangular area on the right side of the minimum height bar which will also be calculated recursively.

We can efficiently find the index of shortest bar in O(log n) time with the help Range min Query using segment tree.

Algorithm :
Step – I :
Find the index of the bar with minimum height.
Step – II :

Recursive call for finding the maximum rectangular area in left side of this minimum index.
Recursive call for finding the maximum rectangular area in right side of this minimum index.
calculation of maximum rectangular area in the current segment.

STEP – III :
Return Maximum of all of the three calculated areas.

Time complexity Discussion :
At every step, we are dividing the subarray into two parts where the separation point is the minimum height bar which is getting calculated using Range min query in Segment tree. Now, in the worst case if the array is sorted in ascending/ descending order, then the division would be, one element in one side and (n-1) elements on other side which will lead to total ‘n’ divisions and at every step finding min index in O(log n) leading to a worst time complexity of O(n*log n).

package Algos;

import java.util.Scanner;

public class maxHistogramArea {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        /* input number of bars in the histogram */
        int n = scn.nextInt();
        int[] a = new int[n];
        /* input height of each bar */
        for (int i = 0; i ei)
        {
            return Integer.MIN_VALUE;
        }

        /*if there is only one bar, then the area will be
         * height of that bar, as width of each bar is one*/
        if (si == ei) {
            return a[si];
        }

        /*find index of the bar with minimum height*/
        int minIdx = getQuery(0, 0, a.length-1, si, ei, a);

        /*recursive call to get maximum area from left of
         * this min height bar*/
        int left = solve(si, minIdx - 1, a);
        /*recursive call to get maximum area from right of
         * this min height bar*/
        int right = solve(minIdx + 1, ei, a);
        /* area calculation for whole of this current segment,
         * which is number of bars multiplied by height of the
         * shortest bar*/
        int current = a[minIdx] * (ei - si + 1);

        /*max of all these areas will be the final result*/
        return Math.max(current, Math.max(left, right));

    }

        static int[] segArr;

        public static void SegInit(int[]arr) {

            int height = (int)(Math.ceil(Math.log(arr.length)/Math.log(2)));
            segArr = new int[(int)Math.pow(2,(height+1)) - 1];
            construct(0, 0, arr.length-1, arr);

        }

        public static int construct(int saIdx, int left, int right, int[] arr) {
            /*
             * if the segment is of length one, then we know 
             * it will be a left node and hence it will 
             * contain an element of the given array
             */
            if (left == right) {
                /*
                 * element at the current index of segArr 
                 * will be the element present at index
                 * left or right in given array, as left 
                 * is equal to right so we can take either
                 * of them
                 */
                return segArr [saIdx] = left;
            }

            /*
             * current segment of parent node is divided 
             * into two halves, if the segment for
             * parent is [left, right], then segment 
             * for left child will be [left, mid] and
             * segment for right child will
             * be [mid+1, right].
             */
            int mid = (left + right) / 2;
            int leftChild = construct(2 * saIdx + 1, left, mid, arr);
            int rightChild = construct(2 * saIdx + 2, mid + 1, right, arr);
            /*
             * result of the current node will be calculated 
             * in the post order after calculating
             *  the result for its children
             */
            segArr [saIdx] = arr [leftChild] > arr [rightChild] ? rightChild : leftChild;
            return segArr [saIdx];
        }

        public static int getQuery(int saIdx, int left, int right, int ql, int qr, int[] arr) {

            // saIdx - pointer for the segment array.
            // left - left limit of the current segment.
            // right - right limit of the current segment.
            // ql - left limit of the given query segment.
            // qr - right limit of the given query segment.

            /*
             * if the range of the query lies completely outside 
             * the range of the current segment, we return a
             * value which contributes nothing to the final answer,
             * that 0 in the case when sum is to be calculated 
             * for given range.
             */
            if (left > qr || right = ql && right  arr [rightResult] ? rightResult : leftResult;
                }
            }

        }

        public static void update(int value, int idx, int saIdx, int left, int right, int[] arr) {
            /*
             * if the index lies outside the range of the current 
             * segment then there is no need for an update/call
             * at that index, so simply return.
             */
            if (idx  right) {
                return;
            }
            /*
             * if we found the index to be updated, we update the 
             * given array as well as the segment array that is 
             * the node which has the segment equal to given index.
             */
            if (idx == left && idx == right) {
                arr [left] = value;
                segArr [saIdx] = left;
                return;
            }
            /*
             * now in post order we need to update all the nodes
             *  which contains the given index in their segment
             */
            else {
                int mid = (left + right) / 2;
                update(value, idx, 2 * saIdx + 1, left, mid, arr);
                update(value, idx, 2 * saIdx + 2, mid + 1, right, arr);

                segArr [saIdx] = arr [segArr [2 * saIdx + 1]] > arr [segArr [2 * saIdx + 2]] ? segArr [2 * saIdx + 2] : segArr [2 * saIdx + 1];
            }  
        }

    }

Approach – III (ITERATIVE) :

As we know, calculation of maximum rectangular area in any segment of the histogram depends upon the shortest bar in that area (if we include all of the bars), hence,

This problem can be solved more efficiently if we calculate area for every bar when being the shortest in its rectangle for which we need to know the index of closest smaller bar on left and the index of closest smaller bar on right. Calculation of these indices for every element in the given histogram would take O(n^2) time which makes it even more inefficient.
But this task can be done in linear time using Stack Data Structures in java data structure in which basically heights are stored in non-increasing order. This stack does not actually stores the height of the bars but instead stores their indices.
For any element on top of the stack, index of closest smaller bar on left will be the element just below the top element and index of closest smaller bar on right will be the next incoming element which is to be pushed.

The stack is maintained such that for any 'i'th element, top of the stack is the index of the shortest bar between the previous stack element (element just below top) and 'i'th element excluding this ‘i’th and element just below top.
Now as top is the smallest element till now, therefore, we can easily calculate area by multiplying this top element height with the number of elements BETWEEN 'i' and index just below top (lets call this as previous index). that is,

area = top * (i - previous index - 1)

Algorithm :

(i) If stack is empty or element on top is smaller than the current incoming element then, push the element straightaway without popping (as the top element will still be the smallest between previous index and i) and increment the index i.

(ii) if top of the stack is greater than the incoming element, then this means that the top element is no longer the smallest element in the current segment, and hence, pop the top element from stack.

Now, if stack becomes empty, then area = top * i
else,area = top * (i - stack.peek() - 1).

There will not be any increment in index i as this element is yet to be pushed into the stack.

(iii) Follow the above steps until index i reached the end of the array.

(iv) Now, after index i has reached the end, there might be a possibility that still there are elements left in the stack to be processed, that is why, we follow the above steps until the stack becomes empty.

Time complexity if this approach is O(n) as every element is getting pushed and popped not more than one time.

package Algos;

import java.util.Scanner;
import java.util.Stack;

public class maxHistogramArea {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        /* input number of bars in the histogram */
        int n = scn.nextInt();
        int[] a = new int[n];
        /* input height of each bar */
        for (int i = 0; i < a.length; i++) {
            a[i] = scn.nextInt();
        }
        System.out.println(solve(a));
    }

    public static int solve(int[] a) {
        Stack stack = new Stack<>();
        int maxArea = Integer.MIN_VALUE;
        for (int i = 0; i < a.length;) {
            /* this condition means that as the top element is
             * smaller than the incoming element, that is why,
             * it must not be popped and should be given more
             * time in stack as it can lead to a larger area later.
             * */
            if (stack.isEmpty() || a[stack.peek()] <= a[i]) {
                stack.push(i);
                i++;
            } else {
                /*As the top of element is greater than the incoming
                 * element, then this top element would no longer be
                 * the smallest element in between 'i' th element and
                 *  previous element, hence, remove this, and calculate
                 *  area corresponding to this element */
                int top = stack.pop();
                if (stack.isEmpty()) {
                    /*as no element is left in the stack this means
                     * that this removed top element was the smallest
                     * element in the array till 'i' th index*/
                    maxArea = Math.max(maxArea, a[top] * i);
                } else {
                    /* area calculation for the removed top as the segment
                     * for this element being the smallest has ended */
                    maxArea = Math.max(maxArea, a[top] * (i - stack.peek()-1));
                }
            }
        }

        /* After 'i' has reached the end of the histogram array so
         * the upper loop will end, but we still have element left to
         * be processed in the stack, hence do the same process again
         * until stack becomes empty*/
        while (!stack.isEmpty()) {
            int top = stack.pop();
            if (stack.isEmpty()) {
                /*updating max rectangular area every time*/
                maxArea = Math.max(maxArea, a[top] * a.length);
            } else {
                maxArea = Math.max(maxArea, a[top] * (a.length - stack.peek()-1));
            }
        }
        return maxArea;
    }

}

That’s all about Largest Rectangular Area in a Histogram.

Count subtrees with Sum equal to target in binary tree

Ayush Kumar — Tue, 29 Jan 2019 17:55:05 +0000

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see about how to count subtrees with Sum equal to target in binary tree

Problem

Given a Binary tree and an integer. You need to find the number of subtrees having the sum of all of its nodes equal to given Integer, that is, Target sum.

Solution

For solving this problem, we calculate the result in postorder while returning from recursion in which we return a Pair object which contains the sum of current subtree and count of subtrees having their sum equal to given sum.

So basically, we keep on recurring to child of the current node until we finally reach to a null node where we return an empty pair class object in which sum of current subtree is zero and also the count of subtrees with sum equal to target sum equal to zero.
Result of any node or the pair to be returned will be calculated using the pair objects returned from left child and right child of the current node.
There are two things we need to calculate for current node :

(i) SUM : Sum of current node will be the summation of left subtree sum, right subtree sum and value of
current node.
(ii) Count : Count of subtrees with sum Equal to target sum will left count + right count and add one if the
overall sum of the current node is equal to target sum.

The time complexity of this algorithm would be similar to all other traversals like postorder, that is, O(n) , where ‘n’ is number of nodes in the tree.

package BinaryTrees;

public class SubtreesWithGivenSum {

    public static class Node {
        int data;   // Data of current Node.
        Node left;  // Pointer to left child Node.
        Node right; // Pointer to right child Node.

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

    public static class pair {
        /*number of subtrees with given target sum*/
        int count;
        /* sum of the current subtree which includes the
         * sum of root of current subtree, left child 
         * subtree and, right child subtree*/
        int sum;

        public pair(int count, int sum) {
            this.count = count;
            this.sum = sum;
        }
    }

    public static void main(String[] args) {

        Node root =  new Node(4);
        root. left = new Node(5);
        root. right = new Node(-2);
        root. left. left = new Node(-1);
        root. left. right = new Node(2);
        root. right. right = new Node(5);
        root. right. left = new Node(8);
        root. right. left. left = new Node(7);
        root. right. left. right = new Node(-9);

        System.out.println(solve(root, 6).count);

    }

    public static pair solve(Node node, int target)
    {
        if(node == null)
        {
            /* if current node is null, then its contribution to total
             * sum of a subtree will be zero and also it won't have
             *  any subtree with sum equal to given target sum  */
            return new pair(0, 0);
        }

        /*calls for left and right subtree*/
        pair left = solve(node.left, target);
        pair right = solve(node.right, target);

        /*sum of current subtree will be the sum of data of current node,
         * sum of left child subtree and, sum of right child subtree*/
        int sum = left.sum + right.sum + node.data;
        int count = left.count + right.count;
        /* count of subtrees with target sum will be the sum of count
         * of subtrees on left with sum equal to target, count of
         * subtrees on right with sum equal to target, and one if 
         * the current subtree has sum equal to target*/
        if(sum==target)
        {
            count++;
        }
        return new pair(count, sum);
    }

}

That’s all about Count subtrees with Sum equal to target in binary tree.

Serialize and Deserialize n-ary tree

Ayush Kumar — Mon, 19 Nov 2018 18:38:33 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

Problem

Given a Generic Tree, Serialize and Deserialize it.
Serialization is a basically a representation of a tree in a String format which takes much lesser space than storing the tree itself.
Deserialization is constructing the actual tree using the the serialized format of the tree.

OUTPUT:

Serialized Tree :
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )

Deserialized Tree :
1 => [ 2 3 4 ]
2 => [ 5 6 ]
5 => [ ]
6 => [ ]
3 => [ ]
4 => [ 7 8 ]
7 => [ ]
8 => [ 9 ]
9 => [ ]

Solution

Serialization is just a traversal of the tree which can be either preorder or a postorder in which we insert an ‘end of subtree’ flag in the serialized string of the tree which helps us constructing the original tree while deserializing it.

SERIALIZATION:

We traverse in preorder in the tree and whenever we visit a new node we store it in the serialized string and in a set so that whenever we visit an already visited node we do not add in the serialized string.
whenever we return from a node, we append an end of subtree/child' flag in the string so that we keep a track on number of children / subtrees under that node.

DESERIALIZATION:

While deserializing the tree using the serialized string, we use a stack to keep the track of parent of the incoming node. So we will keep pushing the nodes into the stack until we get an ‘end of subtree’ marker, lets say we denote it by ‘)’, if we get ‘)’ , we pop a node from stack and make it the child of the node at top of the stack. We keep on doing the same until we are finished with the given serialized string of the tree and eventually the original tree will be constructed. We traverse once again in preorder to print the constructed tree.

package GenericTree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

public class serializeDeserialize {

    public static class Node {
        int data;
        ArrayList children;

        public Node(int data) {

            this.data = data;
            this.children = new ArrayList<>();

        }
    }

    public static void main(String[] args) {

        Node[] nodes = new Node[10];

        for (int node = 0; node < nodes.length; node++) {
            // initializing every node.
            nodes[node] = new Node(node);
        }

        // assuming first node as the root node.
        Node root = nodes[1];

        // adding the children in the arraylist of every parent node.
        nodes[1].children.add(nodes[2]);
        nodes[1].children.add(nodes[3]);
        nodes[1].children.add(nodes[4]);
        nodes[2].children.add(nodes[5]);
        nodes[2].children.add(nodes[6]);
        nodes[4].children.add(nodes[7]);
        nodes[4].children.add(nodes[8]);
        nodes[8].children.add(nodes[9]);

        // this is where our serialized string will be stored.
        StringBuilder str = new StringBuilder();
        serialize(root, new HashSet<>(), str);
        System.out.println("Serialized Tree : \n" + str);

        /*since we have the required information to represent 
         * the tree therefore we can delete the actual tree 
         * but since here we have to deserialize the tree also,
         * so we are reinitializing every node instead 
         */
        nodes = new Node[10];

        for (int node = 0; node < nodes.length; node++) {
            nodes[node] = new Node(node);
        }

        deserialize(str.toString(), nodes);
                System.out.println("Deserialized Tree :");
        printTree(root);

    }
public static void serialize(Node node, HashSet visited, StringBuilder str) {
        /* keeping the track of already visited node, 
         * so that we only proceed with new nodes only
         */
        visited.add(node.data);
        /*adding the node name to the serialized string
         */
        str.append(node.data + " ");

        /*recurring for the children of the current node*/
        for (Node child : node.children) {
            serialize(child, visited, str);
        }

        /*while returning back from recursion i.e. in post order
         * we will add an 'end of the subtree' flag*/
        if (visited.contains(node.data)) {
            str.append(") ");
        }

    }

    public static void deserialize(String str, Node[] nodes) {
        Stack stack = new Stack<>();
        String[] tree = str.split(" ");
        for (String node : tree) {
            if (node.equals(")")) {
                /*if the current character is an 'end of the subtree'
                 *  flag, we pop a node from stack and make it the 
                 *  child of the node which is at the top of stack 
                 *  after popping this child out*/
                int childNode = stack.pop();
                if (stack.size() > 0) {
                    int parentNode = stack.peek();
                    nodes[parentNode].children.add(nodes[childNode]);
                }

            } else {
                /* while traversing the serialized string
                 * if we are currently on a node, we push 
                 * it directly  to the stack without any 
                 * processing
                 */
                stack.push(Integer.parseInt(node));
            }
        }
    }

    public static void printTree(Node node) {
        System.out.print(node.data + " => [ ");
        for (Node child : node.children) {
            System.out.print(child.data + " ");
        }
        System.out.print("] \n");

        for (Node child : node.children) {
            printTree(child);
        }
    }

}

When you run above code, you will get below output

Serialized Tree :
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )
Deserialized Tree :
1 => [ 2 3 4 ]
2 => [ 5 6 ]
5 => [ ]
6 => [ ]
3 => [ ]
4 => [ 7 8 ]

Comment in case of any doubts or Edits, Happy Learning