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