# Data structure interview question set 1/Data structure Interview Questions and Answers for Freshers & Experienced

## Why and when should I use Stack or Queue data structures instead of Arrays/Lists?

Because they help manage your data in more a particular way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants.

Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections.

More practically you should:

<> Use a queue when you want to get things out in the order that you put them in (FIFO)
<> Use a stack when you want to get things out in the reverse order than you put them in (LIFO)
<> Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

Posted Date:- 2021-09-13 04:52:09

## What is Complexity Analysis of Queue operations?

Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is O(n).
Searching for a given value in the queue requires iterating until you find it. So search is O(n).
Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is O(1).
Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `O(1).

Posted Date:- 2021-09-13 04:51:08

## How do you search for a target key in a linked list?

To find the target key in a linked list, you have to apply sequential search. Each node is traversed and compared with the target key, and if it is different, then it follows the link to the next node. This traversal continues until either the target key is found or if the last node is reached.

Posted Date:- 2021-09-13 04:46:48

## What is Fibonacci search?

Fibonacci search is a search algorithm that applies to a sorted array. It makes use of a divide-and-conquer approach that can significantly reduce the time needed in order to reach the target element.

Posted Date:- 2021-09-13 04:45:24

## What is a bubble sort and how do you perform it?

A bubble sort is one sorting technique that can be applied to data structures such as an array. It works by comparing adjacent elements and exchanges their values if they are out of order. This method lets the smaller values â€œbubbleâ€ to the top of the list, while the larger value sinks to the bottom.

Posted Date:- 2021-09-13 04:44:37

## What is a dequeue?

A dequeue is a double-ended queue. This is a structure wherein elements can be inserted or removed from either end.

Posted Date:- 2021-09-13 04:44:04

## Explain the max heap Data Structure.

It is a type of heap data structure where the value of the root node is greater than or equal to either of its child nodes.

Posted Date:- 2021-09-13 04:42:48

## What is the minimum number of nodes that a binary tree can have?

A binary tree can have a minimum of zero nodes, which occurs when the nodes have NULL values. Furthermore, a binary tree can also have 1 or 2 nodes.

Posted Date:- 2021-09-13 04:39:41

## How do signed and unsigned numbers affect memory?

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.

Posted Date:- 2021-09-13 04:39:00

## When does the worst case of QuickSort occur?

It occurs when the picked pivot is an extreme (smallest or largest) element. Usually, when the input array is sorted or reverse sorted, it also leads to the worst case.

Posted Date:- 2021-09-13 04:38:28

## What is a Red-Black Tree?

A red-black tree is a binary tree that has nodes represented by two colors: red and black. The tree follows specific properties.

These include:

1. The root node of the tree is always black.
2. Every path from the root to any of the leaf nodes should have the same number of black nodes.
3. No two red nodes can be adjacent to each other.

Posted Date:- 2021-09-13 04:37:32

## What is quicksort time complexity?

Worst-case time complexity is O(n^2)

Posted Date:- 2021-09-13 04:36:33

## How does Prim's algorithm find a spanning tree?

Prim's algorithm treats each node as a single tree and continues to add new nodes to the spanning tree from the given graph.

Posted Date:- 2021-09-13 04:35:56

## How does Kruskal's algorithm work?

Kruskal algorithm treats a graph as a forest and every node as an individual tree. A tree connects to another only and only if it has the least cost among all available choices without violating Minimum Spanning Tree (MST) properties.

Posted Date:- 2021-09-13 04:35:19

## What is a Balanced Tree and why is that important?

A tree is perfectly height-balanced if the left and right subtrees of any node are of the same height. We can also say that a tree is height-balanced if the heights of the left and right subtrees of each node differ by a maximum of one unit.

Posted Date:- 2021-09-13 04:34:27

## What is the postfix form of (X + Y) * ( Z - C)

The postfix form of the given expression is XY+ZC-*

Posted Date:- 2021-09-13 04:33:42

## What is the meaning of the stack overflow condition?

When a stack is completely full and we try to insert more elements onto the stack then this condition is called stack overflow condition. Here, top=maxsize-1, and no further elements can be inserted.

Posted Date:- 2021-09-13 04:33:15

## What do you mean by Hash Table?

A Hash table is a data structure used to store data points in an associative manner. The values are stored in an array format. Hash tables are used to store keys/value pairs

Posted Date:- 2021-09-13 04:32:45

## List some applications of multilinked structures?

<> Sparse matrix
<> Index generation

Posted Date:- 2021-09-13 04:32:14

## What is an AVL tree?

An AVL (Adelson, Velskii, and Landi) tree is a height balancing binary search tree in which the difference of heights of the left and right subtrees of any node is less than or equal to one. This controls the height of the binary search tree by not letting it get skewed. This is used when working with a large data set, with continual pruning through insertion and deletion of data.

Posted Date:- 2021-09-13 04:31:32

## How does the Selection sort work?

Selection sort works by repeatedly picking the smallest number in ascending order from the list and placing it at the beginning. This process is repeated moving toward the end of the list or sorted subarray.

Scan all items and find the smallest. Switch over the position as the first item. Repeat the selection sort on the remaining N-1 items. We always iterate forward (i from 0 to N-1) and swap with the smallest element (always i).

Time complexity: best case O(n2); worst O(n2)

Space complexity: worst O(1)

Posted Date:- 2021-09-13 04:30:06

## What is the merge sort? How does it work?

Merge sort is a divide-and-conquer algorithm for sorting the data. It works by merging and sorting adjacent data to create bigger sorted lists, which are then merged recursively to form even bigger sorted lists until you have one single sorted list.

Posted Date:- 2021-09-13 04:29:36

## Which sorting algorithm is considered the fastest? Why?

A single sorting algorithm canâ€™t be considered best, as each algorithm is designed for a particular data structure and data set. However, the QuickSort algorithm is generally considered the fastest because it has the best performance for most inputs.

Its advantages over other sorting algorithms include the following:

. Cache-efficient: It linearly scans and linearly partitions the input. This means we can make the most of every cache load.
. Can skip some swaps: As QuickSort is slightly sensitive to input that is in the right order, it can skip some swaps.
. Efficient even in worst-case input sets, as the order is generally random.
. When speed takes priority over stability.

Posted Date:- 2021-09-13 04:29:08

## Which Data Structure Should be used for implementing LRU cache?

We use two data structures to implement an LRU Cache.

1. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near rear end and least recently pages will be near front end.

2. A Hash with page number as key and address of the corresponding queue node as value.

Posted Date:- 2021-09-13 04:27:52

## How to implement a stack using queue?

A stack can be implemented using two queues. Let stack to be implemented be â€˜sâ€™ and queues used to implement be â€˜q1â€™ and â€˜q2â€™. Stack â€˜sâ€™ can be implemented in two ways:

Method 1 (By making push operation costly)
Method 2 (By making pop operation costly)

Posted Date:- 2021-09-13 04:26:28

## How does variable declaration affect memory allocation?

The amount of memory to be allocated or reserved would depend on the data type of the variable being declared. For example, if a variable is declared to be of integer type, then 32 bits of memory storage will be reserved for that variable.

Posted Date:- 2021-09-13 04:25:35

## What is the difference between a PUSH and a POP?

Pushing and popping applies to the way data is stored and retrieved in a stack. A push denotes data being added to it, meaning data is being â€œpushedâ€ into the stack. On the other hand, a pop denotes data retrieval, and in particular, refers to the topmost data being accessed.

Posted Date:- 2021-09-13 04:23:38

A linked list is an ideal data structure because it can be modified easily. This means that editing a linked list works regardless of how many elements are in the list.

Posted Date:- 2021-09-13 04:23:18

## Differentiate NULL and VOID

Null is a value, whereas Void is a data type identifier. A variable that is given a Null value indicates an empty value. The void is used to identify pointers as having no initial size.

Posted Date:- 2021-09-13 04:22:49

## What is merge sort?

Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list.

Posted Date:- 2021-09-13 04:22:13

## What are graphs and their uses?

A graph is a collection of nodes connected to one another via edges. It forms a network of nodes like in the case of a journey from one source to a destination.

Uses:

Posted Date:- 2021-09-13 04:21:53

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

Apart 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.

Posted Date:- 2021-09-13 04:20:48

## What are trees in DSA?

A collection of nodes is a tree. A node is a data point connected with other points with the help of edges. The top of a tree is the root node. Applications of trees include indexing in databases.

Posted Date:- 2021-09-13 04:20:27

## What are the advantages of the heap over a stack?

In this data structure interview questions, try giving various advantages, along with examples, if possible. It will show the interviewer your domain expertise. Generally, both heap and stack are part of memory and used in Java for different needs:

>> Heap is more flexible than the stack because memory space can be dynamically allocated and de-allocated as needed

>> Heap memory is used to store objects in Java, whereas stack memory is used to store local variables and function call

>> Objects created in the heap are visible to all threads, whereas variables stored in stacks are only visible to the owner as private memory

>> When using recursion, the size of heap memory is more whereas it quickly fill-ups stack memory

Posted Date:- 2021-09-13 04:01:29

## What is a Dequeue?

It is a double-ended queue, or a data structure, where the elements can be inserted or deleted at both ends (FRONT and REAR).

Posted Date:- 2021-09-13 04:00:36

## What is a stack?

A stack is an abstract data type that specifies a linear data structure, as in a real physical stack or piles where you can only take the top item off the stack in order to remove things. Thus, insertion (push) and deletion (pop) of items take place only at one end called top of the stack, with a particular order: LIFO (Last In First Out) or FILO (First In Last Out).

Posted Date:- 2021-09-13 04:00:13

## Are linked lists considered linear or non-linear Data Structures?

Linked lists are considered both linear and non-linear data structures depending upon the application they are used for. When used for access strategies, it is considered as a linear data-structure. When used for data storage, it is considered a non-linear data structure.

Posted Date:- 2021-09-13 03:59:29

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

Recursion, is a function that calls itself based on a terminating condition, makes use of the stack. Using LIFO, a call to a recursive function saves the return address so that it knows how to return to the calling function after the call terminates.

Posted Date:- 2021-09-13 03:58:49

## What are binary trees?

A binary tree is one type of data structure that has two nodes, a left node, and a right node. In programming, binary trees are an extension of the linked list structures.

Posted Date:- 2021-09-13 03:58:13

## What are the different types of linked lists?

The different types of linked lists are:

Posted Date:- 2021-09-13 03:57:43

## What is LIFO?

LIFO is a short form of Last In First Out. It refers how data is accessed, stored and retrieved. Using this scheme, data that was stored last should be the one to be extracted first. This also means that in order to gain access to the first data, all the other data that was stored before this first data must first be retrieved and extracted.

Posted Date:- 2021-09-13 03:57:04

## In what areas do data structures are applied?

Data structures are essential in almost every aspect where data is involved. In general, algorithms that involve efficient data structure is applied in the following areas: numerical analysis, operating system, A.I., compiler design, database management, graphics, and statistical analysis, to name a few.

Posted Date:- 2021-09-13 03:56:45

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

To reference all the elements in a one -dimension array, you need to use an indexed loop, So that, the counter runs from 0 to the array size minus one. In this manner, You can reference all the elements in sequence by using the loop counter as the array subscript.

Posted Date:- 2021-09-13 03:56:03

## When is a binary search best applied?

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.

Posted Date:- 2021-09-13 03:55:37

## Differentiate between file and structure storage structure.

The key difference between both the data structure is the memory area that is being accessed. When dealing with the structure that resides the main memory of the computer system, this is referred to as storage structure. When dealing with an auxiliary structure, we refer to it as file structures.

Posted Date:- 2021-09-13 03:55:19

## What are dynamic arrays?

A dynamic array is an array with a modification that is automatic resizing. This means that the array expands when we add more elements. This helps to provide flexibility as size is not fixed. So, thereâ€™s no need to know the size in advance.

Posted Date:- 2021-09-13 03:54:54

## What is an array?

An array is a collection of data points of the same type stored at contiguous memory locations.

For example, an array of integers like 1,2,3,4,5. This array has 5 elements.

The index of an array usually starts with 0.

Posted Date:- 2021-09-13 03:54:36

## What are Infix, prefix, Postfix notations?

Infix: We write expressions in infix notation, e.g. x+y - z, where operators are used in-between operands. For humans, it goes well, but for computing devices, itâ€™s not preferred.

Prefix: Here, the operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +xy instead of x+y.

Postfix: Here, we use the operator after the operands. For example, X*Y is written as XY*.

Posted Date:- 2021-09-13 03:54:14

## What is the use of dynamic Data Structures?

Dynamic data structures are flexible and size changes can occur during insertion or deletion operations. Dynamic data structures play a key role in programming because they provide the programmer with the flexibility to adjust the memory consumption of programs.

Posted Date:- 2021-09-13 03:53:52

## What are data structures?

A data structure is a way of storing and organization of data values for further use in an application. Examples include Graph, Trees, Arrays, Linked List, etc.

Posted Date:- 2021-09-13 03:53:31