Implement the following independent multi-level in-memory service simulations. In an interview, you may receive one scenario and unlock the levels sequentially; later levels build on earlier state. Design your internal data structures so that adding later levels does not require a full rewrite. General rules: - All data is stored in memory. - IDs, names, and prefixes are strings. - Amounts, sizes, capacities, quantities, nights, and counts are positive integers unless stated otherwise. - Invalid operations must not change state and should return false, null, or an empty list as appropriate. - If an operation receives a timestamp, process all lazy expirations due at or before that timestamp before performing the operation. - For ranking queries, sort by the requested numeric value descending, then by ID or name in lexicographic ascending order unless another tie-breaker is specified. ## Problem A: Banking System ### Level 1 Implement: - `create_account(account_id)`: create a new account. Return false if it already exists. - `deposit(account_id, amount)`: add money and return the new balance, or null if the account does not exist. - `transfer(source_account_id, target_account_id, amount)`: immediately move money from source to target. Reject missing accounts, self-transfers, and insufficient funds. ### Level 2 Implement `top_activity(n)`: return the top `n` accounts by total outgoing transfer amount. Deposits do not count. Current balance must not be used as the ranking counter. ### Level 3 Replace immediate transfers with pending transfers: - `transfer(timestamp, source_account_id, target_account_id, amount)` deducts the amount from the source immediately and returns a globally unique transfer ID. - `accept_transfer(timestamp, target_account_id, transfer_id)` succeeds only if the target accepts within 24 hours. - If a pending transfer expires, refund the source account lazily during later operations. ### Level 4 Implement: - `merge_accounts(primary_account_id, secondary_account_id)`: merge the secondary account into the primary account. Merge balances, outgoing counters, and all pending transfers. The secondary account no longer exists afterward. - `get_balance(account_id, time_at)`: return the historical balance of an account at the requested time, or null if the account did not exist then. ## Problem B: Cloud Storage ### Level 1 Implement: - `add_file(name, size)`: add a file if the name is unused. - `get_file_size(name)`: return the file size, or null if missing. - `delete_file(name)`: delete the file and return its size, or null if missing. ### Level 2 Implement `get_n_largest(prefix, n)`: return the largest `n` files whose names start with `prefix`, sorted by size descending and then name ascending. Include both file name and size in the result. ### Level 3 Add users and capacity limits: - `add_user(user_id, capacity)`: create a user with a storage capacity. - `add_file_by(user_id, name, size)`: add a file owned by the user. Fail if the user does not exist, the file name is already used, or the upload would exceed the user capacity. - `merge_users(primary_user_id, secondary_user_id)`: merge the secondary user into the primary user. Capacities add together, all files become owned by the primary user, and the secondary user is removed. ### Level 4 Implement: - `backup_user(user_id)`: store one snapshot of that user files, replacing any previous backup for that user. - `restore_user(user_id)`: replace the user current files with the latest backup. Remove the user current files first, then restore snapshot files whose names are not currently used by other users. Handle name conflicts deterministically and return the number of restored files. ## Problem C: In-Memory Key-Field Database With TTL The database maps each `key` to multiple `field -> value` entries, similar to a hash map inside a key-value store. ### Level 1 Implement: - `set(key, field, value)` - `get(key, field)` - `delete(key, field)` ### Level 2 Implement: - `scan(key)`: return all fields under `key`, sorted lexicographically by field name. - `scan_by_prefix(key, prefix)`: return fields under `key` whose field names start with `prefix`, sorted lexicographically. ### Level 3 All operations now receive a leading `timestamp`. Add: - `set_with_ttl(timestamp, key, field, value, ttl)`: store a value that is visible for timestamps in `[timestamp, timestamp + ttl)`. Expired fields must be treated as absent by `get`, `delete`, `scan`, and `scan_by_prefix`. Use lazy expiration rather than background threads. ### Level 4 Implement: - `backup(timestamp)`: snapshot the visible database at `timestamp`. - `restore(timestamp, timestamp_to_restore)`: restore the database to the latest backup taken at or before `timestamp_to_restore`. For fields with TTL, the snapshot must store remaining lifetime, not absolute expiration time. When restoring at `timestamp`, recompute each expiration as `timestamp + remaining_lifetime`. ## Problem D: Cashback Banking System ### Level 1 Implement: - `create_account(account_id)` - `deposit(account_id, amount)` - `pay(account_id, amount)`: remove money from the account and send it out of the system. Reject missing accounts and insufficient funds. ### Level 2 Implement `top_spenders(n)`: return the top `n` accounts by total amount paid. Cashback refunds do not reduce total spending. ### Level 3 Each successful payment schedules a cashback of 2 percent after 24 hours: - `pay(timestamp, account_id, amount)` returns a global payment ID such as `payment1`, `payment2`, and so on. - `get_payment_status(timestamp, account_id, payment_id)` returns `IN_PROGRESS`, `CASHBACK_RECEIVED`, or null. Process due cashbacks lazily at the start of each timestamped operation. ### Level 4 Implement `merge_accounts(primary_account_id, secondary_account_id)`: merge balances and total spending. Pending cashbacks originally targeting the secondary account must be paid to the primary account. Payment IDs created under the secondary account must be queryable through the primary account after the merge. The secondary account no longer exists. ## Problem E: Inventory and Warehouse System ### Level 1 Implement: - `add_stock(item, quantity)`: increase inventory and return the new quantity. - `remove_stock(item, quantity)`: decrease inventory if enough stock exists; otherwise fail. - `get_quantity(item)`: return the current quantity. ### Level 2 Implement `top_items(n)`: return the top `n` items by total movement volume. Both additions and removals count toward movement. Current quantity and movement volume must be tracked separately. ### Level 3 Add expiring batches: - `add_stock_with_expiry(timestamp, item, quantity, expires_at)`: add a batch that expires at `expires_at`. - Time-aware reads and removals must ignore expired batches. - `remove_stock(timestamp, item, quantity)` must consume non-expired batches in earliest-expiration-first order. ### Level 4 Add a warehouse dimension: - Track stock by `(warehouse_id, item)`. - `transfer(timestamp, source_warehouse_id, target_warehouse_id, item, quantity)` moves stock between warehouses. The transfer must preserve original batch expiration metadata; do not simply subtract from one warehouse and add a fresh batch to the other. ## Problem F: Hotel Reservation System ### Level 1 Implement: - `book_room(room_id, guest_id, start_day, nights)`: create a booking for the half-open interval `[start_day, start_day + nights)` if the room has no conflict. Return a booking ID, or null on conflict. - `cancel_booking(booking_id)`: cancel an existing booking. - `get_room_status(room_id, day)`: return whether the room is available or occupied on that day. ### Level 2 Implement `top_guests(n)`: return the top `n` guests by cumulative booked nights. Canceled bookings still count toward this ranking. ### Level 3 Add pricing and revenue: - `set_rate(weekday_rate, weekend_rate)`: configure nightly rates. - `book_room` must return both booking ID and total price. - `get_revenue(start_day, end_day)`: return total revenue for the requested day range. If a booking partially overlaps the range, count only the overlapping nights. Determine weekday versus weekend using the day index modulo 7. ### Level 4 Implement: - `move_booking(booking_id, new_room_id)`: move a booking to another room only if the destination room has no overlapping booking during the same interval. - `merge_room_history(target_room_id, source_room_id)`: move all source-room bookings into the target-room history only if doing so creates no interval conflicts. ## Problem G: Advertisement Bidding System ### Level 1 Implement: - `submit_bid(advertiser_id, slot_id, amount)`: create or replace the advertiser active bid for the slot. One advertiser may have at most one active bid per slot. - `cancel_bid(advertiser_id, slot_id)`: cancel an active bid. - `get_winning_bid(slot_id)`: return the current highest active bid for the slot, or null if none exists. ### Level 2 Implement `top_advertisers(n)`: return the top `n` advertisers by total amount won in closed slots. ### Level 3 Implement `close_slot(slot_id)`: close the auction. The highest active bid wins, with lexicographic advertiser ID as the tie-breaker. Losing bids are released. Future bids on a closed slot must fail. ### Level 4 Add advertiser budgets: - `set_budget(advertiser_id, budget)` - `submit_bid` must ensure `active_holds + won_total <= budget` after the bid is placed. - `get_budget_remaining(advertiser_id)` returns `budget - active_holds - won_total`. When a slot closes, the winner active hold becomes won total, and losing holds are released.