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;      
 };  

Wildcard Matching

来源：Leetcode

原帖：https://oj.leetcode.com/problems/wildcard-matching/

题目：
 Implement wildcard pattern matching with support for '?' and '*'.
 '?' Matches any single character.
 '*' Matches any sequence of characters (including the empty sequence).
 The matching should cover the entire input string (not partial).
 The function prototype should be:
 bool isMatch(const char *s, const char *p)
 Some examples:
 isMatch("aa","a") ? false
 isMatch("aa","aa") ? true
 isMatch("aaa","aa") ? false
 isMatch("aa", "*") ? true
 isMatch("aa", "a*") ? true
 isMatch("ab", "?*") ? true
 isMatch("aab", "c*a*b") ? false

代码：

 class Solution {  
 public:  
   // s does NOT include '?' and '*'. p has '?' and '*'  
   //Version 1: iteration  
   bool isMatch(const char *s, const char *p) {  
     const char *start_s = NULL, *start_p = NULL;  
     while (*s != '\0') {  
       if (*p == '?' || *s == *p) {  
         s++;  
         p++;  
       } else if (*p == '*') {  
         while (*p == '*') p++;  
         if (*p == '\0') return true;  
         start_s = s;  
         start_p = p;  
       } else {  
         if (!start_s) return false;  
         s = ++start_s;  
         p = start_p;  
       }  
     }  
     while (*p == '*') p++;  
     return *s == '\0' && *p == '\0';  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: recursion:   
   // time limit exceed  
   bool isMatch(const char* s, const char* p) {  
     if (*s == '\0') {  
       while(*p && *p == '*') p++;  
       return *p == '\0';  
     }  
     if (*s == *p || *p == '?') {  
       return isMatch(s+1, p+1);  
     } else if (*p == '*') {  
       while (*p == '*') p++;  
       if (*p == '\0') return true;  
       while (*s != '\0') {  
         if (isMatch(s, p)) return true;  
         s++;  
       }  
     }  
     return false;  
   }  
 };  

Regular Expression Matching

来源：Leetcode

原帖：http://oj.leetcode.com/problems/regular-expression-matching/

题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true  zero or more

思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。

代码：

 class Solution {  
 public:  
   bool isMatch(const char *s, const char *p) {  
     if (*p == '\0') return *s == '\0';  
     if (*(p+1) == '*') {  
       if (isMatch(s, p+2)) return true; // match 0  
       while (*s && (*s == *p || *p == '.')) { // match 1,2,...  
         if (isMatch(s+1, p+2)) return true;  
         s++;  
       }  
     } else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s  
         return true;  
     return false;  
   }  
 };  
   
 // dp solution  
 class Solution {  
 public:  
   bool isMatch(const char* s, const char* p) {  
     if (*p == '\0') return *s == '\0';  
     int M = strlen(s), N = strlen(p);  
     vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配  
     dp[0][0] = true;  
     for (int j = 0; j < N; ++j)  
       dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (s[i] == p[j] || p[j] == '.') {  
           dp[i+1][j+1] = dp[i][j];  
         } else if (p[j] == '*') {  
           dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);  
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };  

186 Reverse Words In a String II

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-words-in-a-string-ii/

题目：
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue", return "blue is sky the".
Could you do it in-place without allocating extra space?

代码：

 class Solution {  
 public:  
   // in-place reverse  
   void reverseWords(string &s) {  
     reverse(s.begin(), s.end());  
     int end = 0;  
     for (int i = 0; i < s.size(); ++i) {  
       if (s[i] == ' ') continue;  
       if (end != 0) s[end++] = ' ';  
       int l = i, h = i;  
       while (i != s.size() && s[i] != ' ') {  
         h++; i++;  
       }  
       reverse(s.begin() + l, s.begin() + h);  
       for (int j = l; j < h; ++j) {  
         s[end++] = s[j];  
       }  
     }  
     s.resize(end);    
   }  
 };  

Peek Iterator

来源：一亩三分地

原帖：http://www.fgdsb.com/2015/01/25/peek-iterator/

题目：
写一个PeekIterator，包装一个普通的Iterator，要实现peek()方法，返回当前iterator指向的元素，但是不能移动它。除此之外也要实现has_next()和next()方法。
PeekIterator可以用普通iterator的get_next()来获得，但是要记录下来，下一次调用get_next的时候直接返回上一次peek的即可。

代码：

 class Iterator {  
 public:  
     Iterator(vector<int>& num) : data(move(num)), size(0) {}  
     bool has_next() {return size < data.size();}  
     int get_next() {  
         return data[size++];  
     }  
 private:  
     vector<int> data;  
     int size;  
 };  
   
 class PeekIterator {  
 public:  
     PeekIterator(vector<int>& num) : iter(num) {}  
     bool has_next() {  
         iter.has_next() || !peek.empty();  
     }  
   
     int get_next() {  
         if (!peek.empty()) {  
             int ret = peek.back();  
             peek.pop_back();  
             return ret;  
         }  
         return iter.get_next();  
     }  
   
     int get_peek() {  
         if (!peek.empty()) {  
             return peek.back();  
         }  
         int ret = iter.get_next();  
         peek.push_back(ret);  
         return ret;  
     }  
   
 private:  
     vector<int> peek;  
     Iterator iter;  
 };