45+ Data Structures Interview Questions and Answers
Wondering what you need to know when preparing for the data structure interview? Read this guide to learn all about data structure interview questions
Data structures are ways to organize the data to make it easily readable and usable. It can be any management, organization, and storage format of data allowing efficient access and modification. Among these are data values, relationships among them, and the various functions or operations applied to the data.
Data structures are a fundamental concept of programming which plays a crucial role in algorithm design. No matter what the programming language, every programmer needs to know the basics of data structures. It is not unusual for interviewers to ask questions about data structures in programming language interviews. You can find below the top data structure interview questions and answers accompanied by their respective explanations.
Learn data structure and algorithms with the best data structure tutorials and advance your software engineering or data science career.
Data Structure Interview Questions and Answers
1. What is a Data Structure?
Answer: A data structure organizes the data in a way that makes the data useable. Different data structures are suitable for different application types, and a number of them are highly specialized for specific tasks. For instance, B-trees are well-suited for implementing databases, while compiler implementations usually use hash tables to locate identifiers.
2. List the area of applications of Data Structure.
Answer: In computer science, data structures feature prominently in the following areas:
- Artificial Intelligence
- Compiler Design
- Database Management System
- Graphics
- Operating System
- Numerical Analysis
- Simulation
- Statistical analysis package
3. Describe the types of Data Structures?
Answer: There are two types of data structures:
Linear Data Structure: Data Structures with sequential elements are called Linear data structures. The elements of linear data structures are stored in a nonhierarchical manner, where each item has a predecessor and successor except the first and last element. Example: Array. Linked List, Queues, and Stacks.
Non-Linear Data Structure: The Non-Linear data structure does not follow a sequence, i.e. each item is connected to two or more other items in a non-linear manner. There is no sequential arrangement of the data elements. Example: Graph and Trees.
4. How does a linear data structure differ from a non-linear data structure?
Answer: A linear data structure is one in which the elements form a linear list or sequence. Non-linear data structures, on the other hand, traverse nodes in a non-linear way.
Linear data structures include arrays, linked lists, queues, and stacks, whereas Non-linear data structures include graphs and trees.
5. Explain the difference between file structure and storage structure?
Answer:
File Structure: The data on a hard drive or external device (such as a USB drive) remains intact until it is deleted manually. A file structure is a representation of data into secondary or auxiliary memory.
Storage Structure: This structure allows users to store data (variables, constants, etc.) in the main memory. This data is stored in RAM and is deleted once the function that uses it is completed.
6. What are the various applications of Data Structures?
Answer: The purpose of using data structures is to organize data and make it more easily accessed. The following are some practical applications of data structures:
- Storing data in a tabular format. A person's contact information, for example. Arrays allow us to accomplish this.
- Image processing and speech processing use arrays extensively.
- Music players and image sliders use Linked Lists to move between items.
- Stack is used most often in undo operations, where the last item appears first.
- A queue is used for scheduling jobs, arranging data packets for communication.
- Machine learning algorithms like Decision Tree use tree structures to make decisions.
- Hashing algorithms play a significant role in technologies such as Blockchain and cryptography.
- As a means of representing data and plotting graphs, matrices often come in handy.
7. Could you explain how to reference all the elements in a one-dimension array?
Answer: In an indexed loop, we can refer to all the elements in a one-dimensional array. The counter runs from 0 to the maximum array size, for example, n, minus one. In the one-dimensional array, the loop counter serves as the array subscript, and the elements of the one-dimensional array appear in sequence.
8. What is a queue? How is it different from a stack?
Answer: Queues are linear structures in which elements are accessed based on the FIFO principle (First in First out). Queue operations include dequeue, enqueue, front, and rear. You can implement a queue using arrays and linked lists, just as on a stack.
In a stack, the most recently added item is removed first. Contrary to this, if a queue exists, the item least recently added is removed first.
9. Can you tell which data structures are used for BFS and DFS of a graph?
Answer: A graph's BFS (Breadth-First Search) uses a queue. Even though the DFS (Depth First Search) of a graph uses a stack, it can also be achieved using recursion by utilizing function call stacks.
10. Explain the postfix expression.
Answer: In a postfix expression, the operator appears after the operands. Here are a few examples:
B++ (i.e. B+B)
AB+ (i.e. A+B)
ABC+ (i.e. A+BC)
ABCD+ (i.e. AB + CD)
11. Please explain Stack and also mention some of its most notable applications.
Answer: Stack is a linear data structure that follows either FILO (First In Last Out) or LIFO (Last In First Out) method to access elements. Peek, push, and pop are the most basic operations of a stack.
Among the notable applications of a stack are:
- Check the balance of parentheses in an expression
- Postfix expression evaluation
- Implement two stacks in an array
- Converting infix to postfix
- String reversal
12. Please explain what do you understand by FIFO and LIFO?
Answer: There are two ways of accessing, storing, and retrieving elements in a data structure, FIFO and LIFO. The term LIFO means Last In First Out. In this approach, recent data is extracted first.
Meanwhile, FIFO stands for First In First Out. As a result, the most recent information is extracted first.
13. What do you understand by a binary search? What is the best scenario for using it?
Answer: An algorithm that starts by searching in the middle element is called a binary search. If the middle element is not the target element, the search continues on the lower half of the higher half. Until the target element is found, the process continues.
As for the best scenario to use it, Binary searches work best on lists where the elements are sorted or ordered.
14. What is a Linked List Data structure
Answer: Elements are stored linearly in a Linked List, but the physical placements do not indicate the order in the memory; instead, each element points to the next node. Last but not least, a terminator marks the end of the list. There are several types of linked lists, including single, double, circular, and multiple.
15. What is the difference between NULL and VOID?
Answer: NULL is a value, whereas VOID is a data type identifier. NULL represents an empty value in a variable. VOIDs are used to identify pointers with no initial size.
16. Write the syntax in C to create a node in the singly linked list.
Answer:
newNode = Node(data); //creates a new node.
17. Could you explain how does variable declaration affects memory allocation?
Answer: In the case of a variable declaration, the amount of memory allocated or reserved depends on the data type. For example, if one declares an integer, there is a 4-byte reserve, while one puts forward a double, there is an 8-byte reserve.
18. Please explain the concept of data abstraction.
Answer: Data Abstraction helps break down complex problems into smaller, easier-to-manage components. This process begins by specifying the various data objects involved and the various operations to be performed on them without stressing too much about the storage of data.
19. If you are using C language to implement the heterogeneous linked list, what type of pointer should you use?
Answer: You can use void pointers. Another option is to use unsigned char pointers. In this way, we can store any data type in the list. As an example,
struct a{
struct a *next;
s_ize d_size;
}
20. Write the pseudocode to perform in-order traversal on a binary tree.
Answer: In-order traversal is a depth-first traversal. Recursive traversal of a binary tree occurs by the method. Here is the code:
struct btnode
{
struct btnode *left;
struct btnode *right;
}
*root = NULL, *temp = NULL;
void inorder(struct btnode *temp)
{
if (root == NULL)
{
printf("Root is empty");
return;
}
if (temp->left != NULL)
inorder(temp->left);
if (temp->right != NULL)
inorder(t->right);
}
21. How does a POP operation differ from a PUSH operation?
Answer: POP and PUSH both refer to a stack. PUSH operation adds data to the stack, whereas POP operation retrieves it.
22. How will you insert a new item in a binary search tree?
Answer: Since a binary search tree does not allow duplicates, the new item must be unique. Let's assume it is, and check whether or not the tree is empty. The new item will be inserted into the root node if it is empty.
On the other hand, if the tree contains no empty items, we will use the key of the new item. Whenever it is smaller than the root item's key, the new item will be added to the left subtree. If the new item's key is larger than the root item's key, then the new item is added to the right subtree.
23. Do you know how does dynamic memory allocation help in managing data?
Answer: Dynamic memory allocation enables simple structured data types to be stored. Additionally, it can combine separately allocated blocks into composite structures that can contract and expand as required.
24. Could you explain how does the selection sort work on an array?
Answer: We start with the smallest element in the selection sort. The element at subscript 0 is switched with it. As a next step, the smallest element of the remaining subarray is located and replaced with the element in subscript 1.
Until the largest element appears at the subscript n-1, the aforementioned process is repeated.
25. List the data structures which are used in RDBMS, Network Data Modal, and Hierarchical Data Model.
Answer:
- RDBMS uses an Array data structure.
- The network data model uses Graph.
- The hierarchal data model uses Tree.
26. Which data structure is used to perform recursion?
Answer: Due to its last in first out nature, the stack data structure is used in recursion. At each function call, the operating system maintains the stack to store the iteration variables
27. How to check if a given Binary Tree is BST or not?
Answer: The binary tree is BST if the inorder traversal of the binary tree is sorted. The idea is to perform an in-order traversal while keeping track of previous key values as we traverse. If the current key value is greater, then continue, otherwise return false
28. Are linked lists considered linear or non-linear data structures?
Answer: According to the situation, a linked list can be either linear or non-linear.
- In terms of data storage, it is considered a non-linear data structure.
- Based on its access strategy, it is considered a linear data structure.
29. Which Data Structure Should be used for implementing LRU cache
Answer: An LRU cache is implemented using two data structures:
- A doubly-linked list is used to implement the queue. There will be a maximum queue size equal to the number of frames (cache size) available. In the rear end are the most recently used pages, while the front end has the least recently used pages.
- Hash with page number as key and queue node address as value.
30. How are the elements of a 2D array are stored in the memory?
Answer: The elements of a 2D array can be stored in memory using two different techniques.
Row-Major Order: During row-major ordering, all the rows of the 2D array are stored in the memory concurrently. The first row of the array is stored completely into the memory, then the second row, and so on until the last row.
Column- Major Order: Column-major ordering stores all the columns of a 2D array continuously in memory. The first column of the array is stored in the memory completely, then the second row, and so on until the last column.
31. What are the advantages of a Linked List over an array?
Answer: Here are the advantages of a Linked List over an array:
- A linked list can have its size increased at runtime, which is not possible with an array.
- Lists are not required to be contiguous in the main memory; if contiguous space is not available, the nodes can be stored anywhere in the memory linked by the links.
- In the main memory, lists are dynamically stored and grow in response to program requests, while arrays are statically stored and whose size must be declared at compile time.
- In a linked list, the number of elements is limited by the available memory space, whereas in an array, the number of elements is limited by the size of the array.
32. If you are using C language to implement the heterogeneous linked list, what pointer type should be used?
Answer: Because heterogeneous linked lists contain different data types, ordinary pointers cannot be used. To accomplish this, you need to use a generic pointer type like a void pointer, which is capable of storing a pointer to any type.
33. What is a doubly-linked list?
Answer: The doubly linked list is a type of linked list in which each node contains a pointer to both the previous and next node in the sequence. 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).
34. What are the drawbacks of array implementation of Queue?
Answer: The drawbacks of array implementation of Queue are:
Memory Wastage: Array space, which is used to store queue elements, cannot be reused to store queue elements since elements can only be inserted at the front end and the value of the front may be so high that all the space before that cannot be filled.
Array Size: When using an array to implement a queue, we may have situations where we need to expand the queue to add more elements, and it will almost be impossible to do so; hence, choosing the right array size is always a challenge when using arrays to implement queues.
35. What is a dequeue?
Answer: Dequeue (also known as a double-ended queue) is an ordered set of elements, in which insertion and deletion are possible at both ends, i.e. at the front and rear.
36. Define the tree data structure.
Answer: The Tree is a recursive data structure that consists of one or more nodes, where one node is the root and the remaining nodes are called the children of the root. Besides the root node, the nodes other than that are given nonempty sets, where each is classified as a sub-tree.
37. Write the C code to perform in-order traversal on a binary tree.
Answer:
void in-order(struct treenode *tree)
{
if(tree != NULL)
{
in-order(tree→ left);
printf("%d",tree→ root);
in-order(tree→ right);
}
}
38. List the types of trees.
Answer: Following are six types of trees:
- Binary Tree
- Binary Search Tree
- Expression Tree
- Forests
- General Tree
- Tournament Tree
39. Which data structure suits the most in the tree construction?
Answer: The answer is Queue Data Structure.
40. Write the syntax in C to create a node in the singly linked list.
Answer:
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
41. List some applications of Tree-data structure?
Answer: Here are some applications of Tree- data structure:
- Syntax analysis
- Hierarchal data model
- Symbol Table construction
- The manipulation of Arithmetic expression
42. How can AVL Tree be useful in all the operations as compared to Binary search tree?
Answer: The AVL tree controls the height of the binary search tree by ensuring that it is not skewed. All operations in a binary search tree of height h take O(h) time. Nevertheless, if the BST is skewed (the worst case), it can extend to O(n). As a result of limiting this height to log n, the AVL tree imposes an upper bound to each operation to be O(log n) where n is the number of nodes.
43. Define the graph data structure?
Answer: A graph G is an ordered set G(V, E) where V(G) represents the set of vertices, and E(G) represents the set of edges connecting these vertices. Graphs can be regarded as cyclic trees, where nodes (vertices) maintain any interconnected network rather than parent-child relationships.
44. What is the maximum number of nodes in a binary tree of height k?
Answer: 2k+1-1 where k >= 1
45. State the properties of the B Tree.
Answer: A B tree of order m has all the properties of an M way tree. Additionally, it has the following properties.
- Every node in a B-Tree contains at most m children.
- In a B-Tree, every node except the root node and the leaf node contains at least m/2 children.
- There must be at least two nodes.
- Leaf nodes must all be at the same level.
46. Differentiate among cycle, path, and circuit?
Answer:
- Path: A path is a sequence of adjacent vertices connected by edges without any restrictions.
Cycle: A Cycle is a closed path whose initial vertex and end vertex is the same. The path cannot visit the same vertex twice
Circuit: A Circuit is any closed path whose initial vertex is identical to its end vertex. It is possible to repeat any vertex.
47. Please explain an MST (Minimum Spanning Tree). Also, explain how does Prim’s algorithm finds a minimum spanning tree.
Answer: In weighted graphs, an MST is a spanning tree with the minimum weight of all possible spanning trees. Moreover, by using Prim's algorithm, each node is treated as a single tree while adding new nodes to the spanning tree from the available graph.
48. What do you understand by hashing?
Answer: Hashing is the process of converting a range of key values into an array of indexes. You can create associative data storage using hash tables, in which data indices can be found by providing corresponding key values.
49. Can you explain the Tower of Hanoi problem?
Answer: The Tower of Hanoi is a mathematical puzzle comprised of three towers (or pegs) and more than one riThe rings are of varying sizes and stacked one above the other so that the larger one is beneath the smaller one.
The Tower of Hanoi involves moving the tower of the disk from one peg to another without distorting the properties.
50. Write the C program to insert a node in a circular singly list at the beginning.
Answer:
#include<stdio.h>
#include<stdlib.h>
void beg_insert(int);
struct node
{
int data;
struct node *next;
};
struct node *head;
void main ()
{
int choice,item;
do
{
printf("\nEnter the item which you want to insert?\n");
scanf("%d",&item);
beg_insert(item);
printf("\nPress 0 to insert more ?\n");
scanf("%d",&choice);
}while(choice == 0);
}
void beg_insert(int item)
{
struct node *ptr = (struct node *)malloc(sizeof(struct node));
struct node *temp;
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nNode Inserted\n");
}
}
If you have reached this far, you are certainly willing to learn more about data structures. Listed below are some additional data structure resources that I believe will be useful to you.