## Google Interview Question for Software Engineers

Country: United States

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

Were there any follow-up questions?

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

``````package Careercup;
import javafx.util.Pair;
import java.util.Queue;

class Test {
public static void main(String args[]) {

Test t = new Test();
int a[][] = {
{1,0,0,0,0},
{0,1,0,0,1},
{0,1,0,0,0},
{0,1,0,0,0},
{0,0,0,0,0}
};
Pair<Integer,Integer> result = t.getShop(a,3,4);
System.out.println(result.getKey()+" "+result.getValue());
}
boolean isSafe(int x, int y, int a[][]){
return (x>=0 && x<a.length && y>=0 &&y<a[0].length);
}
// BFS
Pair<Integer,Integer> getShop(int a[][], int x, int y){
if(a[x][y] == 1) return new Pair(x,y);
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int l[] = {0,1,1,1,0,-1,-1,-1};
int r[] = {1,1,0,-1,-1,-1,0,1};
while(!q.isEmpty()){
Pair<Integer,Integer> temp = q.peek();
q.remove();
int xx = temp.getKey();
int yy = temp.getValue();
for(int i=0;i<l.length;i++){
if(isSafe(xx+l[i],yy+r[i],a)){
if(a[xx+l[i]][yy+r[i]]==1){
return new Pair<>(xx+l[i],yy+r[i]);
}else{
}
}
}
}
return null;
}
}``````

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

This is an analogy to the all-pair-single-source-shortest-path algorithm from Graph Theory and the Greedy Algorithm.

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

``````pair<int,int> solution(vector<pair<int,int>> shopList, pair<int,int> person) {
pair<int,int> retValue;
double distance = -1;
for (pair<int,int> shop : shopList) {
double xDis = person.first - shop.first, yDis = person.second - shop.second;
double chkDistanck = sqrt(xDis * xDis + yDis * yDis);
if (distance == -1 || chkDistance < distance) {
distance = chkDistance;
retValue = shop;
}
}

return retValue;
}``````

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

O(n) algorithm for n shops

``````case class Coordinate(x: Double, y: Double)
case class Shop(c: Coordinate, name: String)

object NearestDistanceToShop {
def findNearestShop(shops: Seq[Shop], person: Coordinate): Option[Shop] = {
if (shops.isEmpty) {
return None
}

val (goodShop, _) = shops.foldLeft((None.asInstanceOf[Option[Shop]], -1.asInstanceOf[Double])) { case ((closestShop, shortestDistance), shop) =>
val shopCoord = shop.c
val distance = Math.sqrt(Math.pow(shopCoord.x - person.x, 2) + Math.pow(shopCoord.y - person.y, 2))
if (-1 == shortestDistance || distance < shortestDistance) {
(Some(shop), distance)
} else {
(closestShop, shortestDistance)
}
}
goodShop
}
}``````

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.

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