JavaByPatel: Data structures and algorithms interview questions in Java: October 2017

Sunday, 29 October 2017

Java Program for Linear Search.

Linear search is a searching algorithm which sequentially searches element in an array.

In this algorithm, elements of array is scanned one by one and check if it is matching with element to search and if found return true else return false.

In last post, we saw how to do Binary search: Binary Search in Java. In this post, we will focus on linear serach.

Lets understand the problem statement graphically and it will be more clear,

Friday, 27 October 2017

Frequently asked Top 10 Matrix Interview Questions.

Question 1: Rotate matrix by 90 degree. (Given N*M Matrix, Rotate it by 90 degrees.)
Answer:
There are 2 ways to Rotate a Matrix by 90 degrees

Using extra Memory.
In Place.

In this post, we will focus on Rotating a Matrix by 90 degrees clockwise using Extra memory.

For Rotating a matrix to 90 degrees clockwise, We need to transform each row of a Matrix to a column in rotated matrix. (Check the rotated matrix image above)

It is very easy to solve this problem if it is well understood.

What will be Rows and Columns of Rotated Result Matrix?
For rotating matrix to 90 degrees, we need to transform rows into columns and columns to rows in a result matrix. So number of rows in rotated matrix will be equal to number of columns of original matrix and number of columns in rotated matrix will be equal to number of rows.

int[][] rotatedMatrix = new int[colsOfOriginalMatrix][rowsOfOriginalMatrix]

More...

Question 2: Rotate Matrix by 90 degrees clockwise Inplace. (Given N*M Matrix, Rotate it by 90 degrees Inplace.)
Answer:
There are 2 ways to Rotate a Matrix by 90 degrees

In Place.
Using extra Memory.

For Rotating a matrix to 90 degrees in-place, it should be a square matrix that is same number of Rows and Columns otherwise inplace solution is not possible and requires changes to row/column.

For rotating a matrix to 90 degrees, we will start rotating it Layer by Layer.
Rotate first outer layer by 90 degrees, Rotate 2nd inner layer by 90 degree, Rotate 3rd inner layer by 90 degree and so on,

We will further break the problem of Rotating each layer to rotate each cell of layer by 90 degrees More...

Question 3: Print Matrix in Spiral form. (Given a Matrix(2D array), print it in spiral form.)
Answer:
There are 2 ways to print matrix in Spiral order.

Iterative.
Recursive.

In this approach, we will focus on Iterative approach.

In Iterative approach, we need to maintain 4 variables rowStart, rowLength, colStart, colLength which help in printing matrix in Spiral way.

STEP 1: Left to Right.
Move variable i from rowStart till colLength. (Print data from first row till last column.)

STEP 2: Top to Bottom. More...

Question 4: Print Matrix in Spiral order using Recursion. (Given a Matrix(2D array), print it in spiral form Recursively.)
Answer:
There are 2 ways to print matrix in Spiral order.

Iterative.
Recursive.

In this approach, we will focus on Recursive approach.

In Iterative approach, we need to maintain 4 variables rowStart, rowLength, colStart, colLength which help in printing matrix in Spiral way.

In Recursive approach, we will be requiring same 4 variable and follow the same process, only difference in this approach will be, after printing first outer Layer of Matrix elements, before moving into inner layers of Matrix, we will check whether next inner layer of Matrix is present or this is end of all Layers.

If Matrix has inner Layer present, we will increment rowStart++, colStart++ and decrement rowLength--, colLength--, which now points to inner matrix layer and pass this variable to next recursive call. More...

Question 5: Transpose of Matrix in Java. (You are given a M * N matrix, find Transpose of Matrix.)
Answer:
Transpose of matrix is obtained by interchanging rows and columns of a matrix that is by changing rows to columns and columns to rows.

Transpose of given matrix can be obtained by changing its rows to columns and columns to rows.

Create a new Matrix as Transpose Matrix of size,

Rows = Total column of original matrix.
Column = Total rows of original matrix.

Iterate through Original matrix, and fill Transpose Matrix data by interchanging rows to column and column to rows as shown below,

TransposeMatrix[col][row] = OriginalMatrix[row][col]. More...

Question 6: Transpose of Matrix Inplace. (You are given a M * N matrix, find Transpose of Matrix in-place.)
Answer:
Transpose of matrix is obtained by interchanging rows and columns of a matrix that is by changing rows to columns and columns to rows.

Note: For Inplace transpose, Matrix should always be Square Matrix that is having same number of Rows and Columns.

Transpose of given matrix can be obtained by changing its rows to columns and columns to rows.

Iterate through a Matrix and swap data of rows and columns.
While iterating make sure, Column start from where Row start.

Java Program to More...

Question 7: Find a Saddle point in Matrix.
Answer:
Given a matrix of n x n size, Find saddle point of matrix.

What is Saddle point of Matrix?
Element is said to be Saddle point of Matrix if it is both a minimum of its row and a maximum of its column or vice versa.

A matrix may have 1 or 2 saddle points or may not have a saddle point. Lets understand what will be input and expected output with the help of an example.
For finding Saddle Point,

Traverse the Matrix row by row and for each row, find the minimum element in that row. let say you find the minimum element at index j.
Check the maximum element on same column j. More...

Question 8: Search in a row wise and column wise sorted matrix.
Answer:
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number k, how to decide whether this k is in the matrix.

There are many approach to solve this problem, Lets see few of them.

Approach 1:
Check for the number one by one by looking at each element of the array.
This approach is not efficient as in worst case we need to traverse complete matrix to identify whethet element is present or not.

Approach 2:
As matrix ix sorted, we can apply binary search on each row and identify whether element is present or not.

Approach 3: In this approach, we will start our search by looking at Right most element of first row. More...

Question 9: Count zeros in a row wise and column wise sorted matrix.
Answer:
Count zeros in a row wise and column wise sorted matrix

There are many approach to solve this problem, Lets see few of them.

Approach 1:
Initialise counter = 0 and check for each element of the array and increment counter if you encounter 0. This approach is not efficient as in worst case we need to traverse complete matrix to identify whether element is present or not.

Approach 2:
As matrix is sorted, we can apply binary search and identify start position of 0 in each row and sum count of 0 of each row.

Approach 3:
In this approach, we will start our search by looking at Right most element of first row More...

Question 10: Print Matrix Diagonally OR Diagonal order of Matrix.
Answer:
Given a Matrix / 2D array, Print all elements of Matrix in Diagonal order.

If we observe the Matrix, there are 2 set of Diagonals,

rowCount diagonals
(colCount - 1) diagonals.

We will first print the rowCount diagonals and then print the remaining columnCount-1 diagonals. More...

Sunday, 22 October 2017

Binary Tree Interview Questions.

Binary tree questions is very common during interviews. In this post we will focus on Top Binary tree and Binary Search tree interview questions and answers.

In this post we will look at,
1. Basic Interview Questions on Binary Tree.
2. Most commonly asked Interview Questions on Binary Tree.

Basic Interview Questions on Binary Tree.

Question 1: What are the types of Binary tree?
Answer:
Types of Binary Tree in Data Structure. Let's see Binary Tree types with example. There are mainly 3 types of Binary trees.

Full binary tree / Proper binary tree / 2-tree / Strictly binary tree)
Perfect Binary Tree.
Complete Binary Tree:

Full binary tree / Proper binary tree / 2-tree / Strictly binary tree)
Full Binary Tree is a tree in which every node except leaves/leaf node has either 0 or 2 children.
There will be no leaves with only 1 child.

Example of Full Binary Tree: More ...

Question 2:
Explain Binary tree Traversals with example?
Answer:
There are 2 types of Graph traversal algorithms Breadth first traversal and Depth First traversal.
Tree is a special kind of Graph in which Breadth first traversal and Depth First traversal is divided as follows,

Breadth First Traversal.
- Level Order Traversal
Depth First Traversal
- Preorder traversal
- Inorder traversal
- Postorder traversal

Breadth First Traversal
Breadth First Traversal is a traversing way where child at same levels are read first before visiting their child. which is nothing but a LEVEL-ORDER Traversal. More....

Question 3:
How to add a Node in Binary Tree?
Answer:
To add a Node in a Binary Tree, Start scanning a Binary Tree level by level and wherever we encounter vacant position, place a new Node there.

See below image to get better understanding of position of a new Node to insert.
Given a binary tree, we need to add a Node with value 8 marked in dotted lines below in its correct position.
Java Program to Insert Node in Bina More....

Question 4:
How to add a Node in Binary Search Tree?
Answer:
While adding a Node in a Binary Search Tree, it should follow below rules,

All values descending on the Left side of a node should be less than (or equal to) the node itself.
All values descending on the Right side of a node should be greater than (or equal to) the node itself.

Java Program to Insert Node in Bina More....

Question 5:
How to Delete a node in Binary Search Tree?
Answer:
There are 3 cases that need to be considered while deleting a node from Binary Search Tree.

Node to delete has no children that is no left child and no right child present. Case 1 in below image.
Node to delete has only one child either left child or right child present. Case 2 in below image.
Node to delete has both child that is left child and right child present. Case 3 in below image.

Case 1:
For case 1, it is very much straightforward,
1. Search for the node that need to be deleted. More....

Frequently Asked Interview Questions on Binary Tree.

Question 6:
Check if Two Binary Trees are identical?
Answer:
Two Binary Trees are considered equal if they are structurally identical and the nodes have the same value.

See below image for better understanding of which Trees are called Identical and which not.
More...

Question 7:
Check a given two Binary Trees are Mirror Image of each other?
Answer:
Two Binary Trees are considered mirror image of each other if there left and right child of every node is inter-exchange. (Left child moved to Right and Right chile moved to Left)

See below image for better understanding of which Trees are called Mirror Image of each other

More...

Question 8:
Connect nodes at same level in a Binary Tree?
Answer:
Let us first understand what we want to achieve? what is the input and what will be the expected output.

Binary Tree is given to you,

some node of tree has both left and right child present,
some node of tree has only left child present and
some node of tree has only right child present,
nextRight pointer of all the node initially is null.

Our task is to connect nextRight pointer of each node to its adjacent node.

1. If the immediate adjacent node is not present then connect to next adjacent node and
2. If next adjacent node is not present then connect to next to next adjacent node and
3. If next to next adjacent node is not present then search until you find the adjacent node along
the same Level and connect to it.
4. If the adjacent node is not present at same level then connect it to null.

More...

Question 9:
Connect nodes at same level in a Binary Tree using constant extra space?
Answer:
This problem is variation of above question number 8. you can see details of this post on this link.
Connect nodes at same level in a binary tree using constant extra space.

Question 10:
Construct a Binary Tree from In-order and Level-order traversals?
Answer:
Two traversals are given as input,

int[] inOrder = { 4, 2, 6, 5, 7, 1, 3 };
int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

By using above two given In order and Level Order traversal, construct Binary Tree like shown below More...

Question 11:
Construct a Binary Tree from In-order and Pre-order traversals?
Answer:
Two traversals are given as input,

int inorder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
int preorder[] = {50, 40, 30, 20, 35, 45, 60, 55, 70};

By using above 2 given In order and Pre Order traversal, construct Binary Tree like shown below,
More...

Question 12:
Zig Zag or Spiral Traversal of Binary Tree?
Answer:
Given a binary tree, write a program to print nodes of the tree in spiral order.
You can also say it as Spiral order traversal of a tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?

If you observe Zig Zag Traversing is very similar to Level order traversal with few modification.
More...

Question 13:
Boundary Traversal of Binary Tree?
Answer:
We have to print the boundary nodes of given Binary Tree in anti-clockwise starting from the root.

Print Left boundary Nodes.
Print Leaf Nodes.
Print Right boundary Nodes in Bottom up fashion.

Let's take an example and try to understand. For reference we will More...

Question 14:
Print a Binary Tree in Vertical Order?
Answer:
Given a binary tree, print it vertically.

Vertical order Traversal of a tree is little bit different than Pre order, Post order, In order and Level order traversal.

We need to identify, which node will be part of Line 1, Line 2, Line 3 and so on, How to do that? If you observe, then there is a close relation between each line from root. More...

Question 15:
Print Nodes in Top View of Binary Tree?
Answer:
Given a binary tree, print the nodes that is visible, when the tree is viewed from the top.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Top view means, when we look the tree from the top, the nodes that are visible will be called the top view of the tree. So in the above image,

Solution: "If two nodes have the same Horizontal Distance from root, then they are on same vertical line." Lets understand this line in more detail. More...

Question 16:
Print Nodes in Bottom View of Binary Tree?
Answer:
Given a binary tree, print the nodes that is visible, when the tree is viewed from the bottom.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Bottom view means, when we look the tree from the bottom, the nodes that are visible will be called the bottom view of the tree. So in the above image,

Solution for printing the nodes visible from bottom view of binary tree is very similar to vertical traversal of binary tree. More...

Question 17:
Find Kth smallest element in BST(Binary Search Tree)?
Answer:
Solution is very simple:

Take a variable counter, which keep track of number of smallest element read till now.
Do In order traversal, instead of printing the node in in-order traversal, increment the counter till it matches K.
Check whether counter value is equal to K.
If YES, then current node is Kth smallest node and return it. If NO, then return -1 as indication that given 'K' is invalid. More...

Question 18:
Find Kth largest element in BST(Binary Search Tree)?
Answer:
Solution is very simple:

Take a variable counter, which keep track of number of largest element read till now.
Do In-order traversal starting from right side (Right to Left instead of Left to Right), instead of printing the node in in-order traversal, increment the counter till it matches K.
Check whether counter value is equal to K.
If YES, then current node is Kth largest node and return it. If NO, then return -1 as indication that given 'K' is invalid.. More...

Question 19:
Find diameter of Binary Tree.?
Answer:
A longest path or route between any two nodes in a tree is called as Diameter/Width of binary tree.

The diameter of tree may or may not pass through the root.
The diagram below shows two trees each with diameter 7, diameter are shaded with blue nodes.

We will discuss 3 solutions,

By using Global variable.
By computing height and diameter of each node.
By computing height and diameter of each node in optimized way. More...

Question 20:
Given an array of numbers, verify whether it is the correct Preorder traversal sequence of a binary search tree?
Answer:
You are given an array of numbers which represents Preorder traversal of Binary Search Tree.
Verify whether it is a correct Preorder sequence or not.

Lets understand what is the input and the expected output.

Input: [40, 30, 35, 20, 80, 100]
Output: Invalid Preorder traversal

Input: [45, 25, 15, 35, 75]
Output: Valid Preorder traversal

Input: [50, 39, 44, 28, 85]
Output: Invalid Preorder traversal. More..

Question 21:
Construct a Binary Tree from In-order and Post-order traversals
Answer:

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question: Two traversals are given as input,

int inOrder[] = {20, 30, 35, 40, 45, 50, 55, 60, 70};
int postOrder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};
By using above 2 given In order and Post Order traversal, construct Binary Tree More..

Question 22:
Serialize and Deserialize a Binary Tree.
Answer:

Design an algorithm to serialize and deserialize given Binary Tree. Serialization is to store tree in a File/String, so that it can be later restored. Deserialization is reading tree back from file.Serialization:
For Serialization process, we can read the given Binary Tree in any order and create a String representation of tree as long as same String is capable of converting back to same given Binary Tree.

More..

Question 23:
Convert Sorted Array to Balanced Binary Search Tree(BST).
Answer:

Given a sorted array, create a Balanced Binary Search Tree using array elements.
A Binary Search Tree is called Balanced if, the height of left subtree and height of right subtree of Root differ by atmost 1.

We are given a sorted array, So which element we will pick as a Root Node for our BST such that it will be balanced.
If we pick the middle element of the array as Root node and distribute the left portion More..

Question 24:
Convert Sorted Linked List to balanced BST.
Answer:

Given a singly Linked List where elements are sorted in ascending orderconvert it to a height balanced BST.

A Binary Search Tree is called balanced if the height of left subtree and height of right subtree of Root differ by at most 1.

Lets understand the problem statement graphically and it will be more clear, More..

Question 25:
Print Nodes at K distance from Root in Binary Tree.
Answer:

Given a Binary Tree, Print all Nodes that are at K distance from root node in Binary Tree.
We can also think of this question as Print all nodes that belong to Level K.

Lets understand what will be input and expected output with the help of an example. More..

Question 26:
Print nodes at K distance from Leaf node in Binary tree.
Answer:

Given a Binary Tree, Print all Nodes that are at K distance from leaf node in Binary Tree.
Lets understand what will be input and expected output with the help of an example.

If k = 1. It means we need to print all nodes that are at distance 1 from Leaf node.

In Case 2, we have 4 leaf nodes (Node 1, Node 10, Node 5, Node7).
Node at distance K that is Node at distance 1 from leaf Node 1 is Node 2 (Print 2)
Node at distance K that is Node at distance 1 from leaf Node 10 is Node 9 (Print 9)
Node at distance K that is Node at distance 1 from leaf Node 5 is Node 6 (Print 6)
Node at distance K that is Node at distance 1 from leaf Node 7 is Node 6 (6 already printed, ignore)

More..

Question 27:
Get Level/Height of node in binary tree.
Answer:

Given a binary tree, you need to find the height of a given node in the tree. Finding level of node of binary tree is equivalent to finding Height of node of binary tree.

There are 2 approach to find level of node in binary tree,

Recursive approach.
Iterative approach. More..

Question 28:
Check if two nodes are cousins in a Binary Tree.
Answer:

Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not.

Two nodes are cousins if,

They are not siblings (Children of same parent).
They are on the same level.

Two nodes are cousins of each other if they are at same level and have different parents. More..

Question 29:
Check whether Binary Tree is foldable or not.
Answer:

Check whether given binary tree can be folded or not. Binary Tree is said to be Foldable if nodes of Left and Right Subtree are exact mirror of each other.

Traverse Binary Tree and compare left node of Left subtree with right node of Right subtree.
Traverse Binary Tree and compare right node of Left subtree with left node of Right subtree.
In both steps 1 and 2 above, check both left and right node is null or both left and right node is not null, if Yes, then Tree is foldable and has identitical structure otherwise not. More..

Thursday, 19 October 2017

Resolve java.net.BindException: Address already in use: bind

Resolve java.net.BindException: Address already in use: bind.

Resolve java.net.BindException: Address already in use: bind. address already in use. port 8080 already in use. address already in use jvm_bind tomcat eclipse.

java.net.bindexception: address already in use

When you face "Address already in use" exception, It is due to port already in use by other/same application.

To resolve this issue, you can check which application is holding the port or you can kill the application running on same port.

In this post we will see,

How to find process id in windows using command prompt.
Kill the process using windows command line.

Steps to kill process running on port 8080,

Step 1:

netstat -ano | findstr < Port Number >
Example: netstat -ano | findstr 8080

This step will give you "process id" of service running on port "8080"

Step 2:

taskkill /F /PID < Process Id >
Example: taskkill /F /PID 25392

This step will Kill the process running on port 8080.

Done... Enjoy

Kill process on port 8080 in Windows

Kill process running on port 8080 in Windows.

Kill process on port in Windows. how to kill process running on port 8080 in Windows or linux. find processes listening on port 8080. stop service on specific port..

kill process running on port 8080 in windows

In this post we will see,

How to find process id in windows using command prompt.
Kill the process in windows command line.

Steps to kill process running on port 8080 in Windows,

Step 1:

netstat -ano | findstr < Port Number >
Example: netstat -ano | findstr 8080

This step will give you "process id" of service running on port "8080"

Step 2:

taskkill /F /PID < Process Id >
Example: taskkill /F /PID 25392

This step will Kill the process running on port 8080.

Done... Enjoy

Saturday, 14 October 2017

How Hashmap works internally in Java with Diagram

How HashMap works in Java.

Internal working of Get and Put operation.

Hashmap store objects in key-value pair in a table.
1. Objects are stored by method hashmap.put(key, value) and
2. Objects are retrieved by calling hashmap.get(key) method.

For detail explanation on hashmap get and put API, Please read this post How Hashmap put and get API works.

Put Operation

Hashmap works on principle of hashing and internally uses hashcode as a base, for storing key-value pair.
With the help of hashcode, Hashmap stores objects and retrieves it in constant time O(1).

Lets recap "Employee Letter Box" example, we saw in last post on Hashcode.

How Hashcode and Equals works in Java Hashmap

How Hashcode and Equals works in Java Hashmap.

This is the famous interview question for the beginners as well as for experienced, So Let's see what it is all about.

Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation. Before getting into Hashmap internals, Please read Hashmap basics and Hashcode.

Before going into details of Hashcode and Equals method, lets first understand how Get and Put
method of Hashmap works internally and it will help you understand where this two method come in picture.

Internal working of Get and Put operation.

Put Operation

Thursday, 12 October 2017

What is Thread in Java with example.

Java Thread is an independent path of execution within a program which can run in parallel with other existing Threads.

Lets try to understand above line with simple scenario and it will be more clear:

Threads in Real time scenario:
Suppose you want to count the population of a India, how will you approach?
Note: There are 29 states in India.

Approach 1:

First approach is, you start with first state and count population of that state then you will start second state and so on for all 29 states.
Once you have population of all the states, just sum the population count of all States.

Imagine the time it will take for you to do this as you are alone and you have to count population state by state.

Approach 2:

Second approach is, you called 29 people to help you out and you distributed the task of population count to 29 person, each person taking care of individual state.

Person 1 will take care of population count for State 1.
Person 2 will take care of population count for State 2 and so on.

Once you have population count of all the states, just sum the population count received from all 29 person and you are done.

Imagine the time it will take for you to do this as compared to Approach 1, surely it will be much less.

So that is what Thread does. In above scenario, you can consider 29 persons as 29 Threads who are doing their respective task of population count.

It is possible that Person 1 may finish population count for State 1 assigned to it much early than Person 2 doing population count for State 2 because State 1 might be small.
Person 2 will continue doing his task even after Person 1 finished early.

In the similar way, Say If you have 2 Threads say Thread 1 and Thread 2. Thread 1 may complete its job early and Thread 2 will continue doing its job even after Thread 1 is done and they both execute separately.

Now to relate it with Threads:
When you have task like above that needs to be run in parallel for faster processing at that time Threading will come in picture.

You can say, Java Threads helps creating multiple independent path of execution within a program which can run parallely.

Application Example:
In Java, when a program requires more than one task to execute in parallel, say for example,

Reading a data from a local file.
Reading a data from remote connection.

When both of above task need to be executed in parallel at that time Threading will come in picture.
So Java Threads helps creating multiple independent path of execution within a program which can run in parallel.

Sunday, 29 October 2017

Friday, 27 October 2017

Top 10 Matrix Interview Questions

Frequently asked Top 10 Matrix Interview Questions.

You may also like to see

Sunday, 22 October 2017

Binary Tree Interview Questions.

You may also like to see

Thursday, 19 October 2017

Resolve java.net.BindException: Address already in use: bind.

You may also like to see

Kill process running on port 8080 in Windows.

You may also like to see

Saturday, 14 October 2017

How HashMap works in Java.

Internal working of Get and Put operation.

Put Operation

How Hashcode and Equals works in Java Hashmap.

Internal working of Get and Put operation.

Put Operation

Thursday, 12 October 2017

What is Thread in Java with example.

You may also like to see