## Google Interview Question

Software Engineers**Country:**United States

```
package Careercup;
import javafx.util.Pair;
import java.util.Queue;
import java.util.LinkedList;
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<>();
q.add(new Pair(x,y));
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{
q.add(new Pair<>(xx+l[i],yy+r[i]));
}
}
}
}
return null;
}
}
```

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

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

Were there any follow-up questions?

- Sithis May 12, 2019