Build an **in-memory credit ledger** for a shared GPU pool. Each event changes exactly one tenant's credit balance, and every event must be applied **at most once** even if it is replayed. ## Event schema An event is a triple **`(eventId, tenantId, delta)`**: - **`eventId`** — a unique identifier used for idempotency. - **`tenantId`** — the tenant whose balance changes. - **`delta`** — a signed integer; a positive value **adds** credits, a negative value **deducts** credits. ## Business rules 1. **Non-negative balance.** A tenant's balance may never drop below `0`. If applying an event would make the resulting balance negative, **reject** that event and leave the balance unchanged. 2. **Idempotency by `eventId`.** Each `eventId` is processed **exactly once**. The first time an `eventId` is seen, it is evaluated under rule 1 and produces an accept/reject result. If the **same `eventId`** is ever seen again, it must **not** change state again — instead, return the **same** accept/reject result that was produced the first time, without re-evaluating it against the current balance. 3. **Initialization.** The initial events are applied **in order** using the exact same rules above (so an init event can be rejected for going negative, and a repeated init `eventId` is deduplicated). 4. **Unknown tenant.** Reading the balance of a tenant that has never had an accepted event returns `0`. ## Function to implement ```python def solution(init_events, operations): ... ``` - **`init_events`** — the ordered list of initial events to seed the ledger (the list passed to `init`). Each item is an `(eventId, tenantId, delta)` triple. - **`operations`** — an ordered list of later actions. Each action is one of: - **`('get', tenantId)`** — read a balance. - **`('apply', (eventId, tenantId, delta))`** — apply an event. First seed the ledger by processing every item in `init_events` (rules 1–3). Then process the `operations` in order. ## Output Return a **list** of outputs, one entry per item in `operations`, in order: - For **`('get', tenantId)`**, append the tenant's current integer balance (`0` if the tenant is unknown). - For **`('apply', event)`**, append **`True`** if the event is accepted, or **`False`** if it is rejected. If the event's `eventId` is a duplicate of one already processed (in `init_events` or in an earlier operation), append the **same** boolean result produced the first time that `eventId` was processed. `('get', ...)` operations produce no state change; they only read. ## Constraints - `0 <= len(init_events), len(operations) <= 2 * 10^5` - `-10^9 <= delta <= 10^9` - Average-case **O(1)** time is expected per `get`/`apply` after O(n) initialization. - A repeated `eventId` represents the same logical event; replays must be idempotent. ## Follow-up (discussion only, not implemented) Be ready to explain your O(1)-average data structures, how you would make updates thread-safe, and how you would persist the ledger for crash recovery (for example, a write-ahead log plus periodic snapshots).