Google Onsite Problem set 2


  • 3
    F
    1. list itemIntersection Of Two Quadtrees
    struct QuadNode {
    	QuadNode (int num_nodes = 0) : ones(num_ones) {};
    	int ones{ 0 };
    	QuadNode* child[4] { nullptr; };
    };
    
    QuadNode* build_tree(const_vector<vector<int>>& matrix) {
    	if(matrix.empty())   return nullptr;
    	return build(matrix.size(), 0, 0);
    }
    
    QuadNode* build(int size, int row, int col)  {
    	if (size == 1)  return new QuadNode(matrix[row][col]);
    	auto root = new QuadNode();
    	size /= 2;
    	int sub_coords[4][2] = {{row, col}, {row + size, col}, {row, col + size}, {row + size, col + size}};
    	for(int i = 0; i < 4; i++) {
    		root->child[i] = build(size, sub_coords[i][0], sub_coords[i][1]);  
    		root->ones += root->child[i]->ones;
    	}
    	return root;
    }
    
    int intersections(QuadNode *t0,  QuadNode *t1) {
    	return solve(t1, t2, 0);
    }
    
    int solve(QuadNode* t1,  QuadNode* t2,  int sum){
    	if(!t1 || !t2 || !t1->ones || !t2->ones)	return 0;
    	int result = sum;
    	/** leaf node **/
    	if(!t1->child[0] && !t2->child[0]) {
    		result += t1->ones && t2->ones ? 1 : 0;
    	} else {
    	/*** non-leaf node **/
    		for(int i = 0; i < 4; i++) {
    			result += solve(t1->child[i], t2-->child[i], sum);
    		}
    	}
    	return result;
    }
    

    1. car parking problem
    void  carPark(vector<int>& order,  vector<int>& cur, int null_pos, int n) {
    	unordered_map<int, int> dict;
    	for(int i = 0; i < n; i++)   dict[order[i]] = i;
    
    	for(int i = 0; i < n; i++) {
    		while(cur[i] != cur[dict[cur[i]]]) {
    			swap(cur[i], cur[dict[cur[i]]]);
    		}
    	}
    	return;
    }
    

    1. Design a tilt maze game. You can tilt in the four directions: Up, Left, Right, Down. When you tilt in one direction, the ball moves in that direction until it is stopped by a wall. Given two points start and end, find the minimum number of moves to for the ball to reach the goal.

      Play it here:
      https://www.mathsisfun.com/games/tilt-maze.html

    const vector<vector<int>>  dirs({{1, 0}, {-1, 0}, {0, 1}, {0, , -1}});
    
    int min_step(vector<vector<int>> &matrix, int s_x, int s_y, int e_x, int e_y) {
    	int  result = -1;
    	int m = matrix.size(), n = matrix[0].size();
    	vector<vector<bool>> visited(m, vector<bool>(n, false));
    	dfs(matrix, visited, s_x, s_y, m, n, e_x, e_y, result);
    	return result;
    }
    /*** 1 means obstacle **/
    void dfs(vector<vector<int>>  &matrix, vector<vector<bool>> visited,
    	int x, int y, int m, int n, int X, int Y, int step, int &min_step) {
    	if(x < 0 || y < 0 || x >= m || y >= n || matrix[i][j] == 1 || min_step != -1)   return;
    	visited[x][y] = true;
    	if(x == X && y == Y)    { min_step = step;  return; }
    	for(auto dir : dirs) {
    		int new_x = x + dir[0],  new_y = y + dir[1]; 
    		if(visited[new_x][new_y])  continue;
    		dfs(matrix, new_x, new_y, m, n, X, Y, step + 1, min_step);
    	}
    }
    

    1. Serialize an n-ary tree.
    void  serialize(TreeNode* root, int N) {
    	ostringstream in;
    	serialize(root, in);
    	return in.str();
    }
    
    void serialize(TreeNode* root, ostringstream& in, int N) {
    	if(!root)   return;
    	in << root->key << " ";
    	for(int i = 0; i < N && root->child[i]; i++) {
    		serialize(root->child[i], in);
    	}
    	in << "# ";
    }
    
    TreeNode* deserialize(string data) {
    	istringstream out(data);
    	return deserialize(out);
    }
    
    int deserialize(TreeNode *&root, istringstream& data) {
    	string temp;
    	data >> temp;
    	if(temp == "#") {
    		return 1;
    	}
    	/** the child node is nullptr default **/
    	root = new TreeNode(stoi(temp));
    	for(int i = 0; i < N; i++) {
    		if(deserialize(root->child[i], data))
    		break;
    	}
    	return 0;
    }
    

  • 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.


  • 0

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

    car parking problem

    Could you please add more details to this problem? Maybe give an example? Thanks.


  • 0

    @1337c0d3r maybe I am wrong but suspect that car problem is famous beloved by Google, Amazon and .... problem.
    There is an array of length n representing a parking place with n slots . All slots are occupied by cars with except of one.It is a free slot.
    The owner of the parking place decides that there is another way to arrange all cars. He/ she provides you another permutation of the cars. Your task is to arrange the cars in the way the owner requires. You can move a car only to a free place, swap car position with free slot position. Of course there is requirements for minimal swaps.
    Lets take a look at the signature of the problem
    carPark(vector<int>& order, vector<int>& cur, int null_pos, int n)
    vector<int>& order - describes how to arrange the cars
    vector<int>& cu -current situations
    int null_pos - position of the empty slot
    n - number of slots
    An example is : order= [4,3,0,1,2] and current = [2,0,3,1,4] and lets nullpos = 2 and n = 5
    @fight.for.dream Could you confirm this and provide us an examples? Thank you


  • 0
    F

    @1337c0d3r @elmirap said in Google Onsite Problem set 2:

    e way the owner requires. You can move a car only to a free place, swap car position with free slot position. Of course there is requiremen

    Your description are right, we have a start order and target order, so we need to implement a function to move one car to the empty slot one by one to finish moving all the cars to their destination place. A little like the method in finding the first missing positive number problem


  • 0

    @fight.for.dream Can we assume that empty place is always 0, or empty place could be marked with other digit from 0 to N - 1? We have to use information given to us, where is the empty place.


  • 0

    For the first problem ItemIntersection. Can we assume that quadtrees have been already built? Do you mean that we have to merge them. Is it the same problem as this with balck and white images? What are rules for the intersection?
    Thank you, very much!


Log in to reply
 

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