DSA-MASTERY
</br>
</br>
[!TIP] DSA Mastery in 9 Weeks: Read, Solve, Code!
This repository covers the roadmap for mastering Data Structures and Algorithms in JavaScript, Python, C/C++, and Java.
| TABLE OF CONTENTS | ||
|---|---|---|
| • | DSA Roadmap | |
| • | JavaScript DSA | |
| • | Python DSA | |
| • | C/C++ DSA | |
| • | Java DSA | |
| • |
Data Structures and Algorithms Roadmap
5 steps to Mastering DSA
Mastering DSA as a beginner is simplified into 5 steps:
- Choose a programming language.
- Understand time and space complexities.
- Learn basic data structures and algorithms.
- Practice a lot.
- Join competitions to get really good.
INDEX
| Steps | Table of Contents |
|---|---|
| 1. | Master at least one Programming Language |
| 2. | Understand Complexities |
| 3. | <summary>Learn essential Data Structures and Algorithms, including:</summary><p> ◌ 3.1 - Mathematics Basic </br> ◌ 3.2 - Array</br> ◌ 3.3 - String</br> ◌ 3.4 - Stack</br> ◌ 3.5 - Queue</br> ◌ 3.6 - Searching Algorithm</br> ◌ 3.7 - Sorting Algorithm</br> ◌ 3.8 - Divide and Conquer Algorithm</br> ◌ 3.9 - Linked List</br> ◌ 3.10 - Tree Data Structure</br> ◌ 3.11 - Graph Data Structure</br> ◌ 3.12 - Recursion</br> ◌ 3.13 - Backtracking Algorithm</br> ◌ 3.14 - Dynamic Programming</br> ◌ 3.15 - Greedy Methodology</br> ◌ 3.16 - Mathematics Advanced </p> |
| 4. | Practice consistently and extensively |
| 5. | Compete to advance and become proficient |
1. Master at least one Programming Language
Embark on your data structures and algorithms journey by mastering a programming language. Just as we learn the alphabet and grammar before writing essays, understanding the basics of a language is essential for programming.
Choose a language, whether it’s Java, C, C++, Python, or any other of your preference. Before diving into coding, grasp the foundational elements of the language, including basic syntax, data types, variables, operators, conditional statements, loops, functions, etc. Optionally, explore Object-Oriented Programming (OOP) concepts to strengthen your coding foundation.
2. Understand Complexities
Now, let’s delve into an interesting and crucial topic. The main goal of using DSA is to solve problems effectively and efficiently. How do you assess if your program is efficient? This is where complexities come in, and there are two types:
- Time Complexity: It measures the time needed to execute the code.
- Space Complexity: It indicates the space required for the code to function successfully.
- Design And Analysis Of Algorithms
- Designing efficient algorithms and analyzing their performance.
- Lecture Notes: Design And Analysis Of Algorithms
In DSA, you’ll often encounter the term Auxiliary Space, referring to extra space used in the program beyond the input data structure.
It overlooks system-dependent constants and focuses solely on the number of modular operations performed in the entire program. Three commonly used asymptotic notations describe the time complexity of algorithms:
- Big-O Notation (Ο): Describes the worst-case scenario.
- Omega Notation (Ω): Specifies the best-case scenario.
- Theta Notation (θ): Represents the average complexity of an algorithm.
Asymptotic analysis (Big-O notation)
Basics: Asymptotic analysis
◌ Big-O notation in 5 minutes | YouTube |
◌ Particularly for Big-O notation | runestone.academy |
Advanced: Asymptotic analysis
◌ A beginner's guide to Big O notation | rob-bell.net |
◌ Particularly for Big-O notation | YouTube |
◌ Lecture 2: Asymptotic Notation CSCI 700 | web.archive.org |
Practice: Time and Space Complexity
◌ MCQs: Time and Space Complexity | CodeChef |
◌ Particularly for Big-O notation | YouTube |
◌ Practice Problems | IITK Lecture Practice |
3. Learn essential Data Structures and Algorithms
◌ 3.1 - Mathematics Basic </br> ◌ 3.2 - Array </br> ◌ 3.3 - String </br> ◌ 3.4 - Stack </br> ◌ 3.5 - Queue </br> ◌ 3.6 - Searching Algorithm </br> ◌ 3.7 - Sorting Algorithm </br> ◌ 3.8 - Divide and Conquer Algorithm </br> ◌ 3.9 - Linked List </br> ◌ 3.10 - Tree Data Structure </br> ◌ 3.11 - Graph Data Structure </br> ◌ 3.12 - Recursion </br> ◌ 3.13 - Backtracking Algorithm </br> ◌ 3.14 - Dynamic Programming </br> ◌ 3.15 - Greedy Methodology </br> ◌ 3.16 - Mathematics Advanced
3.1 Mathematics Basic
Basic Mathematics in DSA
- Fundamental for evaluating algorithm effectiveness.
- Essential for problems with mathematical characteristics.
- Crucial for mastering Data Structures and Algorithms.
Resources: Mathematics
3.2 Array
The array is a fundamental and crucial data structure, presenting a linear arrangement of elements. It serves as a collection of homogeneous data types, with elements allocated contiguous memory. Thanks to this contiguous allocation, accessing any array element occurs in constant time. Each array element is identified by a corresponding index number.
Additional Array Topics to Explore
- Rotation of Array: Shifting elements in a circular manner, such as right circular shift where the last element becomes the first.
- Rearranging an array: Changing the initial order of elements based on specific conditions or operations.
- Range queries in the array: Performing operations on a range of elements, often referred to as range queries.
- Multidimensional array: Arrays with more than one dimension, commonly encountered in the form of 2-dimensional arrays, known as matrices.
- Kadane’s algorithm
- Dutch national flag algorithm
Resources: Arrays
◌ Data Structure Tutorial: Array |
CodeChef |
◌ Arrays: Lecture Notes |
cs.cmu.edu |
◌ Arrays Data Structure |
geeksforgeeks.org |
Practice Problems: Arrays
◌ Little Elephant and Candies |
CodeChef: LECANDY | Editorial |
◌ Chef and Notebooks |
CodeChefL CNOTE | Editorial |
◌ The Minimum Number Of Moves |
CodeChef: SALARY | Editorial |
◌ Mutated Minions |
CodeChef: CHN15A | Editorial |
◌ Chef and Rainbow Array |
CodeChef: RAINBOWA | Editorial |
◌ Forgotten Language |
CodeChef: FRGTNLNG | Editorial |
◌ Leetcode: Interview Practice |
Leetcode: Practice Arrays | Interview Level |
3.3 String
A string, essentially a type of array, can be seen as an array of characters. However, it possesses distinct features, such as the last character being a null character to signify the string’s end. Unique operations, like concatenation merging two strings into one, further set strings apart.
Additional String Concepts to Explore
- Subsequence and Substring: A subsequence is derived from a string by deleting one or more elements, while a substring is a contiguous segment of the string.
- Reverse and Rotation in a String: Reversing involves interchanging character positions, while rotation shifts elements circularly.
- Binary String: Comprising only two types of characters.
- Palindrome: A string with elements equidistant from its center being the same.
- Lexicographic Pattern: A pattern based on ASCII values or in dictionary order.
- Pattern Searching: Advanced topic involving searching for a given pattern within the string.
Resources: Strings
◌ C++ Strings |
tutorialspoint.com |
◌ Java strings |
guru99.com |
◌ Python strings |
docs.python.org |
◌ Python strings |
tutorialspoint.com |
◌ Many string questions |
geeksforgeeks.org |
Practice Problems: Strings
◌ Count Substrings |
CodeChef: CSUB | Editorial |
◌ Lapindromes |
CodeChefL LAPIN | Editorial |
◌ Leetcode: Interview Practice |
Leetcode: Practice Strings | Interview Level |
3.4 Stack
Transitioning to more complex data structures, let’s explore the Stack and Queue.
A Stack is a linear data structure that adheres to a specific order for its operations. This order can be LIFO (Last In First Out) or FILO (First In Last Out).
The complexity of the Stack as a data structure arises from its implementation, utilizing other data structures like Arrays, Linked lists, etc., chosen based on the characteristics and features specific to the Stack data structure.
Resources: Stacks
◌ Stack Data Structure |
geeksforgeeks.org |
◌ Stack Data Structure |
tutorialspoint.com |
◌ Stacks: Lecture Notes |
cs.cmu.edu |
Practice Problems: Stacks
◌ Just Next |
spoj.com: JNEXT |
◌ Transform the Expression |
spoj.com: ONP |
◌ Largest Rectangle in a Histogram |
spoj.com: HISTOGRA |
◌ Compilers and parsers |
CodeChefL COMPILER |
◌ Leetcode: Interview Practice |
Leetcode: Practice Stacks |
3.5 Queue
Similar to a Stack but with distinct characteristics, the Queue is another linear data structure.
A Queue operates on the principle of First In First Out (FIFO) in its individual operations.
Different types of queues include:
- Circular Queue: The last element is connected to the first element, forming a circular structure.
- Double-ended Queue (Deque): Allows operations from both ends of the queue.
- Priority Queue: Elements are arranged based on priority, with lower-priority elements dequeued after higher-priority ones.
Resources: Queues
◌ Array Implementation of Queue |
geeksforgeeks.org |
◌ Stacks and Queues |
viterbi-web.usc.edu |
◌ Stacks and Queues |
cs.cmu.edu |
Practice Problems: Queues
◌ Mass of Molecule |
spoj.com: MMASS |
◌ Transform the Expression |
spoj.com: ONP |
◌ Maximum Xor Secondary |
codeforces.com: 281/D |
◌ Longest Regular Bracket Sequence |
codeforces.com: contest/5/problem/C |
◌ Alternating Current |
codeforces.com: contest/343/problem/B |
◌ Seinfeld |
spoj.com: ANARC09A |
◌ Leetcode: Interview Practice |
Leetcode: Practice Queues |
3.6 Searching Algorithm
Having explored linear data structures, it’s time to delve into fundamental and widely used algorithms, starting with searching algorithms. Searching algorithms aim to locate a specific element in an array, string, linked list, or other data structures. Key searching algorithms include:
- Linear Search: Iteratively checks for the element from one end to the other.
- Binary Search: Divides the data structure into two equal parts to locate the element.
- Ternary Search: Divides the array into three parts, determining the segment to search based on partitioning values.
Other notable searching algorithms include:
- Jump Search
- Interpolation Search
- Exponential Search
Resources: Searching
◌ Naive string searching |
geeksforgeeks.org |
◌ Detailed Theoretical analysis |
cmu.edu |
◌ Binary search |
khanacademy.org |
Practice Problems: Searching
◌ Searching Algorithms |
geeksforgeeks.org |
◌ GFG: Binary Search |
geeksforgeeks.org |
◌ Leetcode: Interview Practice |
Leetcode: Practice Binary-Search |
3.7 Sorting Algorithm
Another crucial algorithm is the sorting algorithm, frequently employed when arranging data based on specific conditions becomes necessary. Sorting algorithms are utilized to rearrange a set of homogeneous data, such as sorting an array in increasing or decreasing order.
These algorithms rearrange the elements of a given array or list according to a comparison operator. The comparison operator determines the new order of elements in the respective data structure.
Widely Used Sorting Algorithms
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
Numerous other sorting algorithms exist, each beneficial in different scenarios.
Resources: Sorting
◌ Sorting |
khanacademy.org |
◌ BUBBLE SORT |
visualgo.net |
◌ Merge sort algorithm |
youtube.com |
◌ Quick sort algorithm |
youtube.com |
◌ Counting Sort |
geeksforgeeks.org |
Practice Problems: Sorting
◌ Merge Sort |
CodeChef: MRGSRT |
◌ Turbo Sort |
CodeChef: TSORT |
◌ Merge Sort |
CodeChef: MRGSRT |
◌ Leetcode: Interview Practice |
Leetcode: Practice Sorting |
3.8 Divide and Conquer Algorithm
An intriguing and significant algorithm to learn in your programming journey is the Divide and Conquer algorithm. True to its name, it breaks down a problem into parts, solves each subproblem, and then merges the solutions to address the original problem.
The algorithmic paradigm of Divide and Conquer involves three key steps:
- Divide: Break the given problem into subproblems of the same type.
- Conquer: Recursively solve these subproblems.
- Combine: Appropriately combine the answers.
This technique is prominently featured in two sorting algorithms—Merge Sort and Quick Sort.
Resources: Divide and Conquer
◌ Divide-and-Conquer and Recurrences |
cs.cmu.edu |
◌ Divide and Conquer |
geeksforgeeks.org |
Practice Problems: Divide and Conquer
◌ Merge Sort |
codechef.com: MRGSRT |
◌ Tasty Dishes |
codechef.com: TASTYD |
◌ Restore the Permutation |
codechef.com: RESTPERM |
◌ A Magical Length |
codechef.com: ACM14KP1 |
◌ Largest Rectangle in a Histogram |
spoj.com: HISTOGRA |
◌ Compilers and parsers |
CodeChefL COMPILER |
◌ Leetcode: Interview Practice |
Leetcode: Practice Divide and Conquer |
3.9 Linked List
Similar to the aforementioned data structures, a linked list is a linear data structure. However, unlike an array, a linked list doesn’t have contiguous memory allocation. Instead, each node in the linked list is assigned to a random memory space, and the previous node maintains a pointer to this node. Direct memory access to any node is not possible, and the linked list is dynamic, allowing for size adjustments at any time.
Linked List Variations to Explore
- Singly Linked List: Each node points only to its next node.
- Circular Linked List: The last node points back to the head of the linked list.
- Doubly Linked List: Each node holds two pointers—one pointing to the next node and the other to the previous node.
Resources: Linked List
◌ Linked List Data Structure |
geeksforgeeks.org |
Practice Problems: Linked List
◌ Leetcode: Interview Practice |
Leetcode: Practice Linked List |
3.10 Tree Data Structure
Having covered the basics of linear data structures, let’s delve into non-linear structures, starting with the Tree.
The Tree data structure resembles an inverted tree from nature, featuring a root and leaves. The root is the initial node, and the leaves are at the bottom-most level. Notably, there’s only one path between any two nodes in a tree.
Based on the maximum number of children a node can have:
- Binary Tree: Each node can have a maximum of 2 children.
- Ternary Tree: Each node can have a maximum of 3 children.
- N-ary Tree: A node can have at most N children.
Additional classifications based on node configuration include:
- Complete Binary Tree: All levels are filled, except possibly for the last level, which is filled from the left as much as possible.
- Perfect Binary Tree: All levels are filled.
- Binary Search Tree: A special binary tree where smaller nodes are on the left, and higher value nodes are on the right.
- Ternary Search Tree: Similar to a binary search tree, but with nodes having at most 3 children.
Resources: Trees
◌ Tree Data Structure |
geeksforgeeks.org |
◌ Heaps (priority queue) |
viterbi-web.usc.edu |
◌ Heaps |
visualgo.net |
◌ Priority Queues: Lecture Notes |
cs.cmu.edu |
◌ UNION-FIND DISJOINT SETS (UFDS) |
visualgo.net |
◌ DISJOINT-SET DATA STRUCTURES |
topcoder.com |
◌ Disjoint set (Union-Find): Lecture Notes |
harvard.edu |
◌ Segment Trees: MIN SEGMENT TREE |
visualgo.net |
◌ RANGE MINIMUM QUERY AND LOWEST COMMON ANCESTOR |
topcoder.com |
◌ Segment Trees |
iarcs.org.in |
◌ BINARY INDEXED TREES: TopCoder |
topcoder.com |
◌ Binary Index Tree (Fenwick tree) |
visualgo.net |
◌ Binary Index Tree: ICO |
iarcs.org.in |
◌ Trees (traversals) |
berkeley.edu |
◌ Dynamic programming on trees |
iarcs.org.in |
Practice Problems: Trees
3.11 Graph Data Structure
Moving on to another crucial non-linear structure, let’s explore the Graph. Unlike the Tree, a Graph lacks a specific root or leaf node and allows traversal in any order.
A Graph is a non-linear structure composed of a finite set of vertices (or nodes) and a set of edges connecting pairs of nodes. It proves invaluable in solving various real-life problems. Graphs can take different forms based on edge orientation and node characteristics.
Key concepts to explore:
- Types of Graphs: Varying types based on connectivity or weights of nodes.
- Introduction to BFS and DFS: Algorithms for traversing through a graph.
- Cycles in a Graph: Series of connections leading to a loop.
- Topological Sorting in the Graph
- Minimum Spanning Tree in Graph
Resources: Graphs
◌ Graph Data Structure And Algorithms |
geeksforgeeks.org |
◌ Depth First Search or DFS for a Graph |
geeksforgeeks.org |
◌ GRAPH TRAVERSAL (DFS/BFS) |
visualgo.net |
◌ Dijkstra’s shortest path algorithm<h/b></p></td> | geeksforgeeks.org | </tr>
◌ SINGLE-SOURCE SHORTEST PATHS |
visualgo.net |
◌ Bellman Ford Algorithm |
geeksforgeeks.org |
◌ One Source Shortest Path |
compprog.wordpress.com |
◌ Minimum spanning tree |
cs.princeton.edu |
◌ Articulation points |
iarcs.org.in |
◌ Strongly connected components |
iarcs.org.in |
◌ Topological Sorting |
geeksforgeeks.org |
◌ Euler Paths and Euler Circuits |
jlmartin.ku.edu |
◌ Fast Modulo Multiplication |
codechef.com |
◌ Algos for Calculating nCr % M |
codechef.com |
◌ Two Closest |
codechef.com: PAIRCLST |
◌ Special Shortest Walk |
codechef.com: SPSHORT |
◌ Robot Control |
codeforces.com: 346/D |
◌ Arbitrage |
spoj.com: ARBITRAG |
◌ Cost |
spoj.com: HIGHWAYS |
◌ Police Query |
spoj.com: POLQUERY |
◌ Visiting Friends |
codechef.com: MCO16405 |
◌ Chef and Roads |
codechef.com: CL16BF |
◌ Codechef Password Recovery |
codechef.com: CHEFPASS |
◌ Tanya and Password |
codeforces.com: contest/508/problem/D |
◌ One-Way Reform |
codeforces.com: contest/723/problem/E |
◌ Problem Statement for NetworkSecurity |
topcoder.com |
◌ Leetcode: Interview Practice |
Leetcode: Practice Graphs |
Resources: Recursion
◌ AN INTRODUCTION TO RECURSION PART ONE |
topcoder.com |
◌ AN INTRODUCTION TO RECURSION PART TWO |
topcoder.com |
◌ Introduction to Recursion |
geeksforgeeks.org |
◌ Backtracking, Memoization & Dynamic Programming! |
loveforprogramming.quora.com |
◌ Recursion Interview Questions & Tips |
interviewing.io |
◌ Connecting Soldiers |
codechef.com: NOKIA |
◌ Fit Squares in Triangle |
codechef.com: TRISQ |
◌ Leetcode: Interview Practice |
Leetcode: Practice Recursion |
◌ Backtracking Algorithms |
geeksforgeeks.org |
◌ Recursion and Backtracking |
codeforces.com |
◌ Backtracking:the essential part of dynamic programming |
codeforces.com |
◌ Backtracking, Memoization & Dynamic Programming! |
loveforprogramming.quora.com |
◌ Backtracking Archives |
geeksforgeeks.org |
◌ Leetcode: Interview Practice |
Leetcode: Practice Backtracking |
Resources: Basic Dynamic Programming
◌ Demystifying Dynamic Programming |
freecodecamp.org |
◌ DP Tutorial and Problem List |
codeforces.com |
◌ DYNAMIC PROGRAMMING: FROM NOVICE TO ADVANCED |
topcoder.com |
◌ Dynamic Programming |
geeksforgeeks.org |
◌ Backtracking, Memoization & Dynamic Programming! |
loveforprogramming.quora.com |
◌ Alternating subarray prefix |
codechef.com: ALTARAY |
◌ Subtraction Game 2 |
codechef.com: AMSGAME2 |
◌ Striver DP Series |
takeuforward.org |
◌ Leetcode: Interview Practice |
Leetcode: Practice Dynamic Programming |
◌ Dynamic Programming over Subsets and Paths |
codeforces.org |
Practice Problems: Adv Dynamic Programming
◌ Histogram |
spoj.com: HIST2 |
◌ Lazy Cows |
spoj.com: LAZYCOWS |
◌ Traveling by Stagecoach |
spoj.com: TRSTAGE |
◌ Rent your airplane and make money |
spoj.com: RENT |
◌ Increasing Subsequences |
spoj.com: INCSEQ |
◌ Distinct Increasing Subsequences |
spoj.com: INCDSEQ |
◌ Dynamic Programming Type |
codechef.com: problem list |
◌ Striver DP Series |
takeuforward.org |
◌ Leetcode: Interview Practice |
Leetcode: Practice Dynamic Programming |
◌ Greedy Algorithms |
geeksforgeeks.org |
◌ Greedy Algorithms |
iarcs.org.in |
◌ GREEDY IS GOOD |
topcoder.com |
◌ GREEDY IS GOOD |
jeffe.cs.illinois.edu |
Practice Problems: Greedy
◌ Biased Standings |
spoj.com: BAISED |
◌ Load Balancing |
spoj.com: BALIFE |
◌ Many Chefs |
codechef.com: MANYCHEF |
◌ Leetcode: Interview Practice |
Leetcode: Practice Greedy |
Resources: Mathematics
| GFG: Mathematical Algorithms for DSA |
| Codeforces: Mathematical Blogs on DSA |
Practice Problems: Mathematics
| Leetcode: Practice Math |
Copyright © 2023 - 2024 SERVER-X-101 All rights reserved.