Select Transactions with Child-Pays-for-Parent Packages
Problem statement
A mempool contains an unordered collection of transactions. Each has a unique identifier, a nonnegative fee, a positive size, and parent dependencies. A block has limited size. Select transactions that collect useful fees without exceeding that limit; every selected transaction must appear after all of its required parents in the returned order.
The interview uses capacity 100 and emphasizes a very large mempool: a fast approximation is preferred over an exact optimum. Child-Pays-For-Parent (CPFP) means evaluating a child together with the unselected ancestors it needs, so a high-fee child can make a low-fee parent worthwhile. Dependencies may have several levels and are acyclic. An empty parent list means no unmined parent is required.
Authored Practice Contract
For this exercise, implement the following deterministic package-greedy policy. The array parameters expose the transaction fields; capacity permits smaller blocks for practice, up to the source capacity of 100. The retained parent-list adapter supports several parents; the report describes one parent identifier.
- Initially no transaction is selected. For each unselected transaction, form its package: itself and every recursive ancestor that is not already selected. Count a shared ancestor only once.
- Consider only packages whose total size fits the remaining capacity and whose total fee is positive. Choose the package with the largest ratio of total fee to total size. Compare ratios exactly. If ratios tie, choose the candidate transaction with the lexicographically smallest identifier.
- Append the chosen package in this exact order: depth-first visit the candidate's parents in lexicographic identifier order, recursively visit their parents, and append each transaction after its parents. Skip already selected or already visited transactions. Mark all appended transactions selected and subtract their sizes.
- Recompute remaining packages and repeat. Stop when no positive-fee package fits. Return the selected identifiers in append order. This policy does not promise maximum possible total fees.
Every parent named in the input is present in the mempool, but it may occur anywhere in the input arrays. Transactions whose complete ancestor closure exceeds the total block capacity can never be selected. Empty input or zero capacity returns an empty array.
Optional discussion: minimum child fee
Given a parent identifier and a proposed child's size, how much fee must that new child pay to enter the next block with its required ancestors? This is strictly optional and is not part of selectBlockTransactions. A numerical threshold depends on the competing mempool and the chosen selection/tie policy; discuss those assumptions rather than claim a universal next-block guarantee.
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 child package has fee 11/size 80, larger than x at 7/60 and p at 1/40. Select that package and emit p before c.
Example 2
ids = ["a","b","c"]fees = [5,5,10]sizes = [50,50,100]parents = [[],[],[]]capacity = 100return = ["a","b"]All three initial ratios are equal. Identifier a wins the tie, then b fits the remaining 50. Transaction c no longer fits. Return [a,b].
Example 3
ids = ["a","b"]fees = [3,100]sizes = [60,50]parents = [[],["a"]]capacity = 100return = ["a"]The child package needs size 110 and cannot fit. Select a alone; the remaining capacity 40 cannot fit the child of size 50.
Constraints
0 <= ids.length <= 10000; all four transaction arrays have the same length.- Identifiers are unique strings of 1 to 20 lowercase ASCII letters or digits. Lexicographic order compares those characters directly.
0 <= fees[i] <= 10^9,1 <= sizes[i] <= 100, and0 <= capacity <= 100.- Each parent list has at most eight distinct identifiers, all present in
ids. The dependency graph is acyclic. - Bounds, deterministic selection, tie and output rules, and the multi-parent representation are authored practice assumptions. No exact global fee optimum is required.