FastPrepSelect Transactions with Child-Pays-for-Parent Packages
Problems/Select Transactions with Child-Pays-for-Parent Packages

Select Transactions with Child-Pays-for-Parent Packages

Coinbase logoCoinbase● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Approximate source match: 85% of the reported task behavior. The reports establish an unordered large mempool, fees and sizes, capacity100, recursive acyclic parent dependencies, parent-before-child output, CPFP and a strictly optional minimum-child-fee discussion. The deterministic package-greedy ratio/tie/order policy, finite bounds and retained multi-parent array adapter are authored practice choices, not recovered interview requirements.

A mempool contains an unordered collection of transactions. Each has a unique identifier, a nonnegative fee, a positive size, and parent dependencies. A block has limited size. Select transactions that collect useful fees without exceeding that limit; every selected transaction must appear after all of its required parents in the returned order.

The interview uses capacity 100 and emphasizes a very large mempool: a fast approximation is preferred over an exact optimum. Child-Pays-For-Parent (CPFP) means evaluating a child together with the unselected ancestors it needs, so a high-fee child can make a low-fee parent worthwhile. Dependencies may have several levels and are acyclic. An empty parent list means no unmined parent is required.

Authored Practice Contract

For this exercise, implement the following deterministic package-greedy policy. The array parameters expose the transaction fields; capacity permits smaller blocks for practice, up to the source capacity of 100. The retained parent-list adapter supports several parents; the report describes one parent identifier.

  1. Initially no transaction is selected. For each unselected transaction, form its package: itself and every recursive ancestor that is not already selected. Count a shared ancestor only once.
  2. Consider only packages whose total size fits the remaining capacity and whose total fee is positive. Choose the package with the largest ratio of total fee to total size. Compare ratios exactly. If ratios tie, choose the candidate transaction with the lexicographically smallest identifier.
  3. Append the chosen package in this exact order: depth-first visit the candidate's parents in lexicographic identifier order, recursively visit their parents, and append each transaction after its parents. Skip already selected or already visited transactions. Mark all appended transactions selected and subtract their sizes.
  4. Recompute remaining packages and repeat. Stop when no positive-fee package fits. Return the selected identifiers in append order. This policy does not promise maximum possible total fees.

Every parent named in the input is present in the mempool, but it may occur anywhere in the input arrays. Transactions whose complete ancestor closure exceeds the total block capacity can never be selected. Empty input or zero capacity returns an empty array.

Optional discussion: minimum child fee

Given a parent identifier and a proposed child's size, how much fee must that new child pay to enter the next block with its required ancestors? This is strictly optional and is not part of selectBlockTransactions. A numerical threshold depends on the competing mempool and the chosen selection/tie policy; discuss those assumptions rather than claim a universal next-block guarantee.

Function

selectBlockTransactions(ids: String[], fees: int[], sizes: int[], parents: String[][], capacity: int) → String[]

Examples

Example 1

ids = ["p","c","x"]fees = [1,10,7]sizes = [40,40,60]parents = [[],["p"],[]]capacity = 80return = ["p","c"]

The child package has fee 11/size 80, larger than x at 7/60 and p at 1/40. Select that package and emit p before c.

Example 2

ids = ["a","b","c"]fees = [5,5,10]sizes = [50,50,100]parents = [[],[],[]]capacity = 100return = ["a","b"]

All three initial ratios are equal. Identifier a wins the tie, then b fits the remaining 50. Transaction c no longer fits. Return [a,b].

Example 3

ids = ["a","b"]fees = [3,100]sizes = [60,50]parents = [[],["a"]]capacity = 100return = ["a"]

The child package needs size 110 and cannot fit. Select a alone; the remaining capacity 40 cannot fit the child of size 50.

Constraints

  • 0 <= ids.length <= 10000; all four transaction arrays have the same length.
  • Identifiers are unique strings of 1 to 20 lowercase ASCII letters or digits. Lexicographic order compares those characters directly.
  • 0 <= fees[i] <= 10^9, 1 <= sizes[i] <= 100, and 0 <= capacity <= 100.
  • Each parent list has at most eight distinct identifiers, all present in ids. The dependency graph is acyclic.
  • Bounds, deterministic selection, tie and output rules, and the multi-parent representation are authored practice assumptions. No exact global fee optimum is required.

More Coinbase problems

  • Scheduled Payments with Account AliasesONSITE INTERVIEW · Seen Oct 2026
  • Task Management SystemOA · Seen Sep 2026
  • Cloud Compute Credits SystemOA · Seen Aug 2026
All Coinbase interview questionsSee Coinbase hiring insights
Saved
class Solution {
    public String[] selectBlockTransactions(String[] ids, int[] fees, int[] sizes, String[][] parents, int capacity) {
        // Write your code here.
    }

}
Checking account…