Sqrt(x)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sqrtx/

题目：
Implement int sqrt(int x). Compute and return the square root of x.

思路：
这道题用binary search搞定。需要注意的是函数签名，在面试中遇到过两种。int sqrt(int); double sqrt(double). 如果输入是int，在进行binary search的时候可能会遇到overflow。 输入是double，需要考虑<1, >1的情况，另外需要考虑double精度问题。

代码：
1] int type input

 class Solution {  
 public:  
     int sqrt(int x) {  
         assert(x >= 0);  
         int l = 0, r = x / 2 + 1;  
         while (l + 1 < r) {  
             // long long mid = l + (r - l) / 2; // overflow problem.   
             // long long sq = mid * mid;  
             // if (sq == x) {  
             //   return mid;  
             // } else if (sq < x) {  
             //   l = mid;  
             // } else {  
             //   r = mid;  
             // }  
   
             int mid = l + (r - l) / 2;  
             int quot = x / mid;  
             if (quot == mid) {  
                 return quot;  
             } else if (quot > mid) {  
                 l = mid;  
             } else {  
                 r = mid;  
             }  
         }  
         if (r * r == x) return r;  
         return l;  
     }  
 };  

2] input is double

 class Solution {  
 public:  
     const double eps = 1.0e-12;  
     // 0 means equal, -1 means smaller, +1 means larger  
     int compare(double a, double b) {  
         if (a == 0) a += eps;  
         if (b == 0) b += eps;  
         double diff = (a - b) / b;  
         return diff > eps ? 1 : diff < -eps ? -1 : 0;  
     };  
   
     double square_root(double x) {  
         // Decide the search range according to x  
         double l, r;  
         if (compare(x, 1.0) < 0) { // x < 1.0  
             l = x; r = 1.0;  
         } else { // x >= 1.0  
             l = 1.0; r = x;  
         }  
         // Keep searching if l < r  
         while (compare(l, r) < 0) {  
             double m = l + 0.5 * (r - l);  
             double square_m = m * m;  
             if (compare(square_m, x) == 0) {  
                 return m;  
             } else if (compare(square_m, x) < 0) {  
                 l = m;  
             } else {  
                 r = m;  
             }  
         }  
         return l;  
     }  
 };  

161 One Edit Distance

来源：Leetcode, Facebook Onsite

原帖：https://leetcode.com/problems/one-edit-distance/

问题：
Given two strings S and T, determine if they are both one edit distance apart.
思路：
fb的高频题了。onsite的时候大脑短路竟然写出了一个bug。首先考虑corner case, 长度相差>=2, 长度相等(s == t), 长度相差1和长度相同但是(s!=t)。这道题有两种思路。I) 第一种思路比较简单，代码也不容易写错。就是同时遍历两个字符串到到第一个不同的地方，然后根据长度判断两个remaining子串是否相等。II) 每一个字符相互比较。当找到第一个不匹配的地方，根据S,T的长度选择i++,j++,还是i++。另外需要最后处理一个corner case. 

代码：1]

 class Solution {   
 public:   
     bool isOneEditDistance(string s, string t) {   
         int M = s.size(), N = t.size();   
         if (s == t) return false;   
         if (abs(M - N) > 1) return false;   
         if (N > M) return isOneEditDistance(t,s);   
         for (int i = 0; i < min(M,N); ++i) {   
             if (s[i] != t[i]) {   
                 return M == N ? s.substr(i+1) == t.substr(i+1) : s.substr(i+1) == t.substr(i);   
             }   
         }   
         return true;   
     }   
 };   

代码：2]

 class Solution {   
 public:   
     bool isOneEditDistance(string s, string t) {   
         int M = s.size(), N = t.size();    
         if (abs(M - N) > 1) return false;   
         if (M < N) return isOneEditDistance(t, s);   
         int count = 0, i = 0, j = 0;   
         while (i < M && j < N) {   
             if (s[i] != t[j]) {   
                 count++;   
                 if (count >= 2) return false;   
                 if (M == N) {   
                     i++; j++;   
                 } else {   
                     i++;   
                 }   
             } else {   
                 i++; j++;   
             }   
         }       
         if (i == M-1) count++;   
         return count == 1;   
     }   
 };  

190 Reverse Bits

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-bits/
            http://articles.leetcode.com/2011/08/reverse-bits.html

题目：
Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?

思路：

[1]. 使用swap trick，就是交换整数中i-th, j-th bit的位置。这个思路比较容易想到。

The XOR swap trick:
Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j), which swaps the i^th bit with the j^th bit. If you still remember how XOR operation works: 0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1. We only need to perform the swap when the i^th bit and the j^th bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both i^th and j^th bits. We could  apply the XOR operation again. By XOR-ing the i^thand j^th bit with 1, both bits are toggled.

代码：

 class Solution {  
 public:  
     void swap(uint32_t& n, int i, int j) {  
         int p_i = ((n >> i) & 1);  
         int p_j = ((n >> j) & 1);  
         if (p_i ^ p_j) {  
             n ^= ((1 << i) | (1 << j));  
         }  
     }  
   
     uint32_t reverseBits(uint32_t n) {  
         int bits = sizeof(n) * 8;  
         for (int i = 0; i < bits/2; i++) {  
             swap(n, i, bits - i - 1);  
         }  
         return n;  
     }  
 };  

[2] 考虑分治法，time complexity O(log(n)).

The divide and conquer approach:Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

      01101001
        /         \
   0110      1001
    /   \         /   \
 01   10   10   01
 /\     /\     /\     /\
0 1  1 0  1 0   0 1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on… Therefore, only a total of log(n) operations are necessary. The below code shows a specific case where n == 32, but it could be easily adapted to larger n‘s as well.

代码：

 class Solution {  
 public:  
     uint32_t reverseBits(uint32_t n) {  
         assert(sizeof(n) == 4);  
         n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1);  
         n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2);  
         n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4);  
         n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8);  
         n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16);  
         return n;  
     }  
 };  

Print a Binary Tree in Vertical Order

来源：Facebook电面

原帖：http://www.mitbbs.com/article_t/JobHunting/32946511.html
            http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

题目：

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

思路：这道题dfs + map (因为需要key的顺序保存，所以使用map).或者bfs + map也可。

代码版本使用了bfs + map， 由于dfs不能保证层的顺序。

代码：

 struct TreeNode {  
      int val;  
      TreeNode* left, *right;  
      TreeNode(int v) : val(v), left(NULL), right(NULL) {};  
 };  
   
 vector<vector<int>> verticalPrintBinaryTree(TreeNode* root) {  
      vector<vector<int>> res;  
      if (!root) return res;  
      map<int, vector<int>> table;  
      queue<pair<TreeNode*, int>> q;  
      q.push({root, 0});  
      table[0].push_back(root->val);  
   
       while (!q.empty()) {  
           auto node = q.front().first;  
           int label = q.front().second;  
           q.pop();  
           if (node->left) {  
                table[label-1].push_back(node->left->val);  
                q.push({node->left, label-1});  
           }  
           if (node->right) {  
                table[label+1].push_back(node->right->val);  
                q.push({node->right, label+1});  
           }  
      }  
   
       for (auto it = table.begin(); it != table.end(); ++it) {  
           res.push_back(it->second);  
      }  
      return res;  
 }  
   
 void print(vector<vector<int>>& num) {  
      for (int i = 0; i < num.size(); ++i) {  
           for (int j = 0; j < num[i].size(); ++j) {  
                cout << num[i][j] << " ";  
           }  
           cout << endl;  
      }  
 }  
   
 int main() {  
   TreeNode *root = new TreeNode(1);  
   root->left = new TreeNode(2);  
   root->right = new TreeNode(3);  
   root->left->left = new TreeNode(4);  
   root->left->right = new TreeNode(5);  
   root->right->left = new TreeNode(6);  
   root->right->right = new TreeNode(7);  
   root->right->left->right = new TreeNode(8);  
   root->right->right->right = new TreeNode(9);  
   cout << "Vertical order traversal is \n";  
   vector<vector<int>> res = verticalPrintBinaryTree(root);  
   print(res);  
   return 0;  
 }  
   

Maximum Rectangle in Histogram

来源：Twitter Phone Interview，Leetcode

原帖：https://leetcode.com/problems/largest-rectangle-in-histogram/

题目：
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

思路：
Twitter first round phone interview。使用stack保存栈内递增序列，原数组需要加入一个最小值-1，保持栈内元素能够完全清空。

代码：

 class Solution {  
 public:  
     //stack keeps increasing/decreasing order numbers.   
     //for example: 2 1 8 9 4 5 3   
     //寻找i左侧比A[i]大的第一个数  
     int largestRectangleArea(vector<int> &height) {  
         if (height.empty()) return 0;  
         stack<int> s;  
         height.push_back(-1); //辅助空间，帮助把栈内所有元素pop  
         int maxRect = 0;  
         int i = 0, size = height.size();  
         while (i < size) {  
             if (s.empty() || height[s.top()] <= height[i]) { // left search  
                 s.push(i++);  
             } else { // right search  
                 int h = height[s.top()]; s.pop(); // stk.top()保存可以作为矩形顶点的最大高度, then s.pop()  
                 int w = s.empty() ? i : i - s.top() - 1; // s.top() is left boundary; i is right boundary  
                 maxRect = max(maxRect, w * h);  
             }  
         }  
         return maxRect;  
     }  
 };  

200 Number of Islands

来源：Leetcode, Google常考题

原帖：https://leetcode.com/problems/number-of-islands/

题目：
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are all surrounded by water.
思路：找到连通域的数目，典型的bfs, dfs题目。

代码：DFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int r, int c) {  
         int M = grid.size(), N = grid[0].size();  
         visited[r][c] = true;  
         for (auto o : offset) {  
             int i = r + o.first, j = c + o.second;  
             if (i < 0 || i >= M || j < 0 || j >= N) continue;  
             if (grid[i][j] == '0' || visited[i][j]) continue;  
             dfs(grid, visited, i, j);  
         }  
     }  
   
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     dfs(grid, visited, i,j);  
                 }  
             }  
         }  
         return count;  
     }  
 };  

代码：BFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     queue<pair<int,int>> q;  
                     visited[i][j] = true;  
                     q.push({i,j});  
                     while (!q.empty()) {  
                         auto neigh = q.front(); q.pop();  
                         for (auto o : offset) {  
                             int r = neigh.first + o.first, c = neigh.second + o.second;  
                             if (r < 0 || r >= M || c < 0 || c >= N) continue;  
                             if (visited[r][c] || grid[r][c] == '0') continue;  
                             visited[r][c] = true;  
                             q.push({r,c});  
                         }  
                     }  
                 }  
             }  
         }  
         return count;  
     }  
 };  

Split BST with Threshold

来源：Google onsite

原帖：来自于一亩三分地或meetqun上的面经

题目：
Given a binary search tree (BST) and a threshold. Split the BST into 2 BST according to
a threshold, one BST is smaller than threshold; the other one is larger than threshold.

思路：
Google的onsite题目，第一次看到这道题的时候完全没有思路。后来仔细思考一下，发现只要考虑到split的时机，然后recursion即可以解这道题。

代码：

 struct TreeNode {   
   int val;   
   TreeNode* left, *right;   
   TreeNode(int v) : val(v), left(NULL), right(NULL) {};   
 };  
    
 void splitTree(TreeNode* root, TreeNode* &t1, TreeNode* &t2, int threshold) {   
   if (!root) return;   
   if (root->val == threshold) {   
     t1 = root->left;   
     t2 = root->right;   
     return;   
   } else if (root->val > threshold) {   
     TreeNode* left = NULL, *right = NULL;   
     splitTree(root->left, left, right, threshold);   
     t2 = root;    
     t2->left = right;   
     t1 = left;   
   } else {   
     TreeNode* left = NULL, *right = NULL;   
     splitTree(root->right, left, right, threshold);   
     t1 = root;   
     t1->right = left;   
     t2 = right;   
   }   
 }   
     
 TreeNode *buildBST(vector<int>& num, int start, int end) {   
   if (start < end) return NULL;   
   int mid = start + (end - start) / 2;   
   TreeNode *root = new TreeNode(num[mid]);   
   root->left = buildBST(num, start, mid - 1);   
   root->right = buildBST(num, mid + 1, end);   
   return root;   
 }   
     
 TreeNode *sortedArrayToBST(vector<int>& num) {   
   return buildBST(num, 0, num.size() - 1);   
 }   
      
 void inorder(TreeNode* root, vector<int>& num) {   
   if (!root) return;   
   inorder(root->left, num);   
   num.push_back(root->val);   
   inorder(root->right, num);   
 }  
   
 int main() {   
   vector<int> num = {1,2,3,4,5,6,7,8,9,10,11,13};   
   int thr = 5;   
     
   TreeNode* root = sortedArrayToBST(num);   
   TreeNode* left = NULL, *right = NULL;   
   splitTree(root, left, right, thr);   
   
   vector<int> l_num, r_num;   
   inorder(left, l_num);   
   inorder(right, r_num);   
   
   for(auto i : l_num) cout << i << " ";   
   cout << endl;   
   for(auto i : r_num) cout << i << " ";   
   cout << endl;   
   return 0;  
 }   

Bipartite Graph

来源：Twitter Second Phone Interview, EPI

原帖：http://www.fgdsb.com/2015/01/03/check-whether-a-graph-is-bipartite-or-not/

题目：

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)

Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).

思路：使用BFS遍历

代码：

 // bipartite graph   
 // G=[(1,2), (2,3), (3,4)] yes   
 // G=[(1,2), (2,3), (3,1)] no   
 // G=[(1,2), (2,3), (3,4), (4,1)] yes    
   
 // adjacency list   
 struct GraphNode {   
   int visited; // -1 visited, 0: 1-color1; 1: 2-colors;   
   vector<GraphNode*> neighbors;   
 };   
   
 // adjacency matrixs   
 // vector<vector<int>> graph;   
 // vector<int> color(num_nodes);   
   
 bool isBipartite(vector<GraphNode*> g) {   
   if (g.empty()) return false;   
   for (int i = 0; i < g.size(); ++i) {   
     if (g[i]->visited == -1) {   
       g[i]->visited = 0;   
       queue<GraphNode*> q;   
       q.push(g[i]);   
       while (!q.empty()) {   
         auto node = q.front(); q.pop();       
         auto neighbors = node->neighbors;   
         for (int k = 0; k < neighbors.size(); ++k) {   
           if (neighbors[k]->visited == -1) {   
             neighbors[k]->visited = node->visited == 0 ? 1 : 0;   
             q.push(neighbors[k]);   
           } else {   
             if (neighbors[k]->visited == node->visited) return false;   
           }   
         }   
       }   
     }   
   }   
   return true;   
 }   

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

License Plate & Dictionary

来源：Meetqun,一亩三分地, Google Phone Interview

原帖：http://www.meetqun.com/thread-2802-1-1.html
            http://www.meetqun.com/forum.php?mod=viewthread&tid=4901&ctid=41

题目：

“AC1234R” => CAR, ARC | CART, CARED not the shortest

“OR4567S” => SORT, SORE | SORTED valid, not the shortest | OR is not valid, missing S

Google电面题目: 04/13/2015

1 <= letters <= 7

O(100) license plate lookups

O(4M) words in the dictionary

d1 = abc   000....111

d2 = bcd   000…..110

s1 = ac1234r  00001...101

s1 & d1 == s1 d1

s1 & d2 != s1

代码：

 int convert2Num(string s) {   
     int res = 0;   
     for (int i = 0; i < s.size(); ++i) {   
         if (!isdigit(s[i]) {   
             res |= 1 << (s[i] - ‘a’);    
         }   
     }   
     return res;   
 }   
   
 string find_shortest_word(string license, vector<string> words) {   
     int lis_num = convert2Num(license);   
     string res;    
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]); // conversion;    
         if (lis_num & word_num == lis_num) {   
             if (res.empty() || res.size() > words[i].size())   
                 res = words[i]; // brute force; 可以sorting来减少比较次数   
         }   
     }   
     return res;   
 }  

<key, conversion number》

<words, save shortest length of words>

abc, abccc,   <000...111, abc>   

Follow up:
dictionary = { “BAZ”, “FIZZ”, “BUZZ” } | BAZ only has one Z

vector<int> map(26, 0);

a -> 0,   z -> 25;

map[s-’a’]++;

need[26];

need[i] < map[i]

代码：

 bool compare(const string& s1, const string& s2) {   
     return s1.size() < s2.size();   
 }    
   
 string find_shortest_string(string license, vector<string> words) {   
     sort(word.begin(), word.end(), compare);   
     int lic_num = convert2Num(license);   
     vector<int> map(26, 0);   
     for (auto i : license) {   
         if (!isdigit(i)) map[i-’a’]++;   
     }   
   
     for (int i = 0; i < words.size(); ++i) {   
         int word_num = convert2Num(words[i]);   
         // First check that it has all the letters, then check the counts   
         if (lic_num & word_num != lic_num) continue;   
   
         vector<int> word_map(26, 0);   
         for (auto k : words[i]) {   
             if (!isdigit(k)) map[k-’a’]++;   
         }    
         int j = 0;   
         for (; j < 26; ++j) {   
             if (word_map[‘a’+j] < map[‘a’+j]) break;   
         }   
         if (j == 26) return words[i];   
     }   
 }    

Follow up:

find_shortest_word(“12345ZZ”, dictionary) 50% => “FIZZ” | 50% => “BUZZ”

vector<string> s = {};

s[rand() % 2];

reservoir sampling;

FIZZ: s = words;

count = 1;

BUZZ: count++; count = 2;

rand() % count == 0 : s = BUZZ;

Rectangle Sum & Update

来源：Mitbbs, Google First Phone Interview

原帖：http://www.mitbbs.com/article_t1/JobHunting/32574909_0_1.html

题目：
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of operations which have to supported. How would you store the values for efficient updates and retrievals ? （二维线段树  说算法+分析复杂度）

思路：
我gg的电面题目。后来发现这道题在mitbbs和meetqun上曾经出现过多次。
有O(logn)的解法，用quad-tree或者树状数组(binary index tree) 
不过面试官对于O(n)的复杂度是可以接受的。面试官期待的也是O(n)的解法

代码：

 vector<vector<int>> matrix;   
 int M = matrix.size(), N = matrix[0].size();   
   
 // update > > sum   
 // update O(1); sum O(n^2)   
 void update(int r, int c, int val) {   
     matrix[r][c] = val;   
 }   
   
 // (r1,c1) upper left, (r2,c2) bottom right   
 int sum(int r1, int c1, int r2, int c2) {   
     int res = 0;   
     for (int i = r1; i <= r2; ++i) {   
         for (int j = c1; j <= j2; ++j) {   
             res += matrix[i][j];   
         }   
     }      
     return res;   
 }   
   
 // sum > > update   
 // dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]   
 // update O(n^2), sum O(1).   
 vector<vector<int>> dp(M,vector(N,0));   
   
 void compute() {   
     dp[0][0] = matrix[0][0];   
     for (int j = 1; j < N; ++j) {   
         dp[0][j] = dp[0][j-1] + matrix[0][j];   
     }   
     for (int i = 1; i < M; ++i) {   
         dp[i][0] = dp[i-1][0] + matrix[i][0];   
     }   
     for (int i = 1; i < M; ++i) {   
         for (int j = 1; j < N; ++j) {   
             dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];   
         }   
     }   
 }   
   
 void update(int r, int c, int val) {   
     int dif = val - matrix[i][j];   
     for (int i = r; i < M; ++i) {   
         for (int j = c; j < N; ++j) {   
             dp[i][j] += dif;   
         }   
     }   
 }   
   
 int sum(int r1, int c1, int r2, int c2) {   
     if (r1 == 0 && c1 == 0) return dp[r2][c2];   
     else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];   
     else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];   
     else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];   
 }   
   
 // sum ~= update   
 // update    
 vector<vector<int>> dp(M,vector(N,0));   
   
 // row dp; dp[i][j] = sum_i_{k = 0}^{k = j};   
 void compute() {   
     for (int i = 0; i < M; ++i) {   
         for (int j = 0; j < N; ++j) {   
             if (j == 0) dp[i][j] = matrix[i][j];   
             else dp[i][j] = dp[i][j-1] + matrix[i][j];   
         }   
     }   
 }   
   
 void update(int r, int c, int val) {   
     int dif = val - matrix[i][j];   
     for (int j = c; j < N; ++j) {   
         dp[r][j] += dif;   
     }   
 }   
   
 int sum(int r1, int c1, int r2, int c2) {   
     int res = 0;   
     for (int i = r1; i <= r2; ++i) {   
         res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];   
     }   
     return res;   
 }  

Fence Painter

来源：Meequn, fgsdb博客, Google

原帖：http://www.fgdsb.com/2015/01/04/fence-painter/

题目：
Write an algorithm that counts the number of ways you can paint a fence with N posts using K colors such that no more than 2 adjacent fence posts are painted with the same color.

思路：
主要考虑最后两位相同和不同，然后推导dp关系
因为题目要求是不超过两个相邻的栅栏有同样颜色，所以可以把题目分解一下：
设T(n)为符合要求的染色可能总数，S(n)为最后两个相邻元素为相同颜色的染色可能数，D(n)为最后两个相邻元素为不同颜色的染色可能数。显然
D(n) = (k - 1) * (S(n-1) + D(n-1))
S(n) = D(n-1)
T(n) = S(n) + D(n)
带入化简一下得出：
T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

代码:

 int numberWays(int n, int k) {   
     if (n == 1) return k;   
     if (n == 2) return k * k;   
     int prev_prev = k, prev = k*k;   
     for (int i = 3; i <= n; ++i) {   
         int old = prev;   
         prev = (k-1)*(prev + prev_prev);   
         prev_prev = old;   
     }   
     return prev;   
 }    
   
 int main() {   
     int k = 2, n = 10;   
     for (int i = 1; i <= n; ++i) {   
         cout << numberWays(i,k) << " ";   
     }   
     cout << endl;   
     return 0;   
 }  

Inverse Pairs

来源：Meetqun, 一亩三分地，Google

原帖：http://www.fgdsb.com/2015/01/03/inverse-pairs/

题目：
Given an integer array, return the number of all inverse pairs. For example:
{7, 5, 6, 4}
There are five inverse pairs in total:
(7,6), (7,5), (7,4), (6,4), (5,4)
The result should be 5.

思路：
用BST, 线段树，或者merge sort. 从后向前merge然后计算pair number.

代码：

 int mergeSort(vector<int>& num, int s, int e, vector<int>& dup) {   
     if (s >= e) return 0;   
     int mid = s + (e - s) / 2;   
     int l = mergeSort(num, s, mid, dup);   
     int r = mergeSort(num, mid+1, e, dup);   
     //cout << "start: " << s << " end " << e << " mid " << mid;   
     //cout << " l " << l << " r " << r << endl;   
   
     int sum = l + r;   
     for (int i = s; i <= e; ++i) {   
         dup[i] = num[i];   
     }   
     int cur = e, i = mid, j = e; // back -> front   
     while (i >= s && j > mid) {   
         if (dup[i] <= dup[j]) {   
             num[cur--] = dup[j--];   
         } else if (dup[i] > dup[j]) {   
             num[cur--] = dup[i--];   
             sum += j - mid;   
         }   
     }   
     while (i >= s) {   
         num[cur--] = dup[i--];   
     }   
     while (j > mid) {   
         num[cur--] = dup[j--];   
     }   
     return sum;   
 }   
   
 int inverse(vector<int>& num) {   
     if (num.empty() || num.size() == 1) return 0;   
     vector<int> dup(num);   
     return mergeSort(num, 0, num.size()-1, dup);   
 }   
   
 int main() {   
     vector<int> num = {7, 5, 6, 4};   
     cout << inverse(num) << endl;   
     return 0;   
 }   

K-th Largest Sum from Two Sorted Array

来源：Meetqun, Google

原帖：http://www.meetqun.com/thread-2183-1-1.html

题目：
X+Y 第K大. X =[1,2,3] Y = [2,3,4], S = {x+y| x属于X, y属于Y}, 求S中的第K大数。下面这个链接给了解释。http://blog.csdn.net/shoulinjun/article/details/19179243

思路：X,Y是从大到小排列数组。将X拆分成X[i] + Y[0,...,n-1]的形式。
X[0] + Y[0], X[0] + Y[1], ...X[0] + Y[n-1]
X[1] + Y[0], X[1] + Y[1], ...X[1] + Y[n-1]
X[m-1] + Y[0], X[m-1] + Y[1],...., X[m-1] + Y[n-1]
然后用最大堆来解决问题。

代码:

 struct Pair {   
     int ai,bj;   
     int val;   
     Pair(int i, int j, int v) : ai(i), bj(j), val(v) {}    
 };   
   
 class compare {   
 public:   
     bool operator() (const Pair& a, const Pair& b) {   
         return a.val < b.val;   
     }   
 };   
   
 vector<int> res; // global variable   
 int findKthElement(vector<int>& A, vector& B, int k) {   
     priority_queue<Pair, vector<Pair>, compare> q;   
     for (int i = 0; i < A.size(); ++i) {   
         q.push(Pair(i,0,A[i] + B[0]));   
     }   
     int count = 0;   
     while (!q.empty() && count < k) {   
         int element = q.top().val;    
         int i = q.top().ai, j = q.top().bj;   
         //cout << element << endl;   
         res.push_back(element);   
         q.pop();   
         if (++count == k) return element;   
         if (j < B.size()-1) {   
             q.push(Pair(i,j+1,A[i]+B[j+1]));   
         }   
     }   
     return -1; // not found;   
 }   
   
 int main() {   
     vector<int> A = {6,3,2};   
     vector<int> B = {5,4,1};   
     int k = 9;   
     findKthElement(A,B,k);   
     //for (auto i : res) cout << i << " ";   
     return 0;   
 }   
   

First Larger Palindrome

来源：Meetqun, Google phone interview

原帖：meetqun.

题目：
找到比当前数字大的第一个palindrome.


代码：

 string largerPanlidrome(string s) {   
     if (s.empty()) return "1";   
     int i, j, L = s.size();   
     if (L % 2 == 0) {   
         i = L / 2 - 1; j = L / 2;   
     } else {   
         i = j = L / 2;   
     }   
   
     // determine carry   
     int ii = i, jj = j;   
     while (ii >= 0 && jj < L && s[ii] == s[jj]) {   
         ii--; jj++;   
     }   
     int carry = ii == -1 || s[ii] < s[jj] ? 1 : 0;    
     while (i >= 0 && j < L) {   
         if (carry == 1) {   
             carry = (s[i] - '0' + 1) / 10;   
             s[i] = s[j] = (s[i] - '0' + 1) % 10 + '0';   
         } else {   
             s[j] = s[i];   
         }   
         i--; j++;   
     }   
     if (carry == 1) {   
         s.insert(s.begin(), '1');   
         s[s.size()-1] = '1';   
     }   
     return s;   
 }   
   
 int main() {   
     //string s = "1231";   
     string s = "456";   
     cout << largerPanlidrome(s) << endl;   
     return 0;   
 }