20+ Most Asked Data Structures Interview Questions with Answers

by IlluminateMinds | Jul 5, 2022 | Data Structures, Technical

In this article, we will be discussing some of the most asked data structures interview questions by both IT-Service based & Product based companies.

Data Structures Interview Questions with Answers

Here are the 30+ most asked data structures interview questions.Data Structures & Algorithms is one of the most frequently tested subjects by a lot of companies. So make sure you have a quick look at these questions before the interview.

1) What do you mean by a Data structure?

Data structure is a format for storing data in a structured manner. For example, data like photos, videos are stored in gallery with the help of a data structure. It is not a separate programming language. It is just an implementation method and can be implemented using any one of the programming language like C, C++, Java, etc.

2) What are some of the applications of DS?

Some of the real-time applications of Data Structures are:

1. For representing a city region telephone network.
2. To implement back functionality in the internet web browser.
3. To store dynamically growing data which is accessed very frequently, based upon a key value.
4. To implement the undo function in a text editor.
5. To store information about the directories and files in a system.

For more applications of each of the data structures, check out the below links:

• Applications of a Stack
• Applications of Priority Queue
• Applications of Depth First Search
• Applications of Breadth-First Search

3) What are the advantages of a Linked list over an array?

Consider a scenario, where we need to store large amount of data in an array. But, the memory to store that data is not available contiguously. In this case we cannot use array. Hence, we go for a linked list. Since each node is connected using link, it is not necessary that memory has to be contiguous.

Also, some of the major differences between a Linked List and an array are given below. For more, click here.

4) Write the syntax in C to create a node in the singly linked list.

struct node 
{
 int data; 
 struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));

5) What is the use of a doubly-linked list when compared to that of a singly linked list?

In a singly linked list, we have only forward links. Hence, we cannot traverse the linked list in a backward manner. In order to overcome this, we go for a doubly linked list. In a doubly linked list, each node has three fields such as previous, data and next field and has two links such as a forward and backward link. The previous field of the first node and the address field of the last node is NULL. The previous field of the second node has the address of the first node and so on.

Also, accessing of elements can be done more efficiently in case of a doubly linked list.

6) What is the difference between an Array and Stack?

Stack Data Structure:

• Size of the stack keeps on changing as we insert and delete the element
• Stack can store elements of different data type

Array Data Structure:

• Size of the array is fixed at the time of declaration itself
• Array stores elements of similar data type

7) What are the minimum number of Queues needed to implement the priority queue?

Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities. Check out the implementation of a Priority Queue.

8) What are the different types of traversal techniques in a tree?

There are three main traversals of a tree such as In-order, Pre-order, Post-order.

Algorithm of In-order traversal:

Traverse the left sub-tree
Visit the root
Traverse the right sub-tree

Algorithm of Pre-order traversal:

Visit the root
Traverse the left sub-tree
Traverse the right sub-tree

Algorithm of Post-order traversal:

Traverse the left sub-tree
Traverse the right sub-tree
Visit the root

9) Why it is said that searching a node in a binary search tree is efficient than that of a simple binary tree?

When searching any node in binary search tree, the value of the target node is compared with the parent node and accordingly either left sub tree or right sub tree is searched. So, one has to compare only particular branches. Thus searching becomes efficient.

10) What are the applications of Graph DS?

Graphs are used in circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph, in transport networks where stations are drawn as vertices and routes become the edges of the graph, in maps that draw cities/states/regions as vertices and adjacency relations as edges, in program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.

11) Can we apply Binary search algorithm to a sorted Linked list?

No, we cannot apply the binary search algorithm to a sorted linked list because finding the index of the middle element is difficult.

12) When can you tell that a Memory Leak will occur?

A memory leak occurs when a program does not free a block of memory allocated dynamically.

13) How will you check if a given Binary Tree is a Binary Search Tree or not?

To know that you need to check the inorder traversal of a binary tree. If it is sorted, then the binary tree is BST. Click here to know how to perform inorder traversal.

14) Which data structure is ideal to perform recursion operation and why?

Stack is the most ideal for recursion operation. This is mainly because of its LIFO (Last In First Out) property, it remembers the elements & their positions, so it exactly knows which one to return when a function is called.

15) What are some of the most important applications of a Stack?

Some of the important applications are given below. Check them out to know the detailed code & explanation.

• Balanced parenthesis checker
• Redundant braces
• Infix to postfix using a stack
• Infix to prefix using a stack

16) Convert the below given expression to its equivalent Prefix And Postfix notations.

((A + B) * C – (D – E) ^ (F + G))

Prefix Notation: ^  * +ABC  DE + FG

postfix Notation: AB + C * DE FG + ^

Important Data Structures Interview Programs

Here are some important programs based on the concepts of data structures which are important data structures interview questions for freshers.

17)Sorting a stack using a temporary stack

18)Program to reverse a queue

19) Program to reverse first k elements of a queue

20)Program to return the nth node from the end in a linked list

21)Reverse a linked list

22)Replace each element of the array by its rank in the array

23) Check if a given graph is a tree or not

24) Find out the Kth smallest element in an unsorted array

25) How to find the shortest path between two vertices

Practice more Data Structure questions

Introduction to Arrays | Types of Arrays and their Representation

by | Feb 19, 2022 | Data Structures, Technical

An Array is a Linear data structure which is a collection of data items having similar data types stored in contiguous memory locations. By knowing the address of the first item we can easily access all items/elements of an array.

Arrays and its representation is given below

• Array Index: The location of an element in an array has an index, which identifies the element. Array index starts from 0.
• Array element: Items stored in an array is called an element. The elements can be accessed via its index.
• Array Length: The length of an array is defined based on the number of elements an array can store. In the above example, array length is 6 which means that it can store 6 elements.

When an array of size and type is declared, the compiler allocates enough memory to hold all elements of data.

For example, an array IM [10] will have 10 elements with index starting from 0 to 9 and the memory allocated contiguously will be 20 bytes. The compiler knows the address of the first byte of the array only. Also, the address of the first byte is considered as the memory address for the whole array.

Normal variables (a1, a2, a3, ….) can be used when we have a small number of elements, but if we want to store a large number of elements, it becomes difficult to manage them with normal variables. Representing many elements with one variable name is the basic idea of arrays.

Why does Array Indexing start with 0?

Let’s try to understand this by taking one example. Assume, we can declare an array of size 10 in the following way.

int a[10];

Here a itself is a pointer which contains the memory location of the first element of the array. Now for accessing the first element, we will write a[0] which is internally decoded by the compiler as *(a + 0).

In the same way, the second element can be accessed by a[1] or *(a + 1). As a contains the address of the first element so for accessing the second element we have to add 1 to it. That’s why here we have written *(a +1). In an array, the index describes the offset from the first element, i.e. the distance from the first element.

Now let’s assume that array indexing starts at 1 instead of 0. In this case for accessing the first element, we have to write a[1] which is internally decoded as *(a + 1 – 1).

Observe here that we have to perform one extra operation i.e. subtraction by 1. This extra operation will greatly decrease the performance when the program is big. That’s why to avoid this extra operation and improve the performance, array indexing starts at 0 and not at 1.

Array Operation

Now that we know the basic idea behind an array, let us now look at the various operations that can be performed on arrays.

• Traverse − Print all the elements in the array one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element in the array using the given index or the value.
• Update − Updates an element at the given index.

Types of Arrays

The various types of arrays are as follows.

• One dimensional array
• Multi-dimensional array

One-Dimensional Array

A one-dimensional array is also called a single dimensional array where the elements will be accessed in sequential order. This type of array will be accessed by the subscript of either a column or row index.

Multi-Dimensional Array

When the number of dimensions specified is more than one, then it is called as a multi-dimensional array. Multidimensional arrays include 2D arrays and 3D arrays.

A two-dimensional array will be accessed by using the subscript of row and column index. For traversing the two-dimensional array, the value of the rows and columns will be considered. In the two-dimensional array IM [3] [4], the first index specifies the number of rows and the second index specifies the number of columns and the array can hold 12 elements (3 * 4).

Similarly, in a three-dimensional array, there will be three dimensions. The array IM [5] [10] [15] can hold 750 elements (5 * 10 * 15).

Declaration/Initialization of Arrays

// A sample program for Array Declaration
#include <stdio.h>
int main()
{
int one_dim [10];    # declaration of 1D array
int two_dim [2][2];  #declaration of 2D array
int three_dim [2][3][4] = { 
                     { {3, 4, 2, 3}, {0, -3, 9, 11}, {23, 12, 23, 2} },
                     { {13, 4, 56, 3}, {5, 9, 3, 5}, {3, 1, 4, 9} }
                 }; #declaration of 3D array. Here the elements are also defined.return 0;
}