~/problems / Simulation & OOP design / Object-oriented design and extensible simulations

OA: Referral Credit Tracker

medium 2 levels ~45 min DatabricksUber

Level 1 Accounts, referral bonuses and the leaderboard

A ride-sharing app rewards riders who bring in friends. Build AccountCreditTracker:

  • add_account(credit: float) -> int: open an account that starts with credit and return its ID. IDs are 0, 1, 2, ... in the order accounts are opened.
  • add_account_with_referral(credit: float, referrer_id: int) -> int: open an account the same way, and also award its direct referrer a bonus equal to the new account's starting credit. The referrer's own referrer gets nothing. Raise ValueError (and open nothing) if referrer_id doesn't exist.
  • get_total_credit(account_id: int) -> float: the account's starting credit plus every referral bonus it has earned. Raise ValueError for an unknown ID.
  • get_top_k(k: int) -> list[int]: the IDs of the k accounts with the highest total credit, highest first; equal totals put the smaller ID first. Return every account if there are fewer than k.

Credits are non-negative floats. (The tests only use values like 12.5 or 0.25 that floats store exactly, so plain == comparisons are safe.)

t = AccountCreditTracker()
t.add_account(10.0)                   # 0
t.add_account_with_referral(5.5, 0)   # 1   account 0 now has 15.5
t.add_account_with_referral(20.0, 1)  # 2   account 1 now has 25.5; account 0 still 15.5
t.add_account(15.5)                   # 3
t.get_total_credit(1)                 # 25.5
t.get_top_k(3)                        # [1, 2, 0]   25.5, 20.0, then 15.5 (0 beats 3 on the tie)
t.get_top_k(10)                       # [1, 2, 0, 3]
t.add_account_with_referral(1.0, 9)   # ValueError

Scale: up to 20,000 accounts with tens of thousands of get_top_k calls (small k) mixed in. Don't sort every account on each call: keep the accounts ordered as totals change.

Level 2 unlocks when level 1 passes.

Topic: Object-oriented design and extensible simulations. Classes that survive new requirements: games, payments, subscriptions, refactors.

0:00
Ctrl ' run · Ctrl ↵ submit
esc