Top Data Structure Interview Questions & Answers

Updated: Jun 3

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.

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

  2. List some applications of stack.

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

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

  5. Why stack is ideal for recursion operation.

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

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

  8. What is priority queue?

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

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

 

Top Data Structures Interview Questions PDF

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.

Top 40 Data Structures Interview Questions and Answers
.pdf
Download PDF • 323KB




 

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:

  1. Find previous node of the node to be deleted.

  2. Change the next of previous node.

  3. 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)

  1. Create an empty queue q

  2. temp_node = root

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

  1. if tree is empty, end search

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

  3. if key== root element , return true.

  4. else check if the key is smaller than the root value

  5. if smaller then check left sub tree

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

 

#DS #algorithm

58 views0 comments

Recent Posts

See All