# Top 100 Data Structures Interview Questions And Answers

These data structure interview questions and answers guide in developing a machine learning career. A machine learning expert, data analyst, and data scientist job examination will be easier for the ones going through data structure interview questions and answers.

Contents

### 1. What are data structures?

• Methods and techniques used to maintain data in an organized fashion.
• Define data dependency and relationships.

### 2. What is the difference between  File Structure and a Data Structure?

Listed below is the difference between file structure and data structure:

### 3. What is a linked list?

• Linked list data structure  consists of individual entities called nodes.
• Nodes have the capability to connect to other nodes and create a chain.
• The continuous chain structure forms to become a linked list data.

### 4. Where are data structures primarily used?

• Numerical computation
• Operating system design
• Artificial Intelligence
• Compiler design
• Database handling
• Graphical processing
• Lexical analysis
• Statistics

### 5. What are the types of searching used in Data Structure?

• Linear Search involves iterating over a data unit to perform the required operation.
• Binary Search: is more efficient in the way that it can split the data unit into chunks and then perform a search operation.

### 6. How does Binary search work?

• Binary search works on ordered data(sorted) only.
• To begin with, the middle element of the array is found out, and the search begins from there.
• The array is searched in two parts based on the search value being higher or lower than the middle element.
• It is key to know the order of the arrangement to help search the value accordingly.

### 7. How are individual elements accessed in an array?

• Each of the values in an array is given an index position starting from 0 to n-1, where ‘n’ is the number of elements in the array.
• Individual elements can be accessed by using the index element for operations.
• Multi-dimensional arrays will have more than one dimension to work with.

### 8. What is a queue in data structures?

• A queue data structure is widely used to denote the ordered access and manipulation of an element.
• The operation of this data structure is the same as a literal queue in the real world.
• Elements are added one after the other and are processed on the front end.

### 9. What is a binary tree?

• A binary tree, the same as the name suggests, is a tree data structure with two nodes, which are the nodes on the left and the right sides of the root node.
• In usage, a binary tree is considered to be an extended linked list.
• Heap data structure is a special balanced binary tree where the root-node key is compared with its children and arranged accordingly.
• If in order traversal of a binary tree is sorted, then the binary tree is BST.

### 10. What is the meaning of the stack?

• A stack is another widely used data structure that provides users with the ability to work with data at one point only.
• As the name suggests, this can correspond to the working of a stack of cards.

### 11. What is the working of LIFO?

• LIFO stands Last in, First out access order.
• This corresponds to how the data can be worked on and modified.
• The data entity that is stored or pushed in last is the first one to be worked on at any point in time.
• If there is a requirement to access the very first element stored, then first you have to retrieve all of the data that came in after the element.

### 12. What are multidimensional arrays?

• Multi-dimensional arrays are arrays that span across more than one dimension.
• There will be more than one index variable for every point of storage.
• It is useful when storing data that cannot be represented using single-dimensional indexing.

### 13. Are linked lists Linear or Non-linear Data  Structures?

• Linked lists are considered to be the best of both worlds here.
• Based on usage, if it is a storage policy, then it can be considered as a non-linear data structure.
• Whereas, if a person is considering it based on retrieval strategies, then it can be considered linear data structure.

### 14. What is a binary search tree?

A binary search tree consists of two primary nodes from the root node.

• Values of the nodes in the left subtree are less in number than the value of the root node, and the values of the nodes on the right of the root node are correspondingly higher than the root.
• Also, individually both of these left and right subtrees are their binary search trees at all points of time.

### 15. What is the meaning of FIFO?

• FIFO, also known as First in, First out, is a way of representing a data operation on factors such as how data is accessed and in what order.
• Here, the data that is first put into the list will be the first entity to exit from the ordered data structure.

### 16. What is the difference between void and null in Data structure?

• Void is a data type identifier in data structures, while null is considered to be a value with no physical presence.
• When the void is used, it indicates that there is no size while initializing the data structure.

### 17. What is dynamic memory management?

• Dynamic memory management is a technique in which storage units are allocated based on the requirements continuously.
• Using dynamic memory allocations, individual data structures can be either stored separately or combined to form entities called composites.
• These composites can be worked on when required.

### 18. What are push and pop operations in Data Structure?

• The push operation denotes that users are adding data into the structure.
• Pop operation denotes that the data is being pulled or removed from the structure.
• Usually, the topmost element is considered when performing push and pop operations.

### 19. How is a variable stored in memory when using data structures?

• A variable is stored based on the amount of memory that is needed.
• First, the required quantity of memory is assigned, and later, it is stored based on the data structure being used.
• Using concepts such as dynamic allocation ensures high efficiency and that the storage units can be supplied based on the requirements in real-time.

### 20. What is merge sort?

• Merge sort is a method of sorting, which is based on the divide and conquer technique.
• Here data entities adjacent to each other are first merged and sorted in every iteration to create sorted lists.
• These smaller sorted lists are combined at the end to form the completely sorted list.

### 21. Why should heap be used over a stack?

• The heap data structure is more efficient to work with when compared to the stack.
• Because the memory allocation in a head is dynamic and can be allocated and removed as per the requirement.
• The memory structure and access time of a stack are comparatively slow.

### 22. What is the meaning of Data Abstraction?

• Data abstraction is one of the widely used tools in data structures.
• The goal is to break down complex entities into smaller problems and solve these by using the concepts of data structures.
• This provides users with the advantage of being focused on the operations and not worried about how the data is stored or represented in the memory.

### 23. What is the meaning of a postfix expression in Data Structures?

• Postfix expressions are used in a scenario where every operator is preceded by its operands.
• Eliminates the need for parentheses or subexpressions when it comes to the concept of operator precedence.

### 24. What is the working of a selection sort?

• The working is simple where the smallest entity is first found out and the index of that is set to zero, thereby permanently sorting this in the first step.
• The remaining steps involve iterating through other elements and adding the next index correspondingly. This is done until all of the elements are sorted.

### 25. What are signed numbers in the data structure?

• Signed numbers are the units that have a data bit at the beginning of the number that denotes if the number is positive or negative.
• Signed numbers have a range of -128 to +127.

### 26. What are the minimum nodes binary trees can have?

• Binary trees can have zero nodes or a minimum of 1 or 2 as well.
• It can be zero in cases where all of the nodes have a NULL value.

### 27. What data structures make use of pointers?

Pointers are used in a variety of data structures. They are majorly used in the following data structures:

• Binary trees
• Queues
• Stacks

### 28. What is the use of dynamic Data Structures?

Dynamic data structure provides users with a lot of flexibility in terms of the provision of data storage and manipulation techniques.

It is used to change during the operation of the algorithm or the execution of the program.

### 29. What is a priority queue?

A priority queue is an abstract data type that resembles a normal queue but has a priority assigned to elements.

• Elements with higher priority are processed before the elements with a lower priority.
• A minimum of two queues are required in this case, one for the data and the other to store the priority.

### 30. Pointers allocate memory for data storage. True or False?

False, pointer operations such as declaration will not allocate any memory for the storage of data. But, memory is allocated for the variable that the pointer is pointing to. Memory processing begins only when the program begins its execution.

### 31. What is the meaning of deque?

A deque is a double-ended queue.

• This means that elements can be added or removed from any one of the two ends. It can be used both as a regular queue and as a stack.
• It performs better than both linked lists and stacks in general.

### 32. Differentiate between Linear and Nonlinear data structure?

Listed below are the differences between linear data structure and non-linear data structures:

### 33. What is the meaning of an AVL tree?

An AVL tree is a type of binary search tree where the tree is only slightly balanced. Balance is the unit of comparison between the heights of the subtrees from the main(root) node. All tree checks the height of left and right subtrees and assures that the difference is not more than 1.

### 34. How does Huffman’s algorithm work?

Huffman’s algorithm uses a table, containing the frequency of the occurrence of every data entity on the list.

• This is used for creating extended binary trees, which are known to have minimum weights for the path lengths.
• This is considering each of the corresponding weights.

### 35. What are recursive algorithms?

Recursive algorithms are algorithms that solve a problem by breaking it down into simpler sub-problems and then solving them iteratively.

The output of one recursion operation is usually the direct input for the next iteration operation, and this process goes on.

### 36. How does bubble sort work?

Applied to arrays where elements adjacent to each other are compared and values are exchanged based on the order of arrangement.

It’s called bubble sort because of the concept of exchanging elements like a bubble floating to the top of the water and larger entities sinking to the bottom end.

### 37. Which is the fastest sorting algorithm available?

Among the many types of algorithms such as bubble sort, quick sort, merge sort, and more it is not right to put one method on the podium for performance.

This greatly varies based on the data, the reaction after the algorithm processes the data, and how it’s sorted.

The concept of time complexity is considered here.

### 38. What is the postfix form of (X+Y)*(Z-C)?

The postfix form of the given expression is XY+ZC-*

### 39. Where are tree data structures used?

A tree data structure is used in a variety of applications. Following are some of them:

• Arithmetic expression handling
• Symbol table creation
• Lexical analysis
• Hierarchical data modeling

### 40. What are data structures that are used in graphs?

To implement graphs, two graph data structures play a key role. They are:

• Adjacency matrix: used for sequential data representation
• Adjacency list: used to represent linked data

### 41. What are the data structures that are used in DFS and BFS algorithms?

• In the depth-first search(DFS), the stack data structure is made use of.
• In the case of the breadth-first search(BFS) technique, queues are used.

### 42. What are the time complexities of linear search and binary search?

Binary search is more effective as it takes lesser comparisons to search for an element in an array.

• The time complexity for linear search is O(n)
• Time complexity is O(log n) for binary search.

### 43. Where are Multi-linked data structures used?

Multi-linked data structures are used in many domains. Following are the two most important use cases of multi-linked data structures:

• Generation of sparse matrices
• Index creation for data entities

### 44. What is the method used for inorder traversal in trees?

Inorder traversal works in the following ways:

• The tree is traversed through the left subtree.
• The root node is visited after the left visit.
• Then, the right subtree is traversed.

### 45. What is the working of postorder traversal in trees?

Postorder traversal works in the following ways:

• First, the left subtree is traversed through.
• The right subtree is traversed next.
• The root node is visited after the right subtree visit.

### 46. What are the disadvantages of implementing queues using arrays?

• Array sizing: 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.
• Memory dumps: The memory that is used to store the queue elements cannot be reused to store the queue. This is because of the working of queues where insertion happens at the head node only.

### 47. How can elements be inserted in the circular queue?

There are two cases in which items can be placed in a circular queue. They are as follows:

• When front != 0 and rear = max -1.This makes it possible as the queue will not be full, and new elements can be inserted here.
• When rear != max -1. This ensures that the rear is incremented to the maximum allocation size, and values can be inserted easily to the rear end of the queue.

### 48. What is the use of void pointers?

Void pointers are used because of their capability to store any pointer, which is pointing to a wide variety of data.

It is used to implement heterogeneous linked lists in many programming languages. Extra memory space for a pointer is required with each element of the linked list.

### 49. What is the meaning of the stack overflow condition?

Stack overflow is the term given when the stack is full and an element cannot be inserted into the stack anymore. Stack overflow happens when top = Maxsize-1

### 50. Have you earned any sort of certification to improve your learning and implementation process?

• Strong aspiration
• Effective learner

List the certifications, if you have any, and do talk about them in brief, explaining what all you learned from the program and how it’s been helpful to you so far.

### 54. How do signed and unsigned numbers affect memory?

In signed the first bit is used to indicate if the number is positive or negative. The recognized unsigned has all bits available for that number.

Example: Unsigned 8-bit number has a range 0-255, while the 8-bit signed number has a range -128 to +127.

### 56. Explain the role of malloc(), calloc(), realloc() and free().

Malloc(): Used for dynamic memory allocation. Syntax: int * p = (int *) malloc(sizeof(int))

Calloc(): Used for contiguous dynamic memory allocation. Syntax : p = (castType*)calloc(n, size);

Realloc(): Used to resize allocated memory without losing old data. Syntax : void * realloc(void * p.size_t newsize);

Free(): Use to free the memory block that had been allocated dynamically. Syntax : free(p);

### 57. Differentiate between file structure and storage.

Listed below are differences between file structure and storage:

### 58. Explain recursion.

It is a process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. It is a recursive data structure having a pointer to its top element.

### 60. Do all declaration statements lead to fixed memory reservation?

Most declarations do, with the exemption of pointers. Point declaration does not allocate memory for data, but the address of the pointer variable. Actual memory allocation for the data comes during run-time.

### 61. What is an array?

It is a data structure that contains a group of elements. An array consists of multiple variables of the same type. It can hold primitive types and object references. Array’s size is always fixed.

### 62. How to create an array?

Arrays can be declared like how a variable is declared.

• Declaration: int myArray[ ]; OR int[ ] myArray;
• Memory allocation: int myArray[ ]; OR int[ ] myArray;

### 63. Explain the types of a linked list?

• Singly-linked list: Every node stores the address of the next node. For example: 1->2->3->4->NULL
• Doubly linked list: Two references are associated with each node. For example: NULL <-1<->2<->3->NULL
• Circular linked list: All nodes are connected to form a circle. There is no NULL at the end, for example, 1->2->3->1

### 65. What are the applications of doubly-linked lists?

• Backward and forward navigation of web pages.
• Image viewer
• Music player
• Deck of cards in a game

### 66. How do you search for a target key in a linked list?

• Start from the leftmost element of arr[ ] and one by one compare x with each element of arr[ ]
• If x matches with an element, return the index.
• If x doesn’t match with any of the elements, return -1

### 67. List some applications of the circular queue.

• Traffic light functioning is the best example for circular queues. The colors in the traffic light follow a circular pattern.
• In page replacement algorithms, a circular list of pages is maintained and when a page needs to be replaced, the page in the front of the queue will be chosen.

### 68. Explain some applications of the stack?

1. Expression handling
• Infix to postfix or infix to prefix conversion.
• Postfix or prefix evaluation.
1. Backtracking procedure
2. Function call and return process

### 69. Which data structure is used to perform recursion?

The stack data structure is used in recursion due to its last-in-first-out nature.

### 70. What is stack underflow?

It is a condition when the array is empty and the user requests for deletion operation.

### 71.  List some applications of queue data structure.

• Used in the printer, disk, CPU.
• Used in the asynchronous transfer of data.
• Used as buffers in MP3 media player, CD player.
• Used to maintain the playlist in media players.
• Used in OS for handling interrupts.

### 72. Which data structure is used for implementing LRU cache?

Two data structures are used to implement an LRU Cache

• Queue
• Hash

### 73. Mention different types of binary trees.

• Full binary tree
• Complete binary tree
• Skewed tree
• Left skewed tree
• Right skewed tree

### 74. Give a basic algorithm for searching a binary search tree.

``````If Root -> Data = Item Or Root = Null
Return ROOT
Else
If Root < Root - > Data
Return Search(root -> LEFT, ITEM)
Else
Return Search(root -> RIGHT, ITEM)``````

### 76. What are the different operations applied on AVL trees?

• Left-Left Rotation(LL)
• Left-Right Rotation(LR)
• Right-Right Rotation(RR)
• Right-Left Rotation(RL)

### 77. What is the degree of a node?

It can be defined as the number of children a node has.

• Node 1 degree = 2
• Node 2 degree = 2
• Node 5 degree = 3

### 78.  What is the degree of a tree?

It is the maximum degree of a node in a tree

• Node 1 degree = 2
• Node 2 degree = 2
• Node 5 degree = 3

Degree of tree = 3

### 79. Explain spanning trees.

It is a subset of Graph G, which has all the vertices covered with a minimum possible number of edges.

### 80. What is a minimum spanning tree?

A minimum spanning tree is a weighted spanning tree where the cost is minimum among all the spanning trees.

### 81. Define the graph data structure

The graph data structure is a non-linear data structure consisting of finite sets of nodes(or vertices) and a set of edges connecting them.

### 82. Differentiate among cycle, path, and circuit.

Path: It is a sequence of adjacent vertices connected by the edges.

Cycle: It is a closed path where any vertex in the path can not be visited twice.

Circuit: It is a closed path where any vertex may be repeated.

### 83. How does depth-first traversal work?

Here, the graph is traversed in a depth ward motion. Stack to remember to get the next vertex.

### 84. How does breadth-first traversal work?

Here, the graph is traversed in a breadth wards motion and uses a queue to remember to get the next vertex.

### 85.  Explain Dijkstra’s algorithm

This algorithm is used to calculate the shortest path between one node of your choice and every other node in a graph.

### 86. What are different approaches to developing algorithms?

• Greedy
• Divide and conquer
• Dynamic programming

### 87.  Explain a greedy approach.

It is an approach used to build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

Examples:

• Dijkstra Algorithm
• Prim’s Algorithm

### 88. Explain the divide and conquer approach.

Using this approach, the problem is divided into smaller subproblems and then each problem is solved independently.

Examples:

• Binary search
• Merge sort

### 89.  Explain dynamic programming.

Dynamic programming is used to find the most optimized solution by eliminating the standard recursive calls.

Examples:

• Finding Fibonacci series
• Knapsack problem

### 90. What is a Fibonacci search?

It is a search algorithm that applies to a sorted array. Here, the next number is the sum of the previous two numbers.

Examples:

• 0,1,1,2,3,5,8,13,21,34,55….

### 91. What is an interpolation search technique?

Interpolation search is an improved variant of binary search.

• Start searching data from the middle of the list.
• If it is a match, return the index of the item, and exit.
• If it is not a match, probe position.
• Divide the list using a probing formula and find the new middle.
• If data is greater than the middle, search in a higher sub-list.
• If data is smaller than the middle, search in the lower sub-list.

### 92.  Explain the working of quicksort.

It is an algorithm based on the divide and conquer approach in which the array is split into subarrays and these subarrays is recursively called to sort the elements.

• Time complexity: D(nlogn)

### 93. What is the worst time complexity of Quicksort?

D(n^2)

• An array is already sorted in the same order
• The array is already sorted in reverse order
• All elements are the same

### 94. What is a Radix sort?

It is a technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements.

### 95. What are the disadvantages of the Radix sort?

• Less flexible
• Constant for Radix sort is greater
• Consumes more space

### 96. What are some applications of data structure?

Knowing the different kinds of data structures available helps the programmer in choosing which data structure suits the best for solving a problem efficiently. Some of the real-time applications of the data structure are:

• For representing a city region telephone network
• To implement back functionality in the internet web browser
• To store dynamically growing data which is accessed very frequently, based upon a key-value
• To implement the undo function in a text editor
• To store the information about the directories and files in a system

### 97. Mention applications of the deque.

• Palindrome checker
• A steal job scheduling algorithm

### 98. What are the advantages of a Linked list over an array?

Consider a scenario, where we need to store a large amount of data in an array. But the memory to store that data is not available contiguously. In this case, we cannot use arrays. Hence, we go for a linked list. Since each node is connected using a link, it is not necessary that memory has to be contiguous.

### 99. Write the syntax in C to create a node in the singly linked list.

``````
struct node
{
int data;
struct node *next;
};
Struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node)); ``````

### 100. What is the use of a doubly-linked list when compared to that of a singly linked list?

In a singly linked list, we have only forward links. Hence, we cannot traverse the linked list in a backward manner. To overcome this, we go for a doubly-linked list.

In a doubly-linked list, each node has three fields such as previous, data, and next field, and has two links such as a forward and backward link.

The previous field of the first node and the address field of the last node is NULL. The previous field of the second node has the address of the first node and so on.

Also, accessing elements can be done more efficiently in the case of a doubly linked list.

This list of top 100  data structure interview questions, covers the major portion of the most frequently asked data structure interview questions.