Google Onsite Problem set


  • 0
    F
    • Problem 1 . given many pairs , output all the conflict pairs
    struct Interval {
    	int index; //event number
    	int start;
         int end;
    };
    
    bool compare(Interval& a, Interval& b) {
    	return a.start == b.start ? a.index < b.index : a.start < b.start;
    }
    
    void ConflictPair(vector<Interval>& event, int n) {
    	sort(event.begin(), event.end(), compare);
        for (int i = 0; i < len; i++) {
        	int s = i + 1, e = len - 1;
      		int cur = i; 
        	while (s < = e) {
     			int mid = (s + e) / 2;
     			/** check overlap event index **/
     			if (event[mid] .start > event[i].end) {
    				end = mid - 1;
     			}
     			else {
    				cur = mid;
    				s = mid + 1;
     			}
      		}
      		for(int j = i + 1; j <= cur; j++) {
    			/***** output the event[i] conflict with the event[j]   ***/
      		}
    	}
    }
    

    Problem 2

    UTF-8 Validation

    Uses 1-4 bytes to represent a character, subjected to the following rules:

    1. For 1-byte character, the first bit is a 0, followed by its unicode code.
    2. For n bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

    Please see this for more details about UTF-8 variable width encoding rules here:
    http://stackoverflow.com/a/6339292/490463

    bool valid_utf8(vector<unsigned char>& data) {
    	int count = 0;
    	for(auto c : data) {
    		if(count == 0) {
    	  		/** set the remained the utf-8 char count **/
    	  		if((c >> 5) == 0b110)  count = 1;  
    	  		else if((c >> 4) == 0b1110)   count = 2;
    	  		else if((c >> 3) == 0b11110)  count = 3;
    	  		else if((c >> 7))   return false;
    	  	} else {
    	        if((c >> 6) != 0b10)   return false;
    	   		count--;
    	  	}
    	}
        return count == 0;
    }
    

    • Problem 3 Given a 2d array, find the submatrix which has the largest sum.
    int max_sub_rect(const vector<vector<int>>& matrix) {
    	if(matrix.empty() || matrix[0].empty())  return 0;
    	int row = matrix.size(),  col = matrix[0].size();
    	vector<vector<int>>  col_sum = matrix;
    	   /*** calculate the accumulated sum of the col elements ***/
    	for(int i = 1; i < row; i++) {
    		for(int j = 0; j < col; j++) {
    			col_sum[i][j] += col_sum[i-1][j];
    		}
    	}
       
        int result = 0;
     	for(int i = 0; i < row; i++) {
    		for(int j = 0; j <=i; j++) {
      		int sum = 0;  
    			for(int k = 0; k < col; k++) {
    	   		/** get the col-sum at col k **/
    				int temp = j == 0 ? col_sum[i][k] : col_sum[i][k] - col_sum[j-1][k]; 
    				sum += temp;
    				result = max(result, sum);
    				sum = max(sum , 0);
    			}
    		}
     	}
     	return result;
    }
    

    • Problem 4 Pacific Atlantic problem
    void   dfs(Point pt, uunordered_map<Point, bool>& visited, vector<vector<int>>& matrix) {
    	vector<Point> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    	for(auto dir : dirs) {
    		Point new_p = { dir.x + pt.x,  dir.y + pt.y };
    		if(new_p.x < 0 || new_p.x >= matrix.size() || 
    	                       new_p.y < 0 || new_p.y >= matrix[0].size()){
    			continue;
    		}
    		if(matrix[new_p.x][new_p.y] < matrix[pt.x][pt.y] || visited.count(new_p) {
    			continue;
    		}
    		visited[new_p] = true;
    		dfs(new_p, visited, matrix);
    	 }
    }
    
    vector<Point> flowing_water(vector<vector<int>>& matrix) {
    	int n = matrix.size();
    	unordered_map<Point, bool> visited_1;
    	/*** up ***/
    	for(int i = 0; i < n; i++) {
    		visited_1[{0, i}] = true;
    		search({0, i}, visited_1, matrix);
    	}
    	/*** left ***/
    	for(int i = 0; i < n; i++) {
    		visited_1[{i, 0}] = true;
    		search({i, 0}, visited_1, matrix);
    	}
    
    	unordered_map<Point, bool> visited_2;
    	/*** down ***/
    	for(int i = 0; i < n; i++) {
    		visited_2[{n - 1, i}] = true;
    		search({n - 1, i}, visited_2, matrix);
    	}
    	/*** right ***/
    	for(int i = 0; i < n; i++) {
    		visited_2[{i, n - 1}] = true;
    		search({i, n - 1}, visited_2, matrix);
    	}
    
    	vector<Point>  result;
    	for(auto p : visited_1) {
    		if(visited_2.count(p.first)) 
    			result.push_back(p.first);
    	}
    	return result;
    }
    
    
    

  • 0

    @fight.for.dream This should be moved to under the "Interview Questions"->"Google" category. I've moved it to the correct category, please take note of this in future.


  • 1

    Where are the problems? I pretty much just see solutions.


  • 0

    @fight.for.dream said in Google Onsite Problem set:

    Problem 4 Pacific Atlantic problem

    Please add more details about this, and could you please provide at least an example?


  • 0

    @StefanPochmann You can see the problem description above each solution. However, some of the descriptions are very vague.


  • 0

    @1337c0d3r Ok, I see some of the Chinese (?) has been replaced by English now. Problem 1 still doesn't make sense, though, and problem 4 is only a useless name. And problem 2 really needs to be translated (I assume it describes the details of UTF-8, which I doubt many people would know).


  • 0

    @fight.for.dream Could you provide more information for the first and the fourth problem?
    Thank you


  • 0

    @StefanPochmann

    Problem 1 is: Given a list of appointments as pair<start_time, end_time> return all the conflicting appointments. O(nlogn) solution using an interval tree.

    I suspect this is Problem 4.


  • 0

    @babhishek21 i don't think that interval tree was used in the soluiton above


  • 0

    @elmirap You are right. He didn't. Instead, he used sorting + binary search, which is just as good.


  • 0

    @babhishek21 could you please state the problem here? Maybe it's worth adding it to the problem base.


  • 0

    @agave I suppose it is:
    Given n appointments, find all conflicting appointments. Example :
    Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}
    Output: Following are conflicting intervals
    [3,7] Conflicts with [1,5]
    [2,6] Conflicts with [1,5]
    [5,6] Conflicts with [3,7]
    [4,100] Conflicts with [1,5]
    That's why @babhishek21 suggested interval tree for nlog(n) solution. I will code it when I have some time.
    You could insert it in the library
    @fight-for-dream can you confirm this?


  • 0

    @elmirap I meant the Pacific Atlantic problem. Also, we should definitely upload Tilt Game - it's been asked again to another guy.


  • 0

    @agave I see, sorry


  • 0

    @agave,please take a look at :
    https://www.careercup.com/question?id=5162862051852288. It might be the problem


  • 0

    @elmirap Ok, so basically we start from points on the shores and from each we do bfs/dfs and mark points as Pacific/Atlantic. So at the end the points with both P/A will be the divide. Right?


  • 0

    @agave I am not sure about this. The provide the example:

    antlantic *
    pacific #
    
        * * * * *
    *  1 2 2 3 (5)  #
    *  3 2 3(4)(4) #
    *  2 4 (5) 3 1  #
    * (6)(7) 1 4 5  #
    *  (5) 1 1  2 4 #
      #  #  # #  #
    It seems that solution points are these from which water fall in antlantic and in pacific.What is time complexity of your solution?

  • 0

    @agave is right. That will do the trick. @fight-for-dream has pretty much written the same.

    Using HashSet-like DS, it takes 2*O(m*n) for discovery with dfs and O(m*n) for finding intersection between two sets. Additionally we need 2*O(m*n) extra space (worst case being when all heights are equal).

    So time complexity: O(m*n), space complexity: O(m*n).


  • 0

    @babhishek21 I can't see the point why you are talking about bfs,dfs and so on, when the algorithm could be summarized as a traversal by rows and traversal by columns


  • 0

    @elmirap what do you mean by traversal? and yes, it would be O(m*n) time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.