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).


Debit means withdraw some money from an account, at a certain timestamp
Credit means deposit some money to an account, at a certain timestamp
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]) &gt; 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]) &gt; 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 &lt;= j:
        mid = i + (j-i)/2
        if nums[mid][0] == target:
            return mid
        elif nums[mid][0] &gt; 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)
I think using dictionaries is about right for this small project.

However, the code will not scale well in terms of readability with lists of tuples. You should consider using object oriented approach, and implement some serialization, deserialization methods (for storing the data onto the disk and reading it back). That way you can add more functionalities in a more manageable way.

I don't understand why you allow negative balance!