Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
We could create an object let us call it a 'Cab' object that looks something like this -
class Cab
{
int x;
int y;
double distance; //distance between (p,q) and (x,y)
}
Now create a MaxHeap (based on distance) of size 5 by adding the first 5 Cab objects. For each object after the 5th Cab object follow the algorithm below:
if(distance(new object) < distance (root))
delete root (max object) and add new object.
else
ignore new object
After traversing all the Cab objects, the 5 objects left in the heap are 5 closest cabs.
NOT the BEST answer, but it works.
import java.util.ArrayList;
import java.util.Random;
public class App {
public static class Car {
private int xCor;
private int yCor;
private String carName;
public Car(String name, int x, int y){
xCor = x;
yCor = y;
carName = name;
}
public int getX(){
return xCor;
}
public int getY(){
return yCor;
}
public String toString(){
return carName+":["+xCor+","+yCor+"]";
}
public String getName(){
return carName;
}
}
public static class Distance{
private String carName;
private double value;
public Distance(String name, double val){
carName = name;
value = val;
}
public String getName(){
return carName;
}
public double getDistance(){
return value;
}
public String toString(){
return carName+":["+value+"]";
}
}
public static double getDistance(int posX, int posY, int carX, int carY){
double result = 0;
double temp1 = Double.parseDouble(Integer.toString(posX))-Double.parseDouble(Integer.toString(carX));
double temp2 = Double.parseDouble(Integer.toString(posY))-Double.parseDouble(Integer.toString(carY));
result = Math.sqrt(Math.pow(temp1, 2)+Math.pow(temp2, 2));
return result;
}
public static ArrayList<Distance> sortDistanceArr(ArrayList<Distance> disArr){
ArrayList<Distance> processArr = new ArrayList<Distance>(disArr);
ArrayList<Distance> resultArr = new ArrayList<Distance>();
double tempDisVal = processArr.get(0).getDistance();
String tempDisName = processArr.get(0).getName();
boolean done = false;
while (!done){
int notice = 0;
tempDisVal = processArr.get(0).getDistance();
tempDisName = processArr.get(0).getName();
for (int ii = 1; ii< processArr.size(); ii++){
if(processArr.get(ii).getDistance()<tempDisVal){
tempDisVal = processArr.get(ii).getDistance();
tempDisName = processArr.get(ii).getName();
notice = ii;
}
}
Distance d = new Distance(tempDisName,tempDisVal);
resultArr.add(d);
processArr.remove(notice);
if(processArr.size()<1){
done = true;
}
}
return resultArr;
}
public static void main(String[] args){
int max = Integer.MAX_VALUE/10000000;
Random rand = new Random();
int pos1 = rand.nextInt((max - 0) + 1) + 0;
int pos2 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
pos1 = pos1 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
pos2 = pos2 * -1;
}
Car givenPosition = new Car("POSIT",pos1,pos2);
int randomNum11 = rand.nextInt((max - 0) + 1) + 0;
int randomNum12 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum11 = randomNum11 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum12 = randomNum12 * -1;
}
Car car01 = new Car("CAR1",randomNum11,randomNum12);
int randomNum21 = rand.nextInt((max - 0) + 1) + 0;
int randomNum22 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum21 = randomNum21 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum22 = randomNum22 * -1;
}
Car car02 = new Car("CAR2",randomNum21,randomNum22);
int randomNum31 = rand.nextInt((max - 0) + 1) + 0;
int randomNum32 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum31 = randomNum31 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum32 = randomNum32 * -1;
}
Car car03 = new Car("CAR3",randomNum31,randomNum32);
int randomNum41 = rand.nextInt((max - 0) + 1) + 0;
int randomNum42 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum41 = randomNum41 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum42 = randomNum42 * -1;
}
Car car04 = new Car("CAR4",randomNum41,randomNum42);
int randomNum51 = rand.nextInt((max - 0) + 1) + 0;
int randomNum52 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum51 = randomNum51 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum52 = randomNum52 * -1;
}
Car car05 = new Car("CAR5",randomNum51,randomNum52);
int randomNum61 = rand.nextInt((max - 0) + 1) + 0;
int randomNum62 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum61 = randomNum61 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum62 = randomNum62 * -1;
}
Car car06 = new Car("CAR6",randomNum61,randomNum62);
int randomNum71 = rand.nextInt((max - 0) + 1) + 0;
int randomNum72 = rand.nextInt((max - 0) + 1) + 0;
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum71 = randomNum71 * -1;
}
if(rand.nextInt((1 - 0) + 1) + 0<1){
randomNum72 = randomNum72 * -1;
}
Car car07 = new Car("CAR7",randomNum71,randomNum72);
System.out.println(car01.toString());
System.out.println(car02.toString());
System.out.println(car03.toString());
System.out.println(car04.toString());
System.out.println(car05.toString());
System.out.println(car06.toString());
System.out.println(car07.toString());
System.out.println(givenPosition.toString());
double d1 = 0;double d2 = 0;double d3 = 0;double d4 = 0;double d5 = 0;double d6 = 0;double d7 = 0;
d1 = getDistance(givenPosition.getX(),givenPosition.getY(),car01.getX(),car01.getY());
d2 = getDistance(givenPosition.getX(),givenPosition.getY(),car02.getX(),car02.getY());
d3 = getDistance(givenPosition.getX(),givenPosition.getY(),car03.getX(),car03.getY());
d4 = getDistance(givenPosition.getX(),givenPosition.getY(),car04.getX(),car04.getY());
d5 = getDistance(givenPosition.getX(),givenPosition.getY(),car05.getX(),car05.getY());
d6 = getDistance(givenPosition.getX(),givenPosition.getY(),car06.getX(),car06.getY());
d7 = getDistance(givenPosition.getX(),givenPosition.getY(),car07.getX(),car07.getY());
Distance dis1 = new Distance("CAR1",d1);
Distance dis2 = new Distance("CAR2",d2);
Distance dis3 = new Distance("CAR3",d3);
Distance dis4 = new Distance("CAR4",d4);
Distance dis5 = new Distance("CAR5",d5);
Distance dis6 = new Distance("CAR6",d6);
Distance dis7 = new Distance("CAR7",d7);
System.out.println("CARS DIS-*-");
System.out.println(dis1.toString());
System.out.println(dis2.toString());
System.out.println(dis3.toString());
System.out.println(dis4.toString());
System.out.println(dis5.toString());
System.out.println(dis6.toString());
System.out.println(dis7.toString());
ArrayList<Distance> distanceArr = new ArrayList<Distance>();
distanceArr.add(dis1);
distanceArr.add(dis2);
distanceArr.add(dis3);
distanceArr.add(dis4);
distanceArr.add(dis5);
distanceArr.add(dis6);
distanceArr.add(dis7);
System.out.println("ANSWER-*-");
ArrayList<Distance> answerArr = sortDistanceArr(distanceArr);
for(Distance d : answerArr){
System.out.println(d);
}
}
}
Search for K Nearest Neighbors Algorithm for the best answer. However since this was asked in an interview looks like the below approach would work. You have N Cordinates of Taxis and you have a Point P(x,y) which is your location. Using the nearest point algorithm find the nearest point to P. This gives you a cab which is closest to You. Now you delete this cab and find another cab closest to you. Do this 3 more times and you get the closest 5 cabs to you.
1. Use MaxHeap(heap_id = 0) for current 5 taxis with minimum distances from (p, q) and MinHeap(heap_id=1) for the rest taxis.
2. Keep metadata information for taxis e.g. taxi_id --> heap_id --> index_location
3. Compare updated taxi_id distance with top of heap with id ( 1 - heap_id ) to either switch the taxi_id to different heap or to update position inside the same heap. O(NLogN) initial heap creation and then O(logN) for each update.
Taking example of some of the real cab systems. Here are things we should think about:
1. There will be a client emitting the location of each car (e.g. a GPS system)
2. There will be a server collecting or updating this data in its system
3. There will be another client asking for information about cabs from the server (e.g. Uber App on my phone)
4. In the end you would need to compute the distance between the points (p,q) and the coordinates (xi,yi) for cab i. This is followed by sorting.
Scenario 1: Let my app (or client) sends a request to the server telling it its coordinates (p,q). The server returns 5 nearest cabs.
Server will need calculate distance for each of the cab that is online from (p,q), followed by sorting and then returning the 5 nearest cabs.
Pros:
1. Client does not have to do much work and since clients are supposed to be light weight, this is good.
2. Server does computation and since servers are supposed to be powerful it can do that.
Cons:
1. Server needs to do computation for all the taxis for every given (p,q). This is lot of computation.
2. Meanwhile client can close the connection or cancel the operation so it sounds like a waste of resources.
Scenario 2: Server sends all cab coordinates to client and client finds the distance, sort it and find 5 closest cabs.
This is opposite of scenario 1.
Pros:
1. Server does not need to compute distance and sort them.
Cons:
1. puts a lot of burden on client. If there are 10000 cabs in the city then it has to find distance with all the cabs.
Scenario 3: Client knows its location (p,q). It asks the server to only send coordinates of cabs that are in 1 KM rectangular area from (p,q). Server sends coordinates and client computes distance for this subset of cabs and sort it.
Pros:
1. Client needs to process a small number of cab data.
2. If client dies or cancels the request then no harm done
3. Server is not computing distances and sorting them.
Cons:
1. What if there are no cabs within 1 KM area from (p,q). In this case we can expand the search.
Client logic should looks something like:
import java.util.Arrays; public class CabClient { private CabServer myserver; // assuming there is server class private static int NumResults = 100; private static int desiredResults = 5; public CabClient(CabServer s) { this.myserver = s; } public double[] findnearestcabs(int p, int q) { int gridSize = 1; // Kilometers or miles // we are asking for upto 100 cab locations near our vicinity int[][] result = myserver.getCabCordinatesInGrid(p, q, gridSize, NumResults); double[] distances = new double[NumResults]; for(int i=0;i<NumResults;i++) { if(result[i][0] == 0 && result[i][1] == 0) { continue; // This entry was not filled by server so ignore it } double dist = Math.pow(p-result[i][0], 2) + Math.pow(q-result[i][1], 2); distances[i] = Math.sqrt(dist); } Arrays.sort(distances); double[] retval = new double[desiredResults]; for(int j=0;j<desiredResults;j++) { // assuming desiredResults < NumResults retval[j] = distances[j]; } return retval; } }Server code will look like something
- CodeNameEagle July 06, 2016public class CabServer { // contains x,y private int[][] coordinatesAllCabs; private static int numCabs = 10000; public CabServer() { coordinatesAllCabs = new int[numCabs][2]; } private void populateCoordinates() { // some logic } public int[][] getCabCordinatesInGrid(int p, int q, int gridSize, int n) { int[][] result = new int[n][2]; int index = 0; int xLeft = p - gridSize; int xRight = p + gridSize; int yDown = q - gridSize; int yUp = q + gridSize; for(int i =0; i < coordinatesAllCabs.length; i++) { if(coordinatesAllCabs[i][0] >= xLeft && coordinatesAllCabs[i][0] <= xRight && coordinatesAllCabs[i][1] >= yDown && coordinatesAllCabs[i][1] <= yUp) { result[index++][0] = coordinatesAllCabs[i][0]; result[index++][1] = coordinatesAllCabs[i][1]; } if(index == n) { // we only want up to n results // This could mean that we found n cabs in vicinity but there // could be other cabs that might be nearer which are not accounted for // to take care of that we can use a large value of N break; } } return result; } }