Top 30+ Data Structure Interview Questions And Answers

This tutorial provides frequently asked Data Structure interview questions and answers with explanations to help you prepare for the interview:

Computer programs use data that gets converted into binary (0 and 1) and digital (positive for 1 and non-positive for 0) format so that computers understand its value.

Computer software and applications are developed using binary data as a reference or as information that will be processed by a computer in a central processing unit. The method to store, organize and efficiently use this data is termed a data structure.

There are many ways data can be organized in memory in order to utilize it efficiently without occupying space or memory of storage. There are a set of rules and sequences applied by a computer in computing this data, known as an algorithm.

Algorithm and Data Structure are the foundation for understanding how data is organized, stored, and optimized for efficient digital outcomes.

About Data Structure

Knowledge and skill of using Data Structure and Algorithm properly help programmers and give them the ability to quickly solve complex problems in the most efficient way.

The algorithm is a set of instructions implemented in a computer to solve problems or for data computation. Ways in which data can be managed and stored in memory to efficiently utilize for computation on this data is known as a data structure.

Interview questions are designed for developers working on applications related to artificial intelligence, graphics, and operating system for efficient data management.

Frequently Asked Data Structure Interview Questions

Q #1) Explain what is data structure.

Answer: It is an efficient way of organizing data in order to use it effectively for retrieving and storing data in computer memory, exchanging information between applications via TCP/IN packets, ordering and sorting, memory allocation, and file directory management.

Data Structure in Java are of two types: Primitive and Non-Primitive

• Primitive type contains char, int, float, double, and pointer.
• Non-Primitive type contains Array, Linked List, Stack, Queue, Tree, and Graphs.

Non-primitive Data Structure image:

Q #2) Describe what is an algorithm?

Answer: A set of rules to be followed on input data to get desired output is called algorithms. These are mainly used in programming, math, and scientific calculations.

In daily life, algorithms can be applied in traffic monitoring and vehicle rerouting, monitoring crime, parcel delivery tracking, rendering of financial data, predicting treatment procedures based on patients’ medical data.

Q #3) How Data structure and algorithms are related to each other?

Answer: Data structure is a format for organizing, managing, and storing data in an optimized manner in computer memory, whereas an algorithm is a set of rules to be followed to resolve data handling problems and retrieve the desired output. Sorting, Searching, and Shortest Path algorithms are some of the commonly applied algorithms to data structures.

A real-life example is a recipe for food delicacy, algorithm will be the steps to cook and order in which ingredients are mixed for desired output, in this case, taste.

Q #4) List various areas in which data structure is used?

Answer: Data structure can be used for storing data, data exchange, ordering, and sorting, searching, indexing, resource/ services management, and scalability in applications.

Various domain areas include:

• Artificial intelligence
• Machine Learning
• Database management
• Blockchain
• Graphics
• Simulation
• Compiler design
• Cryptography
• Statistical and Numerical analysis
• Development of operating systems
• Processing in speech and image

Q # 5) List types of data structure with their example.

Answer: Data structure is divided into the following main categories:

• Primitive data structures in C are:
  • • char
    • pointer
    • integers
    • float
    • double
• Non-primitive data structure is further divided into Linear and Non-Linear
  • Linear
    • Array
    • Linked List
    • Stack
    • Queue
  • Non-linear
    • Tree
    • Graph

Q #6) List and describe various data structures supported in the C programming language?

Answer: Following are the data structures found in C:

• Array: Similar type elements stored sequentially in memory are known as arrays in C. They are of two types single-dimensional and multidimensional array.
• Stack: It follows the last in first out (LIFO) approach with Push function to add elements and Pop function to remove elements from linear data structure called Stack where both operation insert and delete are performed from one end of the stack.
• Queue: It is similar in structure to Stack, Queue follows the first in first out (FIFO) approach, where elements are added from the back and removed from the front of the queue.
• Linked List: Unlike an array, a Linked List is not stored sequentially in memory, composed of a data section and address section known as a node that holds the address of the next element. They are of 3 types – singly link, doubly link, and circular link.
• Trees: With one root node and multiple sub-nodes designed on top of the linked list.
• Hashing: Hash table map keys to values and used for implementing associative array. It uses a hash function for calculating indexes in an array of buckets.

Q #7) What are the benefits offered by the data structure?

Answer: Benefits offered are listed below:

• Storing data efficiently in storage devices.
• Convenient retrieval of data from the storage device.
• Processing small and large data effectively.
• Saves time during storage, retrieval, or processing of data.
• Reuse and scale data using data structures like an array, tree, graph, stack, linked list.

Q #8) Differentiate between linear and non-linear data structures.

Answer: Major differences between Linear and Non-linear data structures are listed below:

Q #9) What is an array as a data structure?

Answer: A collection of elements of similar data types stored in adjacent memory locations is known as Arrays. The lowest and highest address corresponds to the first and the last element of the array. An index can access elements in the array, with 0 as an index for the first element and the last element index is total array size minus 1. Arrays are further divided into single and multidimensional arrays.

In Java array is declared as below:

Array myarr[] = new Array[5];

Q #10) Explain with examples – single and two-dimensional array.

Answer: One-dimensional array is a data structure that stores data values of similar data types in the adjacent memory blocks. In Java, number array memory for the array is allocated using the ‘new’ keyword is defined below:

num = new int [5];

num = {2,4,6,8,10};

Data elements in the array are accessed using the index, starting with 0 as the first element index.

Multi-dimensional array stores multiple data elements of similar data types in table-like format with a number of columns and rows.

nums = new int[2][4];

Above is a two-dimensional array of 2 rows and 4 columns.

Q #11) Describe Linked List.

Answer: Linked list data structure where elements are linked using pointers, with elements not stored to adjacent memory locations. It comprises nodes with each node containing a data field and link referencing the next node in the list. Various operations linked list supports include insertion, deletion, display, and search an element using a given key.

Q #12) List the differences between arrays and linked lists.

Answer: Both arrays and linked list belongs to the linear data structure. The difference between them are listed below:

Q #13) Explain how linked lists are more efficient than arrays

Answer: Following points prove linked lists to be more efficient than arrays:

• The array size, i.e. the number of elements in an array, is fixed. It is essential for arrays to know the upper limit of storing similar elements in advance.
• Inserting new elements in an array is expensive as it requires shifting existing elements to create room for new elements.
• Deleting any of the existing elements from the middle of the array is expensive as all the elements after that element need to be moved
• Linked List provides the advantage of Dynamic Size and Ease of insertion and deletion over arrays, making it more efficient than arrays.

Q #14) Describe various scenarios where linked lists and arrays are used.

Answer: We list the scenarios explaining why a linked list or array is used.

Linked List is used:

• When it is critical to maintain the time taken for insertion or deletion of elements.
• When the number of elements is not certain, a linked list is preferred.
• Linked List is used to store elements when random access to any elements inside the list is not needed.
• When it is required to insert elements at the middle of the list, a Linked list is preferred.

Arrays are used:

• It is needed to access elements at random.
• When the number of elements is already known, arrays are preferred to allocate memory to the total number of elements.
• When iterating through all the elements should be quick for performance.
• When memory is of concern, an array takes less memory than a linked list.

Q #15) Explain the Doubly linked list as a data structure and its uses.

Answer: A linked list that can move back and forth in both directions is called a doubly linked list. Doubly linked lists are used when it is frequently required to find the location of the previous node. Insertion, deletion, searching, and traversal are some of the operations applied on a doubly linked list.

Q #16) Describe Stack as a data structure and its use.

Answer: A stack holds a linear sequence of items of abstract data type in a particular order. It follows LIFO in inserting and removing elements.

The operations performed on Stack are:

• Push(data) – inserts data to the top of the stack,
• Peek() returns a copy of the element on the top of the stack.
• Pop – removes data from the top of the stack

Q #17) Explain Queue as a data structure and its use.

Answer: Queue is an abstract data structure that differs from Stacks as it opens at both its ends, follows FIFO (First In First Out) order when data handling operations are performed on it. One end in the Queue data structure allows insertion of data, whereas the other is used to remove data.

The queue is used when is the processing of data is not immediately needed and a resource is shared across multiple consumers.

Q #18) Explain how the stack differs from the queue?

Answer: Following are the differences between Stack and Queue:

Q #19) Describe hash map as a data structure and its use.

Answer: A data structure known as Hash Table stores values using a pair of keys and values. Each of these values is assigned to a unique key that is generated with a hash function. The associated value is accessed by name of the key.

A Hash table or hash map implements an associative array abstract data type. Some of the uses of the hash tables include Password Verification, Pattern matching, Compiler design, file system, and creating cryptographic message digest.

Q #20) How collision in Java is controlled by HashMap?

Answer: The concept of Chaining is used by HashMap to handle the collision resolution in Java. Each hash code generated by the hash function is mapped to a specific bucket that contains a linked list for the case of collision. Creating a hash function that offers the best distribution possible of values throughout the hash map is the only way to avoid a collision.

Q #21) How variable is stored in memory using data structures?

Answer:

• In Stack data structure, variables are stored, declared, and initialized during runtime, providing temporary storage in a special area of computer memory.
• Heap is a memory space that supports dynamic memory allocation and stores global variables in computer programming languages.
• Text or code segment is sharable single copy to be in memory for the program for frequent execution. It is read-only to prevent any accidental modification.
• The data segment is a virtual address space that contains global and static variables. It is not read-only as variable values can be altered at run time.
• Uninitialized data segments called Block started by the symbol (BSS) is initialized by the kernel to arithmetic 0 before the program starts execution initializing global and static variables to zero.

Q #22) Describe Priority Queue.

Answer: Priority Queue has items stored by key value as in Hash Map, such that items with the highest value of keys will be at the rear and that with the lowest value of keys will be in front.

Principle operations using Priority Queue are inserted/enqueue and remove/dequeue.

• insert/enqueue inserts items at the rear of the queue.
• remove/dequeue removes an item from the front of the queue.
• peek –retrieves element at front of the queue.
• isFull – checks if the queue is full.
• isEmpty – verifies if the queue is empty.

Q #23) Explain Tree as a data structure and its use

Answer: A tree is a hierarchical data structure known as a collection of nodes. The tree has one node known as the root and originates from it, hence it has no parent. Each node represents a single parent connected to multiple edges like children. The tree is used in predictive modeling, as it can handle large data and can be validated statistically.

Q #24) What is a binary tree in data structure?

Answer: A binary tree is a hierarchical data structure having elements with 2 children connected via a node. The structure contains Data, Pointer to left child and pointer to right child.

In Java 8, when the number of elements in a bucket reaches a particular threshold, HashMap replaces Linked List with Binary Trees, as binary trees store at both left and right nodes, hence using more space than a singly linked list.

The binary tree structure is used to search information, manipulate hierarchical data, and sort data lists, creating router algorithms and forms that help in multi-stage decision-making.

Q #25) Explain Binary Search Tree in the data structure.

Answer: Binary Search tree differs little with Binary tree in the following way:

• The Left and right sub-tree (children) should also be a binary search tree with no duplicate node.
• The node at the left sub-tree should contain nodes with keys lesser than the parent node key.
• The node at the right sub-tree should contain nodes with keys greater than the parent node key.

A binary Search tree is helpful in fast lookup, addition, and removal of data items, and in lookup tables, and in implementing dynamic sets.

Q #26) Describe a Graph as a data structure and its use.

Answer: Graph is a data structure where a set of interconnected objects is connected by links. The objects are called vertices, and links connecting the vertices are known as edges.

Basic operations such as Adding Vertex, Adding Edge, and displaying Vertex can be carried out in Graph structure.

Graphs are very useful in designing electrical circuit connections, the study of the algorithm, the relationship between computer networks, the molecular and chemical structure of substance such as DNA of the organism, parsing tree of language and grammar, and connecting nodes between cities.

Q #27) List the difference between Tree and Graph.

Answer: Tree and Graph are both non-linear data structures and are collections of nodes and edges. However, the following are the differences between the two:

Q #28) Differentiate between Breadth-First Search (BFS) and Depth First Search (DFS).

Answer: The differences between BFS and DFS are listed below:

In both BFS and DFS, Time complexity is 0(V+E) and Adjacency List used is 0(V^2) for adjacency matrix, where V stands for Vertices and E is for Edge.

Q #29) Suggest the data structure to build a dictionary or check the spellings.

Answer: Based on memory availability and desired functionalities for spell check and dictionary, the option we have is Hashing. It is observed that hashing is efficient when it is compared with self-balancing binary search trees and skip lists.

Hashing does not support Prefix search, where user types prefix and auto-suggest feature – dictionary display all words starting with prefix entered.- For lookup and prefix search Trie is appropriate, making printing words in alphabetical order possible.

However Trie needs lots of space, here we can try Ternary Search Tree – for the time complexity of search operation.

Q #30) Explain how you will convert infix expression (A + B) * (C + D) into prefix expression

Answer: Following are the three steps needed to be carried out to convert the given infix expression into prefix expression.

Step 1: Reverse the infix expression – which is (D + C) * (B + A)

Simplified form of above expression is DC + * BA +

Step 2: Find post expression – DC + BA + * is post expression of above infix expression

Step 3: Reverse the postfix expression – Reversing above expression we will get * + AB + CD

Hence prefix expression of infix (A + B) * (C+ D) is * + AB + CD

Q #31) How Stack can be implemented in Java using Array?

Answer: Although Array implementation of Stack in Java is not dynamic in nature, the program is as given below:

public class Array2Stack {
	    int size, arr[], top;	
	Array2Stack(int size) {
	    this.size = size;
	    this.arr = new int[size];
	    this.top = -1;
}
public void push(int pushedElement) {
	if (!isFull()) {
	top++;
	arr[top] = pushedElement;
	System.out.println("Pushed element: " + pushedElement);
	} 
       else { 
	System.out.println("Stack is full");
	 }
  }
public int pop() {
	if (!isEmpty()) {
	int returnedTop = top;
	top--;
	System.out.println("Popped element: " + arr[returnedTop]);
	}
	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) {
	Array2Stack arrstk = new Array2Stack(10);
	arrstk.pop();
System.out.println("*************");
	arrstk.push(15);
	arrstk.push(25);
	arrstk.push(49);
	arrstk.push(34);
System.out.println("*************");
	arrstk.pop();
	arrstk.pop();
  	arrstk.pop();
System.out.println("*************");
	}
}

The output for the above program is given below

Stack is empty!

****************

Pushed element: 15

Pushed element: 25

Pushed element: 49

Pushed element: 34

****************

Popped element: 34

Popped element: 49

Popped element: 25

**************

Conclusion

The data structure is divided into primitive data, linear and non-linear data, it helps to store, manipulate and organize data to manage data effectively. Various data structure differs from one another in the way data is connected. Array, Stack, Queue, Linked List, Trees, Graph, and Hash Map are some of the data structures used in the data processing.