#2043

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Simple Bank System

Design a simple bank system that processes transactions like withdrawals, deposits, and transfers while managing account balances.

array hash table design simulation

Problem Statement

In this problem, you are tasked with creating a program for a bank that automates processing incoming transactions such as deposits, withdrawals, and transfers. The bank has multiple accounts, each with an initial balance. The accounts are represented by a zero-indexed array, where the i-th element represents the balance of the (i + 1)-th account.

You need to implement the Bank class with three main methods: withdraw, deposit, and transfer. A transaction is valid if the requested operation does not exceed the balance of the involved accounts. The system must ensure that all operations are processed correctly, and if an operation is not feasible, it should return false.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"] [[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]] Output [null, true, true, true, false, false]

Explanation Bank bank = new Bank([10, 100, 20, 50, 30]); bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw$ 10. // Account 3 has $20 -$ 10 = $10. bank.transfer(5, 1, 20); // return true, account 5 has a balance of$ 30, so it is valid to transfer $20. // Account 5 has$ 30 - $20 =$ 10, and account 1 has $10 +$ 20 = $30. bank.deposit(5, 20); // return true, it is valid to deposit$ 20 to account 5. // Account 5 has $10 +$ 20 = $30. bank.transfer(3, 4, 15); // return false, the current balance of account 3 is$ 10, // so it is invalid to transfer $15 from it. bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist.

Constraints

n == balance.length
1 <= n, account, account1, account2 <= 105
0 <= balance[i], money <= 1012
At most 104 calls will be made to each function transfer, deposit, withdraw.

Solution Approach

Array Scanning for Account Balance Management

The first step in the solution involves scanning the balance array to manage account balances. Each transaction checks whether the involved account has sufficient funds or if the account exists. This operation requires careful index manipulation and constant-time validation of account existence.

Hash Table for Faster Lookup

While scanning the balance array works for managing individual balances, using a hash table allows for faster lookups of account balances. This is especially useful when there are many accounts, making transactions quicker and reducing unnecessary scans of the entire array.

Transaction Validation

Each transaction must be validated based on its type. For withdrawals, the account must have enough funds; for transfers, both the source and target accounts must exist and the source must have sufficient funds. Deposits are straightforward and always valid as long as the account exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies based on the approach, but in general, each operation (withdraw, deposit, transfer) requires constant time validation if using an optimized data structure like a hash table. Without such optimizations, array scanning could make these operations slower for larger input sizes. The space complexity depends on how the account data is stored and managed, such as whether you use just an array or include additional data structures like a hash map for efficient lookups.

What Interviewers Usually Probe

Ability to implement efficient data structures like hash tables for optimal performance.
Understanding of time complexity trade-offs between array scanning and hash lookups.
Familiarity with transaction-based design, ensuring correctness of financial operations.

Common Pitfalls or Variants

Common pitfalls

Not checking for account existence before performing operations like transfer or withdraw.
Over-complicating the solution with unnecessary data structures, making it inefficient.
Ignoring edge cases such as invalid account numbers or insufficient funds for operations.

Follow-up variants

Implementing the Bank class with additional transaction types such as loan management.
Scaling the system for a larger number of accounts and transactions while optimizing for time complexity.
Handling concurrency in the bank system where multiple transactions might happen simultaneously.

FAQ

How do you determine if a transaction will fail in the Simple Bank System?

A transaction will fail if the involved account doesn't have enough funds for withdrawal or transfer, or if an account does not exist.

What is the most important data structure for solving the Simple Bank System problem?

The key data structure is the array for storing account balances, with optional hash tables for faster account lookups.

What is the main challenge in implementing the Simple Bank System?

The main challenge is ensuring the transactions are validated correctly and efficiently, especially as the number of accounts and transactions increases.

What optimizations should be made to the Bank class for better performance?

Using hash tables for account lookups instead of array scanning can greatly improve performance when handling many transactions.

How do you handle edge cases like invalid account numbers in the Simple Bank System?

You should check if the account exists before processing any transaction, returning false if the account number is invalid.

terminal

Solution

Solution 1: Simulation

We can use an array $\textit{balance}$ to store the balance of each account. For each operation, we simply perform the required checks and updates according to the problem statement.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Bank:
    def __init__(self, balance: List[int]):
        self.balance = balance
        self.n = len(balance)

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        if account1 > self.n or account2 > self.n or self.balance[account1 - 1] < money:
            return False
        self.balance[account1 - 1] -= money
        self.balance[account2 - 1] += money
        return True

    def deposit(self, account: int, money: int) -> bool:
        if account > self.n:
            return False
        self.balance[account - 1] += money
        return True

    def withdraw(self, account: int, money: int) -> bool:
        if account > self.n or self.balance[account - 1] < money:
            return False
        self.balance[account - 1] -= money
        return True


# Your Bank object will be instantiated and called as such:
# obj = Bank(balance)
# param_1 = obj.transfer(account1,account2,money)
# param_2 = obj.deposit(account,money)
# param_3 = obj.withdraw(account,money)

Continue Practicing

#2502 design memory allocator #2013 detect squares #2080 range frequency queries