Workspace Credit Ledger: Transfers, Top-K, Scheduled Transfers, Merges, Balance History

Build an in-memory system that manages workspaces holding credit, much like bank accounts that can send money to one another. The task is a timed online assessment (about 90 minutes) in four levels that unlock one after another. Each level adds operations, everything from earlier levels must keep working, and each level is graded by automated tests. The source does not give exact method signatures or return values. This practice version fixes an interface so the behavior can be tested. Where a policy is left open, the default to use is marked as an assumption, and the open policy is repeated under Clarifying Questions. Implement a class `WorkspaceManager` with the methods described in the four Parts. ### Constraints and Clarifications - Every method receives an integer `timestamp` as its first argument. Timestamps are strictly increasing from one call to the next. - Workspace ids are non-empty strings. Every `amount` and every `delay` is a positive integer. - Credit balances are integers and can never go below zero. - Invalid requests, such as one naming an unknown workspace, return the failure value given for each method; they do not raise. ### Clarifying Questions - Should failed operations return a sentinel value or raise an error? (Assumed: return the sentinel.) - When several workspaces have the same credit, how should top-k order them? (Assumed: by workspace id, ascending.) - For a scheduled transfer, is the sender's credit checked when the transfer is scheduled, when it executes, or both, and is it held aside in between? (Assumed: checked only when it executes, and not held aside.) - After a merge removes a workspace, may its id be created again? (Assumed: yes, as a new workspace with its own history.) ### Part 1 — Create workspaces and add credit - `create_workspace(timestamp, workspace_id) -> bool` creates a workspace with zero credit. It returns `False` and changes nothing if a workspace with that id already exists. - `add_credit(timestamp, workspace_id, amount) -> int | None` adds `amount` to the workspace and returns its new balance, or `None` if the workspace does not exist. ```hint Give a workspace its own class Keep each workspace's state and its basic credit operations in a small class of their own, so later levels call those operations instead of editing balances directly. ``` #### What This Part Should Cover - How workspaces are stored and looked up by id - Duplicate creation and unknown ids - A structure that later levels can extend without rewriting ### Part 2 — Instant transfers and top-k - `transfer(timestamp, source_id, target_id, amount) -> int | None` moves `amount` from the source to the target immediately and returns the source's new balance. It returns `None` and changes nothing if either workspace does not exist, if the source and target are the same, or if the source has less than `amount`. - `top_k(timestamp, k) -> list[tuple[str, int]]` returns `(workspace_id, balance)` pairs for the `k` workspaces with the most credit, highest first, with ties broken by workspace id in ascending order. If fewer than `k` workspaces exist, it returns all of them. ```hint Two balances, one decision A transfer changes two workspaces. Decide everything that can make it fail before either balance moves. ``` #### What This Part Should Cover - Validation order and all-or-nothing updates - The cost of producing the ranking, and the tie rule - Boundary cases such as `k` larger than the number of workspaces, and self-transfers ### Part 3 — Scheduled transfers and cancellation - `schedule_transfer(timestamp, source_id, target_id, amount, delay) -> str | None` registers a transfer that is due at time `timestamp + delay` and returns a new transfer id: `"transfer1"`, `"transfer2"`, and so on in creation order (an assumption of this version). It returns `None` if either workspace does not exist or the two ids are equal. - `cancel_transfer(timestamp, transfer_id) -> bool` cancels a scheduled transfer that is still pending and returns `True`. It returns `False` if the id is unknown or the transfer has already executed, failed or been canceled. Rules for scheduled transfers: - Before any method call at time `t` does its own work, every pending scheduled transfer due at or before `t` executes, in order of due time, and in creation order when due times are equal. A cancel at or after a transfer's due time is therefore too late. - A scheduled transfer whose sender has less credit than `amount` when it executes fails and changes nothing. ```hint Time moves only when you are called Nothing runs in the background. Think about which calls must first bring the system up to date, and how to find the due transfers without re-examining every transfer ever scheduled. ``` #### What This Part Should Cover - Where the catch-up step runs, and why every public method needs it - A deterministic execution order for transfers due at the same time - A data structure that finds due transfers efficiently - The life cycle of a scheduled transfer: pending, executed, failed, canceled ### Part 4 — Merge workspaces and look up past balances - `merge_workspaces(timestamp, target_id, source_id) -> bool` folds the source into the target: the target receives all of the source's credit, the source workspace is deleted, and every still-pending scheduled transfer that involves the source, as sender or receiver, is canceled. It returns `False` and changes nothing if either workspace does not exist or the ids are equal. As with every method, transfers due at or before `timestamp` execute first; only transfers still pending afterwards are canceled. - `get_balance(timestamp, workspace_id, time_at) -> int | None`, with `time_at <= timestamp`, returns the balance the workspace had at time `time_at`, after every change made at a time up to and including `time_at`. It returns `None` if no workspace with that id existed at `time_at`. An executed scheduled transfer counts as happening at its due time. A workspace that was merged away stops existing at the merge time, but its earlier history can still be queried. ```hint History only grows forward Each balance change happens at a known time, and time never goes backwards. Think about what to record at each change so that a past time can be answered without replaying every operation. ``` #### Clarifying Questions for this Part - Should the target's history include the source's past balances, or show the merged credit only from the merge time onward? (Assumed: only from the merge time onward.) #### Example across all four levels | Call | Returns | Comment | | --- | --- | --- | | `create_workspace(1, "A")` | `True` | | | `create_workspace(2, "B")` | `True` | | | `add_credit(3, "A", 100)` | `100` | | | `transfer(4, "A", "B", 30)` | `70` | A has 70, B has 30 | | `schedule_transfer(5, "B", "A", 20, 5)` | `"transfer1"` | due at time 10 | | `top_k(6, 2)` | `[("A", 70), ("B", 30)]` | | | `get_balance(11, "A", 9)` | `70` | transfer1 executes first, effective at time 10 | | `get_balance(12, "A", 10)` | `90` | | | `merge_workspaces(13, "A", "B")` | `True` | A has 90 + 10 = 100 | | `get_balance(14, "B", 12)` | `10` | | | `get_balance(15, "B", 13)` | `None` | B was merged away at time 13 | | `top_k(16, 5)` | `[("A", 100)]` | | #### What This Part Should Cover - The steps of a merge and the order they must happen in - How balance history is stored and searched, and what that costs - Recording executed scheduled transfers at their due times - Ids that never existed, were merged away, or were created again ### What a Strong Answer Covers - A workspace class plus a manager, so each level extends the design instead of rewriting it - All-or-nothing updates and consistent failure values across methods - A correct catch-up model for scheduled transfers, applied at the start of every public call in a deterministic order - Data structures with stated costs: hash maps for lookup, an ordered structure for due transfers, binary search over history - Edge cases across levels: self-transfers, insufficient credit at execution time, cancels that come too late, merges with pending transfers, re-created ids - Working level by level and testing each one before moving on, which is how the assessment is scored ### Follow-up Questions - `top_k` is called far more often than balances change. How would you avoid sorting every workspace on each call? - How would a merge cancel the source's pending transfers without scanning every transfer ever scheduled? - If calls could arrive with equal or decreasing timestamps, what in your design breaks, and how would you change it? - How would you make the manager safe when transfers arrive concurrently from many threads?