Mastering data structure interview questions can help you crack placements of most companies such as Infosys, Amazon TCS, Wipro, Accenture, etc. Data Structures and Algorithms are the most important topics asked in the recruitment process.

So let’s get started with the **40** **most important interview questions on Data Structures.**

Write algorithms of preorder, post-order and in-order traversal in trees.

What is the minimum number of queues required for priority queue implementation

What is the maximum number of spanning tree a graph can have?

Mobiprep handbooks are **free downloadable placement preparation resources** that can help you ace any company placement process. We have curated a list of the 40 most important MCQ questions with detailed explanations to ensure the best placement preparation.

These top Data-Structures Interview questions have been segmented into three sections:

__Basic Data Structures Interview Questions____
__

**Question 1. What are the advantages of Linked Lists over array?**

In Linked Lists insertion/deletion is faster than array.

Linked Lists have dynamic size where arrays have fixed size.

Memory utilisation and allocation is efficient in Linked Lists.

**Question 2. List some applications of stack.**

Compilers use stacks to evaluate expressions.

Reversing a string.

Simulating recursion

Syntax parsing

Calling subroutine

**Question 3. Write a syntax in C to create a node in Doubly Linked List.**

```
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
```

**Question 4. Write algorithms of preorder, post-order and in-order traversal in trees.**

PREORDER:

Visit the root

Traverse the left sub-tree

Traverse the right sub-tree

POSTORDER:

Traverse the left sub-tree

Traverse the right sub-tree

Visit the root

INORDER:

Traverse the left sub-tree

Visit the root

Traverse the right sub-tree

**Question 5. Why stack is ideal for recursion operation.**

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.

**Question 6. Write a program to reverse a queue using stack. **

```
void reverse_queue()
{
while(!(front == rear))
{
stack.push(dequeue());
}
stack.push(dequeue());
printf("\nREVERSED QUEUE : ");
while(!stack.empty())
{
printf("%d ",stack.top());
stack.pop();
}
printf("\n");
exit(0);
}
```

**Question 7. What is the minimum number of queues required for priority queue implementation?**

Minimum number of queues required for priority queue implementation is two. One for storing actual data and one for storing priorities.

**Question 8. What is priority queue?**

** **A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

Applications of priority queue:

Prim's algorithm implementation can be done using priority queues.

Dijkstra's shortest path algorithm implementation can be done using priority queues.

A* Search algorithm implementation can be done using priority queues.

Priority queues are used to sort heaps.

Priority queues are used in operating system for load balancing and interrupt handling.

Priority queues are used in Huffman codes for data compression.

In traffic light, depending upon the traffic, the colours will be given priority.

**Question 9. What is the maximum number of spanning tree a graph can have?**

The maximum number of spanning trees that a graph can have depended on how connected the graph is. A complete undirected graph with n number of nodes can have a maximum of n^n-2 number of spanning trees.

Spanning tree has n-1 edges, where n is the number of nodes (vertices).

From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

A complete graph can have maximum n^n-2 number of spanning trees.

**Question 10. Which is the best data structure to check whether an arithmetic expression has balanced parenthesis. Explain.**

Stacks can check equal pair/ balanced pair of parenthesis efficiently. Whenever we get an opening parenthesis we can push it on the stack and when we get the corresponding closing parenthesis, we can pop it.

After performing all push and pop operations, if at the end of the expression stack becomes empty then the expression has a balanced parenthesis.

**Question 11. List some data structure that use pointers.**

Binary trees

Linked lists

Queues

Stacks

**Question 12. How will you delete a node from a linkedlist when a key is given?**

### When a key is given then the following steps can be used:

Find previous node of the node to be deleted.

Change the next of previous node.

Free memory for the node to be deleted.

The time complexity of deleting a node is O(n)

**Question 13. What is the difference between array and array list?**

ArrayList is not static but dynamic in size. As elements added to an ArrayList, its capacity or size grows automatically. The array is static with a fixed size which cannot be changed once declared.

**Question 14. What is a binary tree? What are its applications?**

A binary tree is a form of data structure. It has two nodes, namely the left node and the right node.

Applications of binary trees are:

workflow for compositing digital images for visual effects.

Router algorithms

Form of a multi-stage decision-making (see business chess).

Manipulate hierarchical data.

Make information easy to search (see tree traversal).

Manipulate sorted lists of data.

**Question 15. How do you implement a graph?**

We can implement a graph by using adjacency matrix and adjacency lists.

Adjacency matrix: Used for sequential data representation

Adjacency list: Used to represent linked data

__Intermediate Data Structures Interview Questions__

**Question 16. What is the functionality of the function A regarding circular linkedlist?**

```
public int A()
{
if(head == null)
return Integer.MIN_VALUE;
int var;
Node temp = head;
while(temp.getNext() != head)
temp = temp.getNext();
if(temp == head)
{
var = head.getItem();
head = null;
return var;
}
temp.setNext(head.getNext());
var = head.getItem();
head = head.getNext();
return var;
}
```

First traverse through the list to find the end node, then manipulate the ‘next’ pointer such that it points to the current head’s next node, return the data stored in head and make this next node as the head.

**Question 17. Why is it not feasible to implement a queue using array?**

The queue has to be constantly extended to make way for more elements that get implemented. Always extending the size of the array will not be feasible as there will be a discrepancy in the creation of the correct array size.

**Question 18. What do you mean by stack overflow?**

Stack overflow happens when top = MaxSize – 1

Stack overflow is the term given when the stack is full and an element cannot be inserted into the stack anymore

**Question 19. List some applications of tree data structures.**

Arithmetic expression handling

Symbol table creation

Lexical analysis

Hierarchical data modeling

**Question 20. What is an AVL tree?**

AVL tree is a binary search tree in which the difference of heights in left sub tree and right sub tree is not more than 1. This difference is called the Balance Factor.

BalanceFactor = height(left-sutree) − height(right-sutree)

**Question 21. Name some rotation technique that are used to balance AVL tree.**

Left rotation

Right rotation

Left-Right rotation

Right-Left rotation

**Question 22. What do you mean by a hash table? What is hashing?**

Hash table is a data structure which stores data in a key value pair. In a hash table, data is stored in an array format, where each data value has its own unique index value.

Hashing is a technique to convert a range of key values into a range of indexes of an array.

**Question 23. Explain DFS.**

DFS is an algorithm to traverse graphs and trees. It traverses a graph in a depth-ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Steps:

Step 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

Step 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)

Step 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

**Question 24. What is BFS?**

BFS is an algorithm that traverses a graph in a breadthward motion. It uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Steps:

Step 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

Step 2 − If no adjacent vertex is found, remove the first vertex from the queue.

Step 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

**Question 25. What are the operations can be performed on stacks and queues?**

**
**Stacks:

push() − adds an item to stack

pop() − removes the top stack item

peek() − gives value of top item without removing it

isempty() − checks if stack is empty

isfull() − checks if stack is full

Queues:

enqueue() − add (store) an item to the queue.

dequeue() − remove (access) an item from the queue.

peek() − Gets the element at the front of the queue without removing it.

isfull() − Checks if the queue is full.

isempty() − Checks if the queue is empty.

## Advanced Data Structures Interview Questions

**Question 26. How will you detect a loop in a linkedlist?**

Use two pointer method.

Traverse the linked list using two pointers. Move one pointer by one and another pointer by two. If the pointers meet at same node then there is a loop.

**Question 27. Write the algorithm for level order traversal of a binary tree.**

printLevelorder(tree)

Create an empty queue q

temp_node = root

Loop while temp_node is not NULL

print temp_node->data.

Enqueue temp_node’s children (first left then right children) to q

Dequeue a node from q and assign it’s value to temp_node

**Question 28. What is the minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers?**

The First occurrence of an element can be found out in O(log(n)) time using divide and conquer technique, lets say it is i.

The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique, lets say it is j.

Now number of occurrence of that element(count) is (j-i+1). Overall time complexity = log n +log n +1 = O(logn).

**Question 29. Write code to add all the nodes in a binary tree.**

```
static int ADD(Node root)
{
if (root == null)
return 0;
return (root.key + addBT(root.left) +
addBT(root.right));
}
```

**Question 30. What are the common operations that can be performed on a data structure.**

Insertion − adding a data item

Deletion − removing a data item

Traversal − accessing and/or printing all data items

Searching − finding a particular data item

Sorting − arranging data items in a pre-defined sequence

**Question 31. What is a minimum spanning tree?**

In a weighted graph, a minimum spanning tree is a spanning tree that has a minimum weight that all other spanning trees of the same graph.

Refer adjacent cells for example.

**Question 32. Write C code to show delete function in queue.**

```
void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
```

**Question 33. Write C code to implement enque and dequeue operation in Queue.**

```
void enqueue()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1) /*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
```

**Question 34. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices?**

In an undirected graph, there can be maximum n(n-1)/2 edges.

We can choose to have (or not have) any of the n(n-1)/2 edges. So, total number of undirected graphs with n vertices is 2^(n(n-1)/2).

**Question 35. Write a C function to reverse a list.**

```
void reverse_list()
{
// Initialize current, previous and next pointers
Node *current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL)
{
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead
prev = current;
current = next;
}
head = prev;
}
```

**Question 36. Write a C function to find the shortest path in a graph.**

```
int shortest_path(vector <int> edges[], int u, int v, int n)
{
vector<bool> visited(n, 0);
vector<int> distance(n, 0);
queue <int> queue1;
distance[u] = 0;
queue1.push(u);
visited[u] = true;
while (!queue1.empty())
{
int x = queue1.front();
queue1.pop();
for (int i=0; i<edges[x].size(); i++)
{
if (visited[edges[x][i]])
continue;
distance[edges[x][i]] = distance[x] + 1;
queue1.push(edges[x][i]);
visited[edges[x][i]] = 1;
}
}
return distance[v];
}
```

**Question 37. Write algorithm for searching in a binary tree.**

if tree is empty, end search

If tree is not empty, then check the root element.

if key== root element , return true.

else check if the key is smaller than the root value

if smaller then check left sub tree

check right sub tree.

**Question 38. Write the difference between linear and non-linear data-structure.**

A data structure is a linear data structure if its elements are arranged linearly or elements are adjacent to each other eg. Array.

a non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements. Examples of nonlinear data structure include trees and graphs.

These Data Structure interview questions would give you an insight into what kind of questions could be asked.

Free Practice Tests

__Logical Reasoning Practice Tests____Aptitude Practice Tests____C++ Practice Tests__

Most Important Interview Questions