dsa_topic

Note:This isn't a Competitive Programming guide so number theory,game theory,segment trees aren’t mentioned in detail this is to prepare you for majority of DSA that is good for you to be acquainted with for interviews or any other purpose.

This Article provides a comprehensive overview for DSA if interview is coming soon and you have some practice follow leetcode blind sheet 75 for immediate revision.

If you have more time follow 150 problem set from Leetcode/Neetcode since it also covers most of the patterns mentioned below.

But if you really are there looking to understand major topics asked in DSA I have prepared this list.

Platforms to Practise: LeetCode, NeetCode(great platform with nice roadmap and access to important premium questions), SPOJ(All time Classic), CSES Problem Set(really good for DSA Fundamentals).

Revision Sheets you can follow:

LeetCode 75, NeetCode-75,LeetCode 150,NeetCode 150,Striver A-Z(comprehensive)

What i would however highly recommend if you have time:

Its to practice leetcode topic wise before you are ready for revision and go slowly before going for revision sheets you can refer the big sheets for practice but take your time with them.

Problems to solve:

Easy (Concept Retention)
Medium (Application Based)
Hard (These are less common, but it's good to be prepared. Hard questions often involve multiple concepts and specific applications)

Priority must be Medium questions

Questions to be done as follows to stay consistent:

1-2 daily(Mon-Fri)

3 on weekends if you are not occupied

You may increase your frequency over time.

Don’t rush grasp the fundamentals learn things instead of getting overwhelmed all the best.

Mathematics for DSA

Big O Notation
- Describes upper bounds of time and space complexity.
- Understand growth rates: constant, linear, logarithmic, quadratic.
Recursion and Recurrence Relations
- Analyze recursive algorithms.
- Solve recurrence relations (e.g., Master Theorem).
Mathematical Induction
- Prove algorithm correctness and complexity bounds.
Combinatorics
- Understand permutations and combinations for counting data arrangements.
Logarithms
- Know properties of logarithmic functions for algorithms that halve input sizes.
Summation
- Evaluate sums, especially geometric and arithmetic series.
Graph Theory Basics
- Basic concepts of graphs (nodes, edges, paths) for graph algorithms.
Asymptotic Analysis
- Understand limits and their application to function behavior as input sizes grow.

Arrays

Kadane's Algorithm: Finding the maximum subarray sum.
Prefix Sum: Technique for efficient range sum queries.
Sliding Window: For problems involving contiguous subarrays.
Subarray with Given Sum: Finding subarrays that sum to a specified value.
Two Pointers: Technique for solving problems with sorted arrays or linked lists (e.g., Two Sum).
Three Pointers: Techniques like Dutch National Flag and 3Sum.
Product of Array Except Self: Calculating product without using division.
Maximum Product Subarray: Finding the contiguous subarray that has the largest product.
Array Rotation: Techniques for rotating arrays left or right.
Merge Intervals: Merging overlapping intervals.
Spiral Matrix: Traversing a matrix in spiral order.
Trapping Rain Water: Finding the amount of water that can be trapped between bars.

Strings

String Matching Algorithms: KMP, Rabin-Karp, and Naive approach.
Longest Common Subsequence: Finding the longest subsequence present in two sequences.
Palindrome Checking: Techniques to check if a string is a palindrome.
Anagram Checking: Determining if two strings are anagrams of each other.
Substring Search: Finding all occurrences of a substring in a string.
Longest Palindromic Substring: Finding the longest palindromic substring in a string.
String Compression: Techniques for compressing strings (e.g., Run-Length Encoding).
String Encoding: Techniques for encoding strings, such as Base64 encoding or URL encoding.
Reverse Words in a String: Reversing the order of words in a string.
Longest Substring Without Repeating Characters: Finding the length of the longest substring without repeating characters.

Linked Lists

Reversal of Linked List: Techniques to reverse a singly or doubly linked list.
Detecting Cycles: Floyd's Cycle Detection Algorithm (Tortoise and Hare).
Merging Two Sorted Lists: Merging two sorted linked lists into one sorted list.
Intersection of Two Linked Lists: Finding the node where two linked lists intersect.
Flattening a Multilevel Doubly Linked List: Flattening a linked list with next and child pointers.
Removing N-th Node from End: Deleting the N-th node from the end of a linked list.
Partition List: Rearranging a linked list around a given value.
Palindrome Linked List: Checking if a linked list is a palindrome.

Trees

Binary Search Tree (BST): Operations like insertion, deletion, and searching.
Tree Traversals: Inorder, Preorder, Postorder, and Level Order traversals.
Lowest Common Ancestor: Finding the lowest common ancestor in a binary tree.
Balanced Trees: AVL Trees and Red-Black Trees.
Binary Tree Maximum Path Sum: Finding the maximum path sum in a binary tree.
Diameter of a Binary Tree: Finding the longest path between any two nodes in a tree.
Segment Trees: For range queries and updates.
Binary Tree Zigzag Level Order Traversal: Traversing a binary tree in a zigzag fashion.
Symmetric Tree: Checking if a binary tree is symmetric.

Graphs

Graph Traversal Algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS).
Shortest Path Algorithms: Dijkstra's Algorithm and Bellman-Ford Algorithm.
Minimum Spanning Tree: Prim's and Kruskal's algorithms.
Topological Sorting: Ordering of vertices in a directed acyclic graph (DAG).
Graph Representation: Adjacency Matrix vs. Adjacency List.
Strongly Connected Components: Kosaraju's and Tarjan's algorithms.
Graph Coloring: Techniques for coloring graphs with minimal colors.
Number of Islands: Finding the number of islands in a graph.
Course Schedule: Determining if a set of courses can be completed.
Disjoint Set Union (DSU): Union-Find data structure for managing a partition of a set into disjoint subsets.

Greedy Algorithms

Activity Selection Problem: Selecting the maximum number of activities that don't overlap.
Job Sequencing Problem: Scheduling jobs to maximize profit.
Huffman Coding: Efficiently encoding data based on frequency.
Fractional Knapsack Problem: Maximizing value with fractional items.
Minimum Spanning Tree: Using Prim's and Kruskal's algorithms.
Dijkstra’s Shortest Path Algorithm: Finding the shortest path in a weighted graph.
Minimum Cost to Connect Cities: Connecting all cities with minimal cost.
K-Center Problem: Placing K facilities to minimize the maximum distance to a facility.
Bin Packing Problem: Minimizing the number of bins used to pack items.
Set Cover Problem: Covering all elements with the minimum number of sets.

Priority Queue

Heap Implementation: Using binary heaps for priority queue operations.
Dijkstra’s Algorithm: Finding the shortest path using a priority queue.
A Search Algorithm*: Pathfinding and graph traversal.
Median Maintenance: Finding the median of a stream of numbers efficiently.
Job Scheduling: Scheduling jobs based on priority.

Trie

Insert Operation: Adding a word to the Trie.
Search Operation: Checking if a word exists in the Trie.
Prefix Search: Finding all words with a given prefix.
Autocomplete System: Implementing an autocomplete feature using Trie.
Longest Common Prefix: Finding the longest common prefix among a set of strings.

Bit Manipulation

Basic Bitwise Operations: AND, OR, XOR, NOT, and shifts.
Counting Set Bits: Techniques to count the number of set bits in an integer.
Power of Two: Checking if a number is a power of two using bit manipulation.
Swapping Numbers: Swapping two numbers without a temporary variable.
Finding Missing Number: Using XOR to find a missing number in a sequence.
Bit Masking:Problems made easier with the logic of Bit Operations.

Backtracking

N-Queens Problem: Placing N queens on an N×N chessboard.
Sudoku Solver: Filling a partially completed Sudoku grid.
Permutations and Combinations: Generating all permutations and combinations of a set.
Subsets: Finding all subsets of a set.
Word Search: Finding words in a 2D grid of letters.
Combination Sum: Finding all unique combinations where the chosen numbers sum to a specific target.
Palindrome Partitioning: Partitioning a string into palindromes.

Dynamic Programming

Knapsack Problem: 0/1 Knapsack and Fractional Knapsack.
Dynamic Programming on Trees: Solving problems using DP techniques on trees.
Fibonacci Sequence: Using DP to compute Fibonacci numbers efficiently.
Longest Increasing Subsequence: Finding the longest subsequence in a sequence of numbers.
Edit Distance: Finding the minimum number of operations to convert one string into another.
Coin Change Problem: Finding the number of ways to make change for a given amount.
Matrix Chain Multiplication: Finding the most efficient way to multiply a given sequence of matrices.
Longest Common Substring: Finding the longest common substring between two strings.
Distinct Subsequences: Counting the number of distinct subsequences.

DSA Comprehensive Topic List