# Bank account balance data structure design and code

I'm working on designing a bank account data structure and related operations (1. debit, 2. credit and 3. get balance difference).

1. Debit means withdraw some money from an account, at a certain timestamp
2. Credit means deposit some money to an account, at a certain timestamp
3. Get balance means getting the account balance difference between time A and time B (balance of time B - balance of time A).

Suppose the start balance of the account is zero. Assume transactions happen in a timely order.

My major ideas are:

• Use a hash table to maintain account ID - list of balance. List of balance is represented by a list of tuple, and each tuple has two elements (time_stamp and balance)
• With debit and credit, create a new balance item in a balance list data structure mentioned above
• When calculating the balance difference, try to use binary search to find lower bound of time stamp, then get the balance at that timestamp

Example:

Suppose for a specific account, at time 10, credit 10 USD, at time 20, credit 100 USD, and at time 30 withdraw 20 USD, and at time 40, withdraw 50 USD, and at time 50, credit 20 USD. Then at time 25, balance is 10+100=110, at time 45, balance is 10+100-20-50 = 40, so balance diff between 25 to 45 is 40-110=-70.

Any advice on using the right data structure/algorithm for better performance in terms of algorithm time complexity perspective, any code bugs or code style advice is highly appreciated.

from collections import defaultdict
def debit(account, time_stamp, amount, balance_map):
if len(balance_map[account]) > 0:
balance_map[account].append((time_stamp, balance_map[account][-1][1]-amount))
else:
balance_map[account].append((time_stamp, -amount))
def credit(account, time_stamp, amount, balance_map):
if len(balance_map[account]) > 0:
balance_map[account].append((time_stamp, balance_map[account][-1][1]+amount))
else:
balance_map[account].append((time_stamp, amount))
def get_balance_diff(account, exclusive_start_timestamp, inclusive_end_timestamp, balance_map):
start_balance = (0,0)
end_balance = (0,0)
matched = False
if len(balance_map[account]) != 0:
i = find_lower_bound(balance_map[account], exclusive_start_timestamp)
if i != -1:
start_balance = balance_map[account][i]
if len(balance_map[account]) != 0:
j = find_lower_bound(balance_map[account], inclusive_end_timestamp)
if j != -1:
end_balance = balance_map[account][j]

return end_balance[1] - start_balance[1]

def find_lower_bound(nums, target):
i = 0
j = len(nums) - 1
while i <= j:
mid = i + (j-i)/2
if nums[mid][0] == target:
return mid
elif nums[mid][0] > target:
j = mid - 1
else:
i = mid + 1
return i-1

if __name__ == "__main__":
balance_map = defaultdict(list)
account_id = 1
credit(account_id, 10, 10, balance_map)
credit(account_id, 20, 100, balance_map)
debit(account_id, 30, 20, balance_map)
debit(account_id, 40, 50, balance_map)
credit(account_id, 50, 20, balance_map)
print get_balance_diff(account_id, 25, 45, balance_map)
print get_balance_diff(account_id, 30, 50, balance_map)
print get_balance_diff(account_id, 0, 5, balance_map)
print get_balance_diff(account_id, 0, 60, balance_map)

• Since you have support for timestamp, what is supposed to happen if you get a timestamp that is not the most recent one? Say that you get timestamp 20, then 30, then 25? That transaction has to be considered with which balance, the one at time 20 or the one at time 30? Commented Apr 26, 2017 at 10:41
• Small point: I'd have a newline between your import and first function definition and newlines at the end of all your function definitions. You've done it once or twice, and where you have, the code is much easier to read. Commented May 23, 2023 at 19:24