Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
A problem has an optimal substructure if its optimal solution can be constructed from the optimal solutions of its subproblems.
For instance, consider the 0/1 knapsack problem: Given a set of $n$ items with their weights and values and a knapsack of capacity $C$, put in the items that maximize the value such that the sum of the weights does not exceed $C$.
The maximum value can be obtained by taking the max of the following two values:
Notice that the maximum value obtained by adding $n-1$ items is the optimal solution to a subproblem. The optimal solution of the problem can be constructed using the optimal solutions of the sub-problems. Hence, the 0/1 Knapsack problem has an optimal substructure.
Dynamic programming can be used to solve a problem with optimal substructure and overlapping subproblems.
Greedy algorithms may be used to solve a problem with optimal substructure.
RELATED TAGS
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.