PracHub
QuestionsPremiumLearningGuidesCheatsheetNEW

Quick Overview

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.

  • Medium
  • Anthropic
  • Coding & Algorithms
  • Software Engineer

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

You are given a chronological list of operations on account IDs. An ID may be created only if it is not currently active. A `merge_away` operation means that this ID stopped existing because it was merged into some other account elsewhere. After an ID has been merged away, the same ID may be created again later as a fresh account. For this sub-problem, you only need to decide whether each operation succeeds; historical balances or activities are not queried.

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 result

Time complexity: O(n) average time, where n is the number of operations. Space complexity: O(m), where m is the number of currently active IDs.

Hints

  1. You only need to know whether an ID is currently active or not.
  2. A successful `merge_away` frees that ID for a later `create`.

Part 2: Timestamped Deposits and Payments

Implement the core balance updates of an in-memory bank. Operations arrive in chronological order and may create an account, deposit money into it, or pay money out of it. Deposits and payments use non-negative integer amounts. A payment must be rejected if the account does not exist or if there are insufficient funds. Zero-amount operations are allowed.

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 result

Time complexity: O(n) average time. Space complexity: O(m), where m is the number of existing accounts.

Hints

  1. A hash map from account ID to current balance is enough for this sub-problem.
  2. Treat amount 0 like a normal operation; it still succeeds if the account exists.

Part 3: Pending Transfers and Acceptance

Build a banking engine with pending transfers. A successful transfer from `src` to `dst` immediately debits `src` and creates a pending transfer with a unique integer ID starting from 1. The destination does not receive the money until `accept` is called with the correct destination account and transfer ID. A wrong acceptance attempt must fail but must not destroy the pending transfer. For convenience, this sub-problem also includes `create`, `deposit`, and `balance` operations.

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 result

Time complexity: O(n) average time. Space complexity: O(a + p), where a is the number of accounts and p is the number of pending transfers.

Hints

  1. Store current balances separately from pending transfers.
  2. A transfer should reduce the source balance immediately, even before acceptance.

Part 4: Top Activity at an Exact Timestamp

You are given completed banking records and independent queries. For a timestamp `t`, an account's activity is the sum of absolute amounts of all operations that occur exactly at `t` for that account. In this problem: `deposit` and `pay` each add their amount to the named account's activity at `t`; `accepted_transfer` adds its amount to both the source and the destination at `t`; `create` adds no activity; `merge_away(id, t)` makes `id` ineligible to appear in `top_activity` for timestamp `t` or any later timestamp. A later `create` of the same ID starts a new lifetime. For each query `(t, k)`, return up to `k` active account IDs with positive activity at exactly `t`, ordered by descending activity and then lexicographically by ID.

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 answer

Time complexity: O(R + sum over distinct queried timestamps of (a_t log a_t + a_t log l)), where a_t is the number of accounts with activity at timestamp t and l is the number of lifetimes for an ID. Space complexity: O(R).

Hints

  1. Store activity by exact timestamp rather than cumulatively over time.
  2. 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 with account merges. `merge(dst, src, t)` moves the full current balance of `src` into `dst` and removes `src` from the live system starting immediately. After that, operations on `src` are invalid until it is created again later, in which case it starts fresh with balance 0. This problem only asks about the live state observed while processing operations in order; old pre-merge history is conceptually preserved but not queried here.

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]

Explanation: B is absorbed into A, so only A remains live with combined balance.

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]

Explanation: After being merged away, B can be recreated later as a fresh live account.

Input: ([('create', 'A', 1), ('merge', 'A', 'A', 2), ('merge', 'A', 'B', 3), ('balance', 'A', 4)],)

Expected Output: [True, False, False, 0]

Explanation: You cannot merge an account into itself, and you cannot merge a missing source.

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]

Explanation: Once B is merged away, later operations on B are invalid until re-created.

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 result

Time complexity: O(n) average time. Space complexity: O(m), where m is the number of live accounts.

Hints

  1. For this sub-problem, a merge is just a move of current balance plus deletion of the source ID from the live map.
  2. 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

Given a valid chronological event log and independent queries, return the balance of an account as of timestamp `t`. A query sees the state after all events with timestamp `t` have been processed. Events may create accounts, deposit money, pay money out, or merge one account into another. After `merge(dst, src, t)`, the source account is invalid for any timestamp `>= t`, while the destination immediately includes the source balance at timestamp `t`. If the source ID is created again later, it starts a brand-new lifetime with balance 0 and does not change answers for earlier timestamps.

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 answer

Time complexity: Preprocessing is O(E). Each query is O(log r + log u), where r is the number of lifetimes for that ID and u is the number of updates in the chosen lifetime. Total: O(E + Q(log r + log u)). Space complexity: O(E).

Hints

  1. Because an ID can disappear and later come back, model each ID as a sequence of lifetimes.
  2. Within a lifetime, store balance changes by timestamp so you can answer queries with binary search.
Last updated: Apr 20, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Convert Samples into Event Intervals - Anthropic (medium)
  • Convert State Stream to Events - Anthropic (medium)
  • Build a concurrent web crawler - Anthropic (medium)
  • Implement a Parallel Image Processor - Anthropic (medium)
  • Implement a Batch Image Processor - Anthropic (medium)