CareerCup

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

Were there any follow-up questions?

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

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

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