# DSA Interview Questions And Answers For Freshers

## Top 25 Most Asked DSA Interview Questions for Freshers 2022

Page Highlights:

• What is DSA?
• Top 25 DSA Interview Questions • Introduction to DSA
• What is Data Structure?
• What is a linked list?
• Describe the types of Data Structures.
• How Linked list is different from array?
• How does a linear data structure differ from a non-linear data structure?
• What Is The Difference Between A Stack And An Array?
• Can we apply Binary search algorithm to a sorted Linked list?
• What is asymptotic analysis of an algorithm?
• Explain different types of Linked List.
• What are the operations that can be performed on a data-structures?
• What is a queue?
• What do you understand by a binary search?
• Do you know how does dynamic memory allocation help in managing data?
• How to check if a given Binary Tree is BST or not?
• What are multidimensional arrays?
• What is shell sort?
• What is the advantage of the heap over a stack?
• What Are The Disadvantages Of Representing A Stack Or Queue By A Linked List?
• Which data structure is ideal to perform recursion operation and why?
• What are some examples of divide and conquer algorithms?
• What is stack?
• Why do we use queues?
• What is selection sort?
• How quick sort works?
• How depth first traversal works?

## Introduction to DSA

Data Structure is a way of defining, storing and retrieving data in a structural and systematic way. A  data structure contains different types of data items.

### What is a Data Structure?

A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for the implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

### What is a linked list?

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.

### Describe the types of Data Structures.

Data Structures are mainly classified into two types:
• Linear Data Structure: A data structure is called linear if all of its elements are arranged in sequential order. In linear data structures, the elements are stored in a non-hierarchical way where each item has successors and predecessors except the first and last elements.
• Non-Linear Data Structure: The Non-linear data structure does not form a sequence i.e. each item or element is connected with two or more other items in a non-linear arrangement. The data elements are not arranged in a sequential structure.

### How Linked list is different from array?

Arrays are index based data structure where each element is associated with an index.Linked list relies on references where each node consists of the data and the references to the precious and next element.
Size of an array is fixed.Size of a Linked List is dynamic.
Array elements are accessed randomly using index.Linked List elements are accessed in sequence.
Insertion and Deletion operations are difficult in arrays.Insertion and Deletion is easily done in linked list.
No extra memory space required. Extra memory space is required in linked list for stroing address of next node.
Element location is allocated during compile time.In linked list element location is done during run time.

### How does a linear data structure differ from a non-linear data structure?

If the elements of a data structure form a sequence or a linear list then it is called a linear data structure. On the other hand, non-linear data structures are those in which the traversal of nodes is done in a non-linear way.

Arrays, linked lists, stacks, and queues are examples of linear data structures, while graphs and trees are those of non-linear data structures.

### What Is The Difference Between A Stack And An Array?

Stack Array
Stack is a dynamic object whose size is constantly changing as items are pushed and popped. Array is a static object, i.e. number of items is fixed and is assigned by the declaration of the array.
Stack may contain different data types. Arrays contains same data types.
Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array. Array can be a home of a stack i.e., array can be declared large enough for maximum size of the stack.

### Can we apply 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.

### What is asymptotic analysis of an algorithm?

Asymptotic analysis of an algorithm, refers to defining the mathematical boundation /framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case and worst case scenario of an algorithm.

### Explain different types of Linked List.

1. Singly Linked List: In this type of linked list, every node stores the address or reference of the next node in the list and the last node has the next address or reference as NULL. For example 1->2->3->4->NULL
2. Doubly Linked List: Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL
3. Circular Linked List: Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly a circular linked list. Eg. 1->2->3->1 [The next pointer of the  last node is pointing to the first]

### What are the operations that can be performed on a data-structures?

Following operations can be performed –
•  Insertion: Adding a new data item.
• Deletion: Deleting the existing data item.
• Traversal: Accessing each data item.
• Searching: Finding a particular data item.
• Sorting: Arranging the data item in a particular sequence.

### What is a queue?

A queue is a data structure that can simulate a list or stream of data. In this structure, new elements are inserted at one end, and existing elements are removed from the other end.

### What do you understand by a binary search?

A binary search is an algorithm that starts with searching in the middle element. If the middle element is not the target element then it further checks whether to continue searching the lower half of the higher half. The process continues until the target element is found.

### Do you know how does dynamic memory allocation help in managing data?

Dynamic memory allocation helps in storing simple structured data types. Moreover, it can combine separately allocated structured blocks for forming composite structures that contract and expand as required.

### How to check if a given Binary Tree is BST or not?

If the inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do in order traversal and while traversing keep track of previous key values. If the current key value is greater, then continue, else return false.

### What are multidimensional arrays?

Multidimensional arrays make use of multiple indexes to store data. It is useful when storing data that cannot be represented using single-dimensional indexing, such as data representation in a board game, tables with data stored in more than one column.

### What is shell sort?

Shell sort is a generalized version of insertion sort. It is a highly efficient sorting algorithm. In shell sort, we break the original list into several smaller sub lists, each of which is sorted using an insertion sort.

### What is the advantage of the heap over a stack?

The heap is more flexible than the stack. That’s because memory space for the heap can be dynamically allocated and de-allocated as needed. However, the memory of the heap can at times be slower when compared to that stack.

### What Are The Disadvantages Of Representing A Stack Or Queue By A Linked List?

1. A node in a linked list (info and next field) occupies more storage than a corresponding element in an array.
2. Additional time spent in managing the available list.

### Which data structure is ideal to perform recursion operation and why?

Stack is the most ideal for recursion operation. This is mainly because of its LIFO (Last In First Out) property, it remembers the elements & their positions, so it exactly knows which one to return when a function is called.

### What are some examples of divide and conquer algorithms?

The below given problems find their solution using the divide and conquer algorithm approach −
• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)

### What is stack?

In data structure, stack is an abstract data type (ADT) used to store and retrieve values in the Last in First Out method.

### Why do we use queues?

As Queues follows FIFO method, they are used when we need to work on data items in exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth-first traversal of graphs are some examples of queues.

### What is selection sort?

In the selection sort technique, the list is divided into two parts. In one part all elements are sorted and in another part the items are unsorted. At first we take the maximum or minimum data from the array. After getting the data (say minimum) we place it at the beginning of the list by replacing the data of first place with the minimum data.

### How quick sort works?

Quick sort uses divide and conquer approach. It divides the list in smaller ‘Partitions’ using pivot. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quick sort.

### How depth first traversal works?

Depth First Search algorithm (DFS) traverses a graph in a depth-ward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.