NewProject Coding is here — build features and fix bugs in real codebases with an AI assistantSee what's new

In this follow-up question, each transaction now carries an optional parentId field. A parentId points to another transaction in the mempool that must be mined in the same block before the child transaction can be included.

  • A parent can have multiple children, but a child has at most one parent. No cycles are possible.
  • Child-Pays-For-Parent (CPFP): When evaluating a child transaction's priority, consider the combined fee and combined size of the child plus all its unmined ancestors (traversing up the chain to the root or the nearest already-mined ancestor).
  • Once a parent is mined, its cost is "paid for." Any child of an already-mined parent is evaluated using only its own remaining unmined ancestors.
  • If parentId is an empty string, the transaction has no prerequisites.

Extend mineBlock function with an additional parentIds parameter to account for these dependencies to achieve the best fee-to-size ratio. Return the selected transaction IDs in any order.

Example 1:

Input: transactionIds = ["tx1", "tx2", "tx3", "tx4"], fees = [10, 100, 40, 50], sizes = [50, 20, 30, 30], parentIds = ["", "tx1", "", ""], blockSize = 100 Output: ["tx4", "tx1", "tx2"] Explanation: "tx2" depends on "tx1", and their package has a combined fee of 110 and a combined size of 70, giving an effective ratio of ≈1.57. "tx3" has ratio ≈1.33, and "tx4" has ratio ≈1.67. Therefore, the miner selects "tx4", "tx1", and "tx2".

Example 2:

Input: transactionIds = ["tx1", "tx2", "tx3"], fees = [10, 80, 25], sizes = [20, 10, 20], parentIds = ["", "tx1", ""], blockSize = 50 Output: ["tx1", "tx2", "tx3"]

Example 3:

Input: transactionIds = ["tx1", "tx2", "tx3"], fees = [10, 80, 30], sizes = [20, 10, 10], parentIds = ["", "tx1", "tx1"], blockSize = 40 Output: ["tx1", "tx2", "tx3"]


Accepted
1.8k/3.8k
Acceptance Rate46.9%
Test Cases
Input
transactionIds =
fees =
sizes =
parentIds =
blockSize =
Output
Expected