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

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

Search 2D Matrix II

来源：CC150

原帖：CC150 9.6

题目：
有一个n*m的2维矩阵matrix，矩阵每一行，每一列都是有序的（升序）。判断矩阵中是否存在元素target。提示：时间复杂度O(n+m)，空间复杂度O(1)。
Solution: 从右上角或者左下角开始进行。

代码：

 bool exists(vector<vector<int> > &matrix, int target) {  
   if(matrix.empty()) {  
     return false;  
   }  
   int M = matrix.size(), N = matrix[0].size();  
   int i = 0, j = N - 1;  
   while (i < M && j >= 0) {  
     if (matrix[i][j] == target) {  
       return true;  
     } else if (matrix[i][j] < target) {  
       i++;  
     } else {  
       j--;  
     }  
   }  
   return false;  
 }  

Add Without Add Operator

来源：cc150

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

题目：
Implement add without add operator ('+'). Bit operation.

代码：

 int add(int a, int b) {  
   do {  
     int n1 = a ^ b;  
     int n2 = (a & b) << 1;  
     a = n1;   
     b = n2;  
   } while (b != 0);  
   return a;  
 }