Interview conceptCoding & Algorithms

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 roughly O(n log n) time and O(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 selected and visited sets; 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 / size can 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 mempool is 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

Related concepts