Coinbase Software Engineer Interview Experience — Mempool Block Packing and CPFP Phone Screen

It was the problem about picking transactions from a mempool to pack into a block. I hadn't really touched this area before, so I was a bit lost when I first read the problem.

Part one gives an unsorted array of transactions, each with an id, fee, and size. The block capacity is fixed at 100. You pick some transactions to put in, the total size can't go over, and you want to collect as much fee as possible, then return the selected transactions. The problem explicitly says the mempool will be huge and they care more about speed, so you don't have to find the optimal solution. Read that condition carefully first, because it's easy to jump straight to thinking knapsack.

Part two adds a parent ID to each transaction. To select a child, its parent must be placed in the same block first, and the returned order also has to have the parent before the child. If there is no parent ID, it means the parent has already been mined and you don't need to worry about it.

Then there's CPFP, child pays for parent. Roughly, the parent's own fee is very low, so on its own it isn't worth picking, but the child is willing to pay more, and looked at together they might be worth it. So you can't only look at the child's own fee, you also have to consider the fee and size of the parent it depends on.

This dependency can go up several levels, so it's not guaranteed to be just one parent-child pair, though the problem guarantees there are no cycles. If you pick a child, you have to load the whole chain it needs along with it, and the total still can't exceed 100. I felt this part was much more convoluted than part one. It looks like only one field was added, but suddenly there's a lot more to think about.

Finally, the problem statement had an optional part: given a parent ID and the size of a child, how much fee does this child have to pay at minimum so that it and its parent get into the next block. This part was marked strictly optional, so I focused on the earlier parts first.

Waiting for follow-up news. I feel like you should at least know what CPFP is beforehand, otherwise reading that English problem statement on the spot takes quite a bit of time.