Katkat
Back

Maximize block fee with transaction selection

CoinbaseSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates algorithmic optimization and dependency-aware selection skills, focusing on resource-constrained selection (knapsack-like trade-offs) and graph-based dependency reasoning within the Coding & Algorithms domain.

You are given N transactions. Each transaction has:

  • id (unique identifier)
  • size (positive integer)
  • fee (positive integer)

You are building a block with a maximum total size of 100. Choose a subset of transactions whose total size is ≤ 100 such that the total fee is as large as possible.

Part 1 (no dependencies): Implement a practical, production-friendly approach (the interviewer does not require the mathematically optimal solution). You may not use a heap / priority queue. A common acceptable strategy is to sort transactions by fee / size (fee density) and greedily take them while capacity remains.

Part 2 (parent/child dependencies): Now transactions may have dependencies: a transaction can have a parentId, meaning you may include the child only if you also include its parent (and recursively all ancestors). For example, a dependency chain could be 1 -> 2 -> 3 (2 depends on 1, and 3 depends on 2).

Design an algorithm to select transactions under the same block size limit that respects dependencies and aims to maximize total fee. (You can assume dependencies form a forest/DAG rooted at transactions with no parent.)