Pick Mempool Transactions for a Block with Parent Dependencies and CPFP

A mempool holds transactions that are waiting to be included in a block. Each transaction has an id, a fee that the miner collects for including it, and a size. A block has a fixed capacity of 100 size units. Write code that picks transactions for the next block so that their total size does not exceed the capacity and the total fee collected is as large as possible, and return the chosen transactions.

The problem states that the mempool can be very large and that running fast matters more than always finding the best possible selection. Read that requirement before choosing an approach: an answer that is guaranteed optimal but slow misses the point.

Later parts give transactions a parent and introduce child pays for parent (CPFP), where a child transaction's fee can justify including its low-fee parent.

Part 1 input (an unsorted array)
 {id: "t1", fee: 30, size: 60}
 {id: "t2", fee: 24, size: 30}
 {id: "t3", fee: 20, size: 40}
 {id: "t4", fee: 9, size: 10}
 {id: "t5", fee: 50, size: 120}

Part 2 adds a parent ID
 {id: "p", fee: 1, size: 40, parent_id: None} # its parent is already mined
 {id: "c", fee: 50, size: 20, parent_id: "p"} # c needs p in the same block

Constraints and Clarifications

• The block capacity is fixed at 100; the total size of the chosen transactions must not exceed it.
• The input array is not sorted.
• Speed matters more than optimality: a heuristic that is not always optimal is acceptable.
• From Part 2 on, a transaction without a parent ID has no unmined parent: its parent was already mined, so it imposes no constraint.
• Dependencies can be several levels deep, and the input has no cycles.
• Not given: the units and value ranges of fee and size, the size of the mempool, and whether to return ids or full transaction records. State your assumptions.

Clarifying Questions

• Are fees and sizes non-negative integers, and can a single transaction be larger than the whole block?
• Should the result be ids or full records, and does the order of the result matter before Part 2?
• Can several transactions name the same parent?
• Can a parent ID refer to a transaction that is not in the mempool, and if so, is the child invalid or treated as having a mined parent?
• Is the selection run once, or repeatedly as new transactions arrive and blocks are produced?

Part 1 — Fill one block quickly

Implement select_transactions(txs, capacity=100), returning the chosen transactions. Explain why it is fast enough for a very large mempool and how far from the best possible fee it can end up.

What This Part Should Cover

• A selection rule suited to a very large unsorted input, with its time and space complexity
• Handling of a candidate that does not fit in the remaining room, and of transactions larger than the block
• Inputs where the rule falls short of the best fee, and whether an exact method is affordable when the capacity is only 100

Part 2 — Parents and child pays for parent

Each transaction may now carry a parent_id. A child can be chosen only if its parent is placed in the same block, and in the returned list the parent must come before the child. A transaction without a parent ID has a parent that was already mined, so nothing else is needed for it. A parent can itself have a parent, so choosing a child can require a whole chain of unmined ancestors; the input has no cycles. Everything a chosen child needs goes into the block with it, and the total size still must not exceed 100.

This is where CPFP matters: a parent may pay so little that it is not worth choosing on its own, while its child pays enough that the parent and child together are worth the space. The selection therefore cannot look only at a child's own fee; it has to account for the fees and sizes of the ancestors the child brings along.

Clarifying Questions for this Part

• If a chain is too large to fit even in an empty block, should its ancestors still be considered on their own?
• Must the returned list keep each chain together, or is any order with every parent before its children acceptable?

What This Part Should Cover

• Validity: every chosen transaction's unmined ancestors are in the block and come before it
• A scoring rule that captures CPFP, so a low-fee parent can be pulled in by a well-paying descendant
• Keeping scores correct once some ancestors are already chosen, including parents shared by several children, with the overall complexity
• Chains several levels deep, and chains that cannot fit in the remaining room

Part 3 — Optional: the fee a child must pay

The problem ended with a strictly optional extension: given a parent ID and the size of a new child transaction that spends from that parent, compute the minimum fee the child must pay so that both the child and its parent get into the next block.

Clarifying Questions for this Part

• Is the next block the one your Part 2 procedure builds from the current mempool, with no other transactions arriving?
• Are fees integers, and does the child win or lose a tie with a competing transaction?

What This Part Should Cover

• A precise definition of "gets into the next block" in terms of the selection procedure and the current mempool
• A method to find the minimum fee, and its cost compared with running the selection once
• The cases where no fee is enough and where the child needs no extra fee at all