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. ```text 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. ```hint Room is the scarce resource Compare two transactions with the same fee but different sizes. Ask which one leaves more room for everything else, what that suggests about how to rank candidates, and what to do when the next candidate does not fit. ``` #### 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. ```hint Score what the block actually gains When you consider a transaction, the block gains that transaction plus every unmined ancestor it requires. Decide how to score that whole bundle, and what happens to other transactions' bundles once some of those ancestors are already in the block. ``` ```hint Output order Think about the order in which ancestors are added so that the returned list is valid without a separate sorting pass. ``` #### 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. ```hint Inclusion as a function of the fee The answer depends on what else competes for the space and on how your selection decides. Ask how the child's chance of being chosen changes as its fee grows, and what that lets you compute. ``` #### 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 ### What a Strong Answer Covers - Notices the speed-over-optimality requirement and justifies a heuristic instead of jumping to an exact knapsack - Correct handling of capacity, parent-first ordering, multi-level chains and shared parents - CPFP modeled by scoring a candidate together with the ancestors it requires, kept current as the block fills - Time and space complexity for each part that suits a very large mempool - Tests for a parent too cheap to choose alone, a chain deeper than one level, and a chain larger than the remaining room ### Follow-up Questions - A parent has several children, each paying a moderate fee; no single child makes the parent worth including, but all of them together would. Does your procedure include them, and how would you change it if it should? - New transactions keep arriving between blocks. How would you maintain the candidate scores incrementally instead of rebuilding them for every block? - The interviewer now wants the best possible fee for capacity 100. How would you compute it with and without parent dependencies, and what would it cost? - How would you show that your heuristic is good enough in practice, not merely valid?