Stock Real-time Update

来源：Google 

原帖：http://www.meetqun.com/thread-2227-1-1.html

题目：

假设有一个显示一个公司实时估价的网站，不断的会有最新价格进来（每个价格都会贴上一个timestamp，用于标识），要求提供几个方法查询highest price,和latest price。问如何实现。。。同时该系统支持add(timestamp, price)，和update(timestamp, price)。add()即添加新价格，update即根据timestamp来跟新以前的数据。
- 系统不用提供删除操作
- 假设add()进来的price的timestamp都是递增的，即timestamp没有重复。
- follow up，如果add()需求很大，update只是偶尔的操作，该怎么解决。

解答
我用的是max heap+hash来解决highest pric，用一个变量来解决latest price(因为不要求删除)。
follow up
之前的add()和update()操作都是O(logN)，follow up之后，不再维护heap，将add()降低为O(1)的操作，update()变为O(N)的操作。
这道题的关系在于及时更新heap和hash。

代码：


 #include <iostream>  
 #include <string>  
 #include <vector>  
 #include <algorithm>  
 #include <unordered_map>  
 using namespace std;  
 typedef pair<int,int> Pair;//<timestamp, price>  
 class Price {  
 public:  
   Price() { }  
   void Add(int timestamp, int price);  
   void Update(int timestamp, int price);  
   int GetHighest() const { return _data.front().second; };  
   int GetLatest() const { return _latest; };  
 private:  
   unordered_map<int, int> _hash; //key:timestamp, value:index in container.  
   vector<Pair> _data;  
   int _latest;  
 };  
 void Price::Add(int timestamp, int price) {  
   _data.push_back({timestamp, price});  
   int idx = _data.size()-1;  
   int parent = (idx-1)/2;  
   while (parent >= 0 && idx > 0){  
     if (price > _data[parent].second){  
       _hash[_data[parent].first] = idx;  
       swap(_data[parent], _data[idx]);  
       idx = parent;  
       parent = (idx-1)/2;  
     } else {  
       break;  
     }  
   }  
   _hash[timestamp] = idx;  
   _latest = price;  
   // for (auto i : _data) {  
   //   cout << i.first << " " << i.second << " " << _hash[i.first] << endl;  
   // }  
   // cout << endl;  
 }  
 void Price::Update(int timestamp, int price){  
   int idx = _hash[timestamp];  
   int old_price = _data[idx].second;    
   if (price > old_price) {  
     // move up  
     int parent = (idx-1)/2;  
     while (parent >= 0 && idx > 0) {  
       if (price > _data[parent].second) {  
         _hash[_data[parent].first] = idx;  
         swap(_data[idx], _data[parent]);  
         idx = parent;  
         parent = (idx-1)/2;  
       } else {  
         break;  
       }  
     }  
   } else {  
     // move down  
     int j = 2 * idx + 1;  
     if (j < _data.size()-1 && _data[j].second < _data[j+1].second) {  
       ++j;  
     }  
     while (j < _data.size()) {  
       if (price < _data[j].second) {  
         _hash[_data[j].first] = idx;  
         swap(_data[idx], _data[j]);  
         idx = j;  
         j = 2*idx + 1;  
         if (j < _data.size()-1 && _data[j].second < _data[j+1].second) {  
           ++j;  
         }  
       }  
     }  
   }  
   _hash[timestamp] = idx;  
 }  
 int main(){  
   Price P;  
   P.Add(10, 100);  
   P.Add(20, 200);  
   P.Add(30, 300);  
   P.Update(30, 50);  
   cout << P.GetHighest() << endl;  
   cout << P.GetLatest() << endl;  
   return 1;  
 }  

Implement Heap

来源：Bloomberg onsite

原帖：

题目：
Implement a heap structure.

代码：

 #include <vector>  
 #include <iostream>  
 using namespace std;  

 typedef int heap_element;
 /* 堆，默认为最小堆 */  
 int cmp_int(const heap_element& x, const heap_element& y) {  
      heap_element dif = x - y;  
      if (dif > 0) {  
           return 1;  
      } else if (dif < 0) {  
           return -1;  
      } else {  
           return 0;  
      }  
 }  
 typedef int (*compare)(const heap_element& x, const heap_element& y);  
 class heap {  
 public:  
      heap(compare _cmp) {  
           cmp = _cmp;  
      }  
      bool empty() const {  
           return element.size() == 0;   
      }  
      int size() const {  
           return element.size();  
      }  
      void push(const heap_element x) {  
           element.push_back(x);  
           heap_sift_up(element.size() - 1);  
      }  
      void pop() {  
           if (element.size() <= 0) {  
                cerr << "heap is out of space" << endl;  
           }  
           swap(element[0], element[element.size() - 1]);  
           element.pop_back();  
           if (element.size() == 0) {  
                return;  
           }  
           heap_sift_down(0);  
      }  
      heap_element top() const {  
           return element[0];  
      }  
 private:  
      void heap_sift_down(int start) {  
           int i = start, j = 2 * i + 1;  
           while (j < element.size()) {  
                if (j < element.size() - 1 && cmp(element[j], element[j+1]) > 0) {  
                     j++;  
                }  
                if (cmp(element[i], element[j]) < 0) {  
                     break;                      
                } else {  
                     swap(element[i], element[j]);  
                }  
                i = j;  
                j = 2 * i + 1;  
           }  
      }  
      void heap_sift_up(int start) {  
           int j = start, i = (j - 1) / 2;  
           while (j >= 0) {  
                if (cmp(element[i], element[j]) <= 0) {  
                     break;  
                } else {  
                     swap(element[i], element[j]);  
                }  
                j = i;  
                i = (j - 1) / 2;  
           }  
      }  
      vector<heap_element> element;  
      compare cmp;  
 };  
 int main() {  
      int myints[] = {10,20,30,5,15};  
       vector<int> v(myints,myints+sizeof(myints)/sizeof(int));  
       heap minheap(cmp_int);  
       for(int i = 0; i < v.size(); ++i) {  
            minheap.push(v[i]);  
       }  
       cout << minheap.top() << endl;  
       // const vector<int>& elements = minheap.getElements();   
       // for (auto& i : elements) {  
       //      cout << i << " ";  
       // }  
       // cout << endl;  
 }  

Median In Stream

来源：CC150

原帖：http://www.fgdsb.com/2015/01/03/median-in-stream/#more
            http://www.hawstein.com/posts/20.9.html

题目：
Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.

代码：

 class Online {  
 public:  
     void add_number(int n) {  
         if (max_heap.empty() || max_heap.top() > n) {  
             max_heap.push(n);  
             if (max_heap.size() - min_heap.size() > 1) {  
                 int m = max_heap.top();   
                 max_heap.pop();  
                 min_heap.push(m);  
             }  
         } else {  
             min_heap.push(n);  
             if (min_heap.size() > max_heap.size()) {  
                 int m = min_heap.top();  
                 min_heap.pop();  
                 max_heap.push(m);  
             }  
         }  
     }  
   
     int get_median() const {  
         int total = max_heap.size() + min_heap.size();  
         if (total % 2 == 0) {  
             return (max_heap.top() + min_heap.top()) / 2;  
         } else {  
             return max_heap.top();  
         }  
     }  
   
 private:  
     priority_queue<int,vector<int>,less<int>> max_heap;  
     priority_queue<int,vector<int>,great<int>> min_heap;      
 };