Data Structure Interview Questions and Answers

Most Asked Data Structure Interview Questions & Answers

Data Structure Interview Question and Answers are given on this page for technical interview preparation. You can practice most asked Data Structure questions 2021-22 for freshers. We have covered topics like Stack, Queues, AVL Trees etc. 

Page Highlights:

  • What is Data Structure?
  • Top 40 Data Structure Interview Questions
  • Technical Interview Questions
Data Structures Interview Questions & Answers
  1. Which data structure is used to perform recursion?
  2. Write the stack conditions.
  3. Briefly explain the approaches to develop algorithms?
  4. What is a linked list?
  5. What is a postfix expression?
  6. What is the difference between PUSH and POP?
  7. What is binary search?
  8. How do you reference all the elements in a one-dimension array?
  9. What is a queue? How is it different from a stack?
  10. How does quicksort works?
  11. How does dynamic memory allocation help in managing data?
  12. What is Data abstraction?
  13. How will you insert a new item in a binary search tree?
  14. What do you understand by an AVL tree?
  15. Please explain the Linked List and its various types.
  16. What is data structure?
  17. When is a binary search best applied?
  18. What is bubble sort and how bubble sort works?
  19. Which data structures are applied when dealing with a recursive function?
  20. What is LIFO?
  21. What is FIFO?
  22. Differentiate NULL and VOID
  23. What is the advantage of the heap over a stack?
  24. How do signed and unsigned numbers affect memory?
  25. What is a Stack?
  26. State the properties of B Tree?
  27. Write a recursive C function to calculate the height of a binary tree.
  28. Write the recursive C function to count the number of nodes present in a binary tree.
  29. What is the minimum number of queues that can be used to implement a priority queue?
  30. If you are using C language to implement the heterogeneous linked list, what pointer type should be used?
  31. List some applications of queue data structure.
  32. Can we apply a Binary search algorithm to a sorted Linked list?
  33. When can you tell that a Memory Leak will occur?
  34.  What are the differences between the B tree and the B+ tree?
  35. What are the advantages of Selection Sort?
  36. What is a doubly-linked list?
  37. Are linked lists considered linear or non-linear data structures?
  38. Which notations are used in the Evaluation of Arithmetic Expressions using prefix and postfix forms?
  39.  How to reference all the elements in a one-dimension array?
  40. In what areas do data structures are applied?

What is 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.

Applications of DSA:-

  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.

Top 40 Data Structure Interview Questions and Answers

Which data structure is used to perform recursion?

Ans. Stack is used in recursion because of its Last In First Out(LIFO) nature. Operating System maintains a stack in order to store the values of each iteration.

Write the stack conditions.

Ans. Overflow Condition : top = MaxSize – 1
         Underflow Condition : top = MinSize – 1

Briefly explain the approaches to develop algorithms?

Ans. There are three major approaches to develop algorithms −

  • Greedy Approach − creating a solution by choosing the next best possible option
  • Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently.
  • Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combinedly.

What is a linked list?

Ans. A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. This forms a chain-like link for data storage.

What is a postfix expression?

Ans. An expression in which operators follow the operands is known as postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.The expression “a + b” will be represented as “ab+” in postfix notation.

What is the difference between PUSH and POP?

Ans. PUSH and POP are storage and retrieval operations for data in the stack.

  • PUSH: specifies that data is “inserted” into the stack.
  • POP: specifies data retrieval. It means that data is being removed from the stack.

What is binary search?

Ans:- Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you’ve narrowed down the possible locations to just one. This search first compares the target value to the mid of the list. If it is not found, then it decides on whether.

How do you reference all the elements in a one-dimension array?

Ans:- We can reference all the elements in a one-dimension array using an indexed loop. The counter runs from 0 to the maximum array size, say n, minus one. All elements of the one-dimension array are referenced in sequence by using the loop counter as the array subscript.

What is a queue? How is it different from a stack?

Ans:- A queue is another common data structure that places elements in a sequence, similar to a stack. A queue uses the FIFO method (First In First Out), by which the first element that is enqueued will be the first one to be dequeued.In a stack, the item that is most recently added is removed first. Contrary to this, the item least recently added is removed first in case of a queue.

How does quicksort works?

Ans:- Quick Sort is a sorting algorithm, which is commonly used in computer science. Quicksort is a divide and conquer algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub-arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array. Quicksort uses the divide and conquer approach. It divides the list into smaller partitions using ‘pivot’. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quicksort.

How does dynamic memory allocation help in managing data?

Ans:- Aside from being able to store simple structured data types, dynamic memory allocation can combine separately allocated structured blocks to form composite structures that expand and contract as needed.

What is Data abstraction?

Ans:- Data abstraction is the reduction of a particular body of data to a simplified representation of the whole. Data abstraction is a powerful tool for breaking down complex data problems into manageable chunks. Abstraction, in general, is the process of taking away or removing characteristics from something to reduce them to a set of essential characteristics. As in abstract art, the representation is likely to be one potential abstraction of several possibilities. This is applied by initially specifying the data objects involved and the operations to be performed on these data objects without being overly concerned with how the data objects will be represented and stored in memory.

How will you insert a new item in a binary search tree?

Ans:- As binary search tree doesn’t allow for duplicates, the new item to be inserted must be unique. Assuming it is, we will proceed with checking whether the tree is empty or not. If it is empty, then the new item will be inserted in the root node.

What do you understand by an AVL tree?

Ans:- AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. The measure of the balance is given by the difference of the heights of the subtrees from the root node of the AVL tree.

Explain the Linked List and its various types.

Ans:- Linked lists are of many different types. They are as follows:

  • Singly Linked List – Every node stores the address or reference of the next node in the linked list, leaving for the last node that stores NULL.
  • Doubly Linked List – Every node keeps two references. One point to the next node and the other points to the previous node.
  • Circular Linked List – In this type of linked list, all nodes are connected to form a circle. Hence, there is no NULL at the end. A circular linked list can either be a singly circular linked list or a double circular linked list.

What is data structure?

Ans:- A data structure is a named location that can be used to store and organize data. And, an algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allow us to write efficient and optimized computer programs. For example, we can store a list of items having the same data type using the array data structure.

When is binary search best applied?

Ans:- A binary search is an algorithm that is best applied to search a list when the elements are already in order or sorted. The list is searched starting in the middle, such that if that middle value is not the target search key, it will check to see if it will continue the search on the lower half of the list or the higher half. The split and search will then continue in the same manner.

What is bubble sort and how bubble sort works?

Ans:- Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. Bubble sort is a comparison-based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. It is not suitable for a large set of data because the time complexity is Ο(n²).

Which data structures are applied when dealing with a recursive function?

Ans:- Recursion, is a function that calls itself based on a terminating condition, makes use of the stack. Because of its LIFO (Last In First Out) property, it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of the system stack for storing the return addresses of the function calls.

What is LIFO?

Ans:- LIFO is a short form of Last In First Out. It refers to how data is accessed, stored, and retrieved. A data type that uses LIFO has data that was stored last should be the one to be extracted first. Thus all the other data that was stored before this first data must first be retrieved and extracted.

What is FIFO?

Ans:- FIFO means First-in First-out and is a way that defines how the data within the data structure will be accessed. Mainly followed in QUEUE. Data has been inserted into the queue list the longest is the one that is removed first.

Differentiate NULL and VOID.

Ans:- Null means nothing for data types. Void means function returned type have to be nothing. you also can not return null from a void function. A variable that is given a Null value simply indicates an empty value.

What is the advantage of the heap over a stack?

Ans:- Heap is more flexible than stack because memory space for the heap can be dynamically allocated and de-allocated as per the requirements.

How do signed and unsigned numbers affect memory?

Ans:-In the case of signed numbers, the first bit is used to indicate whether positive or negative, which leaves you one bit short. With unsigned numbers, you have all bits available for that number. The effect is best seen in the number range (an unsigned 8-bit number has a range 0-255, while the 8-bit signed number has a range -128 to +127).

What is a Stack?

Ans. Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). The Stack is a list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having a pointer to its top element. Last-In-First-Out (LIFO) means the element which is inserted first will be deleted last from the stack.

State the properties of B Tree?

Ans. B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.

  • In a B-Tree, each node has a maximum of m children.
  • Except for the root and leaf nodes, every node in a B-Tree has at least m/2 children.
  • There must be at least two root nodes.
  • The level of all leaf nodes must be the same.

Write a recursive C function to calculate the height of a binary tree.

Ans.

int countHeight(struct node* t){  
    int l,r;  
    if(!t)  
        return 0;  
    if((!(t->left)) && (!(t->right)))  
        return 0;  
    l=countHeight(t->left);  
    r=countHeight(t->right);  
    return (1+((l>r)?l:r));  
}  

Write the recursive C function to count the number of nodes present in a binary tree.

Ans.

int count (struct node* t){  
    if(t){  
        int l, r;  
        l = count(t->left);  
        r=count(t->right);  
        return (1+l+r);  
    }  
    else{  
        return 0;  
    }  
} 

What is the minimum number of queues that can be used to implement a priority queue?

Ans:- It is enough to create two queues. The data elements are stored in one queue, while the priorities are stored in another.

If you are using C language to implement the heterogeneous linked list, what pointer type should be used?

Ans:- Since the heterogeneous linked list includes various data types, ordinary pointers cannot be used. You must use a generic pointer type like a void pointer for this purpose, as the void pointer may store a pointer to any type.

List some applications of queue data structure.

Ans:- The following are some examples of queue applications.Queues are often used to create waiting lists for a single shared resource, such as a printer, disc, or CPU.

  • Pipes, file IO, and sockets all use queues for asynchronous data transfer (where data is not transmitted at the same rate between two processes).
  • Many applications, such as MP3 media players and CD players, use queues as buffers.
  • Queues are used in media players to keep track of the playlist and add and delete songs from it.
  • In operating systems, queues are used to handle interruptions.

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

Ans:- No, we can’t use the binary search algorithm on a sorted linked list because it’s difficult to find the index of the middle variable.

When can you tell that a Memory Leak will occur?

Ans:- A memory leak occurs when a program fails to free a dynamically allocated block of memory.

What are the differences between the B tree and the B+ tree?

Ans:- B Tree:

  • Search keys can’t be saved more than once.
  • Data can be stored in both internal and leaf nodes.
  • Since data can be found on both internal and leaf nodes, searching for certain information takes longer.
  • Internal node deletion is extremely difficult and time-consuming.
  • It is not possible to link leaf nodes.
 B+ Tree:
  • It’s possible to have multiple search keys.
  • The leaf nodes are the only places where data can be saved.
  • Since data can only be found on the leaf nodes, searching is comparatively faster.
  • Since elements are always removed from the leaf nodes, deletion will never be a complicated method.
  • To make search operations more effective, leaf nodes are linked together.

What are the advantages of Selection Sort?

Ans:- Advantages:

  • It is quick and straightforward to enforce.
  • It’s suitable for small data sets.
  • It’s 60% more effective than bubble sorting.

What is a doubly-linked list?

Ans:- A doubly linked list is a more complicated form of a linked list in which each node has a pointer to both the previous and next node in the chain. A node in a doubly-linked list is made up of three parts:

  • node data.
  • pointer to the next node in sequence (next pointer).
  • pointer to the previous node (previous pointer).

Are linked lists considered linear or non-linear data structures?

Ans:- Depending on the case, a connected list may be called both a linear and non-linear data structure.

  • It is classified as a non-linear data structure based on data storage.
  • It is classified as a linear data structure based on the access strategy.

Which notations are used in the Evaluation of Arithmetic Expressions using prefix and postfix forms?

Ans:- Polish and Reverse Polish notations.

How to reference all the elements in a one-dimension array?

Ans:- It is possible to accomplish this using an indexed loop with a counter that runs from 0 to the array size minus one. By using the loop counter as the array subscript, you can refer to all of the elements in order.

In what areas do data structures are applied?

Ans:- Data structures are needed in almost every situation involving data. Algorithms involving efficient data structures are used in a variety of fields, including numerical analysis, operating systems, artificial intelligence, compiler design, database management, graphics, and statistical analysis, to name a few.

Also Check:

FAQs on Data Structures Interview Questions

State some examples for sorting.

Ans. Bubble sort, Insertion sort, Merge sort, Quick sort, Radix sort, Heap sort.

Name some types of searching.

Ans. Linear Search, Binary Search