Simple Bank System

Medium

Google

4 views

Topics:

Arrays

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)<sup>th</sup> account having an initial balance of balance[i]. Implement the Bank class with the following methods:

Bank(long[] balance): Initializes the object with the 0-indexed integer array balance.
boolean transfer(int account1, int account2, long money): Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
boolean deposit(int account, long money): Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
boolean withdraw(int account, long money): Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.

A transaction is valid if:

The given account number(s) are between 1 and n, and
The amount of money withdrawn or transferred from is less than or equal to the balance of the account.

For example:

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.

Consider edge cases like invalid account numbers, insufficient balance, and potential overflow issues. How would you implement this Bank class efficiently?

Simple Bank System

Medium

Google

4 views

Topics:

Arrays

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)<sup>th</sup> account having an initial balance of balance[i]. Implement the Bank class with the following methods:

Bank(long[] balance): Initializes the object with the 0-indexed integer array balance.
boolean transfer(int account1, int account2, long money): Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
boolean deposit(int account, long money): Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
boolean withdraw(int account, long money): Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.

A transaction is valid if:

The given account number(s) are between 1 and n, and
The amount of money withdrawn or transferred from is less than or equal to the balance of the account.

For example:

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.

Consider edge cases like invalid account numbers, insufficient balance, and potential overflow issues. How would you implement this Bank class efficiently?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `account` and `money`? Can `money` be negative for deposits, withdrawals, or transfers?
What is the maximum number of accounts that the `balance` array can contain? Should I be concerned about integer overflow when performing transactions?
If a withdrawal or transfer would result in a negative balance for an account, should the transaction fail, or is there different behavior required?
Are the account numbers 1-indexed as suggested in the description (i.e., `balance[i]` represents account `i+1`) or 0-indexed (i.e., `balance[i]` represents account `i`)?
What should I return if the `account` number is out of bounds (e.g., less than 1 or greater than the size of the `balance` array)?

Brute Force Solution

Approach

The brute force approach to managing bank accounts involves directly implementing each requested transaction by meticulously checking all accounts. We examine each account individually to determine if the transaction is possible, updating balances as needed. This method avoids any clever shortcuts or optimized data structures.

Here's how the algorithm would work step-by-step:

When a customer asks to transfer money from one account to another, first confirm if both accounts exist.
Next, verify if the account sending the money has enough funds to cover the transfer amount.
If both conditions are met, subtract the money from the sender's account.
Then, add the same amount of money to the receiver's account.
If either condition is not met at any point, reject the transaction and leave the accounts unchanged.
When a customer asks to deposit money into their account, locate the account and add the money to the balance.
When a customer asks to withdraw money from their account, first verify if the account exists and if there are sufficient funds.
If both conditions are met, subtract the money from the account balance. Otherwise, reject the transaction.

Code Implementation

class Bank:
    def __init__(self, balance):
        self.account_balances = balance

    def transfer(self, account1, account2, money):
        account1 -= 1
        account2 -= 1

        # Validate both accounts exist
        if account1 < 0 or account1 >= len(self.account_balances) or \
           account2 < 0 or account2 >= len(self.account_balances):
            return False

        # Check if the first account has sufficient balance
        if self.account_balances[account1] < money:
            return False

        self.account_balances[account1] -= money
        self.account_balances[account2] += money
        return True

    def deposit(self, account, money):
        account -= 1

        # Check if the account exists
        if account < 0 or account >= len(self.account_balances):
            return False

        self.account_balances[account] += money
        return True

    def withdraw(self, account, money):
        account -= 1

        # Need to validate account exists
        if account < 0 or account >= len(self.account_balances):
            return False

        # Check to see if there is enough money to withdraw
        if self.account_balances[account] < money:
            return False

        self.account_balances[account] -= money
        return True

Big(O) Analysis

Time Complexity

O(n) – The brute force approach described involves checking account existence and balances for each transaction. For deposit, withdraw, and transfer operations, we may need to iterate through all accounts to find the target account. In the worst-case scenario, each transaction requires scanning all 'n' accounts. Therefore, the time complexity for each operation is O(n), and since we analyze a single transaction in isolation, the overall time complexity is O(n).

Space Complexity

O(1) – The described brute force approach iterates through the accounts one by one and modifies them directly. No auxiliary data structures like temporary arrays or hash maps are created. The operations involve only a few variables for indices and the amount being transferred, deposited, or withdrawn. Thus, the auxiliary space used remains constant regardless of the number of accounts, N.

Optimal Solution

Approach

We'll represent bank accounts and their balances. We need to quickly access and modify balances while ensuring we don't try to access nonexistent accounts. The key is using an efficient way to store and retrieve account balances.

Here's how the algorithm would work step-by-step:

First, create a way to hold all the account balances together. Think of it as a ledger.
When the system starts, fill the ledger with the starting balance for each account.
For a transaction like a deposit or withdrawal, first check if the account number is valid by seeing if it exists in the ledger.
If the account exists, get its current balance from the ledger.
Apply the transaction, either adding to (deposit) or subtracting from (withdrawal) the balance. But before subtracting, ensure the balance will not become negative.
Update the account's balance in the ledger with the new value.
For a transfer, check that both the sending and receiving accounts exist, and that the sender has enough money.
If all checks pass for a transfer, subtract the amount from the sender and add it to the receiver.
If any check fails at any point, indicate that the transaction cannot be completed.

Code Implementation

class Bank:
    def __init__(self, balance):
        self.account_balances = balance

    def transfer(self, account1, account2, money):
        # Validate both accounts before proceeding.
        if account1 > len(self.account_balances) or \
           account2 > len(self.account_balances):
            return False

        if self.account_balances[account1 - 1] < money:
            return False

        self.account_balances[account1 - 1] -= money
        self.account_balances[account2 - 1] += money
        return True

    def deposit(self, account, money):
        # Check if account exists.
        if account > len(self.account_balances):
            return False

        self.account_balances[account - 1] += money
        return True

    def withdraw(self, account, money):
        # Important to check sufficient funds first
        if account > len(self.account_balances) or \
           self.account_balances[account - 1] < money:
            return False

        self.account_balances[account - 1] -= money
        return True

Big(O) Analysis

Time Complexity

O(1) – The Bank System stores account balances in a data structure (likely an array or hash map) that allows for direct access by account number. Checking if an account exists takes O(1) time. Deposits, withdrawals, and transfers each involve a fixed number of these constant-time operations: checking account existence, retrieving balances, updating balances. Therefore, each of these operations completes in O(1) time regardless of the number of accounts.

Space Complexity

O(N) – The primary auxiliary space usage comes from storing the account balances in a ledger, which in this case is a data structure that holds the balance for each account. If we have N accounts, the ledger will need to store N balance values. Therefore, the space required grows linearly with the number of accounts, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty balance array	Return false immediately, as there are no accounts to operate on.
Account number is zero or negative	Return false, as account numbers should be positive integers within the valid range.
Account number exceeds the size of the balance array	Return false, as the account number is out of bounds.
Withdrawal amount exceeds the account balance	Return false, as the transaction would result in a negative balance.
Deposit or withdrawal amount is negative	Return false, as deposits and withdrawals should be non-negative.
Transfer amount exceeds the sender's account balance	Return false, as the sender does not have sufficient funds.
Transfer to an invalid or non-existent account	Return false if the recipient account number is invalid (out of bounds).
Integer overflow when adding deposit amount or performing transfer calculations	Use long data type to prevent overflow, and add checks to ensure transaction amounts don't exceed maximum representable values.