Determine K-th Node In An Inorder Traversal

来源：EPI, Facebook Onsite

原帖：EPI 6.6 pg. 233

题目：
It is trivial to find the k-th node that appears in an inorder traversal with O(n) time complexity. However, with additional information on each node, you can do better. Design a function that efficiently computes the k-th node appearing in an inorder traversal. Specifically, your function should take as input a binary tree T and an integer k. Each node has a size field, which is the number of nodes in the subtree rooted at that node. What is the time complexity of your function?

代码：

 //Part I: TreeNodeSize  
 struct TreeNodeSize {  
   int val;  
   int size;  
     TreeNodeSize* left;  
     TreeNodeSize* right;  
     TreeNodeSize(int v) : data(d), size(1), left(NULL), right(NULL) {}  
 };  
   
 // Each node with a size variable  
 TreeNodeSize* find_kth_node_binary_tree(TreeNodeSize* root, int k) {  
   while (root && k) {  
     int left_size = root->left ? root->left->size : 0;  
     if (left_size < k - 1) {  
       k -= (left_size + 1);  
       root = root->right;  
     } else if (left_size == k - 1) {  
       return root;  
     } else {  
       root = root->left;  
     }  
   }  
   return NULL;  
   //throw length_error("no k-th node in binary tree");  
 }  
   
 //Part II: TreeNode structure  
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 TreeNode* find_kth_node(TreeNode* root, int k, int& n) {  
   if (!root) return NULL;  
   TreeNode* node = find_kth_node(root->left, k, n);  
   if (node) return node;  
   n += 1;  
   if (n == k) return root;  
   return find_kth_node(root->right, k, n);  
 }  
   
 TreeNode* find_kth_node_binary_tree(TreeNode* root, int k) {  
   int n = 0;  
   return find_kth_node(root, k, n);  
 }  
   

Meeting Room

来源：Facebook Phone Interview (2/12/2015)

原帖：http://www.fgdsb.com/2015/01/30/meeting-rooms/

题目 1：
write a function that detects conflicts in meeting schedules.

input: a list of schedules [(s1, e1), (s2, e2), ]

output: return True if there's any conflict, and False otherwise

代码：

 struct Interval {  
   double start;  
   double end;  
   Interval(double a, double b) : start(a), end(b) {}  
 };  
   
 bool compare(const Interval& a, const Interval& b) {  
   return a.start < b.start;  
 }  
   
 const double eps = 1.0e-12;  
 int compareDoulbe(double a, double b) {  
   if (b == 0) b += eps;  
   if (a == 0) a += eps;  
   double err = (a-b)/b; // a/b - 1;  
   return err > eps ? 1 : err < -eps ? -1 : 0;   
 }  
   
 bool existConflict(vector<Interval>& meetings) {  
   if (meetings.empty()) return false;  
   sort(meetings.begin(), meetings.end(), compare);  
   int N = meetings.size();  
   for (int i = 1; i < N; ++i) {  
     if (compareDouble(meetings[i].start, meetings[i-1].end)) {  
       return true;  
     }  
   }  
   return false;  
 }  

// test case
// {}, {{1.0,2.0}, {2.5, 3.5}, {5.2, 6.0}, }
// {{1.0, 5.0}, {3.6, 9.0}}

题目 2：

write a function that finds the minimum number of rooms that can accommodate given schedules.

代码：http://www.fgdsb.com/2015/01/30/meeting-rooms/

 bool compare(const pair<int,int>& a, const pair<int, int>& b) {  
   if (a.first == b.first) {  
     return a.second > b.second;  
   }  
   return a.first < b.first;  
 }  
   
 int minimumRoom(vector<Interval>& meetings) {  
   if (meetings.empty()) return 0;  
   vector<pair<int,int> > arrays;  
   for (int i = 0; i < meetings.size(); ++i) {  
     arrays.push_back(meetings[i].start, 0);  //可以使用start, -end来代替pair
     arrays.push_back(meetings[i].end, 1);  
   }  
   sort(arrays.begin(), arrays.end(), compare); //  
   int min = 0, res = 0;  
   for (int i = 0; i < arrays.size(); ++i) {  
     if (arrays[i].second == 0) {  
       min++;  
     } else {  
       min--;  
     }  
     res = max(min, res);  
   }  
   return res;   
 }  

另外一份代码：

 int min_rooms(vector<Interval>& meetings) {  
   vector<int> times;  
   for(auto m : meetings) {  
     times.push_back(m.begin);  
     times.push_back(-m.end);  
   }    
   sort(times.begin(), times.end(), [](int a, int b){  
     return abs(a) == abs(b) ? a < b : abs(a) < abs(b);  
   });    
   int ret = 0, cur = 0;  
   for(auto t : times) {  
     if(t >= 0) ret = max(ret, ++cur);  
     else --cur;  
   }  
   return ret;  
 }  

// test case

// {}, {{1.0, 3.0}, {3.5, 5.0}, {6.8, 10.0}} return 1 

// {{1.0, 8.0}, {2.0,6.0},{3.0, 7.0}} return 3 // 

// {{1.0, 4.0}, {2.0, 7.0}, {5.0, 8.0}} return 2;

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

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

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