80+ Data Structures Interview Questions with Answers

Data Structure Interview Questions Techhyme

A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing different types of data. There are different basic and advanced types of data structures that are used in almost every program or software system that has been developed.

In this article, we’ve compiled the answers to the most frequently asked Data Structure Interview Questions so that you may better prepare for your data structures job interview.

A list of most frequently asked Data Structure related interview questions and answers are given below:

1Q. What is Data?

Data is a raw material for data processing. It refers to unprocessed information.

2Q. What is information?

It is the data that has been processed in the meaningful form to the one who receives it.

3Q. What is Data Structure?

It is the specified format for organizing and storing data.

4Q. What are the different type of data structures?

Data Structures are divided into two categories:

Primitive Data Structure (int, char, float, double etc)
Non Primitive Data Structure
- Linear (Array, linked list, stack, queue)
- Non Linear (Tree,Graph)

5Q. What are the different operations applied on Data Structures?

Traversing, Searching, Insertion, deletion, sorting and searching.

6Q. Give some areas where data structures are used?

Data Structure provide us means to manage large amounts of data efficiently for uses such as large databases and internet indexing services.

7Q. Name the type of data structure used in following:

Hierarchical Data Model : Tree
RDBMS : Array
Network Data Model : Graph

8Q. What is an Algorithm?

Algorithm denotes a sequence of steps to solve a particular problem.

9Q. What are different approaches to develop algorithms?

Greedy, Divide and Conquer, Dynamic Programming.

10Q. What is Hashing?

Hashing is the process of mapping a given value with a particular key for faster access of elements. Efficiency of mapping depends of the efficiency of the hash function used.

11Q. Explain Greedy algorithm?

Algorithms following greedy approach build up solution step by step. It is mostly used in optimization problems. It makes optimal choice at each step, to solve entire problem.

Example: Dijikstra Algo, Prim’s Algo, Kruskal.

12Q. Explain Divide & Conquer algorithm?

Algorithms following D&C approach works in two steps-Divide & Combine. Atfirst 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.

13Q. Explain Dynamic Programming?

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

Example: Finding fibonacci series.

14Q. What are the parameters that are cared for an algorithm?

Time Complexity and Space Complexity.

15Q. What are Abstract Datatypes?

ADTs are the special datatypes constructed from the collection of data items.

Example : Array, Linked list, Queue.

16Q. 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 amount of data efficiently. It provides different techniques for searching and sorting data.

17Q. 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 first argument denotes the number of bytes to be allocated, and 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 use to free the memory block that had been allocated dynamically.

18Q. What is Array?

Array refers to the collection of similar data items.

Syntax – int a[10];

Here, a is the array having size 10.

19Q. What is 2D Array?

2D array or 2 dimensional array is array of arrays. It is used to store the data in tabular form-in the terms of rows and columns. It is represented as int a[m][n], where m denotes number of rows and n denotes number of columns.

20Q. What is Linked List?

Linked list is a list of data elements linked to one another. In linked list, each element consists of a node, with two field each :

data field (variable that denotes the content of node)
next (pointer variable that stores the address of next node)

Types of Linked List :

Singly LL
Doubley LL
Circular LL
Circular Doubley LL

21Q. How linked list is better than array?

Array is static and Linked list is dynamic.
Linked list avoids memory wastage.

22Q. What do you mean by Stack?

Stack is linear data structure in which insertion and deletion is done only from one end. It follows LIFO (Last In First Out) order.

23Q. What are the operations that we can apply on stack?

Push : Insertion of element on top
Pop : Deletion of element on top

24Q. 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.

25Q. In how ways we can implement stack?

Two ways : using arrays and linked list

26Q. What is peek() operation in Stack?

It returns top most element of Stack.

27Q. What is the condition of Stack Overflow?

top=n-1, where n is the number of elements in stack.

28Q. Give some applications of stack?

For data reversal.
Evaluating arithmetic operations.
To calculate postfix expressions.
For parsing.
For simulation of recursion.

29Q. What is recursion?

Recursion is the process in which a function is called by itself again & again.

Example : Recursive solution of printing a factorial of a number

fact(n)
{
if(n==0)
{
return 1;
}
else
{
return n*fact(n-1);
}
}

30Q. What is Queue?

Queue is a non-primitive non-linear data structure. It is a homogenous collection of elements. It follows FIFO order – First In First Out. Insertion of any new value takes place at ‘rear’ while deletion takes place at ‘front’.

31Q. What is the basic condition to check whether a circular queue is full or not?

(rear+1)%size=front

32Q. Explain me 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.

33Q. What are the minimum number of queues required to implement priority queue?

2, one for data & one for priority.

34Q. What is dequeue operation?

It is doubly-ended queue. In doubly-ended queue, insertion and deletion takes place at both ends.

35Q. What do you know about Tree data structure?

Tree is a non-linear data structure which is defined as the finite set of one or more nodes.

36Q. Explain me the property of Tree data structure?

Top most node of a tree is known as ‘root’.
Tree comprises of one or more subtrees.

37Q. What is degree of a node?

It is the number of subtree(s) of a node.

38Q. What is the degree of a tree?

It is the maximum degree of node in tree. A node of tree with degree 0 i.e no child is called leaf node.

39Q. What is the depth of a tree?

It is also known as the height of a tree. It represents the maximum level of tree.

40Q. What is Forest of a tree?

It is the set of disjoint tree. In a tree, if you remove its root node then it becomes a forest.

41Q. How many children a binary tree may have?

0| 1| 2.

42Q. Differentiate between binary tree and tree.

In an ordinary tree, parent may have many children, but a binary tree can have atmost 2 children.

43Q. 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.
Skewed tree : Tree that goes in single direction.

Left Skewed tree : Node have only left child not right.
Right Skewed tree : Node have only right child not left.

44Q. What is the maximum number of nodes in a binary tree of height ‘h’?

2^(h+1)

45Q. What is the depth of binary tree with ‘n’ nodes?

D = log(base 2)(n)+1

46Q. 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.

47Q. In Tower of Hanoi game, what could be the possible number of moves for 5 disks?

31.

General formula is given as : 2^(n)-1

48Q. How Binary Search Tree works?

It is a binary tree which may be either empty or satisfies following properties :

Value of key in the left child is less than the value of the root.
Value of key in the right child is more than or equal to the value of the root.

49Q. What are the different cases for deleting an element?

When node (to be deleted) is leaf node – delete the node directly.
When node has only ONE child – Make child node as parent (swapping the position of both nodes) and then we can delete it directly.
When node has TWO children – Find inorder successor of that given node and swap their position and delete the node.

50Q. Where BST is used?

To implement multilevel indexing in database.
To implement various efficient algorithms.
To implement applications that require a sorted list as input like various e-commerce websites.
To manage Virtual Memory Areas.
To index various IP addresses.

51Q. Give the worst case complexity for BST operation-insertion.

Insertion : O(h), h is height of BST.

52Q. Give me the properties of Threaded Binary tree?

It is a binary tree with ‘n’ nodes out of which n+1 are always null, and this space is used to contain some useful information. A Left null pointer stores the address of inorder predecessor of the node and a right null pointer stores the address of inorder successor of the node. These pointers are referred to as Threads. It is more efficient than a normal binary tree.

53Q. Explain the concept of Huffman coding?

It is a particular type of optimal prefix code that is used for lossless data compression. It is an example of Greedy algorithm. It assigns variable length code to all the characters. The code length of a character depends on how frequently it occurs in the given text. The character which occurs most frequently gets the smallest code. The character which occurs least frequently gets the largest code.

54Q. 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 key only(not pairs), and all pointers to datarecords exists at leaf level only.

55Q. How can we overcome drawbacks of BST?

Using AVL Trees.

56Q. What is AVL Tree?

Concept of AVL Tree was given by Adelson, Velski, Landis. AVL trees are height balancing BST. It checks the height of left&right subtree and assures that difference is not more than 1, this difference is termed as balanced factor.

57Q. What are the different operations applied on AVL tree?

Left-Left Rotation (LL) : right rotate node p.
Left-Right Rotation (LR) : left rotate “parent of p” and right rotate “parent of parent of p (p-parent-parent)”.
Right-Right Rotation (RR) : left rotate node p.
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.

58Q. Define Graph Data Structure?

Graph is an abstract datatype, containing the set of vertices and edges.

59Q. Define Path & cycle?

Path represents the sequence of adjacent vertices whereas a cycle represents a closed path.

60Q. What are the different ways to represent a graph?

There are to ways to represent a graph, using Adjacency Matrix and Adjacency List.

61Q. What are the application areas of Graph data structure?

Circuit Designing.
Computer Networks.
In study of DNA structure of organism.

62Q. What is a vertex in graph?

Vertex is a point where lines meet.

63Q. What is eccentricity?

It is the maximum distance between a vertex to all other vertices.

64Q. What is Spanning Tree?

It is a subset of a graph, which has all the vertices covered with minimum possible number of edges. It does not have cycles and can’t be disconnected.

65Q. What is MST?

MST is minimum spanning tree. It is a spanning tree having minimum weight than any other spanning tree in the same graph.

Example : Prims, Kruskal algorithm.

66Q. Tell something about BFS & DFS?

BFS is Breadth First Search. It is used to traverse a graph in horizontal manner.
DFS is Depth First Search. It is used to traverse a graph in vertical or depthward manner.

67Q. Name the data structure used in BFS?

Queue.

68Q. Name the data structure used in DFS?

Stack.

69Q. Tell any one Single Source Shortest Path algorithm?

Dijikstra Algorithm.

70Q. What is linear searching?

Linear Search is a linear time searching technique in which a complete list/array is traversed in order to search a element. Time complexity of linear search : O(n), where n denotes the number of elements in an item.

71Q. What is the best case for Binary Search?

When element is present at middle position.

72Q. What are inplace sorting techniques, tell me one inplace and one non-inplace sorting technique.

Inplace sorting techniques does not require any extra space to sort a given list/array.

Inplace Sorting – Bubble Sort
Non-inplace Sorting – Merge Sort

73Q. Is bubble sort stable?

Yes.

74Q. 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).

75Q. Explain the working of Insertion Sort?

In this, left most element is considered to be already sorted. From remaining elements, left most is taken out and is compared to already sorted elements to its left.

Best Case Time Complexity : O(n)

76Q. Is insertion sort stable?

Yes.

77Q. Is insertion sort inplace?

Yes.

78Q. Explain me the working of Quick sort?

Quick sort works on divide and conquer technique. In quick sort, we partition the array into subarrays, this partition takes place around a special element called pivot.

Time Complexity of Quick sort is O(nlogn).

79Q. What is the worst time complexity of quick sort?

O(n^2), it happens when :