Data Structure and algorithm interview questions in java

I have been posting data structure and algorithms programs on various topics such as Array,Queue, Stack ,Binary tree, LinkedList , String, Number, ArrayList, etc. So I am consolidating list of programs to create an index post. I will keep adding links to this post whenever I add any new program. These are frequently asked Data Structure and algorithm programs in interview.

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.

Stack :

Question 1:  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 2: 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 3:  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 4 :  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.

Linked List :

Question 5 : 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 6: 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 7: 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 8 : 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 9  : 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 10: 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 11 :  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.

Binary Tree :

Question 12: How can you traverse binary tree?

There are three ways to traverse binary tree.

Question 13 : 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.

Question 14 :  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 15: 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 16: 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 17. 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 18 : 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 19: 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 20 : 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 21 : 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 22 : 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.

Binary Search tree:

Question 23 : 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 24: Can you write algorithm to insert a node in binary search tree.

Solution : Insert node in binary search tree.

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

Solution : Delete node in binary search tree.

Question 26:  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

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

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

Sorting :

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

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

Array:

Question 30  : 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 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 : Find missing number in the array.

Question 31 : 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 32: Find second largest number in an array

Given an unsorted array, you need to find second largest element in the array in o(n) time complexity.
For example:
int[] arr1={7,5,6,1,4,2};
Second largest element in the array : 6

Question 33: 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

Question 34: 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.

Question 35: 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

Question 36: 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

Question 37: 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

Graph:

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

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

Miscellaneous

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

Solution : How to calculate Complexity of algorithm.

String: 

You can find list of interview programs on String.

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012