Google Interview Question
Software EngineersCountry: 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;
}
}
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
}
}
- leochen40505 May 27, 2019