211 Add and Search Word - Data structure design

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

217 Contains Duplicate

来源：Leetcode

原帖：https://leetcode.com/problems/contains-duplicate/

题目：
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

代码：

 class Solution {  
 public:  
   bool containsDuplicate(vector<int>& nums) {  
     unordered_set<int> _set;  
     for (auto i : nums) {  
       if (_set.count(i)) return true;  
       _set.insert(i);  
     }  
     return false;  
   }  
 };  

约瑟夫环问题

来源：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];   
 }  

160 Intersection of Two Linked Lists

来源：Leetcode

原帖：https://leetcode.com/problems/intersection-of-two-linked-lists/

题目：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
 A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗          
 B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

代码：

 class Solution {  
 public:  
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
     ListNode *p1 = headA, *p2 = headB;  
     if (!p1 || !p2) return NULL;  
     while (p1 && p2 && p1 != p2) {  
       p1 = p1->next;  
       p2 = p2->next;  
       if (p1 == p2) return p1;  
       if (!p1) p1 = headB;  
       if (!p2) p2 = headA;  
     }  
     return p1;  
   }  
 };  

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;