.png)
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.
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
Most Important Interview Questions
Last Minute Class Notes
Comments