Bank System , C++ (gcc)

Language: Layout:

/*Bank System
 Design一个bank system, 要实现一个
 - deposite(id, timestamp, amount)，
 - withdraw(id, timestamp, amount)，
 - check(id) --> return int;
 - balance(id, start, end); 
 另外还要实现一个balance的function，这个function跟地里的面经不太一样，要求在logn的时间复杂度内完成;
 给的参数是ID， startTime, endTime, 但是要注意startTime是不包含在内的。
 比如说给你一个startTime 0, 这个时间点下一个时间是10的话，
 你算balance的时间段应该是从10开始，而不是从0开始。
 另外如果startTime是负数的话，那么startTime就从0开始算；这题之前在面经上看到过，
 看到的做法是用一个map来记录timestamp与amount的之间的对应关系，
 但是这样有一个问题便是hashmap中的元素是无序的，所以如果你直接用hashmap的话，
 你得事先排序，这样时间复杂度就不是log级别了。因为准备的时间有效，当时看面经的时候没有考虑到这点，
 其实这里应该另外用一个Map<id, List<timestamp>>来存属于那个用户的时间线，
 这里suppose用户交易的时间是顺序的（跟面试官确认下），所以这样我们存的list就是有序的，就不需要额外的排序了，
 直接用binary search就好了；写到后面发现了这个问题，马上改code，但还是没来得及，没写完。。。哎，还是准备不到位了；
*/

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Bank {
    map<int, int> acc; // accounts balance;
    map<int, vector<pair<long, int>>> history; // vector<p<time, acc-balance>> 
public:
    bool deposit(int id, long time, int money){ 
        if(acc.count(id) == 0) {
            //return 0;
            acc[id] = 0; 
        }
            
        if(money < 0) return false;
        acc[id] += money;
        history[id].push_back({time, acc[id]});  //
        return true;
    
    };
    bool withdraw(int id, long time, int money){
        if(acc.count(id) == 0) return 0; 
        if(money > acc[id]) return false;
        if(money < 0) return false;
        acc[id] -= money;
        history[id].push_back({time, acc[id]});  //
        return true;
    }
    
    int check(int id){ // check balance 
        if(acc.count(id) == 0) return  -1;
        return acc[id];
    }
    
    vector<pair<long,int>> balance(int id, long start, long end){
        vector<pair<long,int>> res; 
        if(history.count(id)==0 || acc.count(id)==0) return res;
        // map start -> idx of vector 
        vector<pair<long, int>> data = history[id];
        int idx = find(data, start);
        int idy = find(data, end);
         for(int i=idx; i<=idy; i++)
             res.push_back(data[i]);
        cout << "idx="<< idx <<endl;
        cout << "idy=" << idy << endl;
        return res;
    }
private:
    int find( vector<pair<long,int>>& data, long t){
        if(t <=data[0].first) return 0; 
        int n = (int)data.size();
        if(t >=data[n-1].first) return n-1; 
        
        for(int i=0; i<(int) data.size(); i++){
            if(data[i].first>= t)
                return i;
        }
    
        // binary search 
        int left =0, right = n-1;
        while(left < right){
            int m = (left+right)/2;
            if(data[m].first <= t) 
                left = m +1;
            else
                right = m;
        }
        return right; 
    }
 
};
int main() {
    Bank b; 
    int id = 1; 
    b.deposit(id, 0, 100);
    b.deposit(id, 1, 100); 
    b.deposit(id, 2, 100); 
    
    cout << "id = " << id << " : balance = " << b.check(id) << endl;
    b.balance(id, 0, 2); 
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.83 sec, absolute running time: 0.08 sec, cpu time: 0.02 sec, memory peak: 3 Mb, absolute service time: 0,91 sec