How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

Maximize block fee with transaction selection

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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.)

Quick Answer: 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.

Part 1: Greedy Block Fee Selection Without Dependencies

You are given N transactions. Each transaction is represented as (id, size, fee), where id is a unique positive integer, size is a positive integer, and fee is a positive integer. You are building a block with maximum total size 100. Implement a practical greedy selection policy: sort transactions by fee density fee / size in descending order, then scan the sorted list and include a transaction if it fits in the remaining block capacity. You may not use a heap or priority queue. To make results deterministic, break density ties by higher fee first, then smaller size first, then smaller id first. Return the total fee obtained by this greedy policy.

Constraints

0 <= len(transactions) <= 100000
Each transaction is (id, size, fee)
id is a unique positive integer
1 <= size <= 10^9
1 <= fee <= 10^9
Block capacity is exactly 100
Do not use a heap or priority queue

Examples

Input: ([(1, 50, 100), (2, 30, 90), (3, 60, 120), (4, 20, 30)],)

Expected Output: 210

Explanation: Sorted by density with tie-breaks: transaction 2, then 3, then 1, then 4. The greedy policy takes 2 and 3 for total size 90 and total fee 210.

Input: ([],)

Expected Output: 0

Explanation: There are no transactions to select.

Input: ([(10, 101, 1000)],)

Expected Output: 0

Explanation: The only transaction is larger than the block capacity, so it is skipped.

Input: ([(1, 25, 50), (2, 50, 100), (3, 25, 40), (4, 75, 120)],)

Expected Output: 190

Explanation: Transactions 1 and 2 have equal density, so transaction 2 comes first due to higher fee. The greedy policy takes 2, then 1, skips 4 because it does not fit, and takes 3.

Input: ([(1, 80, 160), (2, 30, 90), (3, 70, 140), (4, 20, 30)],)

Expected Output: 230

Explanation: The greedy policy takes transaction 2 first, skips transaction 1 because it no longer fits, then takes transaction 3.

Hints

Sort by fee per unit size, not by fee alone.
When comparing fee / size values, cross-multiplication avoids floating-point precision issues.

Part 2: Optimal Block Fee Selection With Parent Dependencies

You are given N transactions. Each transaction is represented as (id, size, fee, parent_id). If parent_id is not -1, then the transaction may be included only if its parent transaction is also included. This requirement applies recursively, so selecting a transaction requires selecting all of its ancestors. The dependency graph is guaranteed to be a forest: each transaction has at most one parent, parent_id is either -1 or the id of another transaction, and there are no cycles. You are building a block with maximum total size 100. Return the maximum possible total fee of any valid subset of transactions whose total size is at most 100 and whose dependencies are respected.

Constraints

0 <= len(transactions) <= 1000
Each transaction is (id, size, fee, parent_id)
id is a unique positive integer
parent_id is -1 or the id of an existing transaction
Each transaction has at most one parent
The dependency graph has no cycles
1 <= size <= 10^9
1 <= fee <= 10^9
Block capacity is exactly 100

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no transactions.

Input: ([(1, 50, 60, -1), (2, 40, 50, -1), (3, 60, 70, -1)],)

Expected Output: 120

Explanation: There are no dependencies. The best valid subset is transactions 2 and 3, with total size 100 and total fee 120.

Input: ([(1, 40, 10, -1), (2, 30, 100, 1), (3, 30, 100, 2)],)

Expected Output: 210

Explanation: Transaction 3 requires 2, and 2 requires 1. All three fit exactly with total size 100 and total fee 210.

Input: ([(1, 40, 5, -1), (2, 40, 100, 1), (3, 60, 80, -1), (4, 50, 70, -1)],)

Expected Output: 105

Explanation: The best subset is transactions 1 and 2. Transaction 2 has high fee but requires transaction 1, so the combined package has size 80 and fee 105.

Input: ([(1, 20, 20, -1), (2, 50, 80, 1), (3, 50, 90, 1), (4, 60, 95, -1)],)

Expected Output: 115

Explanation: The best subset is transactions 1 and 4, with size 80 and fee 115. Although children 2 and 3 are available after selecting 1, neither can fit together with transaction 4.

Hints

For each node, compute a small knapsack table for capacities 0 through 100.
When processing a node, first force the node itself to be selected, then merge in each child subtree. After that, also allow the option of selecting nothing from that subtree.

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.