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

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

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

170 2Sum III - Data structure design

来源：Leetcode

原帖：https://leetcode.com/problems/two-sum-iii-data-structure-design/

题目：
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

代码：

 class Solution {  
 public:  
     int threeSumClosest(vector<int> &num, int target) {  
         int res = INT_MAX;  
         int N = num.size();  
         sort(num.begin(), num.end());  
         for (int i = 0; i < N - 2; ++i) {  
             int l = i + 1, r = N - 1;  
             while (l < r) {  
                 int threesum = num[i] + num[l] + num[r];  
                 if (threesum == target) {  
                     return target;  
                 } else if (threesum < target) {  
                     l++;  
                 } else {  
                     r--;  
                 }  
                 if (res == INT_MAX || abs(threesum - target) < abs(res - target)) { // trick: overflow  
                     res = threesum;  
                 }  
             }  
         }  
         return res;  
     }  
 };  

Runner & Monitor Design

来源：Bloomberg onsite

原帖：在bb的面经出现多次，以后考察时补上相应链接。

题目：
我面bb onsite 的时候遇到的题目。题目是在跑道上存在不同位置的monitor,监控runner的位置。提供当一个运动员路过一个monitor的时候，update运动员的位置void update(runnerID, monitorID)；查询运动员的位置(就是monitor的位置)int getMonitorID(runnerID)；查询排名前k的运动员的函数vector<int> getTopK(k).
方法：使用hash + vector<list<>>; 不同的monitor可以看做一个bucket

代码：

  // hashmap stores <runnerID, list<Data>::iterator>  
  // update: 使用hash变更链表，插入新的位置  
  // topk: 遍历数组  
  class Record {  
  public:  
      Record(int num_p, int num_m) : data(num_m) {  
          for (int i = 0; i < num_p; ++i) {  
              data[0].push_front(Data(i,0));  
              map[i] = data[0].begin();  
          }  
      }  
    
      int getMonitorID(int personID) const {  
          return map[personID]->mID;  
      }  
    
      void update(int personID, int monitorID) {  
          int pre_mID = map[personID]->mID;  
          data[monitorID].splice(data[monitorID].begin(), data[pre_mID], map[personID]);  
      }  
    
      // return top-k person ID from data;  
      vector<int> getTopK(int k) {  
          vector<int> res;  
          for (int i = data.size()-1; i >= 0 && res.size() < k; --i) {  
          if (data[i].empty()) continue;  
          for (auto it = data[i].rbegin(); it != data[i].rend() && res.size() < k; ++it) {  
              res.push_back(it->pID);  
          }  
      }  
          return res;  
      }  
    
  private:  
      struct Data {  
          int pID;  
          int mID;  
          Data(int p, int m) : pID(p), mID(m) {}  
      };  
      vector<list<Data> > data;  
      unordered_map<int, list<Data>::iterator> map;   
  };  
    
  int main() {  
      int num_p = 10; // 0, 1, 2, ..., 9  
      int num_m = 3; // 0, 1, 2.  
    
      Record r(num_p, num_m);  
      cout << r.getMonitorID(1) << endl;  
      r.update(1, 1);  
      r.update(2, 1);  
      r.update(6, 1);  
      r.update(2, 2);  
      r.update(7, 1);  
      vector res = r.getTopK(3);   
      for (auto i : res) cout << i << " ";  
          cout << endl;  
          return 0;  
      }  
  }  

LRU Cache

来源：Leetcode, Facebook Onsite

原帖：http://oj.leetcode.com/problems/lru-cache/

题目：
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
it should invalidate the least recently used item before inserting a new item.

思考：
Hashmap + linkedlist. 03/12/2015 FB的onsite的时候遇到了这道题，题目发生了变化，但本质就是LRU。主要要考虑get和set的时候lru的性质。

代码：

 class LRUCache{  
 public:  
     LRUCache(int capacity) {  
         size = capacity;    
     }  
   
     int get(int key) {  
         if(!kmap.count(key)) return -1;  
         cachelist.splice(cachelist.begin(), cachelist, kmap[key]);  
         return kmap[key]->value;  
     }  
   
     void set(int key, int value) {  
         if(kmap.count(key)){  
             cachelist.splice(cachelist.begin(), cachelist, kmap[key]);  
             kmap[key]->value = value;  
         } else {  
             if(cachelist.size() == size){  
                 kmap.erase(cachelist.back().key);  
                 cachelist.pop_back();  
             }  
             cachelist.push_front(data(key, value));  
             kmap[key] = cachelist.begin();  
         }  
     }  
 private:  
     struct data{  
         int key;  
         int value;  
         data(int k, int v) : key(k), value(v) {}  
     };  
   
     int size;  
     list<data> cachelist;  
     unordered_map<int, list<data>::iterator> kmap;  
 };