# Data Structure Interview Questions and Answers

## Data Structure Interview Questions 2021

Below you will get Data Structure Interview Questions and Answers For freshers 2021. These Data Structure Questions and Answers will help you in preparing for the upcoming technical Interview.

Data Structure is one of the most important subjects. Here you will get the most asked questions of Data Structure at the time of the Interview. ## Data Structure Interview Questions

Data structure is a format for storing data in a structured manner. For example, data like photos, videos are stored in gallery with the help of a data structure. It is not a separate programming language. It is just an implementation method and can be implemented using any one of the programming language like C, C++, Java, etc.

#### Applications of DSA:-

1. For representing a city region telephone network.
2. To implement back functionality in the internet web browser.
3. To store dynamically growing data which is accessed very frequently, based upon a key value.
4. To implement the undo function in a text editor.
5. To store information about the directories and files in a system.

## Data Structure Interview Questions for frehers

#### 1. What is a Stack?

Solution:- Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). The Stack is a list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having a pointer to its top element. Last-In-First-Out (LIFO) means the element which is inserted first will be deleted last from the stack.

#### 2. What is the difference between PUSH and POP?

Solution:- PUSH and POP are storage and retrieval operations for data in the stack.

• PUSH: specifies that data is “inserted” into the stack.
• POP: specifies data retrieval. It means that data is being removed from the stack.

#### 3. Briefly explain the approaches to develop algorithms?

Solution:- There are three major approaches to develop algorithms −

• Greedy Approach − creating a solution by choosing the next best possible option

• Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently.

• Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combinedly

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

Solution:- A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. This forms a chain-like link for data storage.

#### 5. What is a postfix expression?

Solution:- An expression in which operators follow the operands is known as postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.

The expression “a + b” will be represented as “ab+” in postfix notation.

#### 6. Write the postfix form of the expression: (A + B) * (C – D)

Solution:- AB+CD-*

#### 7. What is binary search?

Solution:- Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you’ve narrowed down the possible locations to just one. This search first compares the target value to the mid of the list. If it is not found, then it takes a decision on whether.

#### 8. What is bubble sort and how bubble sort works?

Solution:- Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. Bubble sort is a comparison-based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. It is not suitable for a large set of data because the time complexity is Ο(n2)

#### 9. What is a queue? How is it different from a stack?

Solution:- A queue is another common data structure that places elements in a sequence, similar to a stack. A queue uses the FIFO method (First In First Out), by which the first element that is enqueued will be the first one to be dequeued.

In a stack, the item that is most recently added is removed first. Contrary to this, the item least recently added is removed first in case of a queue.

#### 10. How quick sort works?

Solution:- Quick Sort is a sorting algorithm, which is commonly used in computer science. Quicksort is a divide and conquers algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub-arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array. Quicksort uses the 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 quicksort.

#### 11. How does dynamic memory allocation help in managing data?

Solution:- Aside from being able to store simple structured data types, dynamic memory allocation can combine separately allocated structured blocks to form composite structures that expand and contract as needed.

#### 12. What is Data abstraction?

Solution:- Data abstraction is the reduction of a particular body of data to a simplified representation of the whole. Data abstraction is a powerful tool for breaking down complex data problems into manageable chunks. Abstraction, in general, is the process of taking away or removing characteristics from something in order to reduce them to a set of essential characteristics. As in abstract art, the representation is likely to be one potential abstraction of a number of possibilities. This is applied by initially specifying the data objects involved and the operations to be performed on these data objects without being overly concerned with how the data objects will be represented and stored in memory.

#### 13. How will you insert a new item in a binary search tree?

Solution:- As a binary search tree doesn’t allow for duplicates, the new item to be inserted must be unique. Assuming it is, we will proceed with checking whether the tree is empty or not. If it is empty, then the new item will be inserted in the root node.

#### 14. What do you understand by an AVL tree?

Solution:- AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. The measure of the balance is given by the difference of the heights of the subtrees from the root node of the AVL tree.

Solution:- Linked lists are of many different types. They are as follows:

• Singly Linked List – Every node stores the address or reference of the next node in the linked list, leave for the last node that stores NULL
• Doubly Linked List – Every node keeps two references. One point to the next node and the other points to the previous node
• Circular Linked List – In this type of linked list, all nodes are connected to form a circle. Hence, there is no NULL at the end. A circular linked list can either be a single circular linked list or a double circular linked list

#### 16. What is data structure?

Solution:- A data structure is a named location that can be used to store and organize data. And, an algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allow us to write efficient and optimized computer programs. For example, we can store a list of items having the same data-type using the array data structure.

#### 17. When is a binary search best applied?

Solution:-

A binary search is an algorithm that is best applied to search a list when the elements are already in order or sorted. The list is searched starting in the middle, such that if that middle value is not the target search key, it will check to see if it will continue the search on the lower half of the list or the higher half. The split and search will then continue in the same manner.

#### 18. How do you reference all the elements in a one-dimension array?

Solution:- We can reference all the elements in a one-dimension array using an indexed loop. The counter runs from 0 to the maximum array size, say n, minus one. All elements of the one-dimension array are referenced in sequence by using the loop counter as the array subscript.

#### 19. Which data structures are applied when dealing with a recursive function?

Solution:- Recursion, is a function that calls itself based on a terminating condition, makes use of the stack. Because of its LIFO (Last In First Out) property, it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of the system stack for storing the return addresses of the function calls.

#### 20. What is LIFO?

Solution:- LIFO is a short form of Last In First Out. It refers to how data is accessed, stored, and retrieved. A data type that uses LIFO has data that was stored last should be the one to be extracted first. Thus all the other data that was stored before this first data must first be retrieved and extracted.

#### 21. What is a stack?

Solution:- Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). The Stack is a list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having a pointer to its top element. Last-In-First-Out (LIFO) means the element which is inserted first will be deleted last from the stack.

#### 22. What is FIFO?

Solution:- FIFO means First-in First-out and is basically a way that defines how the data within the data structure will be accessed. Mainly followed in QUEUE. Data has been inserted into the queue list the longest is the one that is removed first.

#### 23. Differentiate NULL and VOID

Solution:- Null means nothing for data types. Void means function returned type have to be nothing. you also can not return null from a void function. A variable that is given a Null value simply indicates an empty value.

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

Solution:- Heap is flexible than stack because memory space for the heap can be dynamically allocated and de-allocated as per the requirements.

#### 25. How do signed and unsigned numbers affect memory?

Solution:-

In the case of signed numbers, the first bit is used to indicate whether positive or negative, which leaves you with one bit short. With unsigned numbers, you have all bits available for that number. The effect is best seen in the number range (an unsigned 8-bit number has a range 0-255, while the 8-bit signed number has a range -128 to +127.