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.

#2043

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

简易银行系统

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。请你执行所有有效…

数组哈希表设计模拟

题目描述

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。

请你执行所有 有效的 交易。如果满足下面全部条件，则交易有效：

指定的账户编号在 1 和 n 之间，且
取款或者转账需要的钱的总数 小于或者等于 账户余额。

实现 Bank 类：

Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
boolean transfer(int account1, int account2, long money) 从编号为 account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
boolean deposit(int account, long money) 向编号为 account 的账户存款 money 美元。如果交易成功，返回 true ；否则，返回 false 。
boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。如果交易成功，返回 true ；否则，返回 false 。

示例：

输入：
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
输出：
[null, true, true, true, false, false]

解释：
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // 返回 true ，账户 3 的余额是 $20 ，所以可以取款 $10 。
                         // 账户 3 余额为 $20 - $10 = $10 。
bank.transfer(5, 1, 20); // 返回 true ，账户 5 的余额是 $30 ，所以可以转账 $20 。
                         // 账户 5 的余额为 $30 - $20 = $10 ，账户 1 的余额为 $10 + $20 = $30 。
bank.deposit(5, 20);     // 返回 true ，可以向账户 5 存款 $20 。
                         // 账户 5 的余额为 $10 + $20 = $30 。
bank.transfer(3, 4, 15); // 返回 false ，账户 3 的当前余额是 $10 。
                         // 所以无法转账 $15 。
bank.withdraw(10, 50);   // 返回 false ，交易无效，因为账户 10 并不存在。

提示：

n == balance.length
1 <= n, account, account1, account2 <= 10⁵
0 <= balance[i], money <= 10¹²
transfer, deposit, withdraw 三个函数，每个最多调用 10⁴ 次

lightbulb

解题思路

方法一：模拟

我们可以使用一个数组 $\textit{balance}$ 来存储每个账户的余额。对于每个操作，我们只需要根据题目要求进行相应的判断和更新即可。

对于 $\textit{transfer}$ 操作，我们需要检查账户编号是否合法以及账户余额是否足够，如果满足条件则进行转账操作。

对于 $\textit{deposit}$ 操作，我们只需要检查账户编号是否合法，然后进行存款操作。

对于 $\textit{withdraw}$ 操作，我们需要检查账户编号是否合法以及账户余额是否足够，如果满足条件则进行取款操作。

以上每个操作的时间复杂度均为 $O(1)$ ，因此整体时间复杂度为 $O(q)$ ，其中 $q$ 是操作次数。空间复杂度 $O(1)$ 。

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

31

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

指标

值

时间

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.

空间

Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2502 设计内存分配器 #2013 检测正方形 #2080 区间内查询数字的频率