👨‍💻
Cracking-Interview
  • Data Structures and Algorithms
  • Arrays
    • 1. Two Sums
    • 2. Rotate Array
    • 3.Remove Duplicates from sorted array
    • 4.Merge Two Sorted Array
    • 5.Majority Element
    • 6.Rotate Image
    • 7.Merge Intervals
    • 8.Increasing Triplet Subsequence
    • 9.Set Matrix Zeroes
    • 10.Product of Array Except Self
    • 11.Container With Most Water
    • 12.Next Permutation
    • 13.Next Greater Element III
    • 14.Largest Number
    • 15.Candy
    • 16.Shortest Unsorted Continuous Subarray
    • 17.Sort Colors(Sort array of 0, 1, 2)
    • 18.Queue Reconstruction by Height
    • 19.Task Scheduler
    • 20.Trapping Rain Water
    • 21.Search a 2D Matrix II
    • 22. Spiral Matrix
    • 23.Median of Two Sorted Arrays
    • 24.Count inversion of an array
    • 25. Reverse Pairs
    • 26. Count Servers that Communicate
    • 27. 3Sum
    • 28. 4Sum
    • 29. Game of Life
    • 30. Sort the Matrix Diagonally
    • 31. Push Dominoes
    • 32. Corporate Flight Bookings
    • 33. Rotating the Box
    • 34. Interval List Intersections
    • 35. Insert Interval
    • 36. Minimum Moves to Equal Array Elements II
    • 37. Pairs of Songs With Total Durations Divisible by 60
    • 38. Remove Covered Intervals
    • Juggling Algorithm
    • Moore’s Voting Algorithm
    • Two Pointer Method
  • Linked List
    • 1.Odd-Even Linked List
    • 2.Add Two Numbers
    • 3. Insert in a Sorted List
    • 4.Rotate List
    • 5.Palindrome Linked List
    • 6.Point of insertion between two Linked List
    • 7.Delete Node in a Linked List
    • 8.Middle of the Linked List
    • 9.Linked List Cycle
    • 10. Swapping Nodes in a Linked List
    • 11.Swap Nodes in Pairs
    • 12.Merge Two Sorted Lists
    • 13.Reverse a Linked List
    • 14. Reverse Linked List II
    • 15.Copy List with Random Pointer
    • 16.Remove Duplicates from Sorted List
    • 17. Merge k Sorted Lists
    • 18. Remove Nth Node From End of List
    • 19. Sort List
    • 20. Reverse Nodes in k-Group
    • 21. Partition List
    • 22. Flattening a Linked List
    • Basic Implementation of Singly Linked List
    • Basic Implementation of Doubly Linked List
  • Strings
    • 1.Reverse Words in a String
    • 2. Is Subsequence
    • 3.Valid Anagram
    • 4.Add Binary
    • 5.Longest Common Prefix
    • 7.Valid Palindrome
    • 8.Implement strStr()
    • 9.String to Integer (atoi)
    • 10.Count and Say
    • 11.Longest Substring Without Repeating Characters
    • 12. Longest Substring with At Most K Distinct Characters
    • 13. Longest Substring with At Least K Repeating Characters
    • 14. Find All Anagrams in a String
    • 15. Permutation in String
    • 16. Maximum Number of Vowels in a Substring of Given Length
    • 17. Partition Labels
    • 18. Minimum Window Substring
    • 19. Compare Version Numbers
    • 20. Shortest Distance to a Character
    • 21. Count Number of Homogenous Substrings
    • 22. Remove Duplicate Letters
    • 23. Count Sorted Vowel Strings
    • 24. Get Equal Substrings Within Budget
    • 25. Sentence Similarity III
    • 26. Shifting Letters
    • 27. Longest Happy Prefix (imp)
    • 28. Sort Characters By Frequency
    • 29. String Compression
    • 30. Palindrome Pairs
    • 31. Shortest Palindrome(Imp)
    • 32. One Edit Distance
    • 33. Can Make Palindrome from Substring
    • 34. Greatest Common Divisor of Strings
    • KMP Algorithm for Pattern Searching
    • Rabin-Karp Algorithm for Pattern Searching
  • Binary Tree
    • Terminology and Formula
    • N-ary Tree
      • 1. N-ary Tree Preorder Traversal
      • 2. N-ary Tree Postorder Traversal
      • 3. N-ary Tree Level Order Traversal
    • Tree Traversals
      • 1.In-order Traversal
      • 2.Pre-order Traversal
      • 3.Post-order Traversal
      • 4.Level-order Traversal
      • 5.Vertical Order Traversal
      • 6. Binary Tree Level Order Traversal II
    • Problems Related to Binary Trees
      • 1.Maximum/Minimum Depth of Binary Tree
      • 2.Lowest Common Ancestor of a Binary Tree
      • 3.Symmetric Tree
      • 4.Path Sum
      • 5.Tree : Top View
      • 6. Diameter of Binary Tree
      • 7.Populating Next Right Pointers in Each Node
      • 8.Balanced Binary Tree
      • 9.Binary Tree Zigzag Level Order Traversal
      • 10.Invert Binary Tree
      • 11.Binary Tree Right Side View
      • 12.Validate Binary Tree Nodes
      • 13.Merge Two Binary Trees
      • 14.Flatten Binary Tree to Linked List
      • 15. Construct Binary Tree from Preorder and Inorder Traversal
      • 16. Construct Binary Tree from Inorder and Postorder Traversal
      • 17. Binary Tree Maximum Path Sum
      • 18. Sum Root to Leaf Numbers
      • 19. Subtree of Another Tree
      • 20. Even Odd Tree
      • 21. Delete Nodes And Return Forest
      • 22. Maximum Binary Tree
      • 23. Linked List in Binary Tree
      • 24. Longest Univalue Path
      • 25. Sum of Distances in Tree
      • 26. Distribute Coins in Binary Tree
      • 27. Find Duplicate Subtrees
      • 28. Serialize and Deserialize BST
      • 29. Serialize and Deserialize Binary Tree
      • 30. Path Sum III
      • 31. Delete Leaves With a Given Value
      • 32. All Possible Full Binary Trees
      • 33. All Nodes Distance K in Binary Tree
      • 34. Maximum Width of Binary Tree
  • Stack and Queue
    • Problems
      • 1.Min Stack
      • 2. Max Stack
      • 3.Valid Parentheses
      • 4.Evaluate Reverse Polish Notation
      • 5.Infix And Prefix and Postfix Conversions
      • 6.Next Greater Element I
      • 7.Next Greater Element II
      • 8.Sliding Window Maximum
      • 9.Gas Station (Circular Tour Problem)
      • 10.Daily Temperatures
      • 11.Decode String
      • 12. Largest Rectangle in Histogram
      • 13. Maximal Rectangle
      • 14. Minimum Remove to Make Valid Parentheses
      • 15. Map of Highest Peak
      • 16. Longest Valid Parentheses
      • 17. Online Stock Span
      • 18. Score of Parentheses
      • 19. Remove K Digits(imp)
      • 20. Design a Stack With Increment Operation
      • 21. Final Prices With a Special Discount in a Shop
      • 22. Valid Parenthesis String
      • 23. Reveal Cards In Increasing Order
      • 24. Remove All Adjacent Duplicates In String
      • 25. Number of Visible People in a Queue
      • 26.Number following a pattern
    • Implementation
      • Implementation of Queue
      • Implementation of Stack
      • Implementation of Circular Queue
      • Implement Queue using Stacks
      • Implement Stack using Queues
  • Hash Table
    • Designing and Definitions
      • Techniques of hashing and collision resolution
      • Design HashSet
      • Design HashMap
    • Problems
      • 1.Intersection of Two Arrays
      • 2.Happy Number
      • 3.Contains Duplicate
      • 4.Find the Duplicate Number
      • 5. Find All Duplicates in an Array
      • 6. Isomorphic Strings
      • 7. Group Anagrams
      • 8. Single Number
      • 9.Valid Sudoku
      • 10.Jewels and Stones
      • 11.First Missing Positive
      • 12. LRU Cache (V.IMP)
      • 13. Encode and Decode TinyURL
      • 14. Alphabet Board Path
  • Binary Search
    • Template I
      • Basic Binary Search
      • 1.Search in a Sorted Rotated Array
      • 5.Sqrt(x)
    • Template II
      • 2.Find Minimum in Rotated Sorted Array
    • Template III
      • 3.Find Peak Element
      • 4. Find First and Last Position of Element in Sorted Array
  • Binary Search Tree
    • 1.Is This a Binary Search Tree
    • 2.Search in a Binary Search Tree
    • 3.Insert into a Binary Search Tree
    • 4.Delete Node in a BST
    • 5.Lowest Common Ancestor of a Binary Search Tree
    • 6.Construct Binary Search Tree from Preorder Traversal
    • 7.Convert Sorted Array to Binary Search Tree
    • 8. Convert Sorted List to Binary Search Tree
    • 9.Kth Smallest Element in a BST
    • 10.Trim a Binary Search Tree
    • 11.Two Sum IV - Input is a BST
    • 12. Binary Search Tree to Greater Sum Tree / Greater Tree
    • 13. Balance a Binary Search Tree
    • 14. Binary Search Tree Iterator
    • 15. Unique Binary Search Trees
    • 16. Unique Binary Search Trees II
    • 17. Inorder Successor in BST
  • Bit manipulation
    • Bitwise Operations
    • 1.Reverse Bits
    • 2.Counting Bits
    • 3.Number of 1 Bits
    • 4.Hamming Distance
    • 5. Power of Two
    • 6. Complement of Base 10 Integer
  • Graph
    • 1.Maximum number of edges to be removed to contain exactly K connected components in the Graph
    • 2. Social Networking Graph
    • 3.The Flight Plan
    • 4.Is it a tree?
    • 5.Possible Bipartition
    • 6.Longest path in an undirected tree
    • 7.Keys and Rooms
    • 8.Is Graph Bipartite?
    • 9.Number of Islands
    • 10. Number of Provinces
    • 11.Surrounded Regions
    • 12. All Paths From Source to Target
    • 13.Word Ladder
    • 14.Rotting Oranges
    • 15.Course Schedule
    • 16.Course Schedule II
    • 17. Minimum Number of Vertices to Reach All Nodes
    • 18.Network Delay Time
    • 19. 01 Matrix
    • 20. Cheapest Flights Within K Stops
    • 21. Critical Connections in a Network
    • 22.Word Search
    • 23. Minimum Time to Collect All Apples in a Tree
    • 24. Time Needed to Inform All Employees
    • 25. As Far from Land as Possible
    • 26. Clone Graph
    • 27. Min Cost to Connect All Points
    • 28. Find the City With the Smallest Number of Neighbors at a Threshold Distance
    • 29. Number of Operations to Make Network Connected
    • 30. Open the Lock
    • 31. Word Search II
    • 32. Number of Ways to Arrive at Destination
    • 33. Knight On Chess Board
    • 34. Shortest Bridge
    • 35. Pacific Atlantic Water Flow
    • 36. Making A Large Island
    • 37. Path with Maximum Probability
    • Graph Algorithms
      • 1.DFS
      • 2.BFS
      • 3.Prim's MST
      • 4.Kruskal (MST)
      • 5.Dijkstra’s Algorithm(Single Source Shortest Path)
      • 6. Floyd Warshall's Algorithm(All Pair Sortest Path)
      • 7. Topological Sort
      • 8. Find if the given edge is a bridge in graph.
  • Disjoint Sets(Union-Find)
    • 1.Implementation of union find
    • 2.Social Network Community
    • 3. Graph Connectivity With Threshold
    • 4. Redundant Connection
    • 5. Smallest String With Swaps
    • 6. Accounts Merge
  • Heap and Priority Queue
    • Concepts of Heap
      • Building Max Heap
    • 1.Kth Largest Element in an Array
    • 2.Kth Largest Element in a Stream
    • 3.Top K Frequent Elements
    • 4.Kth Smallest Element in a Sorted Matrix
    • 5. Find Kth Largest XOR Coordinate Value
    • 6. Top K Frequent Words
    • 7. Find Median from Data Stream
    • 8. Maximum Average Pass Ratio
    • 9. Longest Happy String
    • 10. K Closest Points to Origin
    • 11. Reorganize String
    • 12. Find the Kth Largest Integer in the Array
    • 13. Smallest range in K lists
  • Trie
    • 1. Implement Trie (Prefix Tree)
    • 2. Replace Words
    • 3.Design Add and Search Words Data Structure
    • 4. Search Suggestions System
  • Dynamic Programming
    • 1.House Robber
    • 2.Climbing Stairs
    • 3.Longest Palindromic Substring
    • 4.Longest Palindromic Subsequence
    • 5.Best Time to Buy and Sell Stock
    • 6.Best Time to Buy and Sell Stock with Cooldown
    • 7.Unique Paths
    • 8.Minimum Path Sum
    • 9.Longest Increasing Subsequence
    • 10.Longest Common Subsequence
    • 11.Longest Consecutive Sequence
    • 12.Coin Change
    • 13.Coin Change 2
    • 14.Target Sum
    • 15.Partition Equal Subset Sum
    • 16. Last Stone Weight II
    • 17.Word Break
    • 18. Word Break II
    • 19.Burst Balloons
    • 20. Uncrossed Lines
    • 21. Wildcard Matching
    • 22. Maximal Square
    • 23. Perfect Squares
    • 24. Decode Ways
    • 25. Minimum Cost For Tickets
    • 26. Number of Dice Rolls With Target Sum
    • 27. Delete Operation for Two Strings
    • 28. Maximum Length of Repeated Subarray
    • 29. Longest String Chain
    • 30. Maximum Length of Pair Chain
    • 31. Minimum Falling Path Sum
    • 32. Predict the Winner
    • 33. Delete and Earn
    • 34. House Robber III
    • 35. Partition to K Equal Sum Subsets
    • 36. Different Ways to Add Parentheses
    • 37. Count Square Submatrices with All Ones
    • 38. 2 Keys Keyboard
    • 39. Palindrome Partitioning II
    • 40. Integer Break
    • 41.Cutting a Rod
    • 42. Number of Longest Increasing Subsequence
    • 43. Russian Doll Envelopes
    • 44. 0-1 Knapsack
    • 45. Interleaving String
    • 46. Edit Distance
    • 47. Minimum Insertion Steps to Make a String Palindrome
    • 48.Jump Game
    • 49. Shortest Common Supersequence
    • 50. Length of Longest Fibonacci Subsequence
    • 51. Maximum Alternating Subsequence Sum
    • 52. Palindromic Substrings
    • 53. Distinct Subsequences
    • 54. Best Team With No Conflicts
    • 55. Partition Array for Maximum Sum
    • 56. Ones and Zeroes
  • Greedy Algorithms
    • 1.Activity Selection
    • 2. N meetings in one room
    • 3.Minimum Platforms
    • 4. Car Pooling
    • 5. Maximum Population Year
    • 6.Meeting Rooms
    • 7. Equal Sum Arrays With Minimum Number of Operations
    • 8. Two City Scheduling
    • 9. Non-overlapping Intervals
    • 10. Minimum Number of Arrows to Burst Balloons
    • 11. Maximum Profit in Job Scheduling{IMP}
    • 12.Huffman Coding
    • 13. Minimum Cost Tree From Leaf Values
    • 14.Maximum Number of Events That Can Be Attended
    • 15. Video Stitching
    • 16. Minimum Number of Taps to Open to Water a Garden
  • Backtracking
    • 1.Subsets and Subset II
    • 2.Combinations
    • 3.Generate Parentheses
    • 4.Letter Combinations of a Phone Number
    • 5.Palindrome Partitioning
    • 6.Combination Sum and Combination Sum II
    • 7.Permutations
    • 8. Permutations II
    • 9. Letter Case Permutation
    • 10. Split a String Into the Max Number of Unique Substrings
    • 11. Path with Maximum Gold
    • 12. N-Queens
    • 13. N-Queens II
    • 14. Sudoku Solver
    • 15. Permutation Sequence
    • 16. Beautiful Arrangement
  • Sub Array and Sliding Window Problems
    • 1.Maximum Subarray Sum
    • 2.Maximum Product Subarray
    • 3.Maximum Sum Circular Subarray
    • 4. Maximum Absolute Sum of Any Subarray
    • 5. K-Concatenation Maximum Sum
    • 6.Subarray Sum Equals K
    • 7. Continuous Subarray Sum
    • 8. Contiguous Array
    • 9.Minimum Size Subarray Sum >=k (positive no)
    • 10. Max Subarray sum of positive no <= k
    • 11. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
    • 12. Maximum Subarray Sum with One Deletion
    • 13. Shortest Subarray with Sum at Least K (Negative Numbers)
    • 14. Frequency of the Most Frequent Element
    • 15. Count Number of Nice Subarrays
    • 16. Binary Subarrays With Sum
    • 17.Number of Substrings Containing All Three Characters
    • 18. Find Two Non-overlapping Sub-arrays Each With Target Sum
    • 19. Maximum Points You Can Obtain from Cards
    • 20. Longest Repeating Character Replacement
    • 21. Subarrays with K Different Integers
    • 22. Replace the Substring for Balanced String
    • 23. Maximize the Confusion of an Exam / Max Consecutive Ones III
    • 24. Subarray Sums Divisible by K
  • Design
    • 1. Design Twitter
    • 2. Design Browser History
    • 3. Snapshot Array
  • Maths
    • Formula
    • 1.Count Prime
    • 2.Pascal's Triangle
    • 3.Extra Long Factorials
    • 4.Factorial Trailing Zeroes
    • 5.Excel Sheet Column Number
    • 6.HCF and LCM
    • 7. Fizz Buzz
    • 8. Rearrange an array so that arr[i] becomes arr[arr[i]]
    • 9. XOR Queries of a Subarray
    • 10. Find second largest element
  • Sorting-Algorithms
    • Merge Sort
    • Quick Sort
    • Heap Sort
    • Selection Sort
    • Bubble Sort
    • Insertion Sort
  • Expected Interview MCQ and Questions c++
  • Concepts in C++
  • System Design Questions
  • 💾DBMS
    • Introduction
    • RBMS
    • JOINS
    • SQL
  • 🖥️OS
    • OS and Its Types
    • Process Concept and Threads
    • Process Synchronization
    • Deadlock in Operating System
    • Memory Management
    • Imp Questions of OS for Interviews
  • 🚙OOPS
    • Introduction and Definitions
  • 📨COMPUTER-NETWORKS
    • OSI | TCP IP Model
    • Topology
    • Network Devices
    • IP Address
Powered by GitBook
On this page
  • Linear and Misc Dp Questions
  • Longest Increasing Subsequence variants:
  • Partition Subset / Target Sum:
  • Palindrome:
  • Matrix/2D Array:
  • Minimax DP:
  • Longest Common Subsequence Variant:
  • Coin Change variant:
  • State machine:
  • Matrix multiplication variant:
  • Dp on Strings
  • Unbounded Knapsack:
  • Dp on Trees:

Was this helpful?

Dynamic Programming

Previous4. Search Suggestions SystemNext1.House Robber

Last updated 3 years ago

Was this helpful?

Majority of the Dynamic Programming problems can be categorized into two types:

1. Optimization problems. 2. Combinatorial problems.

  • The optimization problems expect you to select a feasible solution, so that the value of the required function is minimized or maximized.

  • Combinatorial problems expect you to figure out the number of ways to do something, or the probability of some event happening.

Linear and Misc Dp Questions

Longest Increasing Subsequence variants:

Partition Subset / Target Sum:

Palindrome:

Matrix/2D Array:

Minimax DP:

Longest Common Subsequence Variant:

Coin Change variant:

State machine:

Matrix multiplication variant:

Dp on Strings

Unbounded Knapsack:

Dp on Trees:

1.House Robber
2.Climbing Stairs
11.Longest Consecutive Sequence
20. Uncrossed Lines
24. Decode Ways
38. 2 Keys Keyboard
44. 0-1 Knapsack
48.Jump Game
55. Partition Array for Maximum Sum
9.Longest Increasing Subsequence
29. Longest String Chain
30. Maximum Length of Pair Chain
42. Number of Longest Increasing Subsequence
43. Russian Doll Envelopes
50. Length of Longest Fibonacci Subsequence
54. Best Team With No Conflicts
15.Partition Equal Subset Sum
16. Last Stone Weight II
14.Target Sum
35. Partition to K Equal Sum Subsets
3.Longest Palindromic Substring
4.Longest Palindromic Subsequence
39. Palindrome Partitioning II
47. Minimum Insertion Steps to Make a String Palindrome
52. Palindromic Substrings
7.Unique Paths
8.Minimum Path Sum
22. Maximal Square
31. Minimum Falling Path Sum
37. Count Square Submatrices with All Ones
32. Predict the Winner
33. Delete and Earn
10.Longest Common Subsequence
28. Maximum Length of Repeated Subarray
49. Shortest Common Supersequence
53. Distinct Subsequences
12.Coin Change
13.Coin Change 2
23. Perfect Squares
25. Minimum Cost For Tickets
56. Ones and Zeroes
5.Best Time to Buy and Sell Stock
6.Best Time to Buy and Sell Stock with Cooldown
51. Maximum Alternating Subsequence Sum
19.Burst Balloons
17.Word Break
18. Word Break II
21. Wildcard Matching
27. Delete Operation for Two Strings
36. Different Ways to Add Parentheses
45. Interleaving String
46. Edit Distance
40. Integer Break
41.Cutting a Rod
34. House Robber III