Mempool Block Assembly And CPFP
Asked of: Software Engineer
Last updated
What's being tested
These problems test dependency-aware greedy selection: maximizing fees under a fixed block-size budget while respecting parent-before-child constraints and Child-Pays-For-Parent (CPFP) fee incentives. You must demonstrate graph traversal, effective-fee ranking, efficient indexing for a very large mempool, and careful handling of capacity, duplicates, and cycles.
Patterns & templates
-
Compute transaction density as
fee / size; use a max-heap for greedy selection, yielding roughlyO(n log n)time andO(n)space. -
Represent parent links with adjacency lists and
in_degree; select ancestors before descendants using topological ordering or iterative DFS. -
For CPFP, rank a package by
sum(fees) / sum(sizes); include the unconfirmed parent and child atomically when package capacity permits. -
Maintain
selectedandvisitedsets; these prevent duplicate inclusion when multiple chosen transactions share ancestors. -
Before insertion, verify
used_size + tx.size <= block_limit; never assume a high-fee transaction fits the remaining capacity. -
Use a dependency-aware priority queue with lazy invalidation when package scores change after ancestors are selected.
-
Validate malformed input—missing parents, self-links, cycles, zero sizes, and oversized transactions—rather than allowing infinite traversal or division by zero.
Common pitfalls
Pitfall: Sorting only by individual
fee / sizecan reject a low-fee parent required by a highly profitable child; compare dependency packages instead.
Pitfall: Adding a child first violates consensus ordering, while recursively adding parents without deduplication overcounts size and fees.
Pitfall: Claiming globally optimal knapsack selection for a huge
mempoolis usually unrealistic; state the greedy approximation and its complexity clearly.
Practice these
The practice cards below cover the canonical variants—solve all of them and time yourself.
Practice questions
- Pick Mempool Transactions for a Block with Parent Dependencies and CPFPCoinbase · Software Engineer · Technical Screen · hard
- Fee-Maximizing Block Assembly from a Mempool with Child-Pays-For-ParentCoinbase · Software Engineer · Technical Screen · medium
- Implement Game Physics and Block MiningCoinbase · Software Engineer · Onsite · hard
- Maximize block fee with transaction selectionCoinbase · Software Engineer · Onsite · hard
Related concepts
- Wallets, Payments, And Refund LedgersSystem Design
- Greedy, Heaps, And Scheduling OptimizationCoding & Algorithms
- Dynamic Programming For Selection ProblemsCoding & Algorithms
- Heaps, Top-K, And Streaming SelectionCoding & Algorithms
- Distributed Job Scheduling For Payment Workflows
- Reliable Payment Processing And IdempotencySystem Design