Design an in-memory banking service
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Design an in-memory banking service supporting timestamped operations and edge-case semantics. Implement:
(
1) create_account(id, t): Create a new account at timestamp t. Return false if id currently exists and has not been merged since its last existence. After an account id is merged away, it may be created again at a later timestamp with balance initialized to 0, without erasing pre-merge historical activities.
(
2) deposit(id, amount, t) and pay(id, amount, t): Update balance at timestamp t; amounts are non-negative integers; reject pay if insufficient funds.
(
3) transfer(src, dst, amount, t) to initiate a pending transfer that immediately debits src’s available balance; accept_transfer(dst, transfer_id, t
2) to finalize the transfer into dst at timestamp t2. Activity counting rule: only finalized transfers (at t
2) contribute to activity; initiating a transfer does not.
(
4) top_activity(t, k): At timestamp t, return the k account ids with the largest 'activity' at t, where an account’s activity at t is the sum of absolute amounts of all operations occurring exactly at timestamp t for that account (e.g., deposit 200 and pay 100 at the same t yields activity
300). If an account id was merged before t, it must not appear for t or later; its historical activity prior to the merge remains queryable at earlier timestamps.
(
5) merge_accounts(dst, src, t): Merge src into dst at timestamp t. After merge, queries for src at any timestamp ≥ t (balance, activity, etc.) return None; dst’s balance/history continue. The id src may be re-created later via create_account(src, t'), in which case its balance resets to 0 starting at t', without altering pre-merge history.
(
6) get_balance(id, t): Return the account’s balance as of timestamp t. Specify:
(a) data structures to support these semantics efficiently;
(b) exact return values for invalid operations and the edge cases noted above;
(c) time/space complexity of each operation;
(d) a unit-testing plan that covers the tricky merge and activity rules.
Quick Answer: This question evaluates system-design and algorithmic competencies related to stateful in-memory services, including temporal semantics, merge and re-creation semantics, transactional transfer handling, activity aggregation, and appropriate data-structure and complexity reasoning.
Part 1: Reusable Account IDs After Merge-Away
Given a chronological list of account operations, return one boolean verdict per operation indicating whether it **succeeds**.
Each account ID is alive only while it is **active**. The two operations toggle this state, and reusing an ID after it has been merged away is allowed.
## Function
```python
def solution(operations):
...
```
## Input
`operations` is a list, in chronological order, of triples:
```
(kind, account_id, timestamp)
```
- **`kind`** — either `'create'` or `'merge_away'`.
- **`account_id`** — a non-empty string (length at most 20).
- **`timestamp`** — an integer. Timestamps are non-decreasing but **do not affect any verdict** and can be ignored.
## Output
Return a **list of booleans** the same length as `operations`, where the i-th entry is the verdict for the i-th operation (in input order).
## Operation rules
Maintain the set of currently **active** IDs (initially empty), then process each operation in order:
- **`create`**: An ID may be created only if it is **not** currently active.
- If the ID is **not** active → it becomes active and the operation **succeeds** (`True`).
- If the ID **is** already active → the operation **fails** (`False`) and the active set is unchanged.
- **`merge_away`**: An ID is merged into some other account elsewhere and stops existing. This may only be applied to an ID that is currently active.
- If the ID **is** active → it becomes inactive and the operation **succeeds** (`True`).
- If the ID is **not** active → the operation **fails** (`False`) and the active set is unchanged.
Because a successful `merge_away` removes the ID from the active set, that **same ID may be created again later** as a fresh account, and the new `create` succeeds.
You only need to decide success or failure of each operation; you are not asked to track balances or historical activity.
## Examples
```
operations = [('create', 'A', 1), ('create', 'A', 2)]
-> [True, False] # second create fails: 'A' is already active
operations = [('create', 'A', 1), ('merge_away', 'A', 5), ('create', 'A', 7)]
-> [True, True, True] # 'A' is reusable after being merged away
operations = [('merge_away', 'X', 1), ('create', 'X', 2)]
-> [False, True] # nothing active to merge away, then create succeeds
```
## Constraints
- `1 <= len(operations) <= 200000`
- Account IDs are non-empty strings of length at most 20.
- Timestamps are integers in non-decreasing order.
Constraints
- 1 <= len(operations) <= 200000
- Account IDs are non-empty strings of length at most 20
- Timestamps are integers in non-decreasing order
Examples
Input: ([('create', 'A', 1), ('create', 'A', 2)],)
Expected Output: [True, False]
Explanation: The second create fails because A is still active.
Input: ([('create', 'A', 1), ('merge_away', 'A', 5), ('create', 'A', 7)],)
Expected Output: [True, True, True]
Explanation: After A is merged away, the ID can be reused.
Input: ([('merge_away', 'X', 1), ('create', 'X', 2)],)
Expected Output: [False, True]
Explanation: You cannot merge away an inactive ID, but you may create it afterward.
Input: ([('create', 'A', 1), ('create', 'B', 2), ('merge_away', 'A', 3), ('create', 'A', 4), ('merge_away', 'B', 5), ('merge_away', 'B', 6)],)
Expected Output: [True, True, True, True, True, False]
Explanation: The last operation fails because B was already merged away.
Solution
def solution(operations):
active = set()
result = []
for op in operations:
kind = op[0]
if kind == 'create':
_, acc_id, _ = op
if acc_id in active:
result.append(False)
else:
active.add(acc_id)
result.append(True)
elif kind == 'merge_away':
_, acc_id, _ = op
if acc_id in active:
active.remove(acc_id)
result.append(True)
else:
result.append(False)
else:
raise ValueError('Unknown operation type')
return resultExplanation
**Approach — simulate the live set of active IDs.**
The only state that matters for deciding success is *which IDs are currently active*. We track that with a single hash `set` called `active`, then walk the operations in chronological order, appending one boolean verdict per operation to `result`.
For each operation we branch on `op[0]`, the operation kind:
- **`create`**: An ID may be created only if it is *not* currently active. So if `acc_id in active`, the create fails (`False`) and we leave the set unchanged. Otherwise we `add` it and record `True`. Because a merged-away ID was already removed from the set, a later re-create of the same ID correctly succeeds — this is what makes IDs reusable after `merge_away`.
- **`merge_away`**: This succeeds only if the ID is currently active. If `acc_id in active`, we `remove` it (it stops existing) and record `True`; otherwise nothing is active to merge and we record `False`.
- Any other kind raises `ValueError`.
**Why it's correct.** The set is an exact invariant of "IDs that exist right now." `create` toggles an absent ID to present; `merge_away` toggles a present ID to absent. Each verdict depends only on current membership, which is precisely the rule the problem states. Timestamps are never consulted — they're already non-decreasing and don't affect success — so they're simply ignored.
The output list mirrors the input one-to-one, preserving order via `append`.
Time complexity: O(n) average, where n is the number of operations — each does one O(1) average-time set membership test plus at most one O(1) add/remove.. Space complexity: O(m), where m is the peak number of simultaneously active IDs (the size of `active`); the `result` list adds O(n) for the returned output..
Hints
- You only need to know whether an ID is currently active or not.
- A successful `merge_away` frees that ID for a later `create`.
Part 2: Timestamped Deposits and Payments
Simulate the balance updates of a simple in-memory bank, processing a stream of timestamped operations and returning the result of each one.
Implement:
```python
def solution(operations):
...
```
## Input
`operations` is a list of operations given in chronological order. Each operation is a **tuple** whose first element is a string tag identifying its type:
- **Create:** `('create', acc_id, timestamp)` — request to open a new account `acc_id`.
- **Deposit:** `('deposit', acc_id, amount, timestamp)` — add `amount` to account `acc_id`.
- **Pay:** `('pay', acc_id, amount, timestamp)` — withdraw `amount` from account `acc_id`.
`amount` is a non-negative integer (zero is allowed). `timestamp` is an integer; timestamps are non-decreasing. Because the operations already arrive in chronological order, the timestamp is informational only — you do **not** need to read or sort by it.
## Output
Return a **list** with exactly one entry per operation, in the same order as the input. The entry depends on the operation type:
- **`create`** → `True` if the account was newly opened, or `False` if an account with that `acc_id` already exists (the existing account is left unchanged).
- **`deposit`** → `None` if the account does not exist (the deposit is rejected). Otherwise, add `amount` to the balance and return the **new balance** (an integer). A zero-amount deposit on an existing account is valid and returns the unchanged balance.
- **`pay`** → `None` if the account does not exist **or** if the balance is less than `amount` (insufficient funds — the payment is rejected and the balance is unchanged). Otherwise, subtract `amount` from the balance and return the **new balance** (an integer). A payment that brings the balance to exactly `0` is allowed; a zero-amount payment always succeeds when the account exists.
## Rules
- All balances start at `0` when an account is created.
- A payment is allowed only when `amount <= balance` (so an account may be drained to exactly `0`, but not overdrawn).
- A deposit or payment on a non-existent account is rejected with `None` and does not create the account.
## Example
For the input
```python
[('create', 'A', 1), ('deposit', 'A', 100, 2), ('pay', 'A', 30, 3)]
```
the result is `[True, 100, 70]`: account `A` is opened (`True`), the deposit brings the balance to `100`, and the payment of `30` leaves `70`.
## Constraints
- `1 <= len(operations) <= 200000`
- `0 <= amount <= 10^9`
- Timestamps are integers in non-decreasing order.
Constraints
- 1 <= len(operations) <= 200000
- 0 <= amount <= 10^9
- Timestamps are integers in non-decreasing order
Examples
Input: ([('create', 'A', 1), ('deposit', 'A', 100, 2), ('pay', 'A', 30, 3)],)
Expected Output: [True, 100, 70]
Explanation: A is created, then updated twice.
Input: ([('create', 'A', 1), ('pay', 'A', 1, 2)],)
Expected Output: [True, None]
Explanation: The payment is rejected because A has insufficient funds.
Input: ([('deposit', 'X', 10, 1), ('create', 'X', 2), ('pay', 'X', 0, 3)],)
Expected Output: [None, True, 0]
Explanation: The first deposit is invalid because X does not exist yet. A zero payment on balance 0 succeeds.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 50, 2), ('deposit', 'B', 20, 2), ('pay', 'A', 50, 2), ('pay', 'B', 25, 3)],)
Expected Output: [True, True, 50, 20, 0, None]
Explanation: A can pay exactly its balance, but B cannot overdraw.
Solution
def solution(operations):
balances = {}
result = []
for op in operations:
kind = op[0]
if kind == 'create':
_, acc_id, _ = op
if acc_id in balances:
result.append(False)
else:
balances[acc_id] = 0
result.append(True)
elif kind == 'deposit':
_, acc_id, amount, _ = op
if acc_id not in balances:
result.append(None)
else:
balances[acc_id] += amount
result.append(balances[acc_id])
elif kind == 'pay':
_, acc_id, amount, _ = op
if acc_id not in balances or balances[acc_id] < amount:
result.append(None)
else:
balances[acc_id] -= amount
result.append(balances[acc_id])
else:
raise ValueError('Unknown operation type')
return resultExplanation
**Approach.** This is a straightforward simulation of an in-memory bank using a single hash map. `balances` maps each account id to its current integer balance, and `result` collects the outcome of every operation in order. We iterate once over `operations`, dispatching on the operation tag `op[0]`.
**Per-operation logic:**
- **`create`** — `(`'create', acc_id, ts)`. If `acc_id` is already a key, the account exists, so we append `False`. Otherwise we initialize `balances[acc_id] = 0` and append `True`.
- **`deposit`** — `('deposit', acc_id, amount, ts)`. If the account doesn't exist we append `None` (rejected). Otherwise we add `amount` and append the new balance. Since `amount >= 0`, a zero deposit is a valid no-op that still returns the (unchanged) balance.
- **`pay`** — `('pay', acc_id, amount, ts)`. Rejected with `None` if the account is missing **or** has insufficient funds (`balances[acc_id] < amount`). Otherwise subtract and append the resulting balance. A zero payment always succeeds when the account exists.
Any unrecognized tag raises `ValueError`.
**Why it's correct.** Operations already arrive in chronological order, so the embedded timestamp is informational only and never needs to be read for ordering — processing tuples left to right reproduces the real-world sequence. Each operation's accept/reject decision depends solely on the current map state, which is exactly the invariant a bank balance maintains. The `<` (not `<=`) check lets a payment drain an account to exactly zero, and the existence guards make missing-account deposits/payments return `None` as specified.
**Data structure.** A dict gives O(1) average create/deposit/pay, which is what keeps the whole pass linear over up to 200,000 operations.
Time complexity: O(n). Space complexity: O(m).
Hints
- A hash map from account ID to current balance is enough for this sub-problem.
- Treat amount 0 like a normal operation; it still succeeds if the account exists.
Part 3: Pending Transfers and Acceptance
Implement a small **banking engine** that supports **pending (escrow-style) transfers**: a transfer debits the source account immediately, but the destination is not credited until the transfer is explicitly **accepted**.
## Function
```python
def solution(operations):
...
```
`operations` is a list of operation tuples. Process them **in order**, maintaining account balances and a ledger of outstanding pending transfers. For each operation, append one result to an output list, and **return that list**.
Every operation tuple ends with an integer `timestamp` (timestamps are non-decreasing and do not affect the logic). The first element of each tuple is the operation **kind**.
## Operations
**`('create', acc_id, timestamp)`** — Create a new account with balance `0`.
- If `acc_id` already exists, change nothing and append `False`.
- Otherwise create it at balance `0` and append `True`.
**`('deposit', acc_id, amount, timestamp)`** — Add `amount` to an account.
- If `acc_id` does not exist, change nothing and append `None`.
- Otherwise add `amount` to its balance and append the **new balance**.
**`('transfer', src, dst, amount, timestamp)`** — Start a pending transfer from `src` to `dst`.
- The transfer is **rejected** (change nothing, append `None`) if any of these hold:
- `src == dst`, or
- `src` does not exist, or
- `dst` does not exist, or
- `balances[src] < amount` (insufficient funds).
- Otherwise it **succeeds**: immediately **debit** `amount` from `src`, create a pending transfer recording `(src, dst, amount)`, and append the transfer's **id**.
- Transfer ids are unique integers assigned in order, **starting at 1** and incrementing by 1 for each successful transfer.
- The destination is **not** credited at this point — the money sits in escrow until accepted.
**`('accept', dst, transfer_id, timestamp)`** — Complete a pending transfer.
- Append `False` (and change nothing) if any of these hold:
- `transfer_id` is not an outstanding pending transfer, or
- the supplied `dst` does **not** match the transfer's recorded destination, or
- that destination account no longer exists.
- Otherwise **credit** the recorded `amount` to the destination account, remove the pending transfer, and append `True`.
**`('balance', acc_id, timestamp)`** — Look up an account's balance.
- Append the current balance of `acc_id`, or `None` if the account does not exist.
## Important rules
- **A failed `accept` must not destroy the pending transfer.** If `accept` is called with the wrong destination (or otherwise fails the checks above), it returns `False` but leaves the pending transfer intact, so a later **correct** `accept` can still complete it.
- An `amount` of `0` is valid for both `deposit` and `transfer` (a 0-amount transfer with both accounts present succeeds and produces a normal transfer id).
## Examples
For `operations = [('create','A',1), ('create','B',1), ('deposit','A',100,2), ('transfer','A','B',40,3), ('balance','A',4), ('accept','B',1,5), ('balance','B',6)]` the result is `[True, True, 100, 1, 60, True, 40]`.
For `operations = [('create','A',1), ('create','B',1), ('deposit','A',20,2), ('transfer','A','B',30,3), ('balance','A',4), ('accept','B',1,5)]` the result is `[True, True, 20, None, 20, False]` — the transfer is rejected for insufficient funds (returns `None`), `A` keeps its `20`, and the later `accept` of the non-existent transfer `1` returns `False`.
## Constraints
- `1 <= len(operations) <= 200000`
- `0 <= amount <= 10^9`
- Timestamps are integers in non-decreasing order.
Constraints
- 1 <= len(operations) <= 200000
- 0 <= amount <= 10^9
- Timestamps are integers in non-decreasing order
Examples
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 100, 2), ('transfer', 'A', 'B', 40, 3), ('balance', 'A', 4), ('accept', 'B', 1, 5), ('balance', 'B', 6)],)
Expected Output: [True, True, 100, 1, 60, True, 40]
Explanation: The transfer debits A immediately and credits B only on acceptance.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 20, 2), ('transfer', 'A', 'B', 30, 3), ('balance', 'A', 4), ('accept', 'B', 1, 5)],)
Expected Output: [True, True, 20, None, 20, False]
Explanation: The transfer fails because A does not have enough money.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('create', 'C', 1), ('deposit', 'A', 50, 2), ('transfer', 'A', 'B', 20, 3), ('accept', 'C', 1, 4), ('balance', 'B', 5), ('accept', 'B', 1, 6), ('balance', 'B', 7)],)
Expected Output: [True, True, True, 50, 1, False, 0, True, 20]
Explanation: The wrong destination cannot accept the transfer, but the correct destination still can later.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 0, 2), ('transfer', 'A', 'B', 0, 3), ('accept', 'B', 1, 4), ('accept', 'B', 1, 5), ('balance', 'A', 6), ('balance', 'B', 6)],)
Expected Output: [True, True, 0, 1, True, False, 0, 0]
Explanation: A zero-amount transfer is allowed, but it can only be accepted once.
Solution
def solution(operations):
balances = {}
pending = {}
next_transfer_id = 1
result = []
for op in operations:
kind = op[0]
if kind == 'create':
_, acc_id, _ = op
if acc_id in balances:
result.append(False)
else:
balances[acc_id] = 0
result.append(True)
elif kind == 'deposit':
_, acc_id, amount, _ = op
if acc_id not in balances:
result.append(None)
else:
balances[acc_id] += amount
result.append(balances[acc_id])
elif kind == 'transfer':
_, src, dst, amount, _ = op
if src == dst or src not in balances or dst not in balances or balances[src] < amount:
result.append(None)
else:
balances[src] -= amount
pending[next_transfer_id] = (src, dst, amount)
result.append(next_transfer_id)
next_transfer_id += 1
elif kind == 'accept':
_, dst, transfer_id, _ = op
if transfer_id not in pending:
result.append(False)
else:
_, real_dst, amount = pending[transfer_id]
if dst != real_dst or real_dst not in balances:
result.append(False)
else:
balances[real_dst] += amount
del pending[transfer_id]
result.append(True)
elif kind == 'balance':
_, acc_id, _ = op
result.append(balances.get(acc_id))
else:
raise ValueError('Unknown operation type')
return resultExplanation
This is a single-pass **simulation** over the operation list. State lives in two dicts plus a counter:
- `balances` — `account_id -> current balance`
- `pending` — `transfer_id -> (src, dst, amount)` (an escrow ledger)
- `next_transfer_id` — monotonically increasing, starting at `1`
Each op is dispatched on `op[0]` and does only O(1) dict work:
- **create**: rejects (`False`) if the account already exists, else inserts it at balance `0` and returns `True`.
- **deposit**: `None` if the account is missing, else adds `amount` and returns the new balance.
- **transfer**: validates `src != dst`, both accounts exist, and `balances[src] >= amount`. If any check fails it returns `None` and changes nothing. On success it **immediately debits** `src`, escrows `(src, dst, amount)` under the next id, returns that id, and increments the counter. The destination is *not* credited yet — the money sits in `pending`.
- **accept**: returns `False` if `transfer_id` isn't pending. Otherwise it reads the stored `real_dst`/`amount` and requires the supplied `dst == real_dst` (and the destination still exists). Only then does it credit `real_dst`, `del` the pending entry, and return `True`.
**Why it's correct:** the wrong-acceptance guard checks the destination *before* mutating anything and only deletes `pending[transfer_id]` on success, so a mismatched `accept` returns `False` while leaving the escrow intact for a later correct accept (verified by tests 3 and 4). Debiting at transfer time and crediting only on accept makes funds conserved at every step, and a transfer of amount `0` is handled naturally (`balances[src] >= 0` always holds).
Time complexity: O(n), where n is the number of operations — each operation does O(1) average-case dict lookups/updates.. Space complexity: O(a + p), where a is the number of accounts and p is the number of outstanding pending transfers (plus the O(n) result list)..
Hints
- Store current balances separately from pending transfers.
- A transfer should reduce the source balance immediately, even before acceptance.
Part 4: Top Activity at an Exact Timestamp
Given a log of completed banking **records** and a list of independent **queries**, report, for each query, the accounts with the highest *activity* at an exact timestamp.
## Activity at a timestamp
For a timestamp `t`, an account's **activity at `t`** is the sum of the amounts of all operations that occur at *exactly* `t` for that account. (Amounts are non-negative, so this is simply their sum.)
## Inputs
### `records`
A list of operation tuples, **sorted by non-decreasing timestamp**. Each tuple's first element is a kind string. The recognized kinds and how each contributes to activity are:
- **`('create', acc_id, t)`** — Begins a new lifetime for `acc_id` at time `t`. Adds **no** activity.
- **`('deposit', acc_id, amount, t)`** — Adds `amount` to `acc_id`'s activity at `t`.
- **`('pay', acc_id, amount, t)`** — Adds `amount` to `acc_id`'s activity at `t`.
- **`('accepted_transfer', src, dst, amount, t)`** — Adds `amount` to **both** `src` and `dst`'s activity at `t`.
- **`('merge_away', acc_id, t)`** — Makes `acc_id` **ineligible** to appear in any query result for timestamp `t` **or any later timestamp**. Adds no activity.
### `queries`
A list of `(t, k)` pairs. Each query is independent.
## Account lifetimes and eligibility
An account becomes **active** when it is `create`d and remains active until it is `merge_away`'d:
- A `merge_away(acc_id, t)` ends the current lifetime **at `t`, inclusive** — the account is *not* eligible at `t` itself, nor at any later time, for that lifetime.
- Therefore an account created at time `s` and merged away at time `e` is eligible only for timestamps in the half-open range `s <= t < e`.
- An account that is never merged away stays active for all timestamps at or after its `create` time.
- A later `create` of the same ID starts a **fresh, independent lifetime**. An ID can thus be active in one range, ineligible in a gap, and active again in a later range.
## Output
Return a list with **one entry per query**, in the same order as `queries`.
For a query `(t, k)`, produce the list of account IDs that satisfy **all** of:
1. The account is **active** (eligible) at timestamp `t`, and
2. The account has **positive** activity at exactly `t` (activity `> 0`).
Order these IDs by:
- **descending activity** at `t`, then
- **ascending lexicographic order of the ID** to break ties.
Return at most the first **`k`** IDs from this ordering. If no account qualifies (including when no operations occur at `t`), return an empty list for that query.
## Constraints
- `1 <= len(records), len(queries) <= 200000`
- `0 <= amount <= 10^9`
- Records are valid and sorted by non-decreasing timestamp.
## Examples
- `deposit A 200` and `pay A 100` at `t=5`, plus `deposit B 250` at `t=5` (both accounts active), query `(5, 2)` → `[['A', 'B']]` (A has activity 300, B has 250).
- `accepted_transfer A B 40` at `t=3` (both active), query `(3, 2)` → `[['A', 'B']]` (both have activity 40; tie broken lexicographically).
- A and B both deposit at `t=4`, then `merge_away A` at `t=4`; queries `(4, 2), (3, 1)` → `[['B'], []]` (A is ineligible from `t=4` on; nothing happens at `t=3`).
- A active at `t=2`, merged away at `t=3`, re-created at `t=5` and deposits there; queries `(2, 1), (4, 1), (5, 1)` → `[['A'], [], ['A']]` (active in `[1,3)`, ineligible at `t=4`, active again from `t=5`).
Constraints
- 1 <= len(records), len(queries) <= 200000
- 0 <= amount <= 10^9
- Records are valid and sorted by non-decreasing timestamp
Examples
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 200, 5), ('pay', 'A', 100, 5), ('deposit', 'B', 250, 5)], [(5, 2)])
Expected Output: [['A', 'B']]
Explanation: At timestamp 5, A has activity 300 and B has activity 250.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('accepted_transfer', 'A', 'B', 40, 3)], [(3, 2)])
Expected Output: [['A', 'B']]
Explanation: A finalized transfer contributes 40 activity to both accounts at timestamp 3.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 50, 4), ('deposit', 'B', 10, 4), ('merge_away', 'A', 4)], [(4, 2), (3, 1)])
Expected Output: [['B'], []]
Explanation: A is merged away at timestamp 4, so it must not appear for timestamp 4 or later.
Input: ([('create', 'A', 1), ('deposit', 'A', 20, 2), ('merge_away', 'A', 3), ('create', 'A', 5), ('deposit', 'A', 7, 5)], [(2, 1), (4, 1), (5, 1)])
Expected Output: [['A'], [], ['A']]
Explanation: The old A is valid at timestamp 2, absent at 4, and the recreated A is valid at 5.
Solution
def solution(records, queries):
from collections import defaultdict
from bisect import bisect_right
activity = defaultdict(lambda: defaultdict(int))
intervals = defaultdict(list)
active_start = {}
for rec in records:
kind = rec[0]
if kind == 'create':
_, acc_id, t = rec
active_start[acc_id] = t
elif kind == 'deposit' or kind == 'pay':
_, acc_id, amount, t = rec
activity[t][acc_id] += amount
elif kind == 'accepted_transfer':
_, src, dst, amount, t = rec
activity[t][src] += amount
activity[t][dst] += amount
elif kind == 'merge_away':
_, acc_id, t = rec
if acc_id in active_start:
intervals[acc_id].append((active_start[acc_id], t))
del active_start[acc_id]
else:
raise ValueError('Unknown record type')
INF = 10 ** 30
for acc_id, start in active_start.items():
intervals[acc_id].append((start, INF))
lookup = {}
for acc_id, ranges in intervals.items():
starts = [start for start, _ in ranges]
ends = [end for _, end in ranges]
lookup[acc_id] = (starts, ends)
def is_active(acc_id, t):
data = lookup.get(acc_id)
if data is None:
return False
starts, ends = data
i = bisect_right(starts, t) - 1
return i >= 0 and t < ends[i]
cache = {}
answer = []
for t, k in queries:
if t not in cache:
ranked = []
for acc_id, amt in activity.get(t, {}).items():
if amt > 0 and is_active(acc_id, t):
ranked.append((-amt, acc_id))
ranked.sort()
cache[t] = [acc_id for _, acc_id in ranked]
answer.append(cache[t][:k])
return answerExplanation
## Approach
The solution does a single pass over `records` to build two structures, then answers each query against them.
**1. Per-timestamp activity.** `activity[t][acc_id]` accumulates the sum of absolute amounts at exactly `t`:
- `deposit` / `pay` add `amount` to the named account.
- `accepted_transfer` adds `amount` to **both** `src` and `dst`.
- `create` contributes nothing.
**2. Eligibility intervals (lifetimes).** Each ID can be created, merged away, and re-created. We track the open lifetime in `active_start[acc_id]`. On `merge_away`, we close it as the half-open interval `(start, t)` and clear the open start; any still-open lifetime at the end is closed with `INF`. Because `merge_away(id, t)` bans the ID *at `t` and after*, the interval end is exclusive: `is_active` returns true only when `start <= t < end`.
**Active lookup.** For each ID we store sorted `starts`/`ends`. `is_active(acc_id, t)` does `bisect_right(starts, t) - 1` to find the latest lifetime starting at or before `t`, then checks `t < ends[i]`. This correctly handles re-created IDs (a later `create` starts a fresh lifetime) — verified by test 4 where `A` is active at `t=2` and `t=5` but not the merged gap at `t=4`.
**Answering queries.** Results are memoized per timestamp in `cache`. For a new `t`, we collect accounts with positive activity that are active, sort by `(-amt, acc_id)` (descending activity, then lexicographic ID via the tuple), and store the ID order. Each query slices the cached list to `k`. The negated-amount tuple sort gives the exact required ordering.
Time complexity: O(R + Σ_t (a_t·log a_t + a_t·log L)), where R = total records, a_t = accounts with activity at distinct queried timestamp t, and L = lifetimes per ID (from the bisect in is_active). Reusing the per-t cache means repeated timestamps cost only the O(k) slice.. Space complexity: O(R) — activity entries, lifetime intervals, and the per-timestamp answer cache are all bounded by the number of records..
Hints
- Store activity by exact timestamp rather than cumulatively over time.
- Because IDs can be merged away and later recreated, think in terms of active time intervals for each ID.
Part 5: Live Account Merges and Re-Creation
Process a live stream of banking operations on accounts, where accounts can be **created**, **deposited into**, **merged**, and **queried** — returning one result per operation in order.
Implement:
```python
def solution(operations):
```
## Input
`operations` is a list of operation tuples. Each tuple's first element is a string naming the operation type; the remaining elements depend on the type. Every operation ends with an integer timestamp `t`. Timestamps are non-decreasing but do not affect the result of any operation.
Account IDs are arbitrary hashable values (e.g. strings). An account is **live** from the moment it is created until it is removed by a merge; it is not live before its first creation or after being merged away.
## Operations
Process the operations strictly in order. Each produces exactly one entry appended to the result list:
- **`('create', acc_id, t)`** — Create a new account with balance `0`.
- If `acc_id` is **already live**, do nothing and append `False`.
- Otherwise create it (starting at balance `0`) and append `True`. A re-created account always starts fresh at `0`.
- **`('deposit', acc_id, amount, t)`** — Add `amount` to an account's balance.
- If `acc_id` is **not live**, do nothing and append `None`.
- Otherwise add `amount` to its balance and append the **new** balance.
- **`('merge', dst, src, t)`** — Move the full current balance of `src` into `dst`, then remove `src` from the live system immediately.
- If `dst == src`, or `dst` is not live, or `src` is not live, do nothing and append `False`.
- Otherwise add `src`'s balance to `dst`'s balance, remove `src` (it becomes non-live immediately, so subsequent deposits/queries on `src` return `None` until it is created again), and append `True`.
- **`('balance', acc_id, t)`** — Query an account's current balance.
- Append the account's current balance if it is **live**, otherwise append `None`.
## Output
Return a list with one element per operation, in the same order as the input, using the per-operation result values described above.
## Notes
- This problem only concerns the **live state** observed while processing operations in order. Pre-merge history is conceptually preserved but is never queried here.
- After a merge, `src` is gone immediately; a later `create` for that same ID starts a brand-new account at balance `0`.
## Constraints
- `1 <= len(operations) <= 200000`
- `0 <= amount <= 10^9`
- Timestamps are integers in non-decreasing order.
Constraints
- 1 <= len(operations) <= 200000
- 0 <= amount <= 10^9
- Timestamps are integers in non-decreasing order
Examples
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 50, 2), ('deposit', 'B', 20, 3), ('merge', 'A', 'B', 4), ('balance', 'A', 5), ('balance', 'B', 5)],)
Expected Output: [True, True, 50, 20, True, 70, None]
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'B', 15, 2), ('merge', 'A', 'B', 3), ('create', 'B', 4), ('balance', 'B', 4), ('deposit', 'B', 5, 5), ('balance', 'A', 6)],)
Expected Output: [True, True, 15, True, True, 0, 5, 15]
Input: ([('create', 'A', 1), ('merge', 'A', 'A', 2), ('merge', 'A', 'B', 3), ('balance', 'A', 4)],)
Expected Output: [True, False, False, 0]
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'B', 4, 2), ('merge', 'A', 'B', 3), ('deposit', 'B', 1, 4), ('balance', 'B', 5)],)
Expected Output: [True, True, 4, True, None, None]
Input: ([('create', 'A', 1), ('create', 'A', 2), ('deposit', 'A', 10, 3), ('create', 'A', 4)],)
Expected Output: [true, false, 10, false]
Input: ([('balance', 'X', 1), ('deposit', 'X', 5, 2), ('merge', 'X', 'Y', 3)],)
Expected Output: [null, null, false]
Input: ([('create', 'A', 1), ('create', 'B', 1), ('create', 'C', 1), ('deposit', 'B', 7, 2), ('deposit', 'C', 3, 3), ('merge', 'A', 'B', 4), ('merge', 'A', 'C', 5), ('balance', 'A', 6), ('balance', 'B', 7), ('balance', 'C', 8)],)
Expected Output: [true, true, true, 7, 3, true, true, 10, null, null]
Solution
def solution(operations):
balances = {}
result = []
for op in operations:
kind = op[0]
if kind == 'create':
_, acc_id, _ = op
if acc_id in balances:
result.append(False)
else:
balances[acc_id] = 0
result.append(True)
elif kind == 'deposit':
_, acc_id, amount, _ = op
if acc_id not in balances:
result.append(None)
else:
balances[acc_id] += amount
result.append(balances[acc_id])
elif kind == 'merge':
_, dst, src, _ = op
if dst == src or dst not in balances or src not in balances:
result.append(False)
else:
balances[dst] += balances[src]
del balances[src]
result.append(True)
elif kind == 'balance':
_, acc_id, _ = op
result.append(balances.get(acc_id))
else:
raise ValueError('Unknown operation type')
return resultExplanation
The solution maintains a single dictionary `balances` mapping each **live** account ID to its current balance, then replays the operation stream in order, appending one result per operation.
**Why a dict is the right structure:** membership in `balances` *is* the definition of "live". An account exists exactly while it has a key; `merge`/`del` and `create` insertions flip that membership, and every operation just reads/writes this one map in O(1).
Per operation type:
- **`create`**: if the ID is already a key, the account is live, so it's a duplicate → append `False`. Otherwise insert it at `0` and append `True`. A re-created account naturally starts fresh at 0 because the previous incarnation's key was removed by its merge.
- **`deposit`**: if the ID isn't live, the deposit is invalid → append `None`. Otherwise add `amount` and append the **new** balance.
- **`merge(dst, src)`**: reject (append `False`) if `dst == src`, or either side isn't live. Otherwise fold `balances[src]` into `balances[dst]`, `del balances[src]` (so `src` becomes invalid immediately), and append `True`.
- **`balance`**: `balances.get(acc_id)` returns the balance for live accounts and `None` for non-live ones in one expression.
**Correctness hinges on ordering and the membership invariant.** Because operations are processed sequentially, the dict always reflects exactly the live state at that moment — matching the "live state observed while processing in order" requirement. The `del` on merge guarantees later `src` deposits/balances return `None` until a fresh `create`. Timestamps are carried in the tuples but aren't needed for the live-state queries, so they're ignored.
Time complexity: O(n), where n is the number of operations. Each operation does O(1) average-case dictionary work (hash lookup/insert/delete).. Space complexity: O(m), where m is the peak number of simultaneously live accounts stored in the dict, plus O(n) for the output list of results..
Hints
- For this sub-problem, a merge is just a move of current balance plus deletion of the source ID from the live map.
- Re-creating a merged-away ID is the same as inserting a new key with balance 0.
Part 6: Balance Queries As of a Timestamp
Implement `solution(events, queries)` to answer **point-in-time balance queries** against an account event log.
You are given a chronological log of account `events` and a list of independent `queries`. For each query `(id, t)`, return the balance of account `id` **as of timestamp `t`** — the state after every event whose timestamp is `<= t` has been applied. Queries do not modify state and are answered independently.
## Input
- **`events`** — a list of event tuples, already sorted by **non-decreasing timestamp**. Each event is one of:
- `('create', id, t)` — opens a new account `id` (or a fresh lifetime for a reused `id`) with balance `0` at time `t`.
- `('deposit', id, amount, t)` — adds `amount` to `id`'s balance at time `t`.
- `('pay', id, amount, t)` — subtracts `amount` from `id`'s balance at time `t`.
- `('merge', dst, src, t)` — folds account `src` into account `dst` at time `t`.
- **`queries`** — a list of `(id, t)` tuples to answer.
## Output
Return a **list** with one entry per query, in the same order:
- the **integer balance** of `id` as of `t`, or
- `None` if `id` is not valid at `t` (see rules below).
## Rules
- **Same-timestamp events are all applied first.** A query at time `t` reflects every event with timestamp `<= t`, including events that share the timestamp `t`. (E.g. a deposit and a pay both at `t=1` are both included for a query at `t=1`.)
- **Before creation → `None`.** If `t` is earlier than the account's `create` time (or the `id` never appears), return `None`.
- **Merge semantics.** After `merge(dst, src, t)`:
- `dst`'s balance at time `t` becomes `dst_balance + src_balance` (each taken just before the merge).
- `src` becomes **invalid for every timestamp `>= t`**; a query on `src` at any `t' >= t` returns `None`. Queries on `src` for timestamps **before** `t` still return its historical balance.
- **Reused IDs start a brand-new lifetime.** If an `id` that was previously merged away is `create`d again later, it begins a fresh account with balance `0`. This new lifetime does **not** affect answers for any earlier timestamp — queries before the re-creation still resolve against the original lifetime.
## Constraints
- `1 <= len(events), len(queries) <= 200000`
- `0 <= amount <= 10^9`
- The event log is valid and sorted by non-decreasing timestamp.
Constraints
- 1 <= len(events), len(queries) <= 200000
- 0 <= amount <= 10^9
- The event log is valid and sorted by non-decreasing timestamp
Examples
Input: ([('create', 'A', 1), ('deposit', 'A', 100, 2), ('pay', 'A', 30, 5)], [('A', 0), ('A', 1), ('A', 4), ('A', 5), ('B', 5)])
Expected Output: [None, 0, 100, 70, None]
Explanation: Queries before creation or for unknown IDs return None.
Input: ([('create', 'A', 1), ('deposit', 'A', 20, 2), ('create', 'B', 3), ('deposit', 'B', 5, 4), ('merge', 'A', 'B', 6)], [('B', 5), ('B', 6), ('A', 6), ('A', 7)])
Expected Output: [5, None, 25, 25]
Explanation: B exists before timestamp 6, but is invalid from timestamp 6 onward after the merge.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 10, 2), ('merge', 'B', 'A', 3), ('create', 'A', 5), ('deposit', 'A', 7, 6)], [('A', 2), ('A', 3), ('A', 5), ('A', 6), ('B', 6)])
Expected Output: [10, None, 0, 7, 10]
Explanation: The old A disappears at timestamp 3, and the recreated A starts fresh at timestamp 5.
Input: ([('create', 'A', 1), ('deposit', 'A', 5, 1), ('pay', 'A', 2, 1)], [('A', 1), ('A', 0)])
Expected Output: [3, None]
Explanation: A query at timestamp 1 sees the state after all timestamp-1 events.
Solution
def solution(events, queries):
from collections import defaultdict
from bisect import bisect_right
INF = 10 ** 30
lifetimes = defaultdict(list)
current = {}
for event in events:
kind = event[0]
if kind == 'create':
_, acc_id, t = event
life = {
'start': t,
'end': INF,
'times': [t],
'balances': [0]
}
lifetimes[acc_id].append(life)
current[acc_id] = life
elif kind == 'deposit':
_, acc_id, amount, t = event
life = current[acc_id]
life['times'].append(t)
life['balances'].append(life['balances'][-1] + amount)
elif kind == 'pay':
_, acc_id, amount, t = event
life = current[acc_id]
life['times'].append(t)
life['balances'].append(life['balances'][-1] - amount)
elif kind == 'merge':
_, dst, src, t = event
dst_life = current[dst]
src_life = current[src]
dst_life['times'].append(t)
dst_life['balances'].append(dst_life['balances'][-1] + src_life['balances'][-1])
src_life['end'] = t
del current[src]
else:
raise ValueError('Unknown event type')
index = {}
for acc_id, lives in lifetimes.items():
starts = [life['start'] for life in lives]
ends = [life['end'] for life in lives]
index[acc_id] = (lives, starts, ends)
answer = []
for acc_id, t in queries:
data = index.get(acc_id)
if data is None:
answer.append(None)
continue
lives, starts, ends = data
i = bisect_right(starts, t) - 1
if i < 0 or t >= ends[i]:
answer.append(None)
continue
life = lives[i]
j = bisect_right(life['times'], t) - 1
answer.append(life['balances'][j])
return answerExplanation
**Approach — per-lifetime balance snapshots + two binary searches.**
The tricky part is that an account ID can live several separate *lifetimes*: `create` opens one, `merge(dst, src, t)` closes `src`'s lifetime at `t`, and a later `create` of the same ID starts a fresh one. We must answer "balance of `id` as of `t`" against the *right* lifetime.
**Building the index (one pass over events).** For each ID we keep a list of lifetimes. Each lifetime is a dict with `start`, `end` (INF until a merge ends it), and two parallel arrays `times`/`balances` recording the running balance after every update:
- `create`: open a new lifetime seeded with `(t, 0)`; mark it `current[id]`.
- `deposit`/`pay`: append `t` and `prev ± amount` to the current lifetime.
- `merge(dst, src, t)`: push `dst_balance + src_balance` onto `dst`'s arrays at time `t`, set `src.end = t`, and drop `src` from `current` so a future re-`create` starts clean.
Because events are sorted by non-decreasing time, each lifetime's `times` array is non-decreasing, and lifetimes for one ID have increasing `start`s.
**Answering a query `(id, t)`.**
1. `bisect_right(starts, t) - 1` finds the latest lifetime that began at or before `t`.
2. If none exists, or `t >= ends[i]` (the lifetime was already merged away / closed), return `None`.
3. Otherwise `bisect_right(life['times'], t) - 1` finds the last update at or before `t`, and we return `balances[j]`.
**Why correct:** using `bisect_right` means same-timestamp events are all applied before the query "sees" `t` (test 4: deposit+pay at t=1 → 3), and the `t >= end` check makes a merged source invalid exactly from the merge time onward (test 3: query at the merge timestamp returns `None`).
Time complexity: O(E + Q·(log r + log u)) where E = number of events, Q = number of queries, r = lifetimes for the queried ID, u = updates in the chosen lifetime. Building the index is O(E) (one pass, amortized O(1) appends); each query does two binary searches.. Space complexity: O(E) — every event contributes at most one entry to some lifetime's times/balances arrays (or starts a new lifetime), so total stored snapshots are linear in the number of events..
Hints
- Because an ID can disappear and later come back, model each ID as a sequence of lifetimes.
- Within a lifetime, store balance changes by timestamp so you can answer queries with binary search.