Data Structure Interview Questions in Java

Top 25 Most Asked DSA JAVA Interview Questions

Data Structure is again one of the most challenging and most important subjects for the interview. So you have to prepare well for this subject if you want to clear the interview. Here you will get the most essential data structure interview questions in JAVA.  Prepare for your interview with  Prepinsta.

Page Highlights:

  • What is Data Structure?
  • Top Data structure Interview Questions using java
  • Technical Interview Questions
data structure interview questions using java

Introduction to DSA in Java

Data Structure is a way to store and organize data so that it can be used efficiently. Our Data Structure tutorial includes all topics of Data Structure such as Array, Pointer, Structure, Linked List, Stack, Queue, Graph, Searching, Sorting, Programs, etc.

Top 25 Data structure Interview Questions in Java

1. What is data structure?

A data structure is a framework for organizing, managing, and storing data that allows for quick access and modification. A data structure, more properly, is a collection of data values, their relationships, and the functions or operations that may be performed on the data.it is known as a hash table

The data structures provided by the Java utility package are very powerful and perform a wide range of functions. These data structures consist of the following interface and classes −

  • Enumeration
  • BitSet
  • Vector
  • Stack
  • Dictionary
  • Hashtable
  • Properties

2. What is a Stack?

stack is an ordered list in which insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having a pointer to its top element. The stack is sometimes called a Last-In-First-Out (LIFO) list i.e. the element which is inserted first in the stack will be deleted last from the stack.

3. What is merge sorting?

Merge sort is one of Java’s most versatile sorting algorithms. It sorts elements in an array using the divide and conquers approach. It’s also a stable sort, which means it won’t modify the order of the array’s original elements concerning each other.
This algorithm is divided into two parts:

mergeSort() – This function calculates the subarray’s middle index before partitioning it into two halves. The first half runs from left to middle, and the second half runs from middle+1 to right. This function automatically runs the merge() function when partitioning is complete to sort the subarray handled by the mergeSort() call.

4. What is traversing?

To traverse a Data Structure is to go from one element to the next. Any form of DS can be used for this.
import java.util.*;

class Prepinsta{

static void printStack(Stack St)

{       

while (!St.isEmpty()) {

System.out.print(St.peek() +" ");

St.pop();

}

}

public static void main(String[] args)

{

Stack St = new Stack<>() ;

St.add(4);

St.add(3);

St.add(2);

St.add(1);

printStack(St);

}

}

Output: 1 2 3 4

5. What is Queue?

Operations on queue:

  • Insertion and deletion happen on different ends.
  • A queue is a linear structure in which operations are carried out in a specific order. First in, first out is the order (FIFO). Stacks and queues differ in how they are removed. In a stack, the item that was most recently added is removed; in a queue, the item that was least recently added is removed.
  •  Reversing a Queue,  Reversing a queue using recursion, Reversing the first K elements of a Queue, Interleave the first half of the queue with the second half, Sorting a Queue without extra space  

6. How do you find the middle element of the linked list in one pass?

 In order to find the middle element of the linked list in one pass, one needs to maintain a two-pointer. One of these pointers will increment at each node while the other will increment after two nodes at a time, thus by having this type of arrangement, when the first pointer reaches the end of the linked list, the second pointer will point to a middle element of the linked list.

7. What are linear and non-linear types of data Structures? Also, How is an Array different from Linked List?

  • Linear: A data structure is called linear if its elements form a sequence or a linear list such as Array, Linked List, Stacks, and Queues.
  • Non-Linear: A data structure is called non-linear if the traversal of nodes is of nonlinear nature such as Graphs and Trees.

The difference between array and linked list are the following: –

  • The size of the arrays is fixed always, Linked Lists size is not fixed.
  • Insert and deleting in an array is an expensive process, whereas the same can be easily done in Linked Lists.
  • Accessing an element randomly is not possible in the case of Linked Listed, but is possible in an array.
  • Extra memory space for a pointer is needed with each element of the Linked list, arrays don’t have pointers.
  • Arrays have a better cache locality mechanism that can make a big difference in performance.

8. What is a postfix expression?

An expression in which operators follow the operands is known as postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.

The expression “a + b” will be represented as “ab+” in postfix notation.

9. What are Infix, prefix, Postfix notations?Text Here

  • Infix notation: + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as

    A * ( B + C ) / D

  • Postfix notation (also known as “Reverse Polish notation”): X Y Operators are written after their operands. The infix expression given above is equivalent to

    A B C + * D/

  • Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to
    / * A + B C D

10. What is a multidimensional array?

The multidimensional array can be defined as the array of arrays in which, the data is stored in a tabular form consisting of rows and columns. 2D arrays are created to implement a relational database lookalike data structure. It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required.

11. Calculate the address of a random element present in a 2D array, given base address as BA?

Row-Major Order: If an array is declared as a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in row-major order is calculated as,

Address(a[i][j]) = B. A. + (i * n + j) * size

Column-Major Order: If the array is declared as a[m][n] where m is the number of rows while n is the number of columns, then the address of an element a[i][j] of the array stored in column-major order is calculated as

Address(a[i][j]) = ((j*m)+i)*Size + BA.

12. Which data structures are used for the BFS and DFS of a graph?

  • A queue is used for BFS
  • Stack is used for DFS. DFS can also be implemented using recursion

13. What is an array?

A collection of items stored in contiguous memory spaces is referred to as an array. The objective is to group together goods of the same type.

Ex: int a[]=new int[3];

    int a[5]={1,2,3,4,5};

14. Advantages of immutability?

Immutability makes strings thread-safe.

Saves heap memory

Helps maintain string-key hash tables

Secures ClassLoading, which takes a string as an argument, and other string-based authentication.

15. Define the tree data structure.

The Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called the children of the root. The nodes other than the root node are partitioned into the nonempty sets where each one of them is to be called a sub-tree.

16. How can AVL Tree be useful in all the operations as compared to Binary search tree?

AVL tree controls the height of the binary search tree by not letting it be skewed. The time taken for all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log n, the AVL tree imposes an upper bound on each operation to be O(log n) where n is the number of nodes.

17. How to know if a linked list has a loop?

 If two pointers are maintained, and one of them is incremented after processing two nodes and the other after processing every node, it is likely that we find a situation where both the pointers are pointed to the same node. This happens only if a linked list consists of a loop or cycle.

18. Define cycle, path, and circuit?

  • Path: A Path is the sequence of adjacent vertices connected by the edges with no restrictions.
  • Cycle: A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path can not be visited twice
  • Circuit: A Circuit can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex may be repeated

19. What are the advantages of Binary search over linear search?

There is relatively less number of comparisons in binary search than that in linear search. In the average case, the linear search takes O(n) time to search a list of n elements while Binary search takes O(log n) time to search a list of n elements.

20. How to reverse String in Java language?

There are many ways available to reverse String in Java or other programming languages, one could do so by using built-in functions such as reverse() from StringBuffer class.

import java.io.*;
import java.util.Scanner;

class Prepinsta {

public static void main (String[] args) {

String str= "Prepinsta", nstr="";

char ch;

System.out.print("Original word: ");

System.out.println("Prepinsta"); 

for (int i=0; i<str.length(); i++)

{

ch= str.charAt(i); 

nstr= ch+nstr; 

}

System.out.println("Reversed word: "+ nstr);

}

}

Output: atsniperp

21. What do you understand by a Linked List and What are its different types?

A linked list can be regarded as a linear data structure, where each element is considered as a separate object or entity in itself. Each element within a list consists of two items – the data and the reference to the next node.

Types of Linked List:

  • Singly Linked List: In a singly linked list, every node stores two information. One is the address of the next node and the other is data. the last node has NULL.
  • Doubly Linked List: In a doubly-linked list, there are two references to each node, a reference to the next node and the previous node.
  • Circular Linked List: In a circular linked list all nodes are connected and hence no NULL at the end. A circular linked list can be singly circular or doubly circular.

22. What do you understand by Stack and where can it be used?

This is the most popular Data Structure Java Interview Questions asked in an interview. A stack can be understood as a linear data structure that uses the order LIFO (Last In First Out) or FILO (First In Last Out) for accessing its elements. Basic operations on a stack are: Push, Pop, and Peek

Applications of Stack are following:

  • Infix to Postfix Conversion can be done using Stack.
  • Evaluation of Postfix Expression is also possible.
  • Reverse a String using Stack can be done.
  • Implementing two stacks in an array is also a nice use case.
  • Check for balanced parentheses in an expression is done using stacks.

23. What makes Singly Linked Lists unique?

Singly Linked Lists are unidirectional, which means they can only be traversed in one manner.

  • Data and a pointer to the next node are stored in each node. The head node points to the initial entry of the list, whereas the tail node points to null to indicate that the list has ended.
  • A doubly linked list is the polar opposite of this.

24. Difference between Array and Linked List

ArrayLInked List
The size of the arrays is fixed always Linked Lists size is not fixed.
Insert and deleting in an array is an expensive processsame can be easily done in Linked Lists.
It is possible in an array.Accessing an element randomly is not possible in the case of Linked Listed
arrays don’t have pointers.Extra memory space for a pointer is needed with each element of the Linked list

25. Do both of these statements create a string?
String str = new String("Prepinsta");


//or
String str1 = "Prepinsta";

Both statements are correct

  • Both initializations are valid, albeit the second option is the most frequent technique to generate a string.
  • A doubly linked list is the polar opposite of this.

Also Check:

FAQs on DataStructure Interview Questions in Java

Are the elements of a linked list stored in memory in order?

Answer:-

They can be, but they don’t have to be. A linked list’s elements are stored as pointers, which means they don’t have to be placed next to each other to be found. However, by coincidence, two items may be kept in the same order.