1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – ChatterOne Apr 26 '17 at 10:41
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Thanks RChat, good points and vote up. If I just use for small scale, in terms of algorithm time complexity wise, do you have any suggestions for improvements? Currently, I am using binary search. \$\endgroup\$ – Lin Ma Apr 28 '17 at 16:38
  • \$\begingroup\$ Yeah, that is also fine. \$\endgroup\$ – RChat Apr 29 '17 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.