How should I practice Tree-Dependent Knapsack?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Tree-Dependent Knapsack associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Tree-Dependent Knapsack

Google● HardINTERNNEW GRADPHONE SCREEN

Learn

Problem statement

You are given n items arranged as one rooted dependency tree. Item i has cost cost[i], value value[i], and parent parent[i]. The root has parent -1.

You may select any set of items whose total cost is at most capacity. Selecting a non-root item requires selecting its parent, which also recursively requires every ancestor through the root.

Return the maximum total value of a valid selected set. Selecting no items is allowed.

Function

maximizeDependentValue(parent: int[], cost: int[], value: int[], capacity: int) → int

Examples

Example 1

parent = [-1,0,0,1]cost = [2,2,3,2]value = [3,4,5,6]capacity = 6return = 13

Select items 0, 1, and 3. Their total cost is 6, their value is 13, and every selected item's parent is present.

Example 2

parent = [-1,0,0]cost = [5,1,1]value = [2,100,100]capacity = 2return = 0

The root does not fit, so neither child can be selected.

Example 3

parent = [-1,0,0,2]cost = [1,3,2,2]value = [1,8,4,10]capacity = 5return = 15

Select the root, item 2, and item 3 for total cost 5 and value 15.

Constraints

1 <= n == parent.length == cost.length == value.length <= 200.
Exactly one index has parent -1; all other parent indices define one rooted tree.
0 <= cost[i] <= capacity <= 2000.
0 <= value[i] <= 10^6.
The answer fits in a signed 32-bit integer.