PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates knowledge of data structures and algorithms for transactional ledgers, including tracking payments and refundable balances, rule-based prioritization for allocating refunds, handling partial and multiple refunds, and ensuring correctness when payments and refunds interleave.

  • medium
  • Airbnb
  • Coding & Algorithms
  • Software Engineer

Design refundable transaction ledger and prioritization rules

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design and implement a transaction ledger that ingests a stream of records where each record is either a payment or a refund. Each payment has {id, userId, amount, timestamp}; each refund has {id, userId, amount, timestamp, optional paymentIdReference}. ( 1) Choose data structures to store payments and track remaining refundable amounts. ( 2) Implement APIs: addPayment(payment), addRefund(refund, rules), and getUserBalance(userId). ( 3) When a refund arrives without paymentIdReference, select which prior payment(s) to offset based on a provided priority rule set (e.g., a comparator that can express recency-first, amount-first, or other tie-breakers). ( 4) Support partial refunds and multiple refunds against the same payment; ensure refunds cannot exceed a payment’s remaining refundable amount. ( 5) Input may interleave payments and refunds; for each refund, return the list of (paymentId, refundedAmount) pairs it offsets. ( 6) Analyze time and space complexity of each operation and justify your data-structure choices.

Quick Answer: This question evaluates knowledge of data structures and algorithms for transactional ledgers, including tracking payments and refundable balances, rule-based prioritization for allocating refunds, handling partial and multiple refunds, and ensuring correctness when payments and refunds interleave.

Part 1: Build Ledger Storage Indexes

Given an initial batch of payments and already-applied refund allocations, build the core ledger storage views needed to track payments and remaining refundable amounts. Payment and user IDs are integers. Refund allocations are already valid and do not over-refund any payment.

Constraints

  • 0 <= len(payments) <= 100000
  • 0 <= len(refund_allocations) <= 100000
  • paymentId values are unique positive integers
  • amount and refundedAmount are non-negative integers
  • Every refund allocation references an existing payment and total allocations per payment do not exceed its amount

Examples

Input: ([[1, 10, 100, 5], [2, 10, 50, 3], [3, 20, 70, 4]], [[1, 30], [3, 70]])

Expected Output: [[[1, 10, 100, 5], [2, 10, 50, 3], [3, 20, 70, 4]], [[1, 70], [2, 50], [3, 0]], [[10, 2, 1], [20, 3]]]

Explanation: Payment 1 has 70 remaining, payment 3 is fully refunded, and user 10's payments are ordered by timestamps 3 then 5.

Input: ([], [])

Expected Output: [[], [], []]

Explanation: Empty input produces empty storage views.

Input: ([[5, 99, 200, 10]], [])

Expected Output: [[[5, 99, 200, 10]], [[5, 200]], [[99, 5]]]

Explanation: A single payment with no refunds remains fully refundable.

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

Expected Output: [[[1, 1, 100, 1], [2, 1, 50, 2]], [[1, 50], [2, 40]], [[1, 1, 2]]]

Explanation: Multiple allocations against the same payment are accumulated.

Hints

  1. A hash map keyed by paymentId gives direct access to original and remaining payment data.
  2. For the per-user view, group payment IDs by userId and sort each group by timestamp.

Part 2: Simulate Basic Ledger APIs

Implement a basic transaction ledger API simulator. The ledger supports adding payments, adding refunds that explicitly reference one payment, and querying a user's current net balance. A refund is accepted only if it references an existing payment from the same user and does not exceed that payment's remaining refundable amount.

Constraints

  • 0 <= len(operations) <= 100000
  • IDs, amounts, and timestamps are integers
  • paymentId and refundId values are positive integers
  • Refund amounts are non-negative
  • A rejected operation must not change ledger state

Examples

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

Expected Output: [1, 100, 1, 70]

Explanation: The payment increases user 10's balance to 100; the refund decreases it to 70.

Input: ([[3, 42]],)

Expected Output: [0]

Explanation: Unknown users have balance 0.

Input: ([[1, 1, 10, 100, 1], [2, 101, 10, 120, 2, 1], [3, 10]],)

Expected Output: [1, 0, 100]

Explanation: The refund is rejected because it exceeds the payment's remaining refundable amount.

Input: ([[1, 1, 10, 100, 1], [1, 1, 10, 50, 2], [2, 101, 10, 40, 3, 1], [2, 101, 10, 10, 4, 1], [3, 10]],)

Expected Output: [1, 0, 1, 0, 60]

Explanation: Duplicate payment and duplicate refund IDs are rejected.

Hints

  1. Keep one map from paymentId to its user and another map from paymentId to remaining refundable amount.
  2. Maintaining a cached balance per user makes getUserBalance constant time.

Part 3: Allocate an Unreferenced Refund by Priority Rules

A refund arrives without a paymentIdReference. Given the current refundable payments, select prior payments for the same user according to a configurable priority rule list, then greedily allocate the refund amount. The refund must be fully covered; otherwise return an empty allocation.

Constraints

  • 0 <= len(payments) <= 100000
  • 0 <= refund amount <= 10^12
  • paymentId values are unique positive integers
  • remainingAmount values are non-negative integers
  • If no rules are provided, default to OLDEST_FIRST then ID_ASC

Examples

Input: ([[1, 10, 70, 5], [2, 10, 50, 8], [3, 20, 100, 9]], [10, 80, 10], ['RECENT_FIRST'])

Expected Output: [[2, 50], [1, 30]]

Explanation: Recency-first chooses payment 2 before payment 1.

Input: ([[1, 10, 40, 5], [2, 10, 70, 3], [3, 10, 70, 7]], [10, 100, 9], ['LARGEST_REMAINING_FIRST', 'OLDEST_FIRST'])

Expected Output: [[2, 70], [3, 30]]

Explanation: Payments 2 and 3 tie on remaining amount, so OLDEST_FIRST chooses payment 2 first.

Input: ([[1, 10, 20, 1]], [10, 25, 2], ['OLDEST_FIRST'])

Expected Output: []

Explanation: Only 20 is refundable, so a refund of 25 cannot be fully covered.

Input: ([[1, 10, 20, 1]], [10, 0, 2], [])

Expected Output: []

Explanation: A zero-amount refund needs no allocations.

Input: ([[1, 10, 50, 5], [2, 10, 50, 5]], [10, 60, 5], ['ID_DESC'])

Expected Output: [[2, 50], [1, 10]]

Explanation: ID_DESC chooses payment 2 before payment 1.

Hints

  1. Convert each priority rule into a component of a sort key.
  2. After sorting eligible payments, greedily consume each payment's remaining amount until the refund is covered.

Part 4: Process Multiple Partial Refunds per Payment

Given payment amounts and a sequence of refund requests that each reference a specific payment, process requests in order. Partial refunds are allowed, and multiple refunds may target the same payment, but a request must be rejected if it would make total refunded amount exceed that payment's original amount.

Constraints

  • 0 <= len(payment_amounts) <= 100000
  • 0 <= len(refund_requests) <= 100000
  • paymentId values in payment_amounts are unique positive integers
  • Payment and refund amounts are non-negative integers
  • Rejected requests must not change remaining refundable amounts

Examples

Input: ([[1, 100]], [[1, 30], [1, 50], [1, 25], [1, 20]])

Expected Output: [[1, 30, 70], [1, 50, 20], [0, 0, 20], [1, 20, 0]]

Explanation: The third refund is rejected because only 20 remains; the fourth refund exactly consumes the remainder.

Input: ([], [[1, 10]])

Expected Output: [[-1, 0, 0]]

Explanation: There are no payments, so the referenced payment is unknown.

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

Expected Output: [[1, 100, 0], [0, 0, 0]]

Explanation: After a full refund, no additional refund is allowed.

Input: ([[1, 0]], [[1, 0]])

Expected Output: [[1, 0, 0]]

Explanation: A zero-amount refund against a zero-amount payment is valid and changes nothing.

Input: ([[1, 50], [2, 30]], [[1, 20], [2, 30], [1, 30]])

Expected Output: [[1, 20, 30], [1, 30, 0], [1, 30, 0]]

Explanation: Remaining refundable amounts are tracked independently per payment.

Hints

  1. Store only the remaining refundable amount for each payment; you do not need to recompute from history.
  2. A refund is valid exactly when requested amount <= remaining[paymentId].

Part 5: Process Interleaved Payments and Refunds with Allocations

Process a stream where payment and refund records may be interleaved. For every refund, return the list of payment allocations it offsets. A refund may explicitly reference one payment, or it may omit the reference and use priority rules to choose eligible prior payments for the same user. Rejected refunds return an empty allocation and must not mutate payment remaining amounts.

Constraints

  • 0 <= len(records) <= 100000
  • Payment and refund IDs are positive integers and unique within their own type
  • Amounts are positive integers
  • An unreferenced refund may use only payments already ingested, with the same userId, timestamp <= refund timestamp, and positive remaining amount
  • If rules is empty, default to OLDEST_FIRST then ID_ASC

Examples

Input: ([[1, 1, 10, 100, 1], [2, 101, 10, 30, 2, -1], [1, 2, 10, 50, 3], [2, 102, 10, 80, 4, -1]], ['RECENT_FIRST'])

Expected Output: [[[1, 30]], [[2, 50], [1, 30]]]

Explanation: The first refund uses payment 1. The second refund uses the most recent payment 2 first, then payment 1.

Input: ([[1, 1, 10, 100, 1], [1, 2, 10, 40, 2], [2, 201, 10, 60, 3, 1], [2, 202, 10, 50, 4, 1]], ['OLDEST_FIRST'])

Expected Output: [[[1, 60]], []]

Explanation: The second explicit refund against payment 1 is rejected because only 40 remains.

Input: ([[2, 101, 10, 20, 1, -1], [1, 1, 10, 50, 2], [2, 102, 10, 20, 3, -1]], ['OLDEST_FIRST'])

Expected Output: [[], [[1, 20]]]

Explanation: A refund before any eligible payment is rejected; the later refund can use the ingested payment.

Input: ([], ['RECENT_FIRST'])

Expected Output: []

Explanation: No records means no refund outputs.

Input: ([[1, 1, 10, 30, 1], [2, 101, 10, 50, 2, -1], [2, 102, 10, 20, 3, -1]], [])

Expected Output: [[], [[1, 20]]]

Explanation: The insufficient refund is rejected without changing payment 1, so the later refund can still use it.

Hints

  1. For an unreferenced refund, first collect candidate payments and check that total remaining amount is sufficient before mutating state.
  2. Use the same sort-key idea from configurable priority rules, then greedily allocate.

Part 6: Estimate Ledger Operation Complexity Costs

You are comparing two ledger data-structure designs. The naive design uses a hash map plus unsorted per-user payment lists and cached balances. The indexed design uses a hash map plus a per-user priority index and cached balances. Given a workload summary, compute abstract operation costs for both designs and recommend the cheaper one.

Constraints

  • 0 <= len(operations) <= 100000
  • userId values are positive integers
  • For unreferenced refunds, 0 <= touchedPayments <= current number of payments for that user
  • The estimator tracks payment counts only; refunds do not remove payments from the count
  • All costs fit in a 64-bit signed integer

Examples

Input: ([],)

Expected Output: [0, 0, 0, 0]

Explanation: No operations means both designs have zero cost.

Input: ([[1, 10], [1, 10], [2, 10, 0, 1], [3, 10]],)

Expected Output: [6, 7, -1, 2]

Explanation: For this small workload, indexed insert overhead is not recovered.

Input: ([[1, 10], [1, 10], [1, 10], [1, 10], [1, 10], [2, 10, 0, 0], [2, 10, 0, 0], [2, 10, 0, 0], [2, 10, 0, 0], [2, 10, 0, 0]],)

Expected Output: [35, 19, 1, 5]

Explanation: Repeated unreferenced refunds with zero touched payments are much cheaper under the indexed model.

Input: ([[1, 1], [1, 2], [1, 1], [2, 1, 0, 1], [2, 2, 0, 1]],)

Expected Output: [8, 10, -1, 3]

Explanation: Payment counts are maintained separately per user.

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

Expected Output: [3, 4, -1, 1]

Explanation: A referenced refund is constant time in both designs, so the indexed add cost makes it more expensive here.

Hints

  1. Maintain the current number of payments per user while scanning operations once.
  2. ceil(log2(x)) for integer x >= 1 can be computed with bit_length.
Last updated: Jun 14, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimum Canisters to Top Up an Exact Target - Airbnb (medium)
  • Count Candies from Unlockable Boxes - Airbnb (medium)
  • Find Optimal Property Combination - Airbnb (medium)
  • Determine Exact Layover Booking - Airbnb (medium)
  • Solve Linked-List and Iterator Problems - Airbnb (medium)