Interview Question
Country: United States
I guess it might need few improvements, not tested yet
public class CabFinder implements CabStatusListener {
private List<Cab> cabList = null;
private Map<CabWrapper, Cab> cabMap = new TreeMap<CabWrapper, Cab>();
private int maxCabs;
Position userPos = null;
public void initialize(CabApp app, int maxCabs) {
cabList = new ArrayList<Cab>();
Iterator<Cab> iter = app.getCabs();
userPos = app.getUserPosition();
while(iter.hasNext()) {
Cab cab = iter.next();
if (cab.isAvailable()) {//proceed only if it is available
double distance = calculateDistance(cab);
CabWrapper cabWrap = new CabWrapper();
cabWrap.distance = distance;
cabWrap.cabId= cab.getID();
if (distance <= 1000) //if within 1km range add it to the map
cabMap.put(cabWrap, cab);
}
}
this.maxCabs = maxCabs;
}
private double calculateDistance(Cab cab) {
return Math.sqrt(Math.abs(userPos.x
- cab.getCabPosition().x)
^ 2 + Math.abs(userPos.y - cab.getCabPosition().y) ^ 2);
}
public Cab[] getNearestCabs() {
Collection<Cab> sortedList = cabMap.values();
Cab[] cabArrayTotal = (Cab[]) sortedList.toArray();
Cab[] cabArray = Arrays.copyOf(cabArrayTotal, maxCabs);
return cabArray;
}
public void onCabPositionChanged(Cab cab) {
double distance = calculateDistance(cab);
CabWrapper cabWrap = new CabWrapper();
cabWrap.distance = distance;
cabWrap.cabId= cab.getID();
if (cabMap.containsKey(cab)) {
cabMap.remove(cabWrap) ;
}
if(distance <1000 && cab.isAvailable())
cabMap.put(cabWrap, cab);
}
public void onCabAvailabilityChanged(Cab cab, boolean isAvailable) {
CabWrapper cabWrap = new CabWrapper();
double distance = calculateDistance(cab);
cabWrap.cabId= cab.getID();
cabWrap.distance = distance;
// if (!cab.isAvailable() && cabMap.containsKey(cabWrap)) {
cabMap.remove(cabWrap) ;
// } else {
cabMap.put(cabWrap, cab);
}
class CabWrapper implements Comparator<CabWrapper> {
int cabId;
double distance;
@Override
public boolean equals(Object obj) {
if (cabId == ((Cab) obj).getID()) return true;
return false;
}
@Override
public int compare(CabWrapper cab1, CabWrapper cab2) {
if (cab1.distance < cab2.distance) {
return -1;
}
if (cab1.distance > cab2.distance) {
return 1;
} else if (cab1.cabId == cab2.cabId) {
return 0;
} else
return -1;
}
}
Hi!, this was my solution:
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
class CabFinder implements CabStatusListener {
private int maxCabs;
private Position userPosition;
private static int DISTANCE = 1000; //1000 meters => 1KM
private Set<YellowCab> nearestCabs = new HashSet<YellowCab>();
/**
* Initiates CabFinder. Called only once per app startup.
* @app An application object providing services implemented by
* the rest of the application.
* @maxCabs Nearest number of cabs that can be returned to the user
*/
public void initialize(CabApp app, int maxCabs) {
this.maxCabs = maxCabs;
userPosition = app.getUserPosition();
Iterator<Cab> cabs = app.getCabs();
while (cabs.hasNext()) {
Cab cab = cabs.next();
if (cab.isAvailable() && (getDistanceBetweenPoints(userPosition.x, userPosition.y, cab.getCabPosition().x, cab.getCabPosition().y) <= DISTANCE) ){
nearestCabs.add(new YellowCab(cab));
}
}
app.register(this);
}
/**
* Gets nearest cabs within 1km of the current user’s location.
* These must be the *nearest possible* @maxCabs in the 1km area.
* @return An unordered list of the nearest cabs.
*/
public Cab[] getNearestCabs() {
synchronized (nearestCabs) {
int n = Math.min(nearestCabs.size(), maxCabs);
if (n == 0)
return null;
Cab[] result = new Cab[n];
int i = 0;
Iterator<YellowCab> cabs = nearestCabs.iterator();
while (cabs.hasNext()) {
YellowCab YellowCab = cabs.next();
result[i++] = YellowCab.getCab();
if (i == n)
break;
}
return result;
}
}
/**
* Asynchronous Callback per CabStatusListener (see below). Called when the position of a cab has changed.
*/
public void onCabPositionChanged(Cab cab) {
if (cab == null){
throw new IllegalArgumentException();
}else{
System.out.println("Cab:"+cab.getID()+" moved to X:"+cab.getCabPosition().x+" - Y:"+cab.getCabPosition().y+" - Avail:"+cab.isAvailable()
+" - Distance:"+getDistanceBetweenPoints(userPosition.x, userPosition.y, cab.getCabPosition().x, cab.getCabPosition().y)+" Mts");
synchronized (nearestCabs) {
if (cab.isAvailable() && (getDistanceBetweenPoints(userPosition.x, userPosition.y, cab.getCabPosition().x, cab.getCabPosition().y) <= DISTANCE) ){
nearestCabs.add(new YellowCab(cab));
}else{
nearestCabs.remove(new YellowCab(cab));
}
}
}
}
/**
* Asynchronous Callback per CabStatusListener (see below). Called when a cab’s availability changes.
* @cab The cab whose availability has changed
* @isAvailable true if the cab is now available, false otherwise
*/
public void onCabAvailabilityChanged (Cab cab, boolean isAvailable) {
if (cab == null){
throw new IllegalArgumentException();
}else{
System.out.println("Cab:"+cab.getID()+" moved to X:"+cab.getCabPosition().x+" - Y:"+cab.getCabPosition().y+" - Avail:"+isAvailable
+" - Distance:"+getDistanceBetweenPoints(userPosition.x, userPosition.y, cab.getCabPosition().x, cab.getCabPosition().y)+" Mts");
synchronized (nearestCabs) {
if (isAvailable && (getDistanceBetweenPoints(userPosition.x, userPosition.y, cab.getCabPosition().x, cab.getCabPosition().y) <= DISTANCE))
nearestCabs.add(new YellowCab(cab));
else
nearestCabs.remove(new YellowCab(cab));
}
}
}
/**
* Get the distance (meters) using Pythagoras Theorem.
* @pointAX is the X point on the Cartesian plane (2D Map) for person
* @pointAY is the Y point on the Cartesian plane (2D Map) for person
* @pointBX is the X point on the Cartesian plane (2D Map) for cab
* @pointBY is the Y point on the Cartesian plane (2D Map) for cab
*/
public int getDistanceBetweenPoints(int pointAX, int pointAY, int pointBX, int pointBY){
double distance = Math.abs(Math.sqrt(
(pointAX - pointBX) * (pointAX - pointBX) + (pointAY - pointBY) * (pointAY - pointBY)
));
int roundDistance = (int) distance;
return roundDistance;
}
}
/**
* Coordinates on a 2D map with a one meter granularity.
*/
class Position {
public int x;
public int y;
}
interface Cab {
/**
* Unique identifier of a cab.
*/
int getID();
/**
* Gets the current position of the cab
*/
Position getCabPosition();
/**
* Returns whether or not the cab is available
*/
boolean isAvailable();
}
/**
* Provides services implemented by the rest of the Cab Application.
*/
interface CabApp {
/**
* Gets the current location of the user
*/
Position getUserPosition();
/**
* Returns an iterator that gives access to the list of all cabs in the city
*/
Iterator<Cab> getCabs();
/**
* Registers a CabStatusListener object for change notifications of cab
* object data.
*/
void register(CabStatusListener listener);
}
/**
* The CabStatusListener interface
*/
interface CabStatusListener {
/**
* Called when the position of a cab has changed.
*
* @cab The cab object
*/
void onCabPositionChanged(Cab cab);
/**
* Called when a cab’s availability changes.
*
* @cab The cab object
* @isAvailable true if the cab is available, false otherwise
*
*/
void onCabAvailabilityChanged(Cab cab, boolean isAvailable);
}
/* Define Cab Obj */
class YellowCab {
private Cab cab;
public YellowCab(Cab cab){
super();
this.cab = cab;
}
public Cab getCab() {
return cab;
}
@Override
public int hashCode() {
return cab.getID();
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
YellowCab other = (YellowCab) obj;
if (cab == null) {
if (other.cab != null)
return false;
} else if (cab.getID() != other.cab.getID())
return false;
return true;
}
}
/* Test and implementation routine */
class AmazonCabFinderTest implements CabApp {
private final static int maxCabs = 3;
public void test() {
CabFinder cabFinder = new CabFinder();
cabFinder.initialize(this, maxCabs);
System.out.println("Start AmazonCabFinder Map");
cabFinder.onCabPositionChanged(new CabImplementation(1, true, 100, 100));
cabFinder.onCabPositionChanged(new CabImplementation(2, true, 200, 200));
cabFinder.onCabPositionChanged(new CabImplementation(3, true, 300, 300));
System.out.println(cabFinder.getNearestCabs().length+" registered cars");
System.out.println("Move 2 cars away");
cabFinder.onCabPositionChanged(new CabImplementation(2, true, 10000, 10000));
cabFinder.onCabPositionChanged(new CabImplementation(3, true, 10000, 10000));
System.out.println(cabFinder.getNearestCabs().length+" cars closer");
System.out.println("We will test moving car 2 closer");
cabFinder.onCabPositionChanged(new CabImplementation(2, true, 500, 500));
System.out.println(cabFinder.getNearestCabs().length+" cars closer");
System.out.println("We will put 2 as not available");
cabFinder.onCabAvailabilityChanged(new CabImplementation(2, true, 500, 500), false);
System.out.println(cabFinder.getNearestCabs().length+" cars closer");
System.out.println("We will put 2 as available");
cabFinder.onCabAvailabilityChanged(new CabImplementation(2, true, 500, 500), true);
System.out.println(cabFinder.getNearestCabs().length+" cars closer");
System.out.println("We will test moving car 2 away");
cabFinder.onCabPositionChanged(new CabImplementation(2, true, 5000, 5000));
System.out.println(cabFinder.getNearestCabs().length+" cars closer");
}
@Override
public Position getUserPosition() {
return new Position();
}
@Override
public Iterator<Cab> getCabs() {
HashSet<Cab> cabs = new HashSet<Cab>();
return cabs.iterator();
}
@Override
public void register(CabStatusListener listener) {
}
class CabImplementation implements Cab {
int id;
boolean available;
final Position cabPosition;
public CabImplementation(int id, boolean available, int x, int y) {
this.id = id;
this.available = available;
cabPosition = new Position();
cabPosition.x = x;
cabPosition.y = y;
}
@Override
public int getID() {
return id;
}
@Override
public Position getCabPosition() {
return cabPosition;
}
@Override
public boolean isAvailable() {
return available;
}
}
}
/* Main Public Class */
public class AmazonCabFinder {
public static void main(String[] args) {
AmazonCabFinderTest AmazonCabFinderTest = new AmazonCabFinderTest();
AmazonCabFinderTest.test();
}
}
I am working on the following functions:
- ACE CA December 30, 2013getNearestCabs()
onCabPositionChanged(Cab cab)
onCabAvailabilityChanged (Cab cab, boolean isAvailable)