This roadmap provides a step-by-step guide to mastering Data Structures and Algorithms (DSA). It includes an introduction to DSA, detailed explanations of key concepts, and free resources for Java, C++, Python, and JavaScript.

Introduction to Data Structures and Algorithms (DSA)

What are Data Structures and Algorithms?

• Data Structures are ways to organize and store data in a computer so that it can be accessed and modified efficiently. Examples include arrays, linked lists, stacks, queues, trees, and graphs.
• Algorithms are step-by-step procedures or methods for solving problems. They are used to manipulate the data stored in data structures. Examples include sorting algorithms (e.g., Quick Sort) and search algorithms (e.g., Binary Search).

Why Learn DSA?

• Efficiency: DSA helps you write efficient and optimized code, which is crucial for handling large datasets and real-world applications.
• Problem Solving: DSA is the foundation of computer science and is essential for solving complex problems in programming.
• Interviews: DSA is a key component of technical interviews for software engineering roles at top companies like Google, Amazon, and Microsoft.

Most Asked DSA Coding Questions

1. Arrays

• Two Sum
• Best Time to Buy and Sell Stock
• Rotate Array
• Maximum Subarray (Kadane's Algorithm)
• Merge Intervals
• Product of Array Except Self
• Find the Duplicate Number
• Set Matrix Zeroes
• Spiral Matrix
• Next Permutation
• 3Sum
• Container With Most Water
• Trapping Rain Water
• Subarray Sum Equals K
• Longest Consecutive Sequence
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• First Missing Positive
• Count Inversions in an Array
• Sliding Window Maximum

2. Linked Lists

• Reverse a Linked List
• Detect Cycle in a Linked List
• Merge Two Sorted Lists
• Remove Nth Node From End of List
• Intersection of Two Linked Lists
• Palindrome Linked List
• Add Two Numbers Represented by Linked Lists
• Flatten a Multilevel Doubly Linked List
• LRU Cache Implementation
• Clone a Linked List with Random Pointers
• Rotate a Linked List
• Remove Duplicates from Sorted List
• Swap Nodes in Pairs
• Reverse Nodes in k-Group
• Merge k Sorted Lists
• Find the Middle of a Linked List
• Remove Linked List Elements
• Odd Even Linked List
• Reorder List
• Partition List

3. Stacks and Queues

• Valid Parentheses
• Min Stack
• Implement Queue using Stacks
• Implement Stack using Queues
• Next Greater Element
• Largest Rectangle in Histogram
• Sliding Window Maximum
• Design Circular Queue
• Evaluate Reverse Polish Notation
• Remove All Adjacent Duplicates in String
• Daily Temperatures
• Simplify Path
• Asteroid Collision
• Design a Stack with Increment Operation
• Decode String
• Basic Calculator
• Maximum Frequency Stack
• Design Hit Counter
• Minimum Add to Make Parentheses Valid
• Validate Stack Sequences

4. Trees

• Maximum Depth of Binary Tree
• Validate Binary Search Tree
• Invert Binary Tree
• Binary Tree Level Order Traversal
• Lowest Common Ancestor of a Binary Tree
• Serialize and Deserialize Binary Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Diameter of Binary Tree
• Symmetric Tree
• Balanced Binary Tree
• Binary Tree Zigzag Level Order Traversal
• Path Sum
• Flatten Binary Tree to Linked List
• Populating Next Right Pointers in Each Node
• Count Complete Tree Nodes
• Kth Smallest Element in a BST
• Binary Tree Maximum Path Sum
• Sum Root to Leaf Numbers
• Subtree of Another Tree
• Vertical Order Traversal of a Binary Tree

5. Graphs

• Number of Islands
• Clone Graph
• Course Schedule
• Word Ladder
• Minimum Spanning Tree (Prim's/Kruskal's Algorithm)
• Dijkstra's Algorithm (Shortest Path)
• Topological Sort
• Alien Dictionary
• Graph Valid Tree
• Network Delay Time
• Cheapest Flights Within K Stops
• Reconstruct Itinerary
• Evaluate Division
• Redundant Connection
• Walls and Gates
• Word Search
• Surrounded Regions
• Pacific Atlantic Water Flow
• Snakes and Ladders
• Critical Connections in a Network

6. Hashing

• Two Sum
• Longest Substring Without Repeating Characters
• Group Anagrams
• Subarray Sum Equals K
• First Unique Character in a String
• Longest Palindrome
• Contains Duplicate
• Design HashMap
• Design HashSet
• Count Primes
• Insert Delete GetRandom O(1)
• Minimum Window Substring
• Find All Anagrams in a String
• Longest Consecutive Sequence
• Word Pattern
• Bulls and Cows
• Maximum Size Subarray Sum Equals k
• Encode and Decode TinyURL
• Find Duplicate Subtrees
• Top K Frequent Elements

7. Dynamic Programming

• Climbing Stairs
• Longest Increasing Subsequence
• Coin Change
• Edit Distance
• Maximum Subarray
• 0/1 Knapsack Problem
• Longest Common Subsequence
• Word Break
• Unique Paths
• House Robber
• Decode Ways
• Palindrome Partitioning
• Minimum Path Sum
• Maximum Product Subarray
• Burst Balloons
• Perfect Squares
• Target Sum
• Partition Equal Subset Sum
• Best Time to Buy and Sell Stock with Cooldown
• Regular Expression Matching

8. Strings

• Longest Substring Without Repeating Characters
• Longest Palindromic Substring
• Valid Palindrome
• Longest Common Prefix
• Valid Anagram
• Group Anagrams
• Minimum Window Substring
• Implement strStr() (KMP Algorithm)
• Decode String
• Palindrome Partitioning
• Word Break
• Reverse Words in a String
• String to Integer (atoi)
• ZigZag Conversion
• Find All Anagrams in a String
• Multiply Strings
• Simplify Path
• Basic Calculator
• Minimum Remove to Make Valid Parentheses
• Restore IP Addresses

9. Bit Manipulation

• Single Number
• Number of 1 Bits
• Reverse Bits
• Missing Number
• Power of Two
• Sum of Two Integers
• Counting Bits
• Bitwise AND of Numbers Range
• Hamming Distance
• Maximum Product of Word Lengths
• Divide Two Integers
• Gray Code
• Subsets
• Find the Difference
• UTF-8 Validation
• Binary Watch
• Total Hamming Distance
• Maximum XOR of Two Numbers in an Array
• Find the Duplicate Number
• Complement of Base 10 Integer

10. Advanced Data Structures

• Implement Trie (Prefix Tree)
• Design Add and Search Words Data Structure
• Word Search II
• Kth Largest Element in a Stream
• Median of Two Sorted Arrays
• Design Skiplist
• Range Sum Query - Mutable (Segment Tree)
• Count of Smaller Numbers After Self (Fenwick Tree)
• Design In-Memory File System
• Design Search Autocomplete System
• Design Snake Game
• Design Hit Counter
• Design Browser History
• Design Underground System
• Design Twitter
• Design Phone Directory
• Design Log Storage System
• Design Excel Sum Formula
• Design Tic-Tac-Toe
• Design a Leaderboard

DSA Theoretical Interview Questions

Arrays Interview Questions

• What is an array, and how is it stored in memory?
• Explain the difference between a static and dynamic array.
• How do you find the second largest element in an array?
• What is the time complexity of accessing an element in an array?
• How do you reverse an array in-place?
• Explain the concept of a sparse array.
• How do you find duplicates in an array?
• What is the Kadane's algorithm, and how does it work?
• How do you rotate an array by k steps?
• What is the difference between a one-dimensional and multi-dimensional array?
• How do you find the missing number in an array of integers from 1 to n?
• Explain the concept of a circular array.
• How do you merge two sorted arrays into a single sorted array?
• What is the difference between an array and a linked list?
• How do you find the majority element in an array?
• What is the sliding window technique, and how is it used with arrays?
• How do you solve the two-sum problem using an array?
• Explain the concept of a prefix sum array.
• How do you find the maximum subarray sum using divide and conquer?
• What is the difference between an array and a matrix?

Strings Interview Questions

• What is a string, and how is it stored in memory?
• Explain the difference between a string and a character array.
• How do you reverse a string in-place?
• What is the time complexity of concatenating two strings?
• How do you check if two strings are anagrams of each other?
• Explain the concept of a substring and a subsequence.
• How do you find the longest palindromic substring in a string?
• What is the difference between a string and a StringBuilder?
• How do you check if a string is a palindrome?
• Explain the concept of string interning.
• How do you find the first non-repeating character in a string?
• What is the difference between a string and a string buffer?
• How do you implement the KMP algorithm for string matching?
• Explain the concept of a suffix array.
• How do you find the longest common prefix in an array of strings?
• What is the difference between a string and a character sequence?
• How do you count the number of vowels and consonants in a string?
• Explain the concept of a rolling hash in string matching.
• How do you remove duplicates from a string?
• What is the difference between a string and a regular expression?
• How do you implement the Rabin-Karp algorithm for string matching?
• Explain the concept of a trie (prefix tree) for string storage.
• How do you find the smallest window in a string containing all characters of another string?
• What is the difference between a string and a byte array?
• How do you check if a string is a valid number?
• Explain the concept of string compression.
• How do you find the longest substring without repeating characters?
• What is the difference between a string and a string pool?
• How do you implement the Z algorithm for string matching?
• Explain the concept of a suffix tree.
• How do you find the minimum number of edits (insertions, deletions, substitutions) to convert one string to another (Edit Distance)?
• What is the difference between a string and a Unicode string?
• How do you check if a string is a rotation of another string?
• Explain the concept of a palindrome permutation.
• How do you find all anagrams of a string in a given list of strings?
• What is the difference between a string and a mutable string?
• How do you implement the Boyer-Moore algorithm for string matching?
• Explain the concept of a string hash function.
• How do you find the longest common substring between two strings?
• What is the difference between a string and a string builder?

Linked Lists Interview Questions

• What is a linked list, and how does it differ from an array?
• Explain the difference between a singly linked list and a doubly linked list.
• How do you detect a cycle in a linked list?
• What is the time complexity of inserting an element at the beginning of a linked list?
• How do you reverse a linked list?
• Explain the concept of a circular linked list.
• How do you find the middle element of a linked list in one pass?
• What is the difference between a linked list and a stack?
• How do you merge two sorted linked lists?
• Explain the concept of a skip list.
• How do you remove duplicates from a sorted linked list?
• What is the Floyd's cycle detection algorithm?
• How do you find the intersection point of two linked lists?
• What is the difference between a linked list and a queue?
• How do you implement a doubly linked list?
• Explain the concept of a self-organizing list.
• How do you delete a node in a linked list given only a pointer to that node?
• What is the difference between a linked list and a dynamic array?
• How do you implement a linked list with a tail pointer?
• What is the advantage of using a dummy node in a linked list?

Stacks and Queues Interview Questions

• What is a stack, and how does it work?
• Explain the LIFO principle in stacks.
• How do you implement a stack using an array?
• What is the time complexity of push and pop operations in a stack?
• How do you reverse a string using a stack?
• Explain the concept of a queue.
• What is the difference between a stack and a queue?
• How do you implement a queue using two stacks?
• What is a circular queue, and how does it work?
• How do you implement a stack using a linked list?
• Explain the concept of a priority queue.
• What is the difference between a queue and a deque?
• How do you implement a queue using a linked list?
• What is the time complexity of enqueue and dequeue operations in a queue?
• How do you solve the balanced parentheses problem using a stack?
• Explain the concept of a monotonic stack.
• How do you implement a min-stack?
• What is the difference between a stack and a heap?
• How do you implement a queue using a circular array?
• What is the difference between a stack and a recursion?

Trees Interview Questions

• What is a tree, and how is it different from a graph?
• Explain the difference between a binary tree and a binary search tree.
• How do you perform an inorder traversal of a binary tree?
• What is the time complexity of searching in a binary search tree?
• How do you find the height of a binary tree?
• Explain the concept of a balanced binary tree.
• What is the difference between a complete binary tree and a full binary tree?
• How do you check if a binary tree is a BST?
• What is the difference between a tree and a heap?
• How do you perform a level-order traversal of a binary tree?
• Explain the concept of a trie.
• What is the difference between a binary tree and a B-tree?
• How do you find the lowest common ancestor (LCA) of two nodes in a binary tree?
• What is the difference between a binary tree and an AVL tree?
• How do you serialize and deserialize a binary tree?
• Explain the concept of a segment tree.
• What is the difference between a binary tree and a red-black tree?
• How do you find the diameter of a binary tree?
• What is the difference between a tree and a forest?
• How do you implement a binary search tree?

Graphs Interview Questions

• What is a graph, and how is it represented in memory?
• Explain the difference between a directed and undirected graph.
• What is the difference between a graph and a tree?
• How do you perform a depth-first search (DFS) on a graph?
• What is the time complexity of DFS and BFS on a graph?
• Explain the concept of a weighted graph.
• How do you detect a cycle in a directed graph?
• What is the difference between a graph and a multigraph?
• How do you find the shortest path in a weighted graph?
• Explain Dijkstra's algorithm.
• What is the difference between Dijkstra's algorithm and Bellman-Ford algorithm?
• How do you detect a cycle in an undirected graph?
• What is the difference between a graph and a bipartite graph?
• Explain the concept of a topological sort.
• How do you implement a graph using an adjacency list?
• What is the difference between a graph and a network?
• How do you find the strongly connected components in a graph?
• Explain the concept of a minimum spanning tree (MST).
• What is the difference between Prim's and Kruskal's algorithm?
• How do you implement a graph using an adjacency matrix?

Hashing Interview Questions

• What is a hash table, and how does it work?
• Explain the concept of a hash function.
• What is the time complexity of insert, delete, and search operations in a hash table?
• How do you handle collisions in a hash table?
• Explain the difference between open addressing and chaining.
• What is the difference between a hash table and a hash map?
• How do you implement a hash table using an array?
• What is the difference between a hash table and a dictionary?
• Explain the concept of a perfect hash function.
• How do you design a hash function for strings?
• What is the difference between a hash table and a set?
• How do you handle resizing in a hash table?
• Explain the concept of a consistent hashing.
• What is the difference between a hash table and a bloom filter?
• How do you implement a hash table with separate chaining?
• What is the difference between a hash table and a trie?
• How do you implement a hash table with open addressing?
• Explain the concept of a cryptographic hash function.
• What is the difference between a hash table and a priority queue?
• How do you implement a hash table with double hashing?

Sorting and Searching Interview Questions

• What is the difference between comparison-based and non-comparison-based sorting algorithms?
• Explain the time complexity of merge sort.
• How does quicksort work, and what is its worst-case time complexity?
• What is the difference between stable and unstable sorting algorithms?
• How do you implement binary search?
• Explain the concept of a linear search.
• What is the difference between bubble sort and insertion sort?
• How does heap sort work?
• What is the time complexity of radix sort?
• Explain the concept of a counting sort.
• What is the difference between internal and external sorting?
• How do you implement selection sort?
• What is the difference between binary search and ternary search?
• Explain the concept of interpolation search.
• How do you implement shell sort?
• What is the difference between merge sort and quicksort?
• How do you implement bucket sort?
• Explain the concept of a topological sort.
• What is the difference between sorting and searching?
• How do you implement a binary search tree?

Dynamic Programming Interview Questions

• What is dynamic programming, and how does it differ from greedy algorithms?
• Explain the concept of overlapping subproblems.
• What is the difference between top-down and bottom-up dynamic programming?
• How do you solve the Fibonacci sequence problem using dynamic programming?
• What is memoization, and how is it used in dynamic programming?
• Explain the concept of optimal substructure.
• How do you solve the 0/1 knapsack problem using dynamic programming?
• What is the difference between dynamic programming and divide and conquer?
• How do you solve the longest common subsequence (LCS) problem?
• Explain the concept of state transition in dynamic programming.
• How do you solve the coin change problem using dynamic programming?
• What is the difference between dynamic programming and backtracking?
• How do you solve the matrix chain multiplication problem?
• Explain the concept of tabulation in dynamic programming.
• How do you solve the longest increasing subsequence (LIS) problem?
• What is the difference between dynamic programming and recursion?
• How do you solve the edit distance problem?
• Explain the concept of space optimization in dynamic programming.
• How do you solve the subset sum problem using dynamic programming?
• What is the difference between dynamic programming and branch and bound?

Greedy Algorithms Interview Questions

• What is a greedy algorithm, and how does it work?
• Explain the difference between greedy algorithms and dynamic programming.
• How do you solve the fractional knapsack problem using a greedy approach?
• What is the difference between greedy algorithms and divide and conquer?
• How do you solve the activity selection problem using a greedy approach?
• Explain the concept of local optimality in greedy algorithms.
• How do you solve the Huffman coding problem using a greedy approach?
• What is the difference between greedy algorithms and backtracking?
• How do you solve the coin change problem using a greedy approach?
• Explain the concept of a minimum spanning tree (MST) in greedy algorithms.
• How do you solve the job sequencing problem using a greedy approach?
• What is the difference between greedy algorithms and brute force?
• How do you solve the Dijkstra's algorithm using a greedy approach?
• Explain the concept of a greedy choice property.
• How do you solve the Kruskal's algorithm using a greedy approach?
• What is the difference between greedy algorithms and dynamic programming?
• How do you solve the Prim's algorithm using a greedy approach?
• Explain the concept of a matroid in greedy algorithms.
• How do you solve the interval scheduling problem using a greedy approach?
• What is the difference between greedy algorithms and linear programming?

Divide and Conquer Interview Questions

• What is the divide and conquer approach, and how does it work?
• Explain the difference between divide and conquer and dynamic programming.
• How do you solve the merge sort problem using divide and conquer?
• What is the difference between divide and conquer and greedy algorithms?
• How do you solve the quicksort problem using divide and conquer?
• Explain the concept of recursion in divide and conquer.
• How do you solve the binary search problem using divide and conquer?
• What is the difference between divide and conquer and backtracking?
• How do you solve the closest pair of points problem using divide and conquer?
• Explain the concept of subproblem independence in divide and conquer.
• How do you solve the Strassen's matrix multiplication problem using divide and conquer?
• What is the difference between divide and conquer and brute force?
• How do you solve the maximum subarray problem using divide and conquer?
• Explain the concept of problem decomposition in divide and conquer.
• How do you solve the Karatsuba algorithm for multiplication using divide and conquer?
• What is the difference between divide and conquer and dynamic programming?
• How do you solve the convex hull problem using divide and conquer?
• Explain the concept of base case in divide and conquer.
• How do you solve the counting inversions problem using divide and conquer?
• What is the difference between divide and conquer and recursion?

Backtracking Interview Questions

• What is backtracking, and how does it work?
• Explain the difference between backtracking and dynamic programming.
• How do you solve the N-Queens problem using backtracking?
• What is the difference between backtracking and brute force?
• How do you solve the Sudoku solver problem using backtracking?
• Explain the concept of pruning in backtracking.
• How do you solve the subset sum problem using backtracking?
• What is the difference between backtracking and recursion?
• How do you solve the permutation problem using backtracking?
• Explain the concept of state space tree in backtracking.
• How do you solve the combination sum problem using backtracking?
• What is the difference between backtracking and greedy algorithms?
• How do you solve the Hamiltonian cycle problem using backtracking?
• Explain the concept of feasibility in backtracking.
• How do you solve the rat in a maze problem using backtracking?
• What is the difference between backtracking and divide and conquer?
• How do you solve the word search problem using backtracking?
• Explain the concept of choice in backtracking.
• How do you solve the graph coloring problem using backtracking?
• What is the difference between backtracking and branch and bound?

Bit Manipulation Interview Questions

• What is bit manipulation, and why is it useful?
• Explain the difference between bitwise AND, OR, and XOR operations.
• How do you check if a number is a power of 2 using bit manipulation?
• What is the difference between logical and bitwise operators?
• How do you count the number of set bits in a number?
• Explain the concept of two's complement.
• How do you swap two numbers without using a temporary variable?
• What is the difference between left shift and right shift operators?
• How do you find the missing number in an array using bit manipulation?
• Explain the concept of a bitmask.
• How do you check if a number is even or odd using bit manipulation?
• What is the difference between signed and unsigned integers?
• How do you find the single non-repeating number in an array using bit manipulation?
• Explain the concept of bitwise NOT.
• How do you reverse the bits of a number?
• What is the difference between bit manipulation and arithmetic operations?
• How do you find the position of the rightmost set bit?
• Explain the concept of bitwise Hamming distance.
• How do you multiply a number by 2 using bit manipulation?
• What is the difference between bit manipulation and logical operations?

Advanced Data Structures Interview Questions

• What is a segment tree, and how does it work?
• Explain the concept of a Fenwick tree (Binary Indexed Tree).
• How do you implement a suffix array?
• What is the difference between a segment tree and a Fenwick tree?
• How do you implement a disjoint set (Union-Find) data structure?
• Explain the concept of a trie (prefix tree).
• How do you implement a B-tree?
• What is the difference between a B-tree and a binary search tree?
• How do you implement a red-black tree?
• Explain the concept of an AVL tree.
• How do you implement a skip list?
• What is the difference between a trie and a hash table?
• How do you implement a suffix tree?
• Explain the concept of a k-d tree.
• How do you implement a bloom filter?
• What is the difference between a B-tree and a B+ tree?
• How do you implement a quadtree?
• Explain the concept of a persistent data structure.
• How do you implement a splay tree?
• What is the difference between a segment tree and a heap?

Advanced Data Structures Interview Questions

• What is a segment tree, and how does it work?
• Explain the concept of a Fenwick tree (Binary Indexed Tree).
• How do you implement a suffix array?
• What is the difference between a segment tree and a Fenwick tree?
• How do you implement a disjoint set (Union-Find) data structure?
• Explain the concept of a trie (prefix tree).
• How do you implement a B-tree?
• What is the difference between a B-tree and a binary search tree?
• How do you implement a red-black tree?
• Explain the concept of an AVL tree.
• How do you implement a skip list?
• What is the difference between a trie and a hash table?
• How do you implement a suffix tree?
• Explain the concept of a k-d tree.
• How do you implement a bloom filter?
• What is the difference between a B-tree and a B+ tree?
• How do you implement a quadtree?
• Explain the concept of a persistent data structure.
• How do you implement a splay tree?
• What is the difference between a segment tree and a heap?