Select a Fee-Maximizing Dependency-Closed Block
Coinbase● HardFULLTIMEPHONE SCREENProblem statement
A mempool contains transactions with unique identifiers, nonnegative fees, positive sizes, and zero or more parent transaction identifiers. A block may include a transaction only when it also includes every recursive parent.
Given a block-size capacity, return the dependency-closed subset with maximum total fee. The dependency graph is acyclic, and every parent appears earlier than its child in the input. Return selected identifiers in input order, which is therefore topological.
If several valid subsets have the same total fee, choose the one with smaller total size. If still tied, choose the lexicographically smaller sequence of returned identifiers. Return an empty array when no transaction fits.
Function
selectBlockTransactions(ids: String[], fees: int[], sizes: int[], parents: String[][], capacity: int) → String[]Examples
Example 1
ids = ["p","c","x"]fees = [1,10,7]sizes = [40,40,60]parents = [[],["p"],[]]capacity = 80return = ["p","c"]The parent-child package pays fee 11 in size 80, beating the independent transaction's fee 7.
Example 2
ids = ["a","b","c"]fees = [5,5,10]sizes = [50,50,100]parents = [[],[],[]]capacity = 100return = ["a","b"]Both [a,b] and [c] earn fee 10 with size 100. The returned identifier sequence [a,b] is lexicographically smaller.
Example 3
ids = ["a","b"]fees = [3,100]sizes = [60,50]parents = [[],["a"]]capacity = 100return = ["a"]The child cannot fit together with its required parent, while the parent alone is valid.
Constraints
0 <= ids.length <= 20.ids.length = fees.length = sizes.length = parents.length.- Identifiers are unique non-empty strings.
0 <= fees[i] <= 10^9and1 <= sizes[i] <= 100.0 <= capacity <= 100.- Every named parent exists at a smaller input index, and parent lists contain no duplicates.