DSA Interview

Q-1 What do you mean by data structure?

Data structures are an integral part of computers used for the arrangement of data in memory. They are
essential and responsible for organizing, processing, accessing, and storing data efficiently. Data structure
has many different uses in our daily life. There are many different data structures that are used to solve
different mathematical and logical problems.

Data structures can be categorized as linear (like arrays, linked lists, stack and queue ) or non-linear (like
trees, graphs).

Q-2 Can you describe the different types of Data Structures?

There are two main types of Data Structures:

Linear data structures : the elements are arranged in sequence one after the other. It can be traversed on a
single run. That is, if we start from the first element, we can traverse all the elements sequentially in a single
pass.

Non linear data structures : elements in non-linear data structures are not in any sequence. Instead they are
arranged in a hierarchical manner where one element will be connected to one or more elements. It requires
multiple runs. That is, if we start from the first element it might not be possible to traverse all the elements
in a single pass.

Q-3 What is an array in data structure?

An array is a linear data structure and it is a collection of items stored at contiguous memory locations. The
idea is to store multiple items of the same type together in one place.

Arrays use an index-based data structure which helps to identify each of the elements in an array easily using
the index.

The search process in an array can be done very easily.

Q-4 What are the applications of array in real life?

An array can be used for CPU scheduling.

An array can also handle complex data structures (Graph) by storing data in a two-dimensional array.

An array is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables

2D arrays, commonly known as, matrices, are used in image processing.

store the contacts on our phone in alphabetical order

Q-5 what is linked list in data structure?

A linked list is a linear data structure in which elements are not stored at contiguous memory locations.
A linked list is a collection of data called nodes, where each node is divided into two parts that hold data and
the address of the successive node.

Q-6 What type of structure is a linked list?

There are four key types of linked lists:

Singly linked lists : A singly linked list is a unidirectional linked list. So, you can only traverse it in one
direction

Doubly linked lists : A doubly linked list is a bi-directional linked list. So, you can traverse it in both directions.
Unlike singly linked lists, its nodes contain one extra pointer called the previous pointer. This pointer points
to the previous node.

Circular linked lists : A circular Linked list is a unidirectional linked list. So, you can traverse it in only one
direction. But this type of linked list has its last node pointing to the head node.

Circular doubly linked lists : A circular doubly linked list is a mixture of a doubly linked list and a circular
linked list. Like the doubly linked list, it has an extra pointer called the previous pointer, and similar to the
circular linked list, its last node points at the head node. This type of linked list is the bi-directional list. So,
you can traverse it in both directions.

Q-7 What are the applications of linked list in real life?

Web pages can be accessed using the previous and the next URL links which are linked using a linked list.

The music players also use the same technique to switch between music.

Social media content “feeds”.

Q-8 What are the advantages of linked lists over arrays?

Q-9 Explain the concept of a jagged array.

A jagged array is an array of arrays such that member arrays can be of different sizes, i.e., we can create a 2-
D array but with a variable number of columns in each row. These types of arrays are also known as Jagged
arrays.
// Declaring 2-D array with 2 rows

int arr[][] = new int[2][];

// Making the above array Jagged

// First row has 3 columns

arr[0] = new int[3];

// Second row has 2 columns

arr[1] = new int[2];

Q-10 What is a stack in data structure?

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle and allows insertion and
deletion operations from one end.

The common operations on a stack are push (insert an element), pop (remove the top element), and peek
(view the top element).

Q-11 What are the applications of a stack?

It is used for parenthesis checking.

Depth First Search in Graphs, Infix to Postfix Expression Conversion

Stack is used in memory management.

It is also used for processing function calls.

The stack is used in recursion operations.

History of visited websites, E-mails, Google photos and Notifications.

Q-12 What are the disadvantages of stack?

It is difficult in Stack to create many objects as it increases the risk of the Stack overflow.

It has very limited memory.

In Stack, random access is not possible.

Q-13 What is a queue in data structures?

A queue is a linear data structure that stores elements in a specific order, called First-In-First-Out (FIFO).

A queue can be defined as an ordered list which enables insert operations to be performed at one end
called REAR (enqueue) and delete operations to be performed at another end called FRONT (dequeue).
Q-14 What are the applications of Queues?
Operating System uses queues for job scheduling

It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.

In social media to upload multiple photos or videos queue is used

Server while responding to request

Data packets in communication are arranged in queue format.

Q-15 What are different types of queue?

There are four different types of queue that are listed as follows –

Simple Queue or Linear Queue : Linear Queue an insertion takes place from one end while the deletion
occurs from another end.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If the first three
elements are deleted from the Queue, we cannot insert more elements even though the space is available in
a Linear Queue.

Circular Queue : It is similar to the linear Queue except that the last element of the queue is connected to
the first element.

The drawback that occurs in a linear queue is overcome by using the circular queue. The main advantage of
using the circular queue is better memory utilization.

Priority Queue : It is a special type of queue in which the elements are arranged based on the priority.

Priority queue is mainly used to implement the CPU scheduling algorithms.

Double Ended Queue (or Deque) : Double Ended Queue, insertion and deletion can be done from both ends
of the queue either from the front or rear.

Q-16 What defines a tree data structure?

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. A tree is also
known as a Recursive data structure.

the node contains three fields. The second field stores the data; the first field stores the address of the left
child, and the third field stores the address of the right child. (The above structure can only be defined for
the binary trees because the binary tree can have utmost two children, and generic trees can have more
than two children. )

There are different types of Tree-like Binary Tree, Binary Search Tree, AVL Tree, B-Tree, etc.

Q-17 Why do we use trees in data structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data
sequentially. In order to perform any operation in a linear data structure, the time complexity increases with
the increase in the data size. But, it is not acceptable in today's computational world.

Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.
Q-18 What are the applications of tree?
Domain Name Server(DNS) also uses tree structures, DOM in Html

The tree data structure is also used to store the data in routing tables in the routers.

commonly used in decision-making algorithms in artificial intelligence and machine learning algorithms

BST used in computer Graphics

Q-19 Explain Binary tree.

The Binary tree means that the node can have maximum two children. (each node can have either 0, 1 or 2
children.)

the node contains three fields. The second field stores the data; the first field stores the address of the left
child, and the third field stores the address of the right child.

There are four types of Binary tree-

Full/ proper/ strict Binary tree : The tree can only be considered as the full binary tree if each node must
contain either 0 or 2 children.

Complete Binary tree : The complete binary tree is a tree in which all the nodes are completely filled except
the last level and nodes are filled left to right.

Perfect Binary tree : A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf
nodes are at the same level.

Degenerate Binary tree : The degenerate binary tree is a tree in which all the internal nodes have only one
children. right-skewed tree as all the nodes have a right child only. left-skewed tree as all the nodes have a
left child only.

Balanced Binary tree : The balanced binary tree is a tree in which both the left and right trees differ by
atmost 1. For example, AVL and Red-Black trees are balanced binary tree.

Q-20 Explain Binary Search tree.

A binary search tree follows some order to arrange the elements. In a Binary search tree, the value of left
node must be smaller than the parent node, and the value of right node must be greater than the parent
node

As compared to array and linked lists, insertion and deletion operations are faster in BST.

Application of BST D Game Engine, Computer Graphics Rendering, Routing table.

Q-21 Explain AVL Tree.

It is one of the types of the binary tree, or we can say that it is a variant of the binary search tree. AVL Tree
can be defined as height balanced binary search tree in which each node is associated with a balance factor
which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be
unbalanced and need to be balanced.
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. L L rotation, R R
rotation, L R rotation, R L rotation

Mostly it is used when you have fewer insertion and deletion operations but more searching operations.

Application of AVL Tree- Data Analysis and Data Mining and the applications which involve more searches.

Q-22 What is the main reason why AVL trees are useful?
AVL tree always tries to maintain it’s height to O(log(n)) by doing rotations.

The AVL Tree has a bad cost in inserting and removing data because it has to self-sort itself each and every
time. It has a wonderful searching capacity with O(log(n)) running time guaranteed.

Mostly it is used when you have fewer insertion and deletion operations but more searching operations.

Q-23 Explain Red-black Tree.

Red-Black tree is a self-balanced binary search tree. This tree data structure is named as a Red-Black tree as
each node is either Red or Black in color. Every node stores one extra information known as a bit that
represents the color of the node. For example, 0 bit denotes the black color while 1 bit denotes the red color
of the node. Other information stored by the node is similar to the binary tree, i.e., data part, left pointer
and right pointer.

n the Red-Black tree, the root node is always black in color.

Q-24 why do we require a Red-Black tree if AVL is also a height-balanced tree.

Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done
due to relatively relaxed balancing. AVL trees provide complex insertion and removal operations as more
rotations are done due to relatively strict balancing.

The Red-Black tree is used because the AVL tree requires many rotations when the tree is large, whereas the
Red-Black tree requires a maximum of two rotations to balance the tree.

Q-25 Difference between BFS and DFS.

 BFS DFS

BFS stands for Breadth First Search. DFS stands for Depth First Search.

It is an edge-based technique because the vertices along

It a vertex-based technique to find the shortest path
the edge are explored first from the starting to the end
in a graph.
node.

DFS is also a traversal technique in which traversal is

BFS is a traversal technique in which all the nodes of
started from the root node and explore the nodes as far as
the same level are explored first, and then we move
possible until we reach the node that has no unvisited
to the next level.
adjacent nodes.

Queue data structure is used for the BFS traversal. Stack data structure is used for the BFS traversal.

BFS does not use the backtracking concept. DFS uses backtracking to traverse all the unvisited nodes.

BFS finds the shortest path having a minimum

In DFS, a greater number of edges are required to traverse
number of edges to traverse from the source to the
from the source vertex to the destination vertex.
destination vertex.

BFS traversal is optimal for those vertices which are DFS traversal is optimal for those graphs in which
to be searched closer to the source vertex. solutions are away from the source vertex.

BFS is slower than DFS. DFS is faster than BFS.

It is suitable for the decision tree. Based on the decision, it

It is not suitable for the decision tree because it
explores all the paths. When the goal is found, it stops its
requires exploring all the neighboring nodes first.
traversal.

It is not memory efficient as it requires more

It is memory efficient as it requires less memory than BFS.
memory than DFS.

BFS is employed in network broadcasting, social DFS finds its utility in maze solving, topological sorting,
network analysis, and shortest path finding. and detecting cycles in graphs.

Q-26 Explain Graph.

A graph is a non-linear data structure that consists of vertices (or nodes) and edges.

The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two
nodes in the graph.
There are two ways to store Graphs into the computer's memory: Sequential representation (or, Adjacency
matrix representation), Linked list representation (or, Adjacency list representation)

Q-27 What are the applications of Graph?

Google maps uses graphs for building transportation systems.

Recommender systems can model the user-item relationship in recommender systems.

The World Wide Web huge collection of documents pointing to each other via hyperlinks.

Social Networks (facebook) store on their servers an internal graph representation of the human social
network.

Etc..

Q-30 Explain Heap Data structure.

A Heap is a complete binary tree data structure that satisfies the heap property.

Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at
the root of the tree. (It either follows max heap or min heap property)

In a max-heap, each parent node is greater than or equal to its child nodes. In a min-heap, each parent node
is less than or equal to its child nodes.

Heapify : It is the process to rearrange the elements to maintain the property of heap data structure.