Maximize block fee with transaction selection
Quick Overview
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.)