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

Select transactions to maximize fees under size

Q: Select transactions to maximize fees under size

This question evaluates the ability to model and optimize resource allocation under capacity constraints, testing algorithmic skills in dynamic programming and combinatorial optimization for maximizing total fee.

Select transactions to maximize fees under size

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem: Max-fee block assembly You are given `N` transactions. Each transaction has: - `id` (unique) - `size` (positive integer) - `fee` (non-negative integer) A block has a maximum capacity `B` (total size). You must choose a subset of transactions to include in the block such that: - The sum of `size` of chosen transactions is `<= B` - The **sum of `fee`** is **maximized** ### Input - `N` transactions: `[(id, size, fee), ...]` - Block capacity `B` ### Output - The maximum achievable total fee, and/or the list of chosen transaction IDs. ### Constraints (example) - `1 <= N <= 2000` - `1 <= B <= 100` - `1 <= size <= B` - `0 <= fee <= 10^9` ## Follow-up: Parent/child dependencies Now each transaction may optionally have a `parent_id`. If a transaction is included, **all its ancestors must also be included**. Assume dependencies form a forest (no cycles). - Choose a valid subset within capacity `B` that maximizes total fee. Clarify what you would return if multiple optimal subsets exist (any is fine).

Quick Answer: This question evaluates the ability to model and optimize resource allocation under capacity constraints, testing algorithmic skills in dynamic programming and combinatorial optimization for maximizing total fee.

Max-fee block assembly

You are given `N` transactions. Each transaction is a tuple `(id, size, fee)` where `id` is unique, `size` is a positive integer, and `fee` is a non-negative integer. A block has a maximum capacity `B` (total size). Choose a subset of transactions to include in the block such that the sum of `size` of chosen transactions is `<= B` and the sum of `fee` is maximized. Return the maximum achievable total fee. This is the classic 0/1 knapsack problem: each transaction is an item with weight `size` and value `fee`, and the knapsack capacity is `B`. Example: transactions `[(1,50,60),(2,60,100),(3,40,30)]`, `B = 100`. Picking transactions 1 and 3 uses size 50+40=90 <= 100 for fee 60+30=90; picking 2 and 3 uses 60+40=100 for fee 100+30=130. The answer is 130.

Constraints

1 <= N <= 2000
1 <= B <= 100
1 <= size <= B
0 <= fee <= 10^9

Examples

Input: ([(1, 50, 60), (2, 60, 100), (3, 40, 30)], 100)

Expected Output: 130

Explanation: Pick transactions 2 and 3: size 60+40=100 <= 100, fee 100+30=130 — the maximum.

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

Expected Output: 220

Explanation: Pick 2 and 3: size 20+30=50, fee 100+120=220.

Input: ([], 100)

Expected Output: 0

Explanation: No transactions, so the best achievable fee is 0.

Input: ([(1, 100, 999)], 100)

Expected Output: 999

Explanation: The single transaction exactly fills the block; take it for fee 999.

Input: ([(1, 100, 50)], 99)

Expected Output: 0

Explanation: The only transaction has size 100 > capacity 99, so nothing fits and the fee is 0.

Input: ([(1, 1, 5), (2, 1, 5), (3, 1, 5)], 2)

Expected Output: 10

Explanation: Capacity 2 fits any two of the three size-1 transactions for fee 5+5=10.

Input: ([(1, 5, 0), (2, 3, 0)], 8)

Expected Output: 0

Explanation: Both transactions fit but all fees are 0, so the maximum total fee is 0.

Hints

Each transaction is either fully included or excluded — this is a 0/1 knapsack with weight = size and value = fee.
Use a 1-D DP array `dp[c]` = best total fee using capacity exactly up to `c`. Iterate capacity from high to low so each transaction is used at most once.
The interviewer in the real interview discouraged DP and asked for a fee/size ratio greedy; note that greedy is NOT optimal for 0/1 knapsack (it can be off), so DP is the correct exact solution. The answer is `max(dp)`.

Max-fee block assembly with parent/child dependencies

Follow-up to the block-assembly problem. Now each transaction is a tuple `(id, size, fee, parent_id)`. `parent_id` is `None` for a root transaction; otherwise it is the `id` of its parent. Dependencies form a forest (no cycles). If a transaction is included in the block, **all of its ancestors must also be included**. Choose a valid subset whose total `size` is `<= B` and whose total `fee` is maximized. Return the maximum achievable total fee. This is a tree-dependent (rooted-forest) knapsack. A valid selection is closed under taking ancestors. Solve with a tree DP: for each node compute, over its subtree, the best fee for each capacity given the node itself is taken (which makes its children eligible). Combine sibling subtrees and root trees as independent optional groups via knapsack merges. Example: root `(1,30,10,None)` with child `(2,30,100,1)`, `B = 100`. Taking child 2 forces taking parent 1: size 30+30=60 <= 100, fee 10+100=110. With `B = 50` the pair (60) does not fit, so you can take only the root for fee 10. If multiple optimal subsets exist, returning any one (or just the max fee) is acceptable.

Constraints

1 <= N <= 2000
1 <= B <= 100
1 <= size <= B
0 <= fee <= 10^9
Dependencies form a forest (each transaction has at most one parent, no cycles).
parent_id is None (or -1 in Java/C++) for root transactions.

Examples

Input: ([(1, 50, 60, None), (2, 60, 100, None), (3, 40, 30, None)], 100)

Expected Output: 130

Explanation: No dependencies (all roots), so it reduces to plain knapsack: take 2 and 3 for size 100, fee 130.

Input: ([(1, 30, 10, None), (2, 30, 100, 1)], 100)

Expected Output: 110

Explanation: Taking child 2 forces taking parent 1: size 30+30=60 <= 100, fee 10+100=110.

Input: ([(1, 30, 10, None), (2, 30, 100, 1)], 50)

Expected Output: 10

Explanation: The pair needs size 60 > 50, so child 2 is unreachable; the best valid choice is the root alone for fee 10.

Input: ([(1, 10, 5, None), (2, 10, 5, 1), (3, 10, 5, 2), (4, 10, 100, 3)], 30)

Expected Output: 15

Explanation: Chain 1->2->3->4. Reaching the fee-100 node 4 needs all four (size 40 > 30). With capacity 30 the best valid prefix is nodes 1,2,3 for fee 15.

Input: ([(1, 10, 5, None), (2, 10, 5, 1), (3, 10, 5, 2), (4, 10, 100, 3)], 40)

Expected Output: 115

Explanation: Capacity 40 fits the whole chain (size 40), unlocking node 4: fee 5+5+5+100=115.

Input: ([(1, 20, 5, None), (2, 30, 50, 1), (3, 30, 40, 1)], 50)

Expected Output: 55

Explanation: Root 1 has two children. To take child 2 you need root 1: size 20+30=50, fee 55. You cannot fit both children (20+30+30=80 > 50).

Input: ([(1, 20, 5, None), (2, 30, 50, 1), (3, 30, 40, 1)], 80)

Expected Output: 95

Explanation: Capacity 80 fits root 1 plus both children: size 20+30+30=80, fee 5+50+40=95.

Input: ([], 100)

Expected Output: 0

Explanation: No transactions, so the maximum fee is 0.

Input: ([(1, 100, 999, None)], 100)

Expected Output: 999

Explanation: A single root that exactly fills the block; take it for fee 999.

Input: ([(1, 100, 999, None)], 50)

Expected Output: 0

Explanation: The only transaction has size 100 > capacity 50, so nothing can be included and the fee is 0.

Hints

A valid selection must be closed under taking ancestors: if a node is chosen, every node on the path to its root is also chosen. Equivalently, you can only take a node once its parent is already taken.
Solve with a tree DP. For each node compute `dp[c]` = the best total fee achievable within its subtree using capacity at most `c` GIVEN the node itself is taken (this is what makes its children eligible).
Merge each child subtree into the parent's DP as an optional knapsack group (take that child subtree or skip it). Then merge the independent root trees the same way, each root being optional. The answer is the maximum over the final array.
The interviewer's original 'sort by fee/size ratio' greedy does not extend correctly to dependencies; the tree knapsack is the exact approach.

Select transactions to maximize fees under size

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Max-fee block assembly

Constraints

1 <= N <= 2000
1 <= B <= 100
1 <= size <= B
0 <= fee <= 10^9

Examples

Input: ([(1, 50, 60), (2, 60, 100), (3, 40, 30)], 100)

Expected Output: 130

Explanation: Pick transactions 2 and 3: size 60+40=100 <= 100, fee 100+30=130 — the maximum.

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

Expected Output: 220

Explanation: Pick 2 and 3: size 20+30=50, fee 100+120=220.

Input: ([], 100)

Expected Output: 0

Explanation: No transactions, so the best achievable fee is 0.

Input: ([(1, 100, 999)], 100)

Expected Output: 999

Explanation: The single transaction exactly fills the block; take it for fee 999.

Input: ([(1, 100, 50)], 99)

Expected Output: 0

Explanation: The only transaction has size 100 > capacity 99, so nothing fits and the fee is 0.

Input: ([(1, 1, 5), (2, 1, 5), (3, 1, 5)], 2)

Expected Output: 10

Explanation: Capacity 2 fits any two of the three size-1 transactions for fee 5+5=10.

Input: ([(1, 5, 0), (2, 3, 0)], 8)

Expected Output: 0

Explanation: Both transactions fit but all fees are 0, so the maximum total fee is 0.

Hints

Each transaction is either fully included or excluded — this is a 0/1 knapsack with weight = size and value = fee.
Use a 1-D DP array `dp[c]` = best total fee using capacity exactly up to `c`. Iterate capacity from high to low so each transaction is used at most once.
The interviewer in the real interview discouraged DP and asked for a fee/size ratio greedy; note that greedy is NOT optimal for 0/1 knapsack (it can be off), so DP is the correct exact solution. The answer is `max(dp)`.

Max-fee block assembly with parent/child dependencies

Constraints

1 <= N <= 2000
1 <= B <= 100
1 <= size <= B
0 <= fee <= 10^9
Dependencies form a forest (each transaction has at most one parent, no cycles).
parent_id is None (or -1 in Java/C++) for root transactions.

Examples

Input: ([(1, 50, 60, None), (2, 60, 100, None), (3, 40, 30, None)], 100)

Expected Output: 130

Explanation: No dependencies (all roots), so it reduces to plain knapsack: take 2 and 3 for size 100, fee 130.

Input: ([(1, 30, 10, None), (2, 30, 100, 1)], 100)

Expected Output: 110

Explanation: Taking child 2 forces taking parent 1: size 30+30=60 <= 100, fee 10+100=110.

Input: ([(1, 30, 10, None), (2, 30, 100, 1)], 50)

Expected Output: 10

Explanation: The pair needs size 60 > 50, so child 2 is unreachable; the best valid choice is the root alone for fee 10.

Input: ([(1, 10, 5, None), (2, 10, 5, 1), (3, 10, 5, 2), (4, 10, 100, 3)], 30)

Expected Output: 15

Explanation: Chain 1->2->3->4. Reaching the fee-100 node 4 needs all four (size 40 > 30). With capacity 30 the best valid prefix is nodes 1,2,3 for fee 15.

Input: ([(1, 10, 5, None), (2, 10, 5, 1), (3, 10, 5, 2), (4, 10, 100, 3)], 40)

Expected Output: 115

Explanation: Capacity 40 fits the whole chain (size 40), unlocking node 4: fee 5+5+5+100=115.

Input: ([(1, 20, 5, None), (2, 30, 50, 1), (3, 30, 40, 1)], 50)

Expected Output: 55

Explanation: Root 1 has two children. To take child 2 you need root 1: size 20+30=50, fee 55. You cannot fit both children (20+30+30=80 > 50).

Input: ([(1, 20, 5, None), (2, 30, 50, 1), (3, 30, 40, 1)], 80)

Expected Output: 95

Explanation: Capacity 80 fits root 1 plus both children: size 20+30+30=80, fee 5+50+40=95.

Input: ([], 100)

Expected Output: 0

Explanation: No transactions, so the maximum fee is 0.

Input: ([(1, 100, 999, None)], 100)

Expected Output: 999

Explanation: A single root that exactly fills the block; take it for fee 999.

Input: ([(1, 100, 999, None)], 50)

Expected Output: 0

Explanation: The only transaction has size 100 > capacity 50, so nothing can be included and the fee is 0.

Hints

A valid selection must be closed under taking ancestors: if a node is chosen, every node on the path to its root is also chosen. Equivalently, you can only take a node once its parent is already taken.
Solve with a tree DP. For each node compute `dp[c]` = the best total fee achievable within its subtree using capacity at most `c` GIVEN the node itself is taken (this is what makes its children eligible).
Merge each child subtree into the parent's DP as an optional knapsack group (take that child subtree or skip it). Then merge the independent root trees the same way, each root being optional. The answer is the maximum over the final array.
The interviewer's original 'sort by fee/size ratio' greedy does not extend correctly to dependencies; the tree knapsack is the exact approach.

Quick Overview

Quick Overview