Fee-Maximizing Block Assembly from a Mempool with Child-Pays-For-Parent

In cryptocurrency mining, a miner places transactions into a candidate block. Each block has a fixed size `B = 100`. At any point in time, the transactions available for mining are held in an unordered array called the mempool. A transaction is an object with these fields: - `id`: the transaction ID - `fee`: the fee the transaction pays to whoever mines it - `size`: the space the transaction takes up in a block The miner collects the fees of every transaction it mines, so it is motivated to mine transactions that pay higher fees. The interview has two parts, followed by a third that the interviewer marked as strictly optional. ### Constraints and Clarifications - A block holds transactions whose sizes sum to at most `B = 100`, measured in the same unit as `size`. - The mempool can be very large. The interviewer wants a performant solution for a very large mempool rather than an optimal one, so a fast heuristic that may leave some fee uncollected is acceptable. - Assume fees are non-negative integers, consistent with the unsigned 64-bit return type of the optional method in Part 3. ### Clarifying Questions - Are sizes positive integers, and can a single transaction be larger than `B`? - Does the order of the returned transactions matter in Part 1, and how should two equally attractive transactions be ranked? - Is `mine_block` called once on a snapshot of the mempool, or again and again as transactions arrive and leave? ### Part 1 — Select transactions for one block Implement `mine_block(mempool) -> list[Transaction]`, which selects transactions from the mempool that maximize the collected fees while still fitting within block size `B`. Aim for a solution that stays fast on a very large mempool rather than one that is guaranteed optimal, and state its time and space complexity. ```hint Speed over optimality Choosing the best subset under a size cap is a classic hard selection problem, and the prompt lets you give up optimality. Ask which single ordering of the mempool you could walk through once, and what to do when the next candidate does not fit. ``` #### What This Part Should Cover - The selection rule, and why it suits a block whose scarce resource is space - What happens when the next candidate no longer fits, and inputs on which the heuristic does badly - Time and memory on a very large mempool, compared with an exact method ### Part 2 — Parent links and Child-Pays-For-Parent The transaction model gains a `parent_id` field. A parent ID points to another transaction in the mempool that must be mined in the same block, before the child transaction can be mined. If a transaction has no parent ID, its parent has already been mined. Miners may pass over a transaction because its fee is low. A technique called Child-Pays-For-Parent (CPFP) lets a child transaction pay a higher fee so that a miner is motivated to select both the child and its parent in the same block, collecting the sum of their fees. CPFP can be applied recursively to several transactions within the same block, and cycles are not possible. Extend `mine_block` to take CPFP incentives into account. The block must still fit within `B`, every selected transaction's parent must be in the same block, and each parent must come before its child in the returned list. ```hint Rank what you actually take A high-fee child is worth nothing to the miner unless its parent comes with it. Decide which unit you should score and take as a whole, and how that unit's score changes once part of it is already in the block. ``` #### Clarifying Questions for this Part - Can one parent have several children? - What should happen to a transaction whose parent ID matches no transaction in the mempool? #### What This Part Should Cover - A score that accounts for the unmined ancestors a transaction drags in - Keeping scores correct after an ancestor has already been included through another child - A valid output: every needed parent present and listed before its children - The cost of the extended selection on a large mempool ### Part 3 — Minimum fee for a child (strictly optional) Implement `min_fee(mempool, parent_id, child_size) -> uint64`, which returns the fee that a new child transaction of size `child_size`, whose parent is `parent_id`, should pay so that the child and its parent are both included in the next block. ```hint Pin down "included" The answer only means something relative to a concrete selection rule. Ask whether, under your Part 2 rule, raising the child's fee can ever make inclusion less likely, and how you would find the smallest fee once you know that. ``` #### Clarifying Questions for this Part - Is "the next block" the block that your Part 2 `mine_block` would build from the current mempool plus the new child? - If the parent has unmined ancestors of its own, must the child's fee also pay to pull them in? - What should the method return when no fee can work, for example when the parent and the child together are larger than `B`? #### What This Part Should Cover - A precise definition of the minimum fee in terms of the selection rule - An algorithm that finds it, its cost, and exact integer arithmetic on fee rates - Inputs where any fee works and inputs where no fee can work ### What a Strong Answer Covers - Recognizing the knapsack structure and making an explicit, justified choice of speed over optimality - Deterministic tie-breaking and exact comparison of fee-per-size ratios - Treating a transaction and its unmined ancestors as one package whose score is updated as the block fills - Working code for Parts 1 and 2 with stated complexity, within the time of a technical screen - Edge cases: transactions larger than the block, missing parents, an empty mempool, and leftover space that no remaining transaction fits ### Follow-up Questions - The mempool changes continuously and blocks are built one after another. How would you maintain package scores incrementally instead of recomputing them for every block? - If a transaction could list several parents, so dependencies form a DAG instead of chains, what breaks in your scoring and how would you adapt it? - How would you measure how much fee the heuristic leaves uncollected, and against which exact baseline?