Roadmap for Mastering Data Structures and Algorithms (DSA)
Data Structures are the building blocks of any program. Here's a suggested order to learn them:
Data Structures to Practice:
1. Arrays and Strings
Find the maximum sum of a subarray: https://leetcode.com/problems/maximum-subarray/
Reverse a string: https://www.geeksforgeeks.org/reverse-string-in-c/
Find the longest common substring: https://www.geeksforgeeks.org/problems/longest-common-substring1452/1
Remove duplicate characters from a string: https://www.geeksforgeeks.org/problems/remove-all-duplicates-from-a-given-string4321/1
Implement a search function for a sorted array: https://www.geeksforgeeks.org/problems/search-an-element-in-an-array-1587115621/1
2. Linked Lists
Reverse a linked list: https://leetcode.com/problems/reverse-linked-list/
Merge two sorted linked lists: https://leetcode.com/problems/merge-two-sorted-lists/
Detect a cycle in a linked list: https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
Remove the nth node from a linked list: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
Implement a stack using a linked list: https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/
3. Stacks and Queues
Balance parentheses: https://leetcode.com/problems/valid-parentheses/
Implement a queue using two stacks: https://www.geeksforgeeks.org/problems/queue-using-stack/1
Evaluate a postfix expression: https://www.geeksforgeeks.org/evaluation-of-postfix-expression/
Check if a binary tree is a binary search tree: https://www.geeksforgeeks.org/binary-search-tree-data-structure/
Find the next greater element for each element in an array: https://leetcode.com/problems/next-greater-element-i/
4. Trees and Binary Search Trees
Insert a node into a binary search tree: https://www.geeksforgeeks.org/problems/insert-a-node-in-a-bst/1
Delete a node from a binary search tree: https://leetcode.com/problems/delete-node-in-a-bst/
Find the lowest common ancestor of two nodes in a binary tree:https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
Perform a level-order traversal of a binary tree: https://www.geeksforgeeks.org/problems/level-order-traversal/1
Print all the paths from root to leaf in a binary tree: https://www.geeksforgeeks.org/problems/root-to-leaf-paths/1
5. Graphs
Breadth-first search: https://m.youtube.com/watch?v=Y40bRyPQQr0
Depth-first search: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
Dijkstra's algorithm for shortest path: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Bellman-Ford algorithm for shortest path: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
Floyd-Warshall algorithm for all-pairs shortest path: https://www.geeksforgeeks.org/problems/implementing-floyd-warshall2042/1
6. Hash Tables
Implement a hash table: https://www.geeksforgeeks.org/hash-table-data-structure/
Find the frequency of each element in an array: https://leetcode.com/discuss/interview-question/124724/
Check if two strings are anagrams: https://leetcode.com/problems/valid-anagram/
Find the intersection of two arrays: https://leetcode.com/problems/intersection-of-two-arrays/
Find the union of two arrays: https://www.geeksforgeeks.org/problems/union-of-two-arrays3538/1
In addition to the links above, I also recommend the following resources for practicing data structures:
HackerRank: https://www.hackerrank.com/domains/data-structures
LeetCode: https://leetcode.com/problemset/
Interview Cake: https://www.interviewcake.com/
GeeksforGeeks: https://www.geeksforgeeks.org/
Takeuforward By Striver : https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/
Algorithms to Practice:
1. Sorting Algorithms:
Bubble Sort:
Merge Sort:
LeetCode: https://leetcode.com/tag/merge-sort/
Interview Cake: https://devinterview.io/blog/divide-and-conquer-interview-questions/
Quick Sort:
GeeksForGeeks: https://www.geeksforgeeks.org/cpp-program-for-quicksort/
2. Searching Algorithms:
Linear Search:
HackerRank: https://www.hackerrank.com/domains/data-structures
GeeksForGeeks: https://www.geeksforgeeks.org/linear-search/
Binary Search:
LeetCode: https://leetcode.com/problems/search-insert-position/
Interview Cake: https://www.youtube.com/watch?v=ToubBlGXafI
3. Graph Algorithms:
Breadth-First Search (BFS):
Depth-First Search (DFS):
LeetCode: https://leetcode.com/problems/path-sum/
HackerRank: https://www.hackerrank.com/topics/depth-first-search/
4. Dynamic Programming:
LeetCode: https://leetcode.com/tag/dynamic-programming/
- Contains a variety of problems with difficulty levels ranging from easy to hard.
GeeksForGeeks: https://www.geeksforgeeks.org/dynamic-programming/
- Offers many articles and problems on different DP techniques.
TakeUForward: https://takeuforward.org/category/dynamic-programming/
- Provides video lectures and problem-solving approaches for DP.
5. Greedy Algorithms:
LeetCode: https://leetcode.com/tag/greedy/
- A curated list of problems focused on greedy algorithms.
HackerRank: https://www.hackerrank.com/domains/algorithms/greedy/difficulty:easy/page:1
- Contains various challenges involving applying greedy techniques.
GeeksForGeeks: https://www.geeksforgeeks.org/greedy-algorithms/
- Offers explanations and problems categorized by difficulty.
Remember, the best way to improve your understanding of algorithms is to practice solving problems. Start with easier problems and gradually progress to more challenging ones. Don't hesitate to refer to explanations and tutorials if you get stuck.
Problem Solving Techniques:
Divide and Conquer
Problem: Find the maximum subarray sum in a given array.
Link: https://leetcode.com/problems/maximum-subarray/
Opens in a new window
geeksforgeeks.orgMaximum subarray sum problem
Solution: This problem can be solved using the divide-and-conquer technique by dividing the array into two halves, finding the maximum subarray sum in each half, and then comparing the maximum subarray sums of the two halves to find the overall maximum subarray sum.
Recursion
Problem: Print all the permutations of a given string.
Link: https://leetcode.com/problems/permutations/
Opens in a new window
geeksforgeeks.orgPermutations of a string problem
Solution: This problem can be solved using recursion by considering each character of the string one at a time and recursively generating all the permutations of the remaining characters.
Backtracking
Problem: Solve the N-Queens problem.
Link: https://leetcode.com/problems/n-queens/
Opens in a new window
medium.comNQueens problem
Solution: The N-Queens problem is the problem of placing N queens on an N×N chessboard such that no two queens can attack each other. This problem can be solved using backtracking by trying to place queens one at a time on the chessboard and recursively checking if the placement is valid.
Sliding Window
Problem: Find the longest substring without repeating characters in a given string.
Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/
Opens in a new window
medium.comLongest substring without repeating characters problem
Solution: This problem can be solved using the sliding window technique by maintaining a window of characters and checking if all the characters in the window are unique. If all the characters in the window are unique, then the window is expanded by one character. Otherwise, the window is shrunk by one character.
Two Pointers
Problem: Find the two numbers in a sorted array that add up to a given target.
Link: https://leetcode.com/problems/two-sum/
Opens in a new window
chegg.comTwo numbers in a sorted array that add up to a given target problem
Solution: This problem can be solved using the two-pointer technique by having one pointer at the beginning of the array and another pointer at the end of the array. The two pointers are moved towards each other until the sum of the elements pointed to by the two pointers is equal to the target.
Bit Manipulation
Problem: Count the number of set bits in a given integer.
Link: https://leetcode.com/problems/number-of-1-bits/
Opens in a new window
geeksforgeeks.orgCount the number of set bits in a given integer problem
Solution: This problem can be solved using bit manipulation by repeatedly checking the least significant bit of the integer and adding 1 to the count if the bit is set. The integer is then right-shifted by one bit and the process is repeated until the integer becomes zero.