Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

The idea is first put the houses location in a array,
and now traverse the inputArray and find the distance between each point with the houses location array, if any single point distance is equal to all house location array then that point is the answer.

houseLocations[][]<- put locations
int inputArray[][]<- put 1 where location are valid like for A, B, C and rest all is 0
traverse inputArray- now for each inputArray points, cosider index i, j position to calculate the distance,
now for houseLocations array calculate the distance from each points of i,j
if all distance is equal then break with this point and this point is the desired position from where all houses are at equal distance.

If any one need clarification please leave a comment

More clarification on answer.

distance is calculated for (x1, x2), (y1, y2) points using distance formula between two points- sqrroot{(x2-x1)^2 + (y2-y1)^2}
- x1 and x2 are i and j where house location array is having value 1
- For each i, j, goo to loop for houselocation array ie.
start loop k,j - to houselocation array size, now k, j is y1 and y2
- this way you calculate the distance for single point in input array with all house locations values- and this all distance are equal if any point then this is the right location of i,j- which is house location,

still any query please ask.

- Dinkar November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

can u please explain how the distance calculating by index i,j ?

- kathirkarthick12 November 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

let n be the number of houses, w the width, and h the height of the grid and assume moving left, right, down and up us allowed (no diagonales).

the problem is essentially a graph problem, but additional information is given, e.g. the distance from upper-left to lower-right is at least w+h. Maybe this can be used for a heuristics to accellerate the search like in A*.

Let's first approach without heuristics:
Start a BFS from all the houses simultaneously, that means the frontier expands one by one starting at all houses. The first time all frontiers meet is the point for the meeting. It seems natural that this is O(w*h*n) since a BFS will visit all nodes which are w*h and it's run n times.

The problem with this approach is, that, suppose we have a very large map and only two houses that are placed e.g. at (w/4, h/4) and (3/4w, h/4) the BFS's run not only towards each other but as well in directions that won't help solve the problem but extend the frontier heavily, increasing complexity. So for two houses it is very easy to come up with a heuristic. But as soon as a heuristic is added, BFS doesn't work, so we need to switch to Djikstra to pick the element's with lowest distance from origin - heuristic. With several points, this is more difficult, but the expected meeting point will be the point of gravity and then instead of running BFS from each house, we can run Djikstra from each house using this heuristic, which is essentially running A* from each house. This can probably be further optimized by considering the lowest cost next point from each origin (e.g. imagine on the sample above, there is a house exaxtly in the middle between the two houses, around that point I wouldn't explore too much, because it is already close to the expected meeting point)
...
cool question (a bit heavy for an interview), I might code it, if I have time tonight

- Chris November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/*
as with my previous post, the solution here solves the problem with 
BFS and A*

The output shows the number of visits to each field. It's clear that
A* is faster, but it is with this paramter set not guaranteed to find
the absolute optimum: see in qiprio: d + h * 2, replace it with d + h
and A* will cover more land, but is still significant better than 
BFS. 

Expressing this in Big-O is not so meaningful, because it depends so
much on the grid now. A*'s worst case is worse than BFS, because of the 
priority queue. 

Anyway I don't think that is expected by an interview, it's more to 
maybe implement a BFS solution and come up with ideas how to improve and
maybe writing the heuristic function or outline how the algorithm
would fill the grid etc...
*/

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

// helper for point
struct Point
{
	int x_, y_;
	Point(int x, int y) : x_(x), y_(y) { }
	Point() : Point(0, 0) { }
};

// calculates manhatten distance between two points
int manhattend(const Point& a, const Point& b) 
{ 	
	return abs(a.x_ - b.x_) + abs(a.y_ - b.y_); 
}

int qiprio(const Point& current, const Point& expected, int d)
{
	int h = manhattend(expected, current);
	return d + h * 2; 
}

// queue item used for the A-Star approach
struct QI
{
	Point p_;
	int h_; 
	int d_;
	QI(int h, const Point& p, int d) : p_(p), h_(h), d_(d) { }
};

class Village
{
private:
	unordered_set<long long> bushes_; // x << 32 | y for O(1) test
	unordered_map<long long, int> houses4p_; // houses for printing 
	vector<Point> houses_;
	Point guessedMp_;
	int w_;
	int h_;

public:
	Village(int w, int h, const initializer_list<Point>& houses, const initializer_list<Point>& bushes) 
		: w_(w), h_(h), houses_(houses)
	{
		for(auto p : bushes) placeBush(p);		
		int hi = 1;
		for(auto h : houses) placeHouse(h, hi++);
		guessedMp_ = getPointOfGravityManhatten();
	}

	Point findByAstar()
	{
		int n = houses_.size();
		auto cmp = [this](const QI& a, const QI& b) -> bool 
		{   
			return qiprio(a.p_, guessedMp_, a.d_) > qiprio(b.p_, guessedMp_, b.d_);
		};

		vector<priority_queue<QI, vector<QI>, decltype(cmp)>> queues(n, 
			priority_queue<QI, vector<QI>, decltype(cmp)>(cmp)); 
		vector<unordered_set<long long>> visited(n); 
		vector<int> hid(n); // initial distance
		vector<int> c(n, 0); // counter 
		unordered_map<long long, int> visitedCount;

		// initialize queues
		for(int h = 0; h < n; h++)
		{			
			queues[h].push(QI(h, houses_[h], 0));	
			visited[h].insert(getKeyForPoint(houses_[h]));
		}

		int maxQueueSize = 1;
		while(maxQueueSize > 0)
		{
			// distance from best active to target tells how much
			// calculation that part gets
			int mhid = 0; // max initial distance 
			for(int h = 0; h < n; h++)
			{			
				if(queues[h].size() == 0) 
				{
					hid[h] = numeric_limits<int>::max();
				}	
				else
				{
					hid[h] = 1 + manhattend(queues[h].top().p_, guessedMp_) / 5;
					mhid = max(mhid, hid[h]);
				}
			}

			maxQueueSize = 0;
			for(int h = 0; h < n; h++)
			{
				if(queues[h].size() == 0) continue;
				int c = 0;
				while(!queues[h].empty() && c < mhid) // proceed every "house" proportional to initial distance steps
				{
					auto u = queues[h].top(); 
					queues[h].pop();
					visitedCount[getKeyForPoint(u.p_)]++;
					if(visitedCount[getKeyForPoint(u.p_)] == n)
					{ 
						print(visitedCount);
						return u.p_;
					}
					for(auto v : getAdjacents(u.p_))
					{
						if(visited[u.h_].find(getKeyForPoint(v)) != visited[u.h_].end()) continue;
						visited[u.h_].insert(getKeyForPoint(v)); 	
						queues[h].push(QI(u.h_, v, u.d_ + 1));					
					}
					c += mhid / hid[h];
				}
				maxQueueSize = max(maxQueueSize, static_cast<int>(queues[h].size()));
			}
		}

		cout << "couldn't find a solution" << endl;
		return Point(-1, -1); // no solution 	
	}

	// solution using BFS
	Point findByBFS()
	{
		int n = houses_.size();
		vector<queue<Point>> queues(n);
		vector<unordered_set<long long>> visited(n); 
		unordered_map<long long, int> visitedCount;

		for(int h = 0; h < houses_.size(); h++)
		{ 
			queues[h].push(houses_[h]); // start point of all BFS
			visited[h].insert(getKeyForPoint(houses_[h]));
		}
		int maxQueueSize = 1;
		while(maxQueueSize > 0)
		{
			maxQueueSize = 0;
			for(int h = 0; h < n; h++)
			{
				if(queues[h].size() == 0) continue;
				queues[h].push(Point(-1, -1)); // marker element to abort this expansion step
				while(true)
				{
					auto u = queues[h].front(); 
					queues[h].pop();
					if(u.x_ == -1) break; // abort after marker element was found				
					visitedCount[getKeyForPoint(u)]++; // this field is visited once more
					if(visitedCount[getKeyForPoint(u)] == n)
					{ 
						print(visitedCount);
						return u; // if n times visited, done
					}
					
					for(auto v : getAdjacents(u))
					{
						if(visited[h].find(getKeyForPoint(v)) != visited[h].end()) continue;
						visited[h].insert(getKeyForPoint(v)); // BFS starting at h will visit this field on next turn 						
						queues[h].push(v);					
					}
				}
				maxQueueSize = max(maxQueueSize, static_cast<int>(queues[h].size()));
			}
		}
		cout << "couldn't find a solution" << endl;
		return Point(-1, -1); // no solution  			
	}	

private:
	// returns the fields one can go from u considering dimensions of the village and bushes
	vector<Point> getAdjacents(const Point& u)
	{
		vector<Point> result;
		if(u.x_ > 0 && !isBush(Point(u.x_ - 1, u.y_))) result.push_back(Point(u.x_ - 1, u.y_)); // can go left 
		if(u.x_ < w_ - 1 && !isBush(Point(u.x_ + 1, u.y_))) result.push_back(Point(u.x_ + 1, u.y_)); // can go right 
		if(u.y_ > 0 && !isBush(Point(u.x_, u.y_ - 1))) result.push_back(Point(u.x_, u.y_ - 1)); // can go up 
		if(u.y_ < h_ - 1 && !isBush(Point(u.x_, u.y_ + 1))) result.push_back(Point(u.x_, u.y_ + 1)); // can go down
		return result; 
	}

	// place a bush
	void placeBush(const Point& p) 
	{
		bushes_.insert(getKeyForPoint(p));
	}

	// is point a bush?
	bool isBush(const Point& p)
	{
		return bushes_.find(getKeyForPoint(p)) != bushes_.end();
	}

	// finds the point that is equaly far from all houses, not considering
	// bushes etc. this is the optimal place and would be the solution if no 
	// bushes where there. The A* heuristic is set to try to get to this point
	Point getPointOfGravityManhatten()
	{
		Point g(0, 0);

		int mind = w_ + h_ + 1;
		while(true)
		{
			vector<Point> s({Point(g.x_ - 1, g.y_), Point(g.x_ + 1, g.y_), Point(g.x_, g.y_ - 1 ), Point(g.x_, g.y_ + 1)});
			int nd = mind + 1;
			Point ng;
			for(auto p : s)
			{
				int d = 0;
				for(auto h : houses_)
				{
					d = max(d, abs(h.x_ - p.x_) + abs(h.y_ - p.y_));					
				}
				if(nd > d)
				{
					nd = d;
					ng = p;
				}
			}
			if(nd >= mind) return g;
			mind = nd;
			g = ng;			
		}
	}

	inline static long long getKeyForPoint(const Point& p) 
	{
		return (static_cast<long long>(p.x_) << 32) | p.y_;
	}
	
	// infrastructure code for printing to console
	int getHouse(const Point& p)
	{
		auto it = houses4p_.find(getKeyForPoint(p));
		if(it == houses4p_.end()) return 0;
		return it->second;
	}

	// infrastructure code for printing to console
	void placeHouse(const Point& p, int no)
	{
		houses4p_[getKeyForPoint(p)] = no;
	}

	// infrastructure code for printing to console
	void print(const unordered_map<long long, int>& visitedCount)
	{
		for(int y = 0; y < h_; y++)
		{
			for(int x = 0; x < w_; x++)
			{				
				auto vcIt = visitedCount.find(getKeyForPoint(Point(x, y)));
				int vc = vcIt == visitedCount.end() ? 0 : vcIt->second;
				int hNo = getHouse(Point(x, y));
				bool isMeetingPoint = guessedMp_.x_ == x && guessedMp_.y_ == y; 
				if(hNo != 0) cout << static_cast<char>('A' + (hNo - 1));				 
				else if(isBush(Point(x, y))) cout << '#';
				else if(vc == 0) cout << (isMeetingPoint ? 'M' :' ');
				else if(vc < 9) cout << vc;
				else cout << '*';	
			}
			cout << endl;
		}
	}
};


int main()
{
	Village v(80, 40, 
		{{2, 30}, {8, 1}, {65, 19}}, // houses
		{
			// trees suround expected meeting point
			{26, 16}, {27, 16}, {28, 16}, {29, 16}, {30, 16}, 
			{30, 17}, {30, 18}, {30, 19}, {30, 20},
			{29, 20}, {28, 20}, {27, 20}, {26, 20}, 
			{26, 19}, {26, 18}, {26, 17}, {26, 16}, 
			// trees to block path from house 3 slightly (=C)
			{60, 15}, {60, 16}, {60, 17}, {60, 18}, {60, 19}, 
			{60, 20}, {60, 21}, {60, 22}, {60, 23}, {60, 24}, 
			{60, 25} 
		}
	);	
	cout << "find meeting point using BFS" << endl;
	v.findByBFS();

	cout << "\n\nfind meeting point using A*" << endl;	
	v.findByAstar();

	/* output 
	find meeting point using BFS
22222222222222211111111111111111111111111112222222111111111111111111111111111111
22222222B22222221111111111111111111111111122222222211111111111111111111111111111
22222222222222222111111111111111111111111222222222111111111111111111111111111111
22222222222222222211111111111111111111112222222221111111111111111111111111111111
22222222222222222221111111111111111111122222222211111111111111111111111111111111
22222222222222222222111111111111111111222222222111111111111111111111111111111111
22222222222222222222211111111111111112222222221111111111111111111111111111111111
22222222222222222222221111111111111122222222211111111111111111111111111111111111
22222222222222222222222111111111111222222222111111111111111111111111111111111111
22222222222222222222222211111111112222222221111111111111111111111111111111111111
22222222222222222222222221111111122222222211111111111111111111111111111111111111
22222222222222222222222222111111222222222111111111111111111111111111111111111111
22222222222222222222222222211112222222221111111111111111111111111111111111111111
22222222222222222222222222221122222222211111111111111111111111111111111111111111
22222222222222222222222222223222222222111111111111111111111111111111111111111111
222222222222222222222222222222222222211111111111111111111111#1111111111111111111
22222222222222222222222222#####22222111111111111111111111111#1111111111111111111
22222222222222222222222222#   #22221111111111111111111111111#1111111111111111111
22222222222222222222222222# M #22211111111111111111111111111#1111111111111111111
22222222222222222222222222#   #22111111111111111111111111111#1111C11111111111111
22222222222222222222222222#####21111111111111111111111111111#1111111111111111111
222222222222222222222222222222211111111111111111111111111111#1111111111111111111
222222222222222222222222222222111112211111111111111111111111#1111111111111111111
222222222222222222222222222221111122221111111111111111111111#1111111111111111111
222222222222222222222222222211111222222111111111111111111111#1111111111111111111
222222222222222222222222222111112222222211111111111111111111#1111111111111111111
22222222222222222222222222111112222222222111111111111111111111111111111111111111
22222222222222222222222221111111222222222211111111111111111111111111111111111111
22222222222222222222222211111111122222222221111111111111111111111111111111111111
22222222222222222222222111111111112222222222111111111111111111111111111111111111
22A22222222222222222221111111111111222222222211111111111111111111111111111111111
22222222222222222222211111111111111122222222111111111111111111111111111111111111
22222222222222222222111111111111111112222221111111111111111111111111111111111111
22222222222222222221111111111111111111222211111111111111111111111111111111111111
22222222222222222211111111111111111111122111111111111111111111111111111111111111
22222222222222222111111111111111111111111111111111111111111111111111111111111111
122222222222222211111111111111111111111  111111111111111111111111111111111111111
11222222222222211111111111111111111111    11111111111111111111111111111111111111
1112222222222211111111111111111111111      1111111111111111111111111111111111111
111122222222211111111111111111111111        111111111111111111111111111111111111


find meeting point using A*
                                                                                
        B11111111111111111111                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                           111                                                  
                           111                                                  
                           111                                                  
                          11111                                                 
                          11211                                                 
                          122221111111111111111111111111111111                  
                         112222211                          #111                
                         1#####21                           #11111              
                         1#   #21                           #111111             
                        12# M #31                           #1111111            
                         1#   #2                            #1111C11            
                         1#####1                            #111111             
                         1111111                            #11111              
                          11111                             #11                 
                          11111                             #                   
                          11111                             #                   
                           111                              #                   
                           111                                                  
                           111                                                  
                            1                                                   
                           11                                                   
  A11111111111111111111111111                                                   
*/
}

- Chris November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * While not explicitly stated in the problem, this solution assumes that the only valid meeting places are open spaces, or in rare instances, a house
 * runTime O(n*h) where n is number of open spaces and h is number of houses (or h^2 in no open space case)
 * memory O(n + h) two hashsets for houses and open spaces 
 **/

import java.lang.Math; 
import java.util.*;

public class VillageMap
{
  
  public static void main(String[] args)
  {
    String[][] testOne = {{"#","#","#","#","#"},
    				      {"#","#","A"," ","#"},
                          {"#"," "," ","B","#"},
                          {"#"," "," "," ","#"},
                          {"#"," "," ","#","#"},
                          {"#"," ","C"," ","#"},
                          {"#","#","#","#","#"}};
    
    String[][] testTwo = {{"#"}};
    
    String[][] testThree = {{"A"}};
    
    String[][] testFour = {{"#", " ", "#", " ", "#"},
                           {"#", " ", "#", " ", "#"}};
    
    String[][] testFive = {{"A", "#","B"},
                           {"#", "C", "#"},
                           {"D", "#", "E"}};
    
    // base case
    int[] meetingPointTestOne = meetingPoint(testOne);
    System.out.println(meetingPointTestOne[0] + ", " + meetingPointTestOne[1]);
    
    // null input case
    System.out.println(meetingPoint(null));
    
    // 1x1 case, non house
    System.out.println(meetingPoint(testTwo));
    
    // 1x1 case, house
    int[] meetingPointTestThree = meetingPoint(testThree);
    System.out.println(meetingPointTestThree[0] + ", " + meetingPointTestThree[1]);
    
    // no houses case
    System.out.println(meetingPoint(testFour));
    
    // no open spaces case
    int[] meetingPointTestFive = meetingPoint(testFive);
     System.out.println(meetingPointTestFive[0] + ", " + meetingPointTestFive[1]);
  }
  
  public static int[] meetingPoint(String[][] area){
    
    // case where null input, there is no meeting place 
    if(area == null){
    	return null;
    }
    
    // case when area is 1x1 2d array 
    if(area.length == 1 && area[0].length == 1){
      
      int[] response = null; 
      
      // if that one space is a house, we can meet in the house, else, there is no village and thus there is no meeting place
      if(!area[0][0].equals("#") && !area[0][0].equals(" ")){
      	response = new int[2];
        response[0] = response[1] = 0;
      }
      return response;
    }
    
    HashSet<int[]> houses = new HashSet<int[]>();
    HashSet<int[]> meetingSpaces = new HashSet<int[]>();

    for(int i =0; i < area.length; i++){
      for(int j = 0; j < area[i].length; j++){
        if(!area[i][j].equals("#")){
          int[] location = {i, j};
          if(area[i][j].equals(" ")){
            meetingSpaces.add(location);
          }else{
            houses.add(location);
          }
        }
      }
    }

    // case where there are no houses, there is no village so return null
    if(houses.size() == 0){
    	return null;
    }
    
    // case where there is no open spaces, but there are houses, return the location of the closet house to all houses
    if(meetingSpaces.size() == 0){
      Iterator<int[]> it = houses.iterator(); 
      int closestDistance = Integer.MAX_VALUE;
      int[] meetingHouse = new int[2];
      
      while(it.hasNext()){
        int[] currentHouse = it.next();
        int tempDistance = getTempDistance(houses, currentHouse);
        
        if(closestDistance > tempDistance){
        	closestDistance = tempDistance;
        	meetingHouse[0] = currentHouse[0];
        	meetingHouse[1] = currentHouse[1];
      	}
      }
      
      return meetingHouse;
    }
    
    //base case, there is an area made up of houses, bushes and open spaces
    int closestDistance = Integer.MAX_VALUE;
    int[] meetingArea = new int[2];

    for(int[] spot: meetingSpaces){
      
      int tempDistance = getTempDistance(houses, spot);
      
      if(closestDistance > tempDistance){
        closestDistance = tempDistance;
        meetingArea[0] = spot[0];
        meetingArea[1] = spot[1];
      }

    }
    return meetingArea;
  }
  
  private static int getTempDistance(HashSet<int[]> houses, int[] spot){
    int tempDistance = 0;
    for(int[] house: houses){
    	int xS = house[1] - spot[1];
        int yS = house[0] - spot[0];
        tempDistance += (int)Math.sqrt((xS*xS) + (yS*yS));
    }
    return tempDistance;
  }
}

- DCIS November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import deque, defaultdict
town = [
    ["#", "#", "#", "#", "#", "#", "#"],
    ["#",  "",  "", "A", "#",  "", "#"],
    ["#",  "",  "",  "",  "",  "", "#"],
    ["#",  "",  "",  "",  "",  "", "#"],
    ["#",  "", "B",  "",  "",  "", "#"],
    ["#",  "",  "",  "", "#", "C", "#"],
    ["#", "#", "#", "#", "#", "#", "#"]  
]

def find_houses(town):
    houses = []
    for i in xrange(len(town)):
        for j in xrange(len(town[0])):
            if town[i][j] != "#" and town[i][j] != "":
                houses.append(((i,j),town[i][j]))
    return houses

def possible_moves(location, town):
    moves = []
    i = location[0]
    j = location[1]
    if i is not 0 and town[i-1][j] == "":
        moves.append((i-1, j))
    
    if i is not len(town) - 1 and town[i+1][j] == "":
        moves.append((i+1, j))
        
    if j is not 0 and town[i][j-1] == "":
        moves.append((i, j-1))
    
    if j is not len(town[0]) - 1 and town[i][j+1] == "":
        moves.append((i, j+1))
    return moves

def find_meeting_point(town):
    houses = find_houses(town)
    q = deque(houses)
    points = defaultdict(set)
    while q:
        cur = q.popleft()
        moves = possible_moves(cur[0], town)
        for move in moves:
            if cur[1] not in points[move]:
                points[move].add(cur[1])
                if len(points[move]) == len(houses):
                    return move
                q.append((move, cur[1]))
    

print find_meeting_point(town)

- Nitish Garg December 26, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More