Blockchain miners choose which pending transactions will be placed into a block. A block has limited capacity, while every transaction has both a size and a fee. Your task is to choose transactions that collect as much total fee as possible without exceeding the block's size capacity.
The problem has two stages. Part 1 considers transactions without relationships, and Part 2 introduces dependencies between transactions.
You receive N transactions. Each transaction contains an id, a size, and a fee. You are also given block_size, which is the largest combined transaction size allowed in a single block.
Choose the transactions for the block so that:
block_size.Important: The expected approach should scale well and be suitable for production rather than guarantee the theoretical optimum. Real transaction pools may contain thousands of entries, and miners must construct blocks quickly. Prefer a greedy fee-density strategy, where density is the fee divided by the transaction's size, instead of dynamic programming.
class Transaction:
def __init__(self, id: str, size: int, fee: int):
self.id = id
self.size = size
self.fee = fee
def mine_block(transactions: list[Transaction], block_size: int) -> list[str]:
"""
Choose transaction IDs for a block while seeking the greatest total fee.
Args:
transactions: The transactions currently available
block_size: The block's maximum combined transaction size
Returns:
The IDs of the transactions placed in the block
Approach:
Order transactions by fee/size from highest to lowest, then
greedily accept each transaction that still fits.
"""
pass
transactions = [
Transaction("tx1", 30, 60), # ratio: 2.0
Transaction("tx2", 50, 200), # ratio: 4.0
Transaction("tx3", 40, 100), # ratio: 2.5
Transaction("tx4", 20, 30), # ratio: 1.5
Transaction("tx5", 10, 50), # ratio: 5.0
]
block_size = 100
result = mine_block(transactions, block_size)
# Density order: tx5(5.0), tx2(4.0), tx3(2.5), tx1(2.0), tx4(1.5)
# Include tx5 (10), leaving 90
# Include tx2 (50), leaving 40
# Include tx3 (40), leaving 0
# result: ["tx5", "tx2", "tx3"], total fee: 350
The result follows because the first three transactions in fee-density order exactly consume the available size and produce a total fee of 350.
Interviewer: "Suppose a transaction can now name a parent. A child may be mined only when its parent appears in that same block. A parent may have several children, although each child has no more than one parent. How would you obtain the greatest total fee?"
These dependency relationships create a forest. Selecting a child requires every transaction on its ancestor path to be selected in the same block.
Under this rule, consider each path from a root to a node as a candidate group. Because one parent may lead to several children, compare the value offered by the different branches.
class Transaction:
def __init__(self, id: str, size: int, fee: int, parent_id: str | None = None):
self.id = id
self.size = size
self.fee = fee
self.parent_id = parent_id
def mine_block_with_deps(transactions: list[Transaction], block_size: int) -> list[str]:
"""
Choose transactions by fee while honoring all parent relationships.
Rules:
- A child may be selected only when its parent is selected too
- A child has at most one parent, while a parent may have many children
- Compare ancestor-chain groups by their combined fee/size ratio
Args:
transactions: Available transactions, some of which specify parent_id
block_size: The block's maximum combined transaction size
Returns:
The IDs of the transactions placed in the block
"""
pass
Tree structure:
tx1 (size=30, fee=10)
├── tx2 (size=20, fee=80)
│ ├── tx3 (size=10, fee=50)
│ └── tx4 (size=10, fee=40)
└── tx5 (size=20, fee=20)
tx6 (size=15, fee=90) # independent, no parent
block_size = 100
Selecting tx3 also requires tx1 and tx2. Therefore, the group {tx1, tx2, tx3} has:
For the same reason, {tx1, tx2, tx4} has:
If tx3 and tx4 are initially assessed separately, both paths pay for tx1 and tx2. After the path ending at tx3 has been included, however, those ancestors are already present, so adding tx4 consumes only its own size of 10. Consequently, the candidates must be evaluated again after every selection.
block_size is small, such as 100? Discuss whether dynamic programming becomes practical and whether greedy selection should still be preferred.