Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

I am working on the following functions:

getNearestCabs()
onCabPositionChanged(Cab cab)
onCabAvailabilityChanged (Cab cab, boolean isAvailable)

- ACE CA December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- APR January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have you tested it???

- Anonymous January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Brother, Could you provide a main method and some test cases? Also if you could explain your logic that would be great.

- Keith Sanderson January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am kind of confused about how this.maxCabs = maxCabs; is being used. Could you kindly provide a little explanation? And also if possible some test cases. That would be of great help. Thanks

- chandeepsingh85 January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why do we need the map of CarWrappers, why not store the cabs which fit the distance category into the cabList?

- Anonymouse January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- oscar.valenzuela.b April 12, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More