Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Bank System
/*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; }
run
|
edit
|
history
|
help
0
combine c++ string with dynamically allocated c array of chars through overloaded add operator
derive* -> gcc
Teatime Snack
ONP is working!
stack::emplace for 30-second c++
Gauss v1.1
Print reverese string non repeated chars
A • Potato Sacks
Hello World C++ - minimal
gcc set_terminate