Top 50+ Data Structure interview question and answers that are asked for freshers in the technical interview. These are the top 50+ data structure questions along with efficient answers that you can remember easily.
1. What is data structure?
Data structure as a methodology that defines, stores, and retrieves data systematically and structurally. Data structure is the process of organizing, storing data in computer that can be used efficiently.
2. Define Linkedlist
A linked list is a sequence of nodes in which each node is connected to the node following it. This forms a chain-like link for data storage.
3. List the areas where data structures are applied?
Data structures are essential in almost every aspect where data is involved. In general, algorithms that involve efficient data structure are applied in the following areas: numerical analysis, operating system, A.I., compiler design, database management, graphics, and statistical analysis, to name a few.
4. Explain the primary advantage of a linked list?
A linked list is an ideal data structure because it can be modified easily. This means that editing a linked list works regardless of how many elements are in the list.
5. Distinguish linear from a nonlinear data structure.
Linear data structure:
1.The linear data structure is a structure wherein data elements are adjacent to each other.
2. Examples of linear data structure include arrays, linked lists, stacks, and queues.
Nonlinear data structure:
1. A non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements.
2.Examples of nonlinear data structure include trees and graphs.
6. What is an Algorithm?
Algorithm denote a sequence of steps to solve a particular problem.
7. Define graph?
A graph is one type of data structure that contains a set of ordered pairs. These ordered pairs are also referred to as edges or arcs and are used to connect nodes where data can be stored and retrieved.
8. Explain Criteria for algorithm analysis
Algorithms are analysed based on two factors – space and time. It implies execution time and extra space required on the part of an algorithm.
9. Explain algorithm’s asymptotic analysis?
For any algorithm, there are three different levels of execution time based on mathematical binding:
- Representation of the Best Case is done by the symbol Ω(n)
- Representation of the Worst-Case is done by the symbol Ο(n)
- Representation of the Average Case is done by the symbol Θ(n)
10. Can we apply the Binary search algorithm to a sorted Linked list?
No, we cannot apply the binary search algorithm to a sorted linked list because finding the index of the middle element is difficult.
11. List some important applications of a Stack?
- Balanced parenthesis checker
- Redundant braces
- Infix to postfix using a stack
- Infix to prefix using a stack
12. List the common operations performed on a data structure?
- Insertion – Addition of a data item
- Deletion – Data item elimination
- Traversal – Accessing and printing data items
- Search – Find a data item
- Sort – Data items arranged in a predefined sequence
13. Differentiate STACK from ARRAY.
Stack follows a LIFO pattern. It means that data access follows a sequence wherein the last data to be stored when the first one to be extracted.
Arrays, on the other hand, do not follow a particular order and instead can be accessed by referring to the indexed element within the array.
14. 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 non-linear. Whereas, if a person is considering it based on retrieval strategies, then it can be considered linear.
15. What are the different approaches to developing algorithms?
There are three commonly used approaches to developing algorithms, which are:
Greedy Approach: Choosing the next best option for finding a solution.
Divide and Conquer: The problem is divided into a minimum possible subproblems and each subproblem is solved independently.
Dynamic Programming: A problem is divided into minimal subproblems, and they are solved together.
16. Explain the use of stacks?
Stacks uses the LIFO method of addition and retrieval of data items that consume only O(n) time.
If you ever need to access data items in reverse order of their arrival, then you can use stacks.
Stacks are more commonly used in expression parsing, a recursive function call, and depth-first traversal of graphs.
Common operations that you can perform on a stack:
- push(): Adding an item to the stack top
- pop(): Removing an item from the stack top
- peek(): Shows the value of a top item without deleting it
- is empty(): Check if you have an empty stack
- is full(): Checks if you have a full-stack
17. What is the difference between void and null in Data Structures?
Void is a data type identifier in data structures, while null is considered to be a value with no physical presence. When void is used, it indicates that there is no size while initializing the data structure.
18. What is the use of queues?
As the queue follows the First In First Out method, this data structure can be used for working on data items in the exact sequence of their arrival. Queues are widely used in operating systems for different processes. Breadth-First Traversal of Graphs and Priority Queues are some examples of queues.
19. Mention the parts of a linked list?
A linked list typically has two parts: the head and the tail.
Between the head and tail lie the actual nodes. All these nodes are linked sequentially.
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. 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 a case where all of the nodes have a NULL value.
22. List the Operations that can be performed in a queue:
- enqueue(): Adding items to the rear end of the queue
- dequeue(): Removes an item from the front end of the queue
- peek (): Shows the value of the front item without removing it
- is empty(): Checks if the stack is empty
- is full(): Checks if the stack is full
23. What are doubly linked lists?
Doubly linked lists are a special type of linked list wherein traversal across the data elements can be done in both directions. This is made possible by having two links in every node, one that links to the next node and another one that connects to the previous node.
24. Which data structures are used for BFS and DFS of a graph?
BFS (Breadth-First Search) of a graph uses a queue.
Although DFS (Depth First Search) of a graph makes use of a stack, it can also be implemented using recursion that uses function call stack.
How To Prepare for recruitment Drives 2021: Click here
25. What is an AVL tree?
An AVL tree is a type of binary search tree that is always in a state of partially balanced. The balance is measured as a difference between the heights of the subtrees from the root. This self-balancing tree was known to be the first data structure to be designed as such.
26. Explain Greedy algorithm?
Algorithms following greedy approaches build up solutions step by step. It is mostly used in optimization problems. It makes the optimal choice at each step, to solve the entire problem.
Example: Dijkstra Algo, Prim ‘s Algo, Kruskal.
27. Explain Divide & Conquer algorithm?
Algorithms following the D & C approach works in two steps-Divide & Combine. At First we divide the problem into subparts, solve them individually and then combine the result of all subparts to get a collective solution.
Example: Binary Search, Merge Sort.
28. Explain Dynamic Programming?
DP is used to find the most optimized solution by eliminating the standard recursive calls.
Example: Finding fibonacci series.
29. What is the need of Data Structure?
It tells how data can be stored and accessed in its elementary level. It allows us to manage huge amounts of data efficiently. It provides different techniques for searching and sorting data.
30. Explain the role of malloc(), calloc(), realloc() and free()in dynamic memory allocation.
1. malloc() is one of the functions used for dynamic memory allocation. It takes up single arguments, which denotes the number of bytes to be allocated.
malloc() is faster than calloc().
Syntax : int *p = (int *)malloc(sizeof(int))
2. calloc() is one of the functions used for contiguous dynamic memory allocation. It takes up two arguments, in which the first argument denotes the number of bytes to be allocated, and the second argument denotes size of each block. It initializes allocated memory by 0.
3. The realloc() function is used to resize allocated memory without losing old data.
Syntax: void *realloc(void *p, size_t newsize);
4. free() is used to free the memory block that had been allocated dynamically.
31. List types of Linked List ?
- 1. Singly LL
- 2. Doubly LL
- 3. Circular LL
- 4. Circular Doubly LL
32. How is a linked list better than an array?
1. Array is static and Linked list is dynamic.
2. Linked list avoids memory wastage
33. What is Stack Overflow & Stack Underflow?
Stack Overflow : Condition when array is full and user requests for another insertion.
Stack Underflow : Condition when array is empty and user requests for deletion operation.
34. What is the condition of Stack Overflow?
top=n-1, where n is the number of elements in stack
35. Give some applications from stack?
- 1. For data reversal.
- 2. Evaluating arithmetic operations.
- 3. To calculate postfix expressions.
- 4. For parsing.
- 5. For simulation of recursion.
36. What is the basic condition to check whether a circular queue is full or not?
37. Explain the concept of Priority Queue?
Priority queue is the collection of elements such that each element has been assigned a priority i.e order in which elements are deleted or processed. An element of high priority is processed before any element of lower priority.
38. What are the minimum number of queues required to implement priority queue?
2, one for data & one for priority.
39. Explain different types of binary tree?
- Full Binary tree : Every node has 0 or 2 children.
- Complete Binary tree : All internal nodes have 2 children.
- Perfect Binary Tree : All internal nodes have 2 children and leaf node at same level
- Skewed tree : Tree that goes in a single direction.
- Left Skewed tree : Node have only left child not right.
- Right Skewed tree : Node have only right child not left
40. What is the maximum number of nodes in a binary tree of height ‘h’?
41. What is the depth of a binary tree with ‘n’ nodes?
D = log(base 2)(n)+1
42. Explain the game of Tower of Hanoi.
The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
43. Differentiate between B-Tree & B+ Tree?
B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. In B+ Tree, each node contains keys only(not pairs), and all pointers to data records exist at leaf level only.
44. What are the different operations applied on AVL trees?
1. Left-Left Rotation (LL) : right rotate node p.
2. Left-Right Rotation (LR) : left rotate “parent of p” and right rotate “parent of parent of p (p-parent-parent)”.
3. Right-Right Rotation (RR) : left rotate node p.
4. Right-Left Rotation (RL) : right rotate “parent of p” and left rotate “parent of parent of p (p-parent-parent)”.
where p is the node with violating balance-factor.
45. Define Path & cycle?
Path represents the sequence of adjacent vertices whereas a cycle represents a closed path.
46. What are the different ways to represent a graph?
There are two ways to represent a graph, using Adjacency Matrix and Adjacency List.
47. What are the application areas of Graph data structure?
- Circuit Designing.
- Computer Networks.
- In study of DNA structure of organisms.
48. What is Spanning Tree?
It is a subset of a graph, which has all the vertices covered with the minimum possible number of edges. It does not have cycles and can’t be disconnected.
49. Explain the working of selection sort?
In Selection sort, we select a minimum element from the array and store it in the appropriate position.
Time complexity for selection sort – O(n^2).
50. Explain the working of Insertion Sort?
In this, the leftmost element is considered to be already sorted. From the remaining elements, left most is taken out and is compared to already sorted elements to its left.