A former coworker referred me, and HR contacted me about three weeks later.
The first round was technical.
Part one
Cryptocurrency "mining" is the operation where a "miner" places "transactions" in a candidate "block". Each block has a fixed size B = 100. At any point in time there is a set of transactions available for mining in an unordered array called the mempool.
A transaction can be described as an object with the following fields:
- Transaction ID
- Fee
- Size
The miner collects all fees from transactions they mine, thus they are incentivized to mine transactions that pay higher fee amounts.
Problem:
Implement a method mine_block(mempool) -> []Transaction which selects transactions from the mempool which maximize collected transaction fees and which still fit within block size B.
We are interested in a performant solution for a very large mempool rather than an optimal solution.
Part two
Let's extend our transaction model by adding 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, it means its parent has been mined already.
In certain cases, a transaction may not be chosen by miners because of its low fee. A technique known as Child-Pays-For-Parent (CPFP) allows a "child" transaction to pay a higher transaction fee in order to incentivize a miner to select both itself and its parent transaction in the same block. In doing so, the miner can collect the sum of the fees. CPFP can be applied recursively to multiple transactions within the same block, but cycles are not possible.
Problem:
- Extend the mine_block method to take into account CPFP incentives for the miner.
- STRICTLY OPTIONAL: Implement a method min_tee(mempool, parent_id, child_size) -> uint64 which returns the fee that a child transaction of size child_size should pay to include itself and its parent in the next block.
Discussion
Loading comments…