Smart Pointer C++

来源：Bloomberg Phone Interview

原帖：http://www.hawstein.com/posts/13.9.html

题目：
Write a smart pointer (smart_ptr) class.

代码：

 #include <iostream>  
 #include <cstdlib>  
 using namespace std;  
   
 template <typename T>  
 class SmartPointer{  
 public:  
   SmartPointer(T* ptr){  
     ref = ptr;  
     ref_count = (unsigned*)malloc(sizeof(unsigned));  
     *ref_count = 1;  
   }  
     
   SmartPointer(SmartPointer<T> &sptr){  
     ref = sptr.ref;  
     ref_count = sptr.ref_count;  
     ++*ref_count;  
   }  
     
   SmartPointer<T>& operator=(SmartPointer<T> &sptr){  
     if (this != &sptr) {  
       if (--*ref_count == 0){  
         clear();  
         cout<<"operator= clear"<<endl;  
       }  
         
       ref = sptr.ref;  
       ref_count = sptr.ref_count;  
       ++*ref_count;  
     }  
     return *this;  
   }  
     
   ~SmartPointer(){  
     if (--*ref_count == 0){  
       clear();  
       cout<<"destructor clear"<<endl;  
     }  
   }  
     
   T getValue() { return *ref; }  
     
 private:  
   void clear(){  
     delete ref;  
     free(ref_count);  
     ref = NULL; // 避免它成为迷途指针  
     ref_count = NULL;  
   }  
     
 protected:    
   T *ref;  
   unsigned *ref_count;  
 };  
   
 int main(){  
   int *ip1 = new int();  
   *ip1 = 11111;  
   int *ip2 = new int();  
   *ip2 = 22222;  
   SmartPointer<int> sp1(ip1), sp2(ip2);  
   SmartPointer<int> spa = sp1;  
   sp2 = spa; // 注释掉它将得到不同输出  
   return 0;  
 }  

约瑟夫环问题

来源：Bloomberg Onsite

原帖：http://blog.csdn.net/wuzhekai1985/article/details/6628491

题目：
最近看bloomberg的面经看到出现过几次约瑟夫环问题。这道题的模拟解法非常直观，更好的解法是观察索引的映射关系采用recursion来解。以前没有仔细思考过这个问题。博客链接给了很好的解释。

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。  稍微简化一下。

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

代码：
1] Brute force solution

 int JosephusProblem(int n, int m) {   
   if (n < 1 || m < 1)   
     return -1;   
    
   list<int> listInt;   
   unsigned i;   
   //初始化链表   
   for (i = 0; i < n; i++)   
     listInt.push_back(i);    
   list<int>::iterator iterCurrent = listInt.begin();   
   while (listInt.size() > 1) {   
     //前进m - 1步   
     for(i = 0; i < m-1; i++) {   
       if(++iterCurrent == listInt.end())   
         iterCurrent = listInt.begin();   
     }   
     //临时保存删除的结点   
     list<int>::iterator iterDel = iterCurrent;   
     if(++iterCurrent == listInt.end())   
       iterCurrent = listInt.begin();   
     //删除结点   
     listInt.erase(iterDel);   
   }  
   return *iterCurrent;   
 }  

2] dp solution

 int JosephusProblem(int n, int m) {   
   if(n < 1 || m < 1)   
     return -1;   
   vector<int> f(n+1,0);   
   for(unsigned i = 2; i <= n; i++)   
     f[i] = (f[i-1] + m) % i;    
   return f[n];   
 }  

Ugly Numbers

来源：cc150, fgdsb

原帖：http://www.hawstein.com/posts/ctci-ch10-math.html
            http://www.fgdsb.com/2015/01/03/ugly-numbers/

题目：
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 150’th ugly number.

cc150上也有相类似的题目，不过prime factors是3,5,7。

代码：

 int uglyNumber(int n) {  
   vector<int> num(n+1);  
   num[0] = 1;  
   int i3 = 0, i5 = 0, i7 = 0;  
   for (int i = 1; i <= n; ++i) {  
     int next = min({num[i3]*3, num[i5]*5, num[i7]*7});  
     num[i] = next;  
     if (next == num[i3]*3) i3++;  
     else if (next == num[i5]*5) i5++;  
     else i7++;  
   }  
   return num[n];  
 }  
   
 int main() {  
   vector<int> ugly = {1,3,5,7,9,15,21,25,27,35,45,49,63};  
   int k = 5;  
   cout << uglyNumber(k) << endl;  
   return 0;  
 }  

Singleton

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/singleton/

题目：
Singleton is a most widely used design pattern. If a class has and only has one instance at every moment, we call this design as singleton. For example, for class Mouse (not a animal mouse), we should design it in singleton.
You job is to implement a getInstance method for given class, return the same instance of this class every time you call this method.

Have you met this question in a real interview? Yes
Example
In Java:
A a = A.getInstance();
A b = A.getInstance();
a should equal to b.

Challenge
If we call getInstance concurrently, can you make sure your code could run correctly?

代码：

 class Solution {  
 public:  
   /**  
    * @return: The same instance of this class every time  
    */  
   static Solution* getInstance() {  
     // write your code here  
     if (obj == NULL) {  
       obj = new Solution();  
     }  
     return obj;  
   }  
 private:  
   Solution() {}  
   static Solution* obj;  
 };  
 Solution* Solution::obj = NULL;  

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

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

Implement Hash

来源：Bloomberg面试题

原帖：http://www.cnblogs.com/xiekeli/archive/2012/01/13/2321207.html
            http://www.cnblogs.com/xiekeli/archive/2012/01/16/2323391.html

题目：
Hash表的简单实现可以作为一个好的练习和理解hash结构。使用拉链法实现hash。

代码：

 struct Node {  
   string key;  
   string val;  
   Node* next;  
   Node() {};  
   Node(string k, string v) : key(k), val(v) {}  
 };  
   
 const int HASHSIZE = 10001; // Hashsize; bucket size  
 const int CAPACITY = 1205; // 哈希能够装载最大的容量，一定大于最大元素个数, capacity; < hashsize;  
   
 class Hash {  
 public:  
   Hash() : node(CAPACITY), table(HASHSIZE,NULL), size(0) {}  
   
   bool insert(string k, string v) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return false;  
       cur = cur->next;  
     }  
     node[size] = Node(k,v);  
     node[size].next = table[code];  
     table[code] = &node[size++];  
     return true;  
   }  
   
   bool find(string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return true;  
       cur = cur->next;  
     }  
     return false;  
   }  
   
   const string& operator[](string k) const {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
   string& operator[](string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
 private:  
   int hashcode(const string& s) const {  
     unsigned int hash = 0;  
     for (auto i : s) {  
       hash = hash * + i;  
     }  
     return (hash & 0x7FFFFFFF) % HASHSIZE;  
   }  
   
   static const int seed = 131;   
   int size;  
   vector<Node> node;  
   vector<Node*> table;  
 };  
   
   
 int main() {  
   Hash hash;  
   hash.insert("tiger", "1");  
   hash.insert("monkey", "2");  
   hash.insert("cat", "3");  
   
   if (hash.find("tiger")) {  
     cout << "find the animal" << endl;  
   } else {  
     cout << "not find the animal" << endl;  
   }  
     
   cout << hash["tiger"] << endl;  
   return 0;  
 }  

Task Schedule

来源：itint5

原帖：http://www.itint5.com/oj/#10

题目：
有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
Solution: topological sorting
Refer to http://www.geeksforgeeks.org/topological-sorting/

代码：

 /*  
  * deps[id]表示任务id所依赖的任务  
  * 如果存在合法的任务完成序列，返回true，否则返回false  
  * 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）  
    2->1; 3->1  
    4->3  
    拓扑排序方法如下:  
    (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.  
    (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.  
    (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.  
  */  
   
 typedef int JobID;  
 // BFS  
 // deps: <key, node(-->key) INDEGREE>  
 // rmap: <key, node(<--key) OUTDEGREE>  
 bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n, vector<JobID> &result) {  
   vector<JobID> indegree(n+1, 0); // 计算图形入度  
   map<JobID, vector<JobID>> rmap; //   
   for (auto it = deps.begin(); it != deps.end(); it++) {  
     indegree[it->first] = it->second.size();  
     for (int i = 0; i < it->second.size(); i++) {  
       rmap[it->second[i]].push_back(it->first);  
     }  
   }  
   stack<JobID> s;  
   for (int i = 1; i <= n; i++) {  
     if(indegree[i] == 0) {  
       s.push(i);  
     }  
   }  
   for (int i = 0; i < n; i++) {  
     if (s.empty()) return false;  
     JobID id = s.top(); s.pop();  
     result[i] = id;  
     for (int j = 0; j < rmap[id].size(); j++) {  
       indegree[rmap[id][j]]--;  
       if(indegree[rmap[id][j]] == 0) {  
         s.push(rmap[id][j]);  
       }  
     }  
   }  
   return true;  
 }  

Longest Common Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
                 = MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]
intialize: f[i][0] = 0
               f[0][j] = 0
answer: f[a.length()][b.length()]

代码：

 int longestCommonSubsequence(string s1, string s2) {  
   int M = s1.size(), N = s2.size();  
   int dp[M + 1][N + 1] = {0};  
   //memset(dp, 0, sizeof(dp));  
   for (int i = 0; i <= M; ++i) {  
     dp[i][0] = 0;  
   }  
     
   for (int j = 0; j <= N; ++j) {  
     dp[0][j] = 0;  
   }  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
       }  
     }  
   }  
   return dp[M][N];  
 }  

Coin Change

来源：g4g, Facebook Onsite

原帖：http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

题目：

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

代码：

 #include <iostream>  
 #include <string>  
 #include <vector>  
 using namespace std;  
   
 int changeCoins(int m, vector<int>& amount, int idx) {  
   if (idx == 0) return m % amount[idx] == 0 ? 1 : 0;  
   int count = 0;  
   for (int i = 0; i * amount[idx] <= m; ++i) {  
     count += changeCoins(m - i * amount[idx], amount, idx - 1);  
   }  
   return count;  
 }  
   
 vector<int> amount = {2, 3, 5};  
 int main() {  
   int m = 7;  
   int idx = amount.size();  
   cout << changeCoins(m, amount, idx-1);  
   return 0;  
 }  

二维dp

 int count( int S[], int m, int n )  
 {  
   int i, j, x, y;  
    
   // We need n+1 rows as the table is consturcted in bottom up manner using   
   // the base case 0 value case (n = 0)  
   int table[n+1][m];  
     
   // Fill the enteries for 0 value case (n = 0)  
   for (i=0; i<m; i++)  
     table[0][i] = 1;  
    
   // Fill rest of the table enteries in bottom up manner   
   for (i = 1; i < n+1; i++)  
   {  
     for (j = 0; j < m; j++)  
     {  
       // Count of solutions including S[j]  
       x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;  
    
       // Count of solutions excluding S[j]  
       y = (j >= 1)? table[i][j-1]: 0;  
    
       // total count  
       table[i][j] = x + y;  
     }  
   }  
   return table[n][m-1];  
 }  
    

Longest Common Substring

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS‘的长度 (一定以第i个和第j个结尾的LCS’)
function: f[i][j]  = f[i-1][j-1] + 1 // a[i] == b[j]
                  = 0 // a[i] != b[j]
intialize: f[i][0] = 0
            f[0][j] = 0
answer: MAX(f[0..a.length()][0..b.length()]

代码：

 int longestCommonSubstring(string s1, string s2) {  
   int M = s1.size(), N = s2.size();   
   vector<vector<int> > dp(M, vector<int>(N,0));  
   for (int i = 0; i <= M; ++i)  
     dp[i][0] = 0;  
   for (int j = 0; j <= N; ++j)  
     dp[0][j] = 0;  
   int maximum = 0;  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = 0;  
       }  
       maximum = max(maximum, dp[i][j]);  
     }  
   }  
   return maximum;  
 }  

Longest Increasing Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
Longest Increasing Subsequence
1 1000 2 3 4
10 11 12 1 2 3 4 13

代码：

 int longestIncreasingSubsequence(const vector<int> &nums) {  
   vector<int> dp(nums.size(), 0);  
   dp[0] = 1;  
   unordered_map<int, vector<int> > map;  
   map[0] = {nums[0]};  
   for (int i = 1; i < nums.size(); ++i) {  
     for (int j = 0; j < i; ++j) {  
       if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {  
         map[i] = move(map[j]);  
         map[i].push_back(nums[i]);  
         dp[i] = max(dp[i], dp[j] + 1);  
       }  
     }  
   }  
   for (auto i : map[nums.size()-1]) cout << i << " ";  
   cout << endl;   
   return dp[nums.size() - 1];  
 }  
   
 int main() {  
   vector<int> nums = {1,2,4,3,2,7,8,9};  
   longestIncreasingSubsequence(nums);  
   return 0;  
 }  

Longest Increasing Box

来源：cc150, itint5

原帖：http://www.itint5.com/oj/#34

题目：
有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。样例：
有7个积木boxes:
 [(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木，从上到下分别为：
 (56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。

题目来源：CRACKING THE CODING INTERVIEW 9.7
Solution: 先按照vol进行排序，题目就变成了根据weight寻找最长严格递增子序列。

代码：

 /*积木的定义(请不要在代码中定义该结构)  
 struct Box {  
  int vol, weight;  
 };*/  
    
 int mycompare(const Box& a, const Box& b) {  
   if (a.vol == b.vol)  
     return a.weight < b.weight;  
   return a.vol < b.vol;  
 }  
   
 int maxBoxes(vector<Box> &boxes) {  
   int N = boxes.size();  
   if (N == 0) return 0;  
   sort(boxes.begin(), boxes.end(), mycompare);  
   vector<int> dp(N, 0);  
   int res = 1;  
   for (int i = 0; i < N; ++i) {  
     dp[i] = 1;  
     for (int j = 0; j < i; ++j)  
       if (boxes[i].vol > boxes[j].vol && boxes[i].weight > boxes[j].weight)  
         dp[i] = max(dp[i], dp[j] + 1);  
     res = max(res, dp[i]);  
   }  
   return res;  
 }  

Binary Search

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/binary-search/

题目：
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example: If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

代码：

 class Solution {  
 public:  
   /**  
    * @param nums: The integer array.  
    * @param target: Target number to find.  
    * @return: The first position of target. Position starts from 0.   
    */  
   int binarySearch(vector<int> &array, int target) {  
     // write your code here  
     if (array.empty()) return -1;  
     int start = 0, end = array.size()-1;  
     while (start + 1 < end) {  
       int mid = start + (end-start) / 2;  
       if (array[mid] >= target) {  
         end = mid;  
       } else {  
         start = mid;  
       }  
     }  
     if (array[start] == target) return start;  
     if (array[end] == target) return end;  
     return -1;  
   }  
 };  

Find First Bad Version

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/first-bad-version/

题目：
The code base version is an integer and start from 0 to n. One day, someone commit a bad version in the code case,  so it caused itself and the following versions are all failed in the unit tests. You can determine whether a version is bad by the following interface: boolean isBadVersion(int version);
Find the first bad version.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
   
 void find_k_largest_in_BST_helper(TreeNode* root, int k, vector<int> &k_elements) {  
   if (!root || k_element.size() == k) {  
     return;  
   }  
   // Perform reverse inorder traversal  
   if (root && k_elements.size() < k) {  
     find_k_largest_in_BST_helper(root->right, k, k_elements);  
     if (k_elements.size() < k) {  
       k_elements.push_back(root->val);  
       find_k_largest_in_BST_helper(root->left, k, k_elements);  
     }  
   }  
 }  
   
 vector<int> find_k_largest_in_BST(TreeNode* root, int k) {  
   vector<int> k_elements;  
   find_k_largest_in_BST_helper(root, k , k_elements);  
   return k_elements;  
 }  

Find K Largest Elements in BST

来源：EPI

原帖：EPI 11.11. pg. 312.

题目：
Given the root of a BST and an integer k, design a function that finds the k largest elements in this BST. For example, if the input to your function is the BST in Figure 11.1 on Page 87 and k = 3, your function should return <53, 47, 43>.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
   
 void find_k_largest_in_BST_helper(TreeNode* root, int k, vector<int> &k_elements) {  
   if (!root || k_element.size() == k) {  
     return;  
   }  
   // Perform reverse inorder traversal  
   if (root && k_elements.size() < k) {  
     find_k_largest_in_BST_helper(root->right, k, k_elements);  
     if (k_elements.size() < k) {  
       k_elements.push_back(root->val);  
       find_k_largest_in_BST_helper(root->left, k, k_elements);  
     }  
   }  
 }  
   
 vector<int> find_k_largest_in_BST(TreeNode* root, int k) {  
   vector<int> k_elements;  
   find_k_largest_in_BST_helper(root, k , k_elements);  
   return k_elements;  
 }  

Serialize & Deserialize A Tree

来源：EPI, Facebook Interview

原帖：http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

题目：
A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back? For example,
         1
      /    \
     2      3
      \     /  
       4   5  
      /  \
     6    7

[Thoughts]
一个比较简单直接的做法是，通过前序遍历来做，把所有空节点当做“#”来标示。那么这棵树可以表示为
             1
          /     \
         2        3
       /   \     /   \
     #      4    5     #
          /   \
         6     7
        /  \  /  \
       #   # #    #
那么前序遍历的结果就是： {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下：
参考 http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

代码：

 // Tree serialize   
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void serialize(TreeNode* root, vector<char> &result) {  
   if (root == NULL) {  
     result.push_back('#'); // 表示终结结点  
     return;  
   }  
   result.push_back(root->val + '0');  
   serialize(root->left, result);  
   serialize(root->right, result);  
 }  
   
 // de-serialize  
 TreeNode* deserialize(const vector<char> &num, int &index) {  
   if (index >= num.size()) {  
    return NULL;  
   }   
   if (num[index] == '#') {  
     index++;  
     return NULL;  
   }  
   TreeNode *root = new TreeNode(num[index] -'0');  
   index++;  
   root->left = Deserialize(num, index);  
   root->right = Deserialize(num, index);  
   return root;  
 }  
   
 int main() {  
   vector<char> numbers = {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'};  
   int index = 0;  
   TreeNode* root = deserialize(number, index);  
   vector<char> res;  
   serialize(root, res);  
   return 0;  
 }  

Deserialize Tree的stack解法
EPI 6.8. pg. 236.
Reconstructing A Binary Tree From A Preorder Traversal With Marker. Design an O(n) time algorithm for reconstructing a binary tree from a preorder visit sequence that uses null to mark empty children. How would you modify your reconstruction algorithm if the sequence corresponded to a postorder or inorder walk.

代码：

 #define null 0;  
 TreeNode* reconstruct_preorder(const vector<int>& preorder) {  
   stack<TreeNode*> s;  
   // traversal back to forth  
   for (auto it = preorder.crbegin(); it != preorder.crend(); ++it) {  
     if (!(*it)) {  
       s.push(NULL);  
     } else {  
       TreeNode* l = s.top(); s.pop();  
       TreeNode* r = s.top(); s.pop();  
       TreeNode* root = new TreeNode(*it);  
       root->left = l;  
       root->right = r;  
       s.push(root);  
     }  
   }   
   return s.top();  
 }  

K Balanced Tree

来源：EPI

原帖：EPI 6.2. pg. 230

题目：
Define a node in a binary tree to be k-balanced if the difference in the number of nodes in its left and right subtrees is no more than k. Design an algorithm that takes as input a binary tree and positive
integer k, and returns a node u in the binary tree such that u is not k-balanced, but all of u's descendants are k-balanced. If no such node exists, return null. For example, when applied to the binary tree in Figure 6.1 on Page 55, your algorithm should return Node J if k = 3.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 pair<TreeNode*, int> find_non_k_balanced_node_helper(TreeNode* root, int k) {  
   // Empty tree  
   if (!root) {   
     return {NULL, 0};  
   }  
   // Early return if left subtree is not k-balanced  
   auto L = find_non_k_balanced_node_helper(root->left, k);  
   if (L.first) {  
     return L;  
   }  
   // Early return if right subtree is not k-balanced  
   auto R = find_non_k_balanced_node_helper(root->right, k);  
   if (R.first) {  
     return R;  
   }  
   int node_num = L.second + R.second + 1; // #nodes in n  
   if (abs(L.second - R .second) > k) {  
     return {root, node_num};  
   }  
   return {NULL, node_num};  
 }  
   
 TreeNode* find_non_k_balanced_node(TreeNode* root, int k) {  
   return find_non_k_balanced_node_helper(root, k).first;  
 }