DSA-Quick-Revison

KO | EN

gitlite — search

#python #java #python3 #tensorflow #machine-learning #opencv #raspberry-pi #javascript #golang #nodejs #blockchain #cnn

DSA-Quick-Revison

★ 14 Open GitHub ↗

No description available.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# DSA-Quick-Revison

Data Structures and Algorithms (DSA) is an important part of Computer Science that deals with the organization of data values and code optimization. To understand more about DSA, let’s break down the word DSA into two parts:

- Data Structures
- Algorithms

A data structure is used for the storage and organization of data values for further use in an application. Talking about an algorithm, it is a stepwise process to solve a problem.

Now, let’s look at some of the most commonly used data structures:

|Data Structure| Meaning |
|---|---|
|Array|It is one of the basic data structures that is like a linear list of data points of the same type.|
|Linked List|This is similar to an array but here it has two fields: Data Field: For data values Reference Field: For storing address|
|Trees|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.|
|Stacks|Imagine a pile of chairs. If you want to add another chair, for that, you will have to add the chair at the top. That’s a stack. Insertion or deletion takes place at the top of the stack of data values. It follows Last-In-First-Out (LIFO) Principle.|
|Queues|A queue in English is a line. Similarly, in DSA, it is a line of data values that follows the FIFO ( First in First out) Principle.|
|Graphs|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.|

## Applications of Data Structures and Algorithms 
Data Structures are used in a wide variety of fields. Some of the important applications include:

## Useful resources to learn DSA

Here is a list of some of the best resources that can help you learn the inside-out of the DSA:

|||
|--|--|
|Books|Data Structures and Algorithms Made Easy Narshima Karumanchi. Introduction to Algorithms (Cormen)|
|Youtube Channels|Abdul Bari Tushar Roy Apni Kaksha Neso Academy Jenny’s Lectures Kunal Kushwaha|
|Online Sites	|Udemy Coursera GeeksforGeeks|

Now, let’s look at some of the important DSA questions.

## Top 51 must-know DSA questions and answers
### 1. 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.

### 2. Name different types of data structures?
Data structures are of two types:
|||
|--|--|
|Linear	| Array, Stack, Queue, Linked-List|
| Non-Linear |	Graphs, Trees |

### 3. 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.

### 4. Name various operations that can be performed in DSA.
Insert: Here, we add a new data item in a data structure.

Search: In this, we find an element in the data structure.

Sort: Simple sorting like arranging values in ascending or descending order. For example, arranging values in an array.

Delete: Here, we delete unwanted data points in a data structure.

Traversal: We access each data item exactly once so that it can be processed for further use.

### 5. 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*.

### 6. What are the types of searching used in Data Structures?

- Linear Search.
- Binary Search.
- Jump Search.
- Interpolation Search.
- Exponential Search.

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

### 8. 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.

### 9. Name some characteristics of Array Data Structure.
- Array elements are stored in contiguous memory blocks in the primary memory.
- Array name represents its base address.
- The base address is the address of the first element of the array.
- Array’s index starts with 0 and ends with size-1.

### 10. What is a linked list?
This is similar to an array but it consists of a node that has two fields:

Data Field: For storing data values.

Reference Field: For storing address.

A linked list is used in the next feature of a music player.

### 11. What are the different types of linked lists?
Ans: The different types of linked lists are:

- Singly Linked list
- Doubly Linked list
- Circular Linked list
- Doubly Circular Linked list

### 12. 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.

### 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:
- Google Maps
- Linkedin
- Facebook

### 14. What's the difference between the data structure Tree and Graph?
Ans: A tree structure is connected and can never have loops whereas in the graph there are no such constraints. A tree provides information about the relationship between nodes in a hierarchical manner and the graph follows a network model.

### 15. What is the LIFO and FIFO principle?
LIFO: (Last-In-First-Out) Last inserted element is removed first in the LIFO principle. Example: Stack follows LIFO.

FIFO: (First-In-First-Out) First Element (first to be inserted) is taken out first.

Example: Queue follows FIFO

### 16. What is a queue?
A queue in English is a line. Similarly, in DSA, it is a line of data values that follows the FIFO ( First in First out) principle. Insertion is done at the rear end and deletion at the front end.

### 17. What is a priority queue?
A priority queue is like a normal queue of elements but here each element has some priority. The elements in the priority queue occur in this order only.

Say, we have some values like 1, 2, 7, 8, 14, 31 inserted in a priority queue with an ordering based on least values to the greatest value. Therefore, the 1 number will have the highest priority while 31 will have the lowest priority.

### 18. What is a stack?
A stack is a linear data structure having values that are inserted as per the LIFO principle. To make the point more clear, imagine a pile of chairs. You want to add another chair, for that, you will have to add the chair at the top. That’s a stack. Insertion or deletion takes place at the top of the stack of data values.

### 19. State the difference between stack and queue?

|Stack|Queue|
|--|--|
|Insertion and deletion in stacks take place only from one end of the list called the top.| Insertion and deletion in queues take place from the opposite ends of the list. The insertion takes place at the rear end of the queue and the deletion takes place from the front end.|
|Insert operation is called push in a stack.| Insert operation is called enqueue operation.|
|Delete operation is called pop in a stack.|Delete operation is called dequeue operation.|

### 20. What is a heap in DSA?
A heap data structure is a complete binary tree that follows a specific order. Heaps are of two types:

- Max Heap
- Min Heap

### 21. What is a binary heap?
- A binary heap is a complete binary tree that satisfies the heap ordering property. 
- A Binary Heap can either be Min Heap or Max Heap.
- It’s a complete tree, thus it is suitable for being stored in an array.

### 22. What is the meaning of the AVL tree?
An AVL tree is a type of binary search tree. It is named after its inventors Adelson, Velskii, and Landis. An AVL tree is a balanced binary search tree where the height of the two subtrees of a node differs by a maximum of one unit.

### 23. 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

### 24. What is the complexity of a Hash Table?
Hash tables provide constant-time O(1) lookup on average, irrespective of the number of items(n) in the table.

### 25. What Data Structures make use of pointers?
- Stack
- Queue 
- Linked List
- Binary Tree.

### 26. What is a dequeue?

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

### 27. 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.

### 28. What is the postfix form of (X + Y) * ( Z - C)
The postfix form of the given expression is XY+ZC-*

### 29. 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.

### 30. What are the Data Structures that are used to represent graphs?
- Adjacency matrix 
- Adjacency list 
- And adjacency set.

### 31. What operations can be performed on stacks?
- push() - Adds an element at the top of the stack. 
- pop() - Deletes an element from the top of the stack.
- peek()- Displays the topmost element.

### 32. Why use queues?
Queues are important in computer science. They are useful in transport, and operations research. They are also useful in a case where resource sharing takes place among a myriad of consumers. For example, FCFS scheduling.

### 33. What is linear search?
Linear search is a technique in which we traverse a list in a sequential manner to find an element. When we find the element that is required, we return the index or position of that element.

### 34. What is binary search?
In this type of search technique, we divide the sorted array or list into two halves. This is done to save time in searching. Here, we consider arrays in sorted form only.

### 35. What are the time complexities of linear search and binary search?
Linear Search-O(N) Binary Search- O(log 2 N)

### 36. Tell me about tree traversal.
Tree traversal is a process that goes through the entire tree in a particular manner. Depending upon the order of traversal, we have different types:

- Inorder Traversal (Left, Root, Right) 
- Preorder Traversal (Root, Left, Right) 
- Postorder Traversal  (Left, Right, Root) 
### 37. 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.

### 38. 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.

### 39. What is a minimum spanning tree (MST)?
It is a spanning tree that has the minimum weight among all the spanning trees of the same graph.

### 40. Explain the Tower of Hanoi Problem.

1. The Tower of Hanoi is a problem that comprises three rods and multiple disks.

2. At the start, all the disks are placed on one rod, one over the other in increasing order.

3. The aim of this problem is to move the stack of disks from the starting rod to another rod, following these rules as below:
    - A disk cannot be placed on top of a smaller disk
    - No disk can be placed on top of the smaller disk.

### 41. What are recursive algorithms?
Recursion in general is a function calling itself. Extending the same logic for Algorithms, we can say that an algorithm that calls itself is a recursive algorithm. One good example of their use would be searching through a file system.  Usually, they are used when the iterative approach is not useful for complex problems.

### 42. Explain why stack is a recursive data structure?
A stack is a recursive data structure because:

- A stack can either be empty or
- It will have a top pointer and the rest part apart from the top is also a stack by itself, thus it’s recursive.

### 43. What is merge sort time complexity?
The time complexity of MergeSort is O(n*log n)

### 44. What is shell sort?
Shell sort is a sorting algorithm based on the insertion sort algorithm.

This algorithm is highly efficient in sorting. This algorithm tries to avoid large shifts as in the case of insertion sort if the smaller value is to the far right and has to be moved to the far left.

### 45. What is quicksort time complexity?
Worst-case time complexity is O(n^2)

### 46. 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.

### 47. 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.

### 48. Which data structures are used for the BFS and DFS of a graph?
- For BFS - Queue Data Structure
- For DFS - Stack Data Structure

### 49. What do you mean by BFS and DFS?

BFS Algorithm stands for Breadth-First Search. It is a vertex-based technique for finding the shortest path in the graph. For BFS, we use a Queue data structure.

DFS Algorithm stands for Depth First Search. It is an edge-based technique. In DFS, traversal can be started from any node. For DFS, we use a stack data structure.

### 50. What is the maximum number of nodes in a binary tree of height k?
Ans: The maximum nodes in a binary tree are: 2k+1-1 where k >= 1.

### 51. What is the difference between the 4 different types of linked lists?
Ans: 1.Single linked list consist of nodes that has member which points to the address of the next node and there is no provision of coming back to the previous node. 
 
 2.Double linked list consists of nodes that has members to point to the address of the previous and next node along with the data of the list. The first node's previous member is NULL and last node's next member is NULL. Here, the list can be traversed in both directions. 
 3.Circular Linked list consists of nodes in which the last node's next member of the list points to the address of the first node and no previous member is present in the node. It is a single circular linked list. 
 4.Double circular linked list consists of both previous and next member in node and the next of last node points to address of the first node and previous of first node points to the address of the last node.

## Need Help in [Web-Development-Path-And-Resources](https://github.com/arpit456jain/Web-Development-Path-And-Resources)
## DSA path And Important Questions [click here](https://github.com/arpit456jain/DSA-Path-And-Important-Questions)
## 11 Weeks Workshop on Data Structures and Algorithms Solution in [python](https://github.com/arpit456jain/gfg-11-Weeks-Workshop-on-DSA-in-Python)
## 11 Weeks Workshop on Data Structures and Algorithms Solution in [C++](https://github.com/arpit456jain/gfg-11-Weeks-Workshop-on-DSA-in-CPP)

## 💬Join Our CodeSmashers Community

Join - https://discord.gg/gtYUZQSjTt

Show some ❤️&nbsp; by giving <img src="https://imgur.com/o7ncZFp.jpg" height=25px width=25px> to this repo

DSA-Quick-Revison

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README