Billing Status Replay (OOD)

Rebuild one billing-state object per advertiser by replaying a transaction log in increasing timestamp order, breaking ties by transaction id. Model a BillingStatus class that ingests transactions and grows through three layers: additive aggregation over known monetary columns, overwrite transactions that replace a column instead of adding to it, and stack-based undo_last / redo_last commands. The main OOD discussion is whether to store only deltas or reversible before/after snapshots so that overwrite and undo/redo stay correct together. Billing Status Replay (OOD) Rebuild one billing-state object per advertiser by replaying a transaction log in increasing timestamp order, breaking ties by transaction id. Model a BillingStatus class that ingests transactions and grows through three layers: additive aggregation over known monetary columns, overwrite transactions that replace a column instead of adding to it, and stack-based undo_last / redo_last commands. The main OOD discussion is whether to store only deltas or reversible before/after snapshots so that overwrite and undo/redo stay correct together. MLE SWE medium oop-design object-design simulation stack transactions python Frequency Low Last asked 2026-01-08 Stage phone-screen 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: Basic additive aggregation Overwrite transactions 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 1 Solution Use a per-user object and replay the log in timestamp order. class BillingStatus: def __init__(self, monetary_columns: tuple[str, ...]): self.monetary_columns = tuple(monetary_columns) self.amounts = {column: 0 for column in self.monetary_columns} def ingest(self, transaction_id: str, transaction: dict) -> None: for column in self.monetary_columns: self.amounts[column] += transaction.get(column, 0) def as_dict(self) -> dict[str, int]: return dict(self.amounts) def rebuild_billing_statuses( transactions: dict[str, dict], monetary_columns: tuple[str, ...], ) -> dict[int, BillingStatus]: statuses: dict[int, BillingStatus] = {} ordered_transactions = sorted( transactions.items(), key=lambda item: (item[1]["transaction_timestamp"], item[0]), ) for transaction_id, transaction in ordered_transactions: user_id = transaction["user_id"] status = statuses.setdefault(user_id, BillingStatus(monetary_columns)) status.ingest(transaction_id, transaction) return statuses Complexity Sorting: O(n log n) Replay: O(n * c), where c is the number of monetary columns Space: O(u * c), where u is the number of users 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 2 Solution The replay loop does not change. Only BillingStatus.ingest(...) changes: class BillingStatus: def __init__(self, monetary_columns: tuple[str, ...]): self.monetary_columns = tuple(monetary_columns) self.amounts = {column: 0 for column in self.monetary_columns} def ingest(self, transaction_id: str, transaction: dict) -> None: overwrite = transaction.get("overwrite", False) for column in self.monetary_columns: if column not in transaction: continue if overwrite: self.amounts[column] = transaction[column] else: self.amounts[column] += transaction[column] def as_dict(self) -> dict[str, int]: return dict(self.amounts) Why This Matches The Example For user 1: ad += 1000 ad += 1000 payment += 500 overwrite both columns to ad = 1000, payment = 500 payment += 100 Final state: { "ad_delivery_pennies": 1000, "payment_pennies": 600, } For user 2, the overwrite only touches payment_pennies, so ad_delivery_pennies keeps its accumulated value. 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), } Part 3 Solution Store enough history to reverse and reapply the effect of each regular transaction. from dataclasses import dataclass @dataclass class ReplayRecord: columns: tuple[str, ...] before: dict[str, int] after: dict[str, int] class BillingStatus: def __init__(self, monetary_columns: tuple[str, ...]): self.monetary_columns = tuple(monetary_columns) self.amounts = {column: 0 for column in self.monetary_columns} self._applied: list[ReplayRecord] = [] self._undone: list[ReplayRecord] = [] def ingest(self, transaction_id: str, transaction: dict) -> None: if transaction.get("undo_last"): self._undo_last() return if transaction.get("redo_last"): self._redo_last() return touched_columns = tuple( column for column in self.monetary_columns if column in transaction ) if not touched_columns: return overwrite = transaction.get("overwrite", False) before = {column: self.amounts[column] for column in touched_columns} for column in touched_columns: value = transaction[column] if overwrite: self.amounts[column] = value else: self.amounts[column] += value after = {column: self.amounts[column] for column in touched_columns} self._applied.append( ReplayRecord( columns=touched_columns, before=before, after=after, ) ) self._undone.clear() def _undo_last(self) -> None: if not self._applied: return record = self._applied.pop() for column in record.columns: self.amounts[column] = record.before[column] self._undone.append(record) def _redo_last(self) -> None: if not self._undone: return record = self._undone.pop() for column in record.columns: self.amounts[column] = record.after[column] self._applied.append(record) def as_dict(self) -> dict[str, int]: return dict(self.amounts) def rebuild_billing_statuses( transactions: dict[str, dict], monetary_columns: tuple[str, ...], ) -> dict[int, BillingStatus]: statuses: dict[int, BillingStatus] = {} ordered_transactions = sorted( transactions.items(), key=lambda item: (item[1]["transaction_timestamp"], item[0]), ) for transaction_id, transaction in ordered_transactions: user_id = transaction["user_id"] status = statuses.setdefault(user_id, BillingStatus(monetary_columns)) status.ingest(transaction_id, transaction) return statuses Why This Design Works BillingStatus owns the mutable state for one user each regular transaction stores the exact before and after values for the touched columns undo_last restores before redo_last restores after overwrite transactions work naturally because the history captures absolute values, not only deltas This is usually the main OOD discussion point: do you store only deltas, or do you store reversible command history? Once overwrite exists, storing before and after snapshots for touched columns keeps the implementation simple and correct. Complexity Let c be the number of monetary columns. regular ingest: O(c) undo_last: O(k) redo_last: O(k) where k is the number of columns touched by that transaction, and k <= c. Overall replay remains: Sorting: O(n log n) Replay: O(n * c) Space: O(u * c + h), where h is the per-user history retained for undo/redo Common Follow-Ups Interviewers may push on a few practical extensions: Idempotency What if the logs contain duplicate transaction IDs? One answer is to keep a per-user or global seen_transaction_ids set. Streaming ingestion The same BillingStatus.ingest(...) API works for both historical replay and live traffic. Checkpointing If the logs are huge, periodically snapshot BillingStatus and only replay newer transactions after the latest checkpoint. 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.