Chapter 62: DSA Examples
DSA Examples – What people usually mean when they say “DSA Examples”
When someone asks for “DSA Examples”, they almost always mean one (or a combination) of these three things:
- Classic well-known problems that appear again and again in interviews, contests and college placements (the ones almost every serious student is expected to know)
- Typical examples for each major data structure and algorithm topic (so you can see how the concept is actually used)
- Real interview-style questions with a short explanation + why they are asked
I will give you both:
- a big list of the most important classic problems (the ones you should aim to solve at least 150–300 of)
- and then detailed examples for each major DSA topic with one or two very representative problems
1. The “Must-Know” Classic DSA Problems (2025–2026 style)
These are the problems that appear in almost every product-based company interview (Amazon, Google, Microsoft, Atlassian, Uber, Flipkart, Goldman Sachs, startups etc.)
| Category | Very High Frequency Problems (solve these first) |
|---|---|
| Arrays / Hashing | Two Sum, 3Sum, Contains Duplicate, Longest Consecutive Sequence, Product of Array Except Self, Maximum Subarray (Kadane), Trapping Rain Water, Longest Substring Without Repeating Characters |
| Two Pointers / Sliding Window | Valid Palindrome, 3Sum, Container With Most Water, Longest Repeating Character Replacement, Minimum Window Substring, Sliding Window Maximum |
| Binary Search | Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Median of Two Sorted Arrays, Kth Smallest Element in Sorted Matrix |
| Linked List | Reverse Linked List, Merge Two Sorted Lists, Reorder List, Detect Cycle (Floyd), Remove Nth Node From End, LRU Cache |
| Stack / Queue / Monotonic | Valid Parentheses, Next Greater Element, Largest Rectangle in Histogram, Daily Temperatures, Min Stack, Implement Queue using Stacks |
| Binary Tree / BST | Maximum Depth, Invert Binary Tree, Validate BST, Lowest Common Ancestor, Diameter of Binary Tree, Kth Smallest in BST, Binary Tree Level Order Traversal |
| Graph – BFS | Number of Islands, Rotten Oranges, Word Ladder, Shortest Path in Binary Matrix, Course Schedule (topological sort via BFS) |
| Graph – DFS | Number of Islands, Course Schedule (cycle detection), Clone Graph, Pacific Atlantic Water Flow |
| Dynamic Programming – 1D | Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, Partition Equal Subset Sum |
| Dynamic Programming – 2D | Unique Paths, Longest Common Subsequence, Edit Distance, Minimum Path Sum, Interleaving String |
| Greedy | Jump Game, Jump Game II, Gas Station, Task Scheduler, Candy, Non-overlapping Intervals |
| Heap / Priority Queue | Kth Largest Element, Merge K Sorted Lists, Top K Frequent Elements, Sliding Window Maximum |
| Trie | Implement Trie, Word Search II, Design Add and Search Words, Longest Word in Dictionary |
| Bit Manipulation | Single Number, Missing Number, Reverse Bits, Number of 1 Bits, Subsets (bitmask) |
If you solve 150–200 good quality problems from the above categories (especially LeetCode top 150–200 + company-tagged questions), you are usually well prepared for most product-based companies.
2. Detailed Examples – One Strong Representative Problem per Major Topic
I will pick one very typical, very frequently asked problem for each major DSA topic and explain it like a teacher.
Arrays / Hashing – Two Sum
Problem: Given an array of integers nums and an integer target, return indices of two numbers that add up to target.
Example: nums = [2,7,11,15], target = 9 → return [0,1] (because 2 + 7 = 9)
Naive way: two nested loops → O(n²)
Optimal way (hash map):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def twoSum(nums, target): seen = {} # value → index for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return [] |
Why hash map works: We store every number we’ve seen so far. When we reach a number, we immediately ask: “Have I already seen the complement (target – current) before?”
Time: O(n) Space: O(n)
This is the most asked array + hashing problem in the world.
Binary Search – Search in Rotated Sorted Array
Problem: You are given a sorted array that has been rotated at some pivot unknown to you beforehand. Find a target value. Return its index, or -1 if not found.
Example: nums = [4,5,6,7,0,1,2], target = 0 → return 4
Key insight:
Even after rotation, one half of the array is always sorted.
So in every step we can decide:
- Is the left half sorted? → check if target lies in left half
- Or is the right half sorted? → check if target lies in right half
Code (classic interview version):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 |
Time: O(log n) This is one of the most loved hard binary search problems.
Dynamic Programming – Longest Increasing Subsequence
Problem: Find the length of the longest strictly increasing subsequence in an array.
Example: [10,9,2,5,3,7,101,18] → longest = 4 → [2,3,7,18]
DP approach (classic tabulation):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def lengthOfLIS(nums): if not nums: return 0 n = len(nums) dp = [1] * n # dp[i] = length of LIS ending at index i for i in range(1, n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) |
Time: O(n²) (There is O(n log n) version using patience sorting / binary search, but O(n²) is the standard DP way interviewers expect first)
Final Summary – What “DSA Examples” usually means
When someone asks for “DSA Examples”, they normally want:
- The most repeated / high-frequency problems (Two Sum, Valid Parentheses, Number of Islands, LRU Cache, Kth Smallest, etc.)
- One representative problem + solution explanation for each major topic (array, binary search, linked list, tree, graph, DP, greedy, etc.)
- Understanding why that problem is important and what concept it teaches
If you want, I can now give you:
- A curated list of 50–70 must-do problems categorized by topic
- Or deep-dive into one specific topic with 3–4 very strong examples
- Or explain any particular famous problem in full detail (e.g. LRU Cache, Word Ladder, Trapping Rain Water, Kth Largest Element, etc.)
Just tell me what you want next — I’ll teach it in the same detailed, human-friendly way 😊
