{"id":1101,"date":"2026-04-04T14:13:51","date_gmt":"2026-04-04T08:43:51","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1101"},"modified":"2026-04-04T14:13:53","modified_gmt":"2026-04-04T08:43:53","slug":"dsa-interview-cheat-sheet","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/dsa-interview-cheat-sheet\/","title":{"rendered":"DSA Interview Cheat Sheet: All Patterns You Need to Know"},"content":{"rendered":"\n<p>Most <strong>DSA interviews<\/strong> test the same set of <strong>patterns<\/strong> again and again. Whether it is <strong>TCS, Infosys, Amazon, Google<\/strong>, or any startup, the problems change but the underlying <strong>patterns stay the same<\/strong>. If you learn to <strong>recognize these patterns<\/strong>, you can solve most interview problems without memorizing <strong>hundreds of questions<\/strong>.<\/p>\n\n\n\n<p>This cheat sheet covers every <strong>major DSA pattern<\/strong>, when to use it, what type of problems fall under it, and the <strong>key idea behind each one<\/strong>. Bookmark this page and come back to it before every interview.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Why Patterns Matter More Than Problems<\/strong><\/h2>\n\n\n\n<p>A lot of students make the mistake of solving <strong>500+ LeetCode problems randomly<\/strong>. They solve a problem, feel good, and move to the next one. But when a slightly different version shows up in an interview, they get stuck.<\/p>\n\n\n\n<p>The reason is simple. They <strong>memorized solutions instead of understanding patterns<\/strong>. Once you know a pattern, you can apply it to <strong>20 or 30 different problems<\/strong>. That is a much better use of your time.<\/p>\n\n\n\n<p>Think of it this way. If someone asks you to find <strong>two numbers that add up to a target in a sorted array<\/strong>, and you know the <strong>two pointer pattern<\/strong>, you do not need to have seen that exact problem before. You just <strong>recognize the pattern and apply it<\/strong>. Same goes for finding the <strong>longest substring without repeating characters<\/strong>. If you know the <strong>sliding window<\/strong>, the problem is <strong>half solved before you even start coding<\/strong>.<\/p>\n\n\n\n<p>The patterns listed below cover roughly <strong>90% of what you will face in interviews<\/strong> at <strong>Indian product companies, service companies, and startups<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>1. Two Pointers<\/strong><\/h2>\n\n\n\n<p>The <strong>two pointer pattern<\/strong> uses two variables (usually called <strong>left and right<\/strong>) that move through an array or string from different positions.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The input is <strong>sorted<\/strong><\/li>\n\n\n\n<li>You need to find <strong>pairs or triplets<\/strong> that satisfy a condition<\/li>\n\n\n\n<li>Useful when comparing elements from <strong>both ends of an array<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/\" data-type=\"post\" data-id=\"375\">Two Sum (sorted array)<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/\" data-type=\"post\" data-id=\"439\">Three Sum<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/remove-duplicates-from-sorted-array-leetcode-26\/\" data-type=\"post\" data-id=\"47\">Remove Duplicates from Sorted Array<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/trapping-rain-water\/\" data-type=\"post\" data-id=\"867\">Trapping Rain Water<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Instead of checking every possible pair using <strong>two nested loops (O(n\u00b2))<\/strong>, you use two pointers that move towards each other based on some condition. This reduces the time complexity to <strong>O(n)<\/strong>.<\/p>\n\n\n\n<p><strong>How to spot it:<\/strong><br>If the problem says <strong>&#8220;sorted array&#8221;<\/strong> and asks you to find a <strong>pair or group of elements<\/strong>, think <strong>two pointers first<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>2. Sliding Window<\/strong><\/h2>\n\n\n\n<p><strong>Sliding window<\/strong> is one of the <strong>most frequently asked patterns<\/strong> in interviews. It works on problems where you need to find something (<strong>maximum, minimum, count<\/strong>) within a <strong>contiguous subarray or substring<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The problem involves a <strong>subarray or substring<\/strong><\/li>\n\n\n\n<li>You need to optimize from a <strong>brute force approach<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/maximum-subarray-kadanes-algorithm\/\" data-type=\"post\" data-id=\"411\">Maximum Sum Subarray of Size K<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/longest-substring-without-repeating-characters\/\" data-type=\"post\" data-id=\"910\">Longest Substring Without Repeating Characters<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/number-of-substrings-containing-all-three-characters\/\" data-type=\"post\" data-id=\"931\">Minimum Window Substring<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/fruit-into-baskets\/\" data-type=\"post\" data-id=\"917\">Fruits Into Baskets<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/\" data-type=\"post\" data-id=\"920\">Longest Repeating Character Replacement<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Maintain a <strong>window (two pointers)<\/strong> and <strong>expand or shrink<\/strong> it based on conditions. As the window slides forward, you <strong>add new elements and remove old ones<\/strong>, avoiding recomputation.<\/p>\n\n\n\n<p><strong>Fixed window vs variable window:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Fixed window:<\/strong> Size is given (e.g., size K)<\/li>\n\n\n\n<li><strong>Variable window:<\/strong> Find smallest\/largest window satisfying a condition<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>3. Binary Search<\/strong><\/h2>\n\n\n\n<p><strong>Binary search<\/strong> is not just about searching in a <strong>sorted array<\/strong>. Its real power is <strong>search space reduction<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Input is <strong>sorted<\/strong><\/li>\n\n\n\n<li>You are searching in a <strong>monotonic space<\/strong> (increasing\/decreasing)<\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/search-in-rotated-sorted-array\/\" data-type=\"post\" data-id=\"515\">Search in Rotated Sorted Array<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/find-minimum-in-rotated-sorted-array\/\" data-type=\"post\" data-id=\"566\">Find Minimum in Rotated Sorted Array<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/koko-eating-bananas-leetcode-875\/\" data-type=\"post\" data-id=\"587\">Koko Eating Bananas<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/median-of-two-sorted-arrays\/\" data-type=\"post\" data-id=\"617\">Median of Two Sorted Arrays<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/aggresive-cows\/\" data-type=\"post\" data-id=\"601\">Aggressive Cows<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/allocate-minimum-pages\/\" data-type=\"post\" data-id=\"605\">Book Allocation Problem<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Check the <strong>middle element<\/strong> and eliminate <strong>half of the search space<\/strong> each time \u2192 <strong>O(log n)<\/strong><\/p>\n\n\n\n<p><strong>Important for Indian interviews:<\/strong><br>Problems like <strong>Book Allocation, Aggressive Cows, Painter&#8217;s Partition<\/strong> are extremely common. These are <strong>&#8220;binary search on answer&#8221;<\/strong> problems where you search on the <strong>answer space instead of the array<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>4. Hashing<\/strong><\/h2>\n\n\n\n<p><strong>Hashing<\/strong> is the go-to technique when you need <strong>fast lookups, counting, or tracking elements<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Need <strong>O(1) lookup<\/strong><\/li>\n\n\n\n<li>Counting <strong>frequency of elements<\/strong><\/li>\n\n\n\n<li>Checking if something <strong>exists<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/\" data-type=\"post\" data-id=\"375\">Two Sum (unsorted)<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/longest-consecutive-sequence\/\" data-type=\"post\" data-id=\"426\">Longest Consecutive Sequence<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/sum-of-subarray-minimums\/\" data-type=\"post\" data-id=\"900\">Subarray Sum Equals K<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/valid-anagram\/\" data-type=\"post\" data-id=\"1057\">Valid Anagram<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Use a <strong>hash map (dictionary)<\/strong> to store elements and their properties (index, frequency, etc.), converting slow lookups into <strong>O(1)<\/strong> operations.<\/p>\n\n\n\n<p><strong>Watch out for:<\/strong><br>Worst-case <strong>hash collisions<\/strong>, but in interviews, <strong>average O(1)<\/strong> is what matters.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>5. Stack and Queue<\/strong><\/h2>\n\n\n\n<p><strong>Stack problems<\/strong> usually involve <strong>matching or tracking elements in order<\/strong>. The <strong>monotonic stack<\/strong> is a very important subpattern.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Matching <strong>brackets<\/strong><\/li>\n\n\n\n<li>Finding <strong>next greater\/smaller elements<\/strong><\/li>\n\n\n\n<li>Evaluating expressions<\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/valid-parentheses\/\" data-type=\"post\" data-id=\"849\">Valid Parentheses<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/next-larger-element\/\" data-type=\"post\" data-id=\"860\">Next Greater Element<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/daily-temperatures\/description\/\" target=\"_blank\" rel=\"noopener\">Daily Temperatures<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/largest-rectangle-in-histogram\/description\/\" target=\"_blank\" rel=\"noopener\">Largest Rectangle in Histogram<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/\" data-type=\"post\" data-id=\"853\">Min Stack<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/evaluate-reverse-polish-notation\/description\/\" target=\"_blank\" rel=\"noopener\">Evaluate Reverse Polish Notation<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/implement-queue-using-stacks\/\" data-type=\"post\" data-id=\"839\">Implement Queue Using Stacks<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Stack \u2192 <strong>Last In First Out (LIFO)<\/strong><\/li>\n\n\n\n<li>Monotonic stack \u2192 maintain <strong>increasing or decreasing order<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Monotonic stack trick:<\/strong><br>For every element, <strong>pop elements that are smaller (or larger)<\/strong>. The remaining top gives the answer.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>6. Linked List Patterns<\/strong><\/h2>\n\n\n\n<p>Linked list problems test <strong>pointer manipulation skills<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Problem involves a <strong>linked list<\/strong><\/li>\n\n\n\n<li>Need <strong>in-place rearrangement<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/reverse-linked-list-leetcode-206\/\" data-type=\"post\" data-id=\"634\">Reverse Linked List<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/linked-list-cycle-leetcode-141\/\" data-type=\"post\" data-id=\"638\">Detect Cycle<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/middle-of-the-linked-list-leetcode-876\/\" data-type=\"post\" data-id=\"628\">Find Middle<\/a>, <a href=\"https:\/\/www.geeksforgeeks.org\/dsa\/merge-two-sorted-linked-lists\/\" target=\"_blank\" rel=\"noopener\">Merge Two Lists<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/remove-nth-node-from-end-of-list-leetcode-19\/\" data-type=\"post\" data-id=\"655\">Remove Nth Node<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/\" data-type=\"post\" data-id=\"647\">Palindrome Linked List<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/intersection-of-two-linked-lists-leetcode-160\/\" data-type=\"post\" data-id=\"670\">Intersection<\/a><\/p>\n\n\n\n<p><strong>Key tricks:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Slow and fast pointer<\/strong> (middle, cycle detection)<\/li>\n\n\n\n<li><strong>Reverse technique<\/strong><\/li>\n\n\n\n<li><strong>Dummy node<\/strong> (simplifies edge cases)<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>7. Trees (BFS and DFS)<\/strong><\/h2>\n\n\n\n<p>Tree problems are extremely common and mostly follow <strong>BFS or DFS<\/strong>.<\/p>\n\n\n\n<p><strong>When to use BFS:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Level order traversal<\/strong><\/li>\n\n\n\n<li><strong>Shortest path<\/strong><\/li>\n\n\n\n<li>Process nodes <strong>level by level<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>When to use DFS:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Path-based problems<\/strong><\/li>\n\n\n\n<li>Checking <strong>tree properties<\/strong><\/li>\n\n\n\n<li>Computing <strong>depth<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/maximum-depth-of-binary-tree\/\" data-type=\"post\" data-id=\"120\">Maximum Depth<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/\" data-type=\"post\" data-id=\"89\">Level Order Traversal<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/validate-binary-search-tree\/description\/\" target=\"_blank\" rel=\"noopener\">Validate BST<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/lowest-common-ancestor-of-a-binary-tree\/description\/\" target=\"_blank\" rel=\"noopener\">Lowest Common Ancestor<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/diameter-of-binary-tree\/\" data-type=\"post\" data-id=\"125\">Diameter<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/binary-tree-right-side-view\/\" data-type=\"post\" data-id=\"1093\">Right Side View<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/binary-tree-zigzag-level-order-traversal\/\" data-type=\"post\" data-id=\"1031\">Zigzag Traversal<\/a><\/p>\n\n\n\n<p><strong>Key idea (DFS):<\/strong><br>Ask:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>What do I need from the <strong>left subtree<\/strong>?<\/li>\n\n\n\n<li>What do I need from the <strong>right subtree<\/strong>?<\/li>\n\n\n\n<li>How do I <strong>combine them<\/strong>?<\/li>\n<\/ul>\n\n\n\n<p><strong>Key idea (BFS):<\/strong><br>Use a <strong>queue<\/strong> and process nodes <strong>level by level<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>8. Graph Traversal<\/strong><\/h2>\n\n\n\n<p>Graphs extend trees with <strong>cycles and multiple paths<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Problems involving <strong>connections, grids, networks<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/number-of-islands-leetcode-200\/\" data-type=\"post\" data-id=\"231\">Number of Islands<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/course-schedule-1\/\" data-type=\"post\" data-id=\"276\">Course Schedule<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/rotting-oranges-leetcode-994\/\" data-type=\"post\" data-id=\"140\">Rotten Oranges<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/word-ladder-leetcode-127\/\" data-type=\"post\" data-id=\"183\">Word Ladder<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/number-of-provinces\/description\/\" target=\"_blank\" rel=\"noopener\">Number of Provinces<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/surrounded-regions-leetcode-130\/\" data-type=\"post\" data-id=\"169\">Surrounded Regions<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/topo-sort-kahns-algorithm\/\" data-type=\"post\" data-id=\"259\">Topological Sort<\/a><\/p>\n\n\n\n<p><strong>Key ideas:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Track <strong>visited nodes<\/strong><\/li>\n\n\n\n<li>BFS \u2192 <strong>shortest path<\/strong><\/li>\n\n\n\n<li>DFS \u2192 <strong>connected components<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Topological sort:<\/strong><br>Used for <strong>task ordering with dependencies<\/strong> (Kahn\u2019s algorithm or DFS).<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>9. Recursion and Backtracking<\/strong><\/h2>\n\n\n\n<p>Backtracking is <strong>recursion with undoing choices<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Find <strong>all combinations, permutations, subsets<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/print-all-subsequences\/\" data-type=\"post\" data-id=\"717\">Subsets<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/print-all-subsequences\/\" data-type=\"post\" data-id=\"717\">Permutations<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum\/\" data-type=\"post\" data-id=\"748\">Combination Sum<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/\" data-type=\"post\" data-id=\"767\">N Queens<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/sudoku-solver\/description\/\" target=\"_blank\" rel=\"noopener\">Sudoku Solver<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/word-search\/description\/\" target=\"_blank\" rel=\"noopener\">Word Search<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/palindrome-partitioning\/description\/\" target=\"_blank\" rel=\"noopener\">Palindrome Partitioning<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Think of it as a <strong>decision tree<\/strong>.<\/p>\n\n\n\n<p><strong>Template:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Define <strong>base case<\/strong><\/li>\n\n\n\n<li>Loop through choices<\/li>\n\n\n\n<li><strong>Make a choice<\/strong><\/li>\n\n\n\n<li><strong>Recurse<\/strong><\/li>\n\n\n\n<li><strong>Undo choice (backtrack)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Pruning:<\/strong><br>Skip invalid paths early to improve performance.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>10. Dynamic Programming<\/strong><\/h2>\n\n\n\n<p><strong>Dynamic Programming (DP)<\/strong> is <strong>optimized recursion<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Overlapping subproblems<\/strong><\/li>\n\n\n\n<li><strong>Optimal substructure<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/\" data-type=\"post\" data-id=\"782\">Climbing Stairs<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/house-robber\/\" data-type=\"post\" data-id=\"806\">House Robber<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/longest-palindromic-subsequence\/\" data-type=\"post\" data-id=\"994\">LCS<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/0-1-knapsack-problem\/\" data-type=\"post\" data-id=\"895\">Knapsack<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/edit-distance\/description\/\" target=\"_blank\" rel=\"noopener\">Edit Distance<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/minimum-number-of-coins\/\" data-type=\"post\" data-id=\"948\">Coin Change<\/a>, <a href=\"https:\/\/www.geeksforgeeks.org\/problems\/matrix-chain-multiplication0303\/1\" target=\"_blank\" rel=\"noopener\">Matrix Chain Multiplication<\/a><\/p>\n\n\n\n<p><strong>Approach:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start with <strong>recursion<\/strong><\/li>\n\n\n\n<li>Identify <strong>state variables<\/strong><\/li>\n\n\n\n<li>Add <strong>memoization<\/strong><\/li>\n\n\n\n<li>Convert to <strong>tabulation<\/strong><\/li>\n<\/ol>\n\n\n\n<p><strong>Common categories:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>1D DP (Linear)<\/strong><\/li>\n\n\n\n<li><strong>2D DP (Grid)<\/strong><\/li>\n\n\n\n<li><strong>String DP<\/strong><\/li>\n\n\n\n<li><strong>Knapsack variants<\/strong><\/li>\n\n\n\n<li><strong>Interval DP<\/strong><\/li>\n\n\n\n<li><strong>Tree DP<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Important for Indian interviews:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>0\/1 Knapsack and variants<\/strong><\/li>\n\n\n\n<li><strong>Longest Common Subsequence (LCS)<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>11. Greedy<\/strong><\/h2>\n\n\n\n<p><strong>Greedy algorithms<\/strong> make the <strong>best local choice<\/strong> at each step.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When <strong>local optimal \u2192 global optimal<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/fractional-knapsack\/\" data-type=\"post\" data-id=\"944\">Fractional Knapsack<\/a>, <a href=\"https:\/\/www.geeksforgeeks.org\/problems\/activity-selection-1587115620\/1\" target=\"_blank\" rel=\"noopener\">Activity Selection<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/job-sequencing-problem\/\" data-type=\"post\" data-id=\"967\">Job Scheduling<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/minimum-platforms\/\" data-type=\"post\" data-id=\"964\">Minimum Platforms<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/jump-game\/\" data-type=\"post\" data-id=\"958\">Jump Game<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/minimize-max-distance-to-gas-station\/\" data-type=\"post\" data-id=\"613\">Gas Station<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><br>Sort input and make <strong>locally optimal decisions<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>12. Heap \/ Priority Queue<\/strong><\/h2>\n\n\n\n<p>A <strong>heap<\/strong> gives quick access to the <strong>minimum or maximum element<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Kth largest\/smallest problems<\/strong><\/li>\n\n\n\n<li><strong>Top K elements<\/strong><\/li>\n\n\n\n<li><strong>Merging sorted lists<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/description\/\" target=\"_blank\" rel=\"noopener\">Kth Largest Element<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/top-k-frequent-elements\/description\/\" target=\"_blank\" rel=\"noopener\">Top K Frequent Elements<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/merge-k-sorted-lists\/description\/\" target=\"_blank\" rel=\"noopener\">Merge K Sorted Lists<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/find-median-from-data-stream\/description\/\" target=\"_blank\" rel=\"noopener\">Median from Data Stream<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/task-scheduler\/description\/\" target=\"_blank\" rel=\"noopener\">Task Scheduler<\/a><\/p>\n\n\n\n<p><strong>Key idea:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use <strong>min heap \/ max heap<\/strong><\/li>\n\n\n\n<li>Maintain a <strong>heap of size K<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>13. Bit Manipulation<\/strong><\/h2>\n\n\n\n<p>Less frequent but important for <strong>optimization-heavy problems<\/strong>.<\/p>\n\n\n\n<p><strong>When to use it:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Finding <strong>unique elements<\/strong><\/li>\n\n\n\n<li>Checking <strong>power of 2<\/strong><\/li>\n\n\n\n<li><strong>Bit counting<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Common problems:<\/strong><br><a href=\"https:\/\/codeanddebug.in\/blog\/single-number\/\" data-type=\"post\" data-id=\"704\">Single Number<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/power-of-two\/description\/\" target=\"_blank\" rel=\"noopener\">Power of Two<\/a>, <a href=\"https:\/\/leetcode.com\/problems\/counting-bits\/description\/\" target=\"_blank\" rel=\"noopener\">Counting Bits<\/a>, <a href=\"https:\/\/codeanddebug.in\/blog\/find-the-missing-number\/\" data-type=\"post\" data-id=\"360\">Missing Number<\/a><\/p>\n\n\n\n<p><strong>Key operations:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>AND, OR, XOR, shifts<\/li>\n\n\n\n<li><strong>XOR properties:<\/strong>\n<ul class=\"wp-block-list\">\n<li>a XOR a = 0<\/li>\n\n\n\n<li>a XOR 0 = a<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>How to Use This Cheat Sheet<\/strong><\/h2>\n\n\n\n<p>Do not try to master all patterns at once.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Week 1\u20132:<\/strong> Two Pointers, Sliding Window, Hashing<\/li>\n\n\n\n<li><strong>Week 3\u20134:<\/strong> Binary Search, Stack, Linked List<\/li>\n\n\n\n<li><strong>Week 5\u20136:<\/strong> Trees, Graphs<\/li>\n\n\n\n<li><strong>Week 7\u20138:<\/strong> Recursion, Backtracking, DP<\/li>\n\n\n\n<li><strong>Ongoing:<\/strong> Greedy, Heap, Bit Manipulation<\/li>\n<\/ul>\n\n\n\n<p>For each pattern, solve <strong>5 to 8 problems<\/strong>. Focus on <strong>understanding<\/strong>, not memorizing.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>One Last Tip<\/strong><\/h2>\n\n\n\n<p>After solving a problem, spend <strong>2 minutes<\/strong> asking:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>What pattern did I use?<\/strong><\/li>\n\n\n\n<li><strong>How would I recognize this pattern in a new problem?<\/strong><\/li>\n<\/ul>\n\n\n\n<p>This habit builds <strong>pattern recognition faster than solving more problems blindly<\/strong>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Start Your DSA Journey<\/h2>\n\n\n\n<p>If you are just getting started with DSA and Python, check out our <a href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\">Zero to Hero Python DSA<\/a> course. It covers everything from basics to advanced topics in a structured way.<\/p>\n\n\n\n<p>Already comfortable with the fundamentals and want to practice problems pattern by pattern? Our <a href=\"https:\/\/codeanddebug.in\/course\/master-dsa-with-leetcode\">Master DSA with LeetCode<\/a> course walks you through<strong> 150+ handpicked problem<\/strong>s organized exactly by the patterns covered in this cheat sheet.<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Most DSA interviews test the same set of patterns again and again. Whether it is TCS, Infosys, Amazon, Google, or any startup, the problems change but the underlying patterns stay the same. If you learn to recognize these patterns, you can solve most interview problems without memorizing hundreds of questions. This cheat sheet covers every<\/p>\n","protected":false},"author":1,"featured_media":1106,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":{"0":"post-1101","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2026\/04\/DSA-Interview-Cheat-Sheet-Banner.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1101"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1101\/revisions"}],"predecessor-version":[{"id":1103,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1101\/revisions\/1103"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1106"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1101"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}