- DSA Full Form
- What is DSA?
- How to Learn DSA
- Learn Data Structures
- Learn Algorithms
- Learn About Complexities
- Practice Problem Cheat Sheets
- Manual Notes
The term DSA stands for Data Structures and Algorithms in the context of Computer Science.
Data Structures and Algorithms (DSA) refer to the study of methods for organizing and storing data and the design of procedures (algorithms) for solving problems that operate on these data structures.
The process of learning DSA can be broken down into five parts:
- Learn at least one programming language.
- Learn Data Structures.
- Learn Algorithms.
- Learn about Time and Space complexities.
- Practice Problems on DSA.
Data structures are essential components that help organize and store data efficiently in computer memory. Common data structures include arrays, linked lists, stacks, queues, trees, and graphs.
An array is a linear data structure that stores a collection of elements of the same data type. Elements are allocated contiguous memory, allowing for constant-time access.
- Traversal: Iterating through the elements of an array.
- Insertion: Adding an element to the array at a specific index.
- Deletion: Removing an element from the array at a specific index.
- Searching: Finding an element in the array by its value or index.
- One-dimensional array: A simple array with a single dimension.
- Multidimensional array: An array with multiple dimensions, such as a matrix.
- Storing data in a sequential manner.
- Implementing queues, stacks, and other data structures.
- Representing matrices and tables.
A string is a sequence of characters, typically used to represent text.
- Concatenation: Joining two strings together.
- Comparison: Comparing two strings lexicographically.
- Substring extraction: Extracting a substring from a string.
- Search: Searching for a substring within a string.
- Modification: Changing or replacing characters within a string.
- Text processing.
- Pattern matching.
- Data validation.
- Database management.
A linked list is a linear data structure that stores data in nodes, which are connected by pointers. Unlike arrays, linked lists are not stored in contiguous memory locations.
- Creation: Creating a new linked list or adding a new node to an existing list.
- Traversal: Iterating through the list and accessing each node.
- Insertion: Adding a new node at a specific position in the list.
- Deletion: Removing a node from the list.
- Search: Finding a node with a specific value in the list.
- Singly Linked List: Each node points to the next node in the list.
- Doubly Linked List: Each node points to both the next and previous nodes in the list.
- Circular Linked List: The last node points back to the first node, forming a circular loop.
- Implementing queues and stacks.
- Representing graphs and trees.
- Maintaining ordered data.
- Memory management.
- Linked List Tutorial
- Top 50 Problems on Linked List for Interviews
- Practice problems on Linked Lists
A matrix is a two-dimensional array of elements, arranged in rows and columns.
- Image processing.
- Data analysis.
- Optimization problems.
A stack is a linear data structure that follows a LIFO (Last In First Out) or FILO (First In Last Out) order.
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the element at the top of the stack.
- Peek: Returns the element at the top of the stack without removing it.
- Size: Returns the number of elements in the stack.
- IsEmpty: Checks if the stack is empty.
- Function calls.
- Expression evaluation.
- Backtracking.
- Undo/redo operations.
A queue follows the FIFO (First In First Out) principle.
- Enqueue: Adds an element to the rear of the queue.
- Dequeue: Removes an element from the front of the queue.
- Peek: Retrieves the front element without removing it.
- IsEmpty: Checks if the queue is empty.
- IsFull: Checks if the queue is full.
- Circular Queue: Last element connects to the first element.
- Double-Ended Queue (Deque): Operations can be performed from both ends.
- Priority Queue: Elements are arranged based on priority.
- Job scheduling.
- Message queuing.
- Simulation modeling.
- Data buffering.
A heap is a complete binary tree that satisfies the heap property.
- Insert: Adds a new element to the heap while maintaining heap properties.
- Extract-Max/Extract-Min: Removes the root element and restructures the heap.
- Increase/Decrease-Key: Updates the value of a node and restructures the heap.
- Max-Heap: Root node has the maximum value among its children.
- Min-Heap: Root node has the minimum value among its children.
- Priority queues.
- Sorting.
- Graph algorithms (e.g., Dijkstra’s algorithm).
Hashing generates a fixed-size output (hash value) from an input of variable size.
- Hash Function: Maps an input to a hash value.
- Hash Table: Stores key-value pairs.
- Collision: When two different keys produce the same hash value.
- Separate Chaining (Open Hashing): Stores colliding elements in a linked list at the corresponding hash value.
- Open Addressing (Closed Hashing): Finds an alternative location for colliding elements within the hash table.
- Efficiently storing and retrieving data in databases and file systems.
- Verifying passwords and digital signatures.
- Distributing requests across multiple servers.
- Generating secure hashes for data integrity and authentication.
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
- In-Order: Visit left subtree, current node, then right subtree.
- Pre-Order: Visit current node, left subtree, then right subtree.
- Post-Order: Visit left subtree, right subtree, then current node.
- Binary Tree: Each node has at most two children.
- Ternary Tree: Each node has at most three children.
- N-ary Tree: Each node has at most N children.
- Binary Search Tree (BST): Left child < parent < right child.
- Heap: Specialized binary tree with the heap property.
- Balanced Tree: Heights of subtrees differ by at most one.
- Unbalanced Tree: Heights of subtrees can differ significantly.
- Organizing hierarchical data (e.g., file systems, XML/HTML documents).
- Representing relationships (e.g., organizational structures, family trees).
- Efficient searching and sorting (e.g., binary search trees, AVL trees).
- Storing data in memory (e.g., heap, trie, segment trees).
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges.
- Vertex (Node): Fundamental unit of a graph.
- Edge (Link): Connection between two vertices.
- Directed Graph: Edges have direction.
- Undirected Graph: Edges have no direction.
- Weighted Graph: Edges have weights.
- Unweighted Graph: Edges have no weights.
- Adjacent: Two vertices connected by an edge.
- Path: Sequence of vertices connected by edges.
- Cycle: Path that starts and ends at the same vertex.
- Degree: Number of edges connected to a vertex.
- Adjacency Matrix: 2D array representing edge presence.
- Adjacency List: List of adjacent vertices for each vertex.
- Representing networks (e.g., social networks, communication networks).
- Finding shortest paths (e.g., GPS navigation, Dijkstra’s algorithm).
- Modeling relationships and dependencies (e.g., task scheduling, dependency graphs).
- Analyzing data structures (e.g., trees, finite state machines).
Algorithms are step-by-step procedures for solving specific problems. They play a crucial role in computer science and software development, providing efficient solutions to a wide range of problems.
Searching algorithms are designed to find specific elements within data structures.
- Linear Search: Sequentially checks each element.
- Binary Search: Efficiently searches in a sorted array by dividing the search space in half.
- Information retrieval.
- Database management.
- Optimization problems.
- Searching Algorithms Tutorial
- Top 50 Problems on Searching Algorithms for Interviews
- Practice problems on Searching Algorithms
Sorting algorithms arrange elements in a specific order.
- Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.
- Selection Sort: Selects the smallest element and swaps it with the first unsorted element.
- Insertion Sort: Builds the sorted array one element at a time by inserting each new element in its correct position.
- Merge Sort: Divides the array into halves, recursively sorts each half, and merges the sorted halves.
- Quick Sort: Divides the array into subarrays based on a pivot, sorts each subarray, and combines them.
- Data organization.
- Searching and filtering.
- Optimization problems.
- Sorting Algorithms Tutorial
- Top 50 Problems on Sorting Algorithms for Interviews
- Practice problems on Sorting Algorithms
Divide and Conquer algorithms solve problems by breaking them down into smaller subproblems, solving each subproblem independently, and combining their solutions.
- Sorting (e.g., Merge Sort, Quick Sort).
- Searching (e.g., Binary Search).
- Matrix multiplication (e.g., Strassen's algorithm).
- Divide and Conquer Tutorial
- Top 50 Problems on Divide and Conquer Algorithms for Interviews
- Practice problems on Divide and Conquer Algorithms
Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum.
- Optimization problems.
- Shortest path problems.
- Greedy Algorithms Tutorial
- Top 50 Problems on Greedy Algorithms for Interviews
- Practice problems on Greedy Algorithms
Recursion is a programming technique where a function calls itself to solve a problem.
- Tree and graph traversal.
- Searching algorithms.
- Divide and conquer algorithms.
Backtracking is a technique for finding solutions to combinatorial problems by systematically exploring all potential candidates.
- Solving puzzles (e.g., Sudoku, N-Queens).
- Generating permutations and combinations.
- Constraint satisfaction problems.
This README.md file provides an overview of memory management and function calls in C++.
- All pointers of all types take the same size of 8 bytes.
- Declaration in heap memory in C++ is done using the
newkeyword. - For an array:
a = new int[5]; - For a structure:
a = new rectangle;
- Call by value in function is not suitable for changing the value of actual parameters.
- Call by address is used when we have to change the value of actual parameters.
- Call by reference: the formal parameters becomes the nickname for actual parameters, thus can change the value of actual parameters.
- When returning an array from a function, use a pointer:
int* fun(int n) {
int* p;
p = new int[n];
return (p);
}
int main() {
int* A;
A = fun(5);
}- Arrays are always passed by address, never by value.
- On passing array to a function, we can use
*instead of[]. - Array cannot be passed as call by value to a function, but while using array inside the structure, we can use call by value.
- For creating objects of class in C++, the syntax is
classname objectname;. - Use
::as scope resolution to define the function outside the class. - For destroying or removing heap memory, use a destructor:
~class name(){}. - While changing the class to template class, we have to mention the template type after scope resolution also:
template <class T> class Arithmetic{};.
- Array is created in heap or in stack.
- Linked list is always created in heap.