# DSA Interview Questions And Answers For Freshers

## What is DSA?

DSA Interview Questions and Answers for Freshers

This page will provide you the most common DSA Interview Question and Answer. Before answering the question one must be aware about WHAT IS DSA?

These all are part of Technical Interview. Technical Interviews are considered as one of the toughest part of the whole recruitment process.

Go through the page in detailed to know more about DSA Interview Questions and Answers For Freshers. Click on the button below to know more about Technical Interview Questions. ## DSA Interview Questions and Answers for Freshers : Definition

Data structure is a way of defining, storing & retriving of data in a structural & systemetic way. A data structure may contain different type of data items.

Topics in DSA-

• Searching
• Sorting
• Linked Lists

and more. Click on the button below to know more about DSA.

## Commonly Asked DSA Interview Questions and Answers for Freshers

1. #### What is a Data Structure?

Solution:-

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 implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

#### 2. What is a linked list?

Solution:-

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. Describe the types of Data Structures?

Solution:-

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 the sequential order. In linear data structures, the elements are stored in a non-hierarchical way where each item has the successors and predecessors except the first and last element.

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 the sequential structure.

#### 4. How Linked list is different from array?

Solution:-

Differences between array and linked list are –
1) Arrays are index based data structure where each element is associated with an index. On the other hand, Linked list relies on references where each node consists of the data and the references to the previous and next element.
2) The size of the arrays is fixed, Linked Lists are Dynamic in size.
3) In array elements are accessed randomly using index while in linked list elements are accessed in sequence.
4) Insertion and Deletion operations are expensive in array whereas it can be easily done in linked list.
5) Extra memory space is required in linked list for storing address of next node.
6) Element location is allocated during compile time in array while in linked list it is done during run time.

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

Solution:-

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.

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

Solution:-

STACK:

i) Stack is a ordered collection of items.

ii) Stack is a dynamic object whose size is constantly changing as items are pushed and popped.

iii) Stack may contain different data types.

iv) 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:

i) Array is an ordered collection of items.

ii) Array is a static object i.e. no of item is fixed and is assigned by the declaration of the array.

iii) It contains same data types.

iv) Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.

#### 7. Can we apply Binary search algorithm to a sorted Linked list?

Solution:-

No, we cannot apply the binary search algorithm to a sorted linked list because finding the index of the middle element is difficult.

#### 8. What is asymptotic analysis of an algorithm?

Solution:-

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.

#### 9. Explain different types of Linked List.

Solution:-

Types of Linked List :

1. Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has 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 circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

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

Solution:-

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.

#### 11. What is a queue?

Solution:-

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.

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

Solution:-

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.

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

Solution:-

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.

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

Solution:-

If 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 value. If current key value is greater, then continue, else return false.

#### 15. What are multidimensional arrays?

Solution:-

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.

#### 16.What is shell sort?

Solution:-

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

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

Solution:-

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.

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

Solution:-

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

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

Solution:-

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.

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

Solution:-

The below given problems find their solution using divide and conquer algorithm approach −

• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)

#### 21. What is stack?

Solution:-

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

#### 22. Why do we use queues?

Solution:-

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.

#### 23. What is selection sort?

Solution:-

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.

#### 24. How quick sort works?

Solution:-

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.

#### 25. How depth first traversal works?

Solution:-

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.

### IMPORTANT!!

Few Important pages to be checked

Check these pages to know more Technical Questions and prepare well for you Placements.