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

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