Billing Status Replay (OOD)

Problem Overview

We accidentally dropped the database that stored the current billing state for advertisers. The old transaction logs still exist, so the task is to replay those transactions and rebuild one BillingStatus object per user.

This interview is usually framed as an object-oriented coding problem. The core idea is to model a single account as a BillingStatus class that can ingest transactions over time, then build a dictionary like:

{
    user_id: BillingStatus(...),
    user_id_2: BillingStatus(...),
}

The interviewer typically adds three layers:

1. Basic additive aggregation
2. Overwrite transactions
3. undo_last and redo_last

Assume:

• replay order is increasing transaction_timestamp
• if two transactions have the same timestamp, break ties by transaction_id for deterministic replay
• monetary_columns is known in advance
• missing monetary fields mean "no change" for that column
• undo_last and redo_last only affect the history of the same user
• overwrite, undo_last, and redo_last are control fields, not monetary columns
• if a transaction uses undo_last or redo_last, treat it as a command row and ignore any monetary fields on that same row
• redo_last follows standard stack semantics: it reapplies the most recently undone regular transaction
• each transaction uses at most one of overwrite, undo_last, or redo_last as its behavioral option, except that plain regular transactions may omit all of them

Part 1: Rebuild Billing Statuses

Problem Statement

Implement a BillingStatus class with two starting monetary columns:

ad_delivery_pennies = 0
payment_pennies = 0

Each transaction may contain one or more monetary columns. When ingesting a transaction, add the transaction values into the current billing status.

Then implement a function that replays a collection of transactions and returns one BillingStatus per user.

Example

monetary_columns = ("ad_delivery_pennies", "payment_pennies")

transactions = {
    "ff8bc1c2-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000001,
    },
    "ff8bc2e4-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000002,
    },
    "ff8bc4ec-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000003,
    },
    "fv24z4ec-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000004,
    },
}

Expected result:

{
    1: BillingStatus(
        ad_delivery_pennies=3000,
        payment_pennies=1000,
    )
}

Part 2: Add Overwrite Transactions

Problem Statement

Now support a control flag:

"overwrite": True

If overwrite is True, any monetary column present in that transaction should replace the current value for that column instead of being added to it.

Important detail:

• overwrite only applies to columns present in the transaction
• columns not mentioned in the transaction should remain unchanged

Example

monetary_columns = ("ad_delivery_pennies", "payment_pennies")

transactions = {
    "ff8ba98a-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000001,
        "overwrite": False,
    },
    "ff8bad4a-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000004,
    },
    "ff8baea8-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "payment_pennies": 600,
        "transaction_timestamp": 1500000007,
        "overwrite": False,
    },
    "ff8bb4ac-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000002,
        "overwrite": False,
    },
    "ff8bb600-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "ad_delivery_pennies": 1000,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000003,
        "overwrite": False,
    },
    "ff8bb89e-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "payment_pennies": 2000,
        "transaction_timestamp": 1500000005,
        "overwrite": True,
    },
    "ff8bb9c0-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000003,
        "overwrite": False,
    },
    "ff8bbf74-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000004,
        "overwrite": True,
    },
    "ff8bc0a0-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000001,
    },
    "ff8bc1c2-8d45-11e9-bc42-526af7764f64": {
        "user_id": 2,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000002,
    },
    "ff923488-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "payment_pennies": 100,
        "transaction_timestamp": 1500000013,
    },
}

Expected result:

{
    1: BillingStatus(ad_delivery_pennies=1000, payment_pennies=600),
    2: BillingStatus(ad_delivery_pennies=4000, payment_pennies=2600),
}

Part 3: Add undo_last And redo_last

Problem Statement

Now add two more control flags:

"undo_last": True
"redo_last": True

Rules:

• undo_last=True undoes the most recent regular transaction for the same user
• redo_last=True reapplies the most recently undone regular transaction for the same user
• if there is nothing to undo, discard the operation
• if there is nothing to redo, discard the operation
• a regular transaction is:
  • a transaction with no control flags, or
  • a transaction that only uses overwrite
• assume a transaction never sets both undo_last and redo_last
• undo_last and redo_last transactions are commands, not regular transactions
• if a new regular transaction is applied after an undo, the redo history should be cleared
• if a command row also contains monetary columns, ignore those monetary columns and only execute the command

To remove ambiguity, assume standard editor-style undo/redo semantics:

• undo pops from the applied-history stack
• redo pops from the undone-history stack
• any newly applied regular transaction invalidates redo history

Example

monetary_columns = ("ad_delivery_pennies", "payment_pennies")

transactions = {
    "ff8bc1c2-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "transaction_timestamp": 1500000001,
    },
    "ff8bc2e4-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "undo_last": True,
        "transaction_timestamp": 1500000002,
    },
    "ff8bc4ec-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000003,
    },
    "fv24z4ec-8d45-11e9-bc42-526af7764f64": {
        "user_id": 1,
        "ad_delivery_pennies": 1000,
        "payment_pennies": 500,
        "transaction_timestamp": 1500000004,
    },
}

Expected result:

{
    1: BillingStatus(ad_delivery_pennies=1000, payment_pennies=1000),
}

Common Follow-Ups

Interviewers may push on a few practical extensions:

1. Idempotency

   • What if the logs contain duplicate transaction IDs?
   • One answer is to keep a per-user or global seen_transaction_ids set.

2. Streaming ingestion

   • The same BillingStatus.ingest(...) API works for both historical replay and live traffic.

3. Checkpointing

   • If the logs are huge, periodically snapshot BillingStatus and only replay newer transactions after the latest checkpoint.

4. Auditability

   • In production you would likely store the command history, not just the final balances, so that later investigations can explain why a balance has its current value.