Data Structure Interview Questions in Java

December 1, 2023

dsa_in_jav_interview_question

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
Read more: Data structure in java
Read more: data structure in 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

DSA in JAVA Interview Questions and Answers For Freshers

Also Check Out:-

Complete Interview Preparation
Technical Interview Questions
HR Interview Questions
Interview Puzzles

Ques 1: What is a class?

Ans.

A class is nothing more than a description of an object. It is a model, design, or prototype that describes an object’s features.

Ques 2: What is Stack?

Ans.

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.

Ques 3: What is merge sorting?

Ans. 

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.

Ques 4: What is traversing?

Ans. 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

Ques 5: Define What is Queue?

dsa_in_java_interview_questions_queue

Ans.

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  

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

Ans. 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.

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

Ans.

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.

Ques 8:What is a postfix expression?

Ans.

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.

Ques 9: What are Infix, prefix, Postfix notations?

Ans.

Infix notation: X + 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

Ques 10: What is a multidimensional array?

dsaIn_java_interview_questions

Ans.

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.

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

Ans.

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.

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

Ans. 

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

 

Ques 13: What is an array?

Ans.

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};

Ques 14: Advantages of immutability?

Ans.

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.

Ques 15: Define the tree data structure.

dsa_in_java_interview_questions_tree

Ans.

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.

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

Ans.

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.

Ques 17: How to know if a linked list has a loop?

Ans.

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.

Ques 18: Define cycle, path, and circuit?

Ans

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

Ques 19: What are the advantages of Binary search over linear search?

Ans.

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.

Ques 20: How to reverse String in Java language?

Ans. 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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

JAVA Interview Questions and Answers For Experienced.

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

dsa_in_java_interview_questions_linked_list

Ans.

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.

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

Ans.

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.

 

Ques 23: What makes Singly Linked Lists unique?

Ans.

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.

Ques 24: Difference between Array and Linked List

Array LInked List
The size of the arrays is fixed always  Linked Lists size is not fixed.
Insert and deleting in an array is an expensive process same 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

Ques 25:Do both of these statements create a string? String str = new String("Prepinsta"); //or String str1 = "Prepinsta";

Ans.

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.

Getting Ready for Interviews

Also Check:-