Bloomberg LP Interview Question for Software Engineer / Developers


Team: Derivatives
Country: United States
Interview Type: In-Person




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

The solution is to build maxHeap of 100 elements according to the distances of planes to the tower, and each time a plane is detected or distances are changed heap must be rebuild, it means at any moment you can show the 100 planes which are closest to the tower.

- madi.sagimbekov December 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, I did not quite catch your idea.
"each time a plane is detected ... heap must be rebuild" - how to imagine that.
Let's model radar's work: radar starts to scan space from point {0,0}. Next step is point {1,0} and let's say at this point radar finds first nearest plane. So, what heap must be rebuilt?

- zr.roman December 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's the c++ implementation to print closest distance given 2d coordinates. The closest distance are kept in map container in sorted order. It also handles the follow up question of handling same plane multiple times. Removing the plane from DS is open ended, and can be implemented in many different ways - remove planes outside certain distance, or when coordinates goes outside certain limits.

#include <iostream>
#include <map>
#include <cmath>

using namespace std;

struct Plane
{
    Plane(int inX, int inY, int inId)
	:x(inX),
	 y(inY),
	 id(inId) {}
    int x;
    int y;
    int id;
};

// Map of Plane id to distance
typedef map<int, double> MPlaneId;
MPlaneId planeIdMap;
// Map of distance to Plane coordinates sorted
typedef multimap<double, Plane> MMCloseDist;
MMCloseDist closestDistMap;

void scan(const Plane& P)
{

    // Calculate the distance between two 2d coords
    // a^2 + b^2 = c^2
    double distance = sqrt(pow(abs(P.x),2) + pow(abs(P.y),2));
    MPlaneId::iterator itFind = planeIdMap.find(P.id);
    if (planeIdMap.end() != itFind)
    {
	// Plane already detected
	// Find matching entry from multimap to erase
	pair<MMCloseDist::iterator, MMCloseDist::iterator> ret =
	    closestDistMap.equal_range(itFind->second);
	MMCloseDist::iterator it = ret.first;
	for (; it != ret.second; ++it)
	{
	    Plane&  plane = it->second;
	    if (plane.id == P.id)
	    {
		closestDistMap.erase(it);
		break;
	    }
	}
	
	// Insert new entry
	closestDistMap.insert(pair<double, Plane>(distance, P));
	// Update distance in id map
	planeIdMap[P.id] = distance;
    }
    else
    {
	// New Plane detected
	planeIdMap.insert(pair<int, double>(P.id, distance));
	closestDistMap.insert(pair<double, Plane>(distance, P));
    }
}

void printDistanceMap()
{
    // Print out closestDistMap
    MMCloseDist::iterator itDist = closestDistMap.begin();
    for (; itDist != closestDistMap.end(); ++itDist)
    {
	cout << "Plane Id " << (itDist->second).id
	     << " coordinates (" << (itDist->second).x << " " << (itDist->second).y << ")"
	     << " at distance " << itDist->first << endl;
    }
}

/* Test Output
Plane Id 1 coordinates (2 1) at distance 2.23607
Plane Id 4 coordinates (1 -2) at distance 2.23607
Plane Id 3 coordinates (-1 -3) at distance 3.16228
Plane Id 2 coordinates (-3 2) at distance 3.60555
-------------------------------------------------
Plane Id 4 coordinates (1 -2) at distance 2.23607
Plane Id 3 coordinates (-1 -3) at distance 3.16228
Plane Id 2 coordinates (-3 2) at distance 3.60555
Plane Id 1 coordinates (3 4) at distance 5
*/

int main()
{

    Plane p1(2,1,1);
    Plane p2(-3,2,2);
    Plane p3(-1,-3,3);
    Plane p4(1,-2,4);
    scan(p1);
    scan(p2);
    scan(p3);
    scan(p4);
    printDistanceMap();
    // Update p1
    p1.x = 3;
    p1.y = 4;
    scan(p1);
    printDistanceMap();

    return 0;
}

- codemepat January 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the task is unclear.
"void scan(const Plane &P) that is called periodically whenever the radar detects a plane" - radar works in another manner: it scans the sky all the time, trying to detect planes, and shows all the planes that are in radar's scope per each scan.
The API should be:
List<Plane> scan();

for example (c#):

using System;
using System.Collections.Generic;

namespace Radar {

    class Program {

        readonly static List<Plane> FlyingPlanes = new List<Plane> {/*add planes which are in the sky now*/};
        private const int RadiusLimit = 10000;
        private const int RadiusStep = 1;
        private const int AngleStep = 1;
        private const int PlanesLimit = 100;

        private static List<Plane> Scan() {

            var nearestPlanes = new List<Plane>();

            for ( int radius = 1; radius < RadiusLimit; radius += RadiusStep ) {

                for (int angle = 0; angle < 360; angle += AngleStep) {
                    var radians = Math.PI  * angle / 180;
                    double x = Math.Cos( radians ) * radius;
                    double y = Math.Sin( radians ) * radius;

                    var potentialPlane = new Plane { x = x, y = y };
                    if ( FlyingPlanes.Contains( potentialPlane ) ) {
                        nearestPlanes.Add( potentialPlane );
                    }
                    if ( nearestPlanes.Count >= PlanesLimit ) {
                        return nearestPlanes;
                    }
                }
            }
            return nearestPlanes;
        }

        private struct Plane {
            public double x;
            public double y;
        }

        static void Main(string[] args) {
            var nearestPlanes = Scan();
        }
    }
}

- zr.roman December 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem is to find nearest 100 planes, in your solution what if there are less than 100 planes within radius RadiusLimit? what if there is no plane within radius RadiusLimit?

- madi.sagimbekov December 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"what if there are less than 100 planes within radius RadiusLimit?" - then the output will be the actual number of nearest planes.
"what if there is no plane within radius RadiusLimit?" - it is ok, the output will be a list with 0 elements.
Any radar has its limit, meaning that no one radar can scan infinite space.
Weak radars can scan 10 km of space (for example), powerful radars can scan 100 km (or more) of space, etc. Limit exists for every radar.
This means that if we have a weak radar (10 km of scanning space) and if the nearest plane is 11 km away, then the radar will not detect it.

- zr.roman December 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

really, it's something wrong with the task.
Could the author please clarify if.
Firstly, I've mentioned above that radar works in another manner than it is described in the task.
Secondly, the API's signature is "void scan(const Plane &P)", the return value is void.
But the task requires that function Scan could at any given time be able to RETURN the 100 closest planes to the tower (0,0).

- zr.roman December 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There scan API is correct. You can view it as an interrupt service routine that is called periodically. You should have separate data structures that will hold the relevant information so that when a query comes, you can return the right information (e.g. the closest 100 planes). you should obviously modify these data structures in the Scan routine. Also, as a follow up make sure you handle correctly the fact that the same plane might be spotted multiple times - How would you change your DS to handle this scenario ? Next follow up - clean up of your data structure. When do you know it is OK to remove an airplane from your DS ? I'll submit an answer to this question later on.

- Johnybegood December 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Breadth-First-Search should work!!

- prodigy January 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats correct. Its a Graph Theory problem. A BFS will give the closest 100 planes.

- itsmeamit January 18, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like the simplest solution for the given description is just push each plane info a global vector. When information about nearest places is needed, a separate function should return/print it.

bool compare(const Plane &p1, const Plane &p2)
{
    return p1.dist < p2.dist;
}

static std::vector<Plane> radar;

void scan(const Plane &P)
{
    Plane plane = P;
    plane.dist = std::sqrt((plane.x*plane.x) + (plane.y * plane.y));
    radar.push_back(plane);
}

void printNearest(size_t num)
{
    std::sort(radar.begin(), radar.end(), compare);
    std::for_each(radar.begin(), 
                  radar.size() > num ? radar.begin() + num : radar.end(),
                  [](auto p) { std::cout << p.dist << std::endl; });
}

That gives 'nlogn' complexity on returning nearest planes plus 'n' complexity on adding places to the global vector.

- dmitry.sharipo February 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
//
// Imagine an airport with the control tower having a constantly 
// rotating radar scanning for airplanes. The radar's coordinates 
// in the 2-d plane are (0,0). 
//
// The radar has an API: void scan(const Plane &P) 
// that is called periodically whenever the radar detects a plane. 
// You can imagine that the Plane structure has x,y coordinates 
// for that plane. You should fill in the function Scan, such that 
// at any given time you are able to return the 100 closest planes 
// to the tower (0,0).
// 
//    -- Johnybegood December 24, 2015 
//       in United States for Derivatives
//       Bloomberg LP Interview Question 
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.*;

class Plane implements Comparable<Plane> {
	
	String airline;
	int flightNumber;
	int x;
	int y;
	int speed;
	
	Plane(String a, int b, int c, int d, int e) {
		this.airline = a;
		this.flightNumber = b;
		this.x = c;
		this.y = d;
		this.speed = e;
	}
	
	/**
	 * public int compareTo(Plane o)
	 * 
	 * Compares two planes relative to the radar by converting 
	 * the aircraft's x & y 2D coordinates into two Pythagorean values
	 * and converting the difference between the two aircraft relative
	 * to the radar station into a +-1 or 0 value.
	 * 
	 */
	@Override
	public int compareTo(Plane o) {
		double p = Math.sqrt((x*x)+(y*y));
		double po = Math.sqrt((o.x*o.x)+(o.y*o.y));
		System.out.println(p - po+" : "+getFlightName());
		return (int)(p - po);
	}
	
	public String getFlightName() {
		return airline+" "+flightNumber;
	}
	
}


public class LPMain006 {

	static Plane[] getReport(Plane[] planes) {
		List<Plane> list = new ArrayList<Plane>();
		for ( Plane product : planes )
			list.add(product);	
		Collections.sort(list);
		Plane[] report = list.toArray(new Plane[planes.length]);
		return report;
	}

	public static void main(String[] args) {
		
		Plane[] test1 = { 
				new Plane("WestJet",205,50,50,50),
				new Plane("United Airlines",99,25,25,25),
				new Plane("Canadiar",310,-45,-45,45),
				new Plane("NorthWest",202,35,-35,35),
				new Plane("SouthWest",500,-60,60,25)
		};
		
		Plane[] results1 = { 
				new Plane("United Airlines",99,25,25,25),
				new Plane("NorthWest",202,35,-35,35),
				new Plane("Canadiar",310,-45,-45,45),
				new Plane("WestJet",205,50,50,50),
				new Plane("SouthWest",500,-60,60,25)
		};
		
		/*
		 * Due to a glitch in the JVM we have to compare the arrays
		 * using a manual approach;
		 */
		
//		assert Arrays.equals(getReport(test1), results1);
//		assert !Arrays.equals(getReport(test1), test1);

		Plane[] report = getReport(test1);
		for ( int i=0; i<test1.length; i++ )
			if ( !report[i].getFlightName().equals(results1[i].getFlightName()) )
				System.out.println("Different");
		
	}
		
}

- perry.anderson November 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static Plane[] scan(Plane[] planes) {
		List<Plane> list = new ArrayList<Plane>();
		for ( Plane product : planes )
			list.add(product);	
		Collections.sort(list);
		Plane[] report = list.toArray(new Plane[planes.length]);
		return report;
	}

- perry.anderson November 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
	 * public int compareTo(Plane o)
	 * 
	 * Compares two planes relative to the radar by converting 
	 * the aircraft's x & y 2D coordinates into two Pythagorean values
	 * and converting the difference between the two aircraft relative
	 * to the radar station into a +-1 or 0 value.
	 * 
	 */
	@Override
	public int compareTo(Plane o) {
		double p = Math.sqrt((x*x)+(y*y));
		double po = Math.sqrt((o.x*o.x)+(o.y*o.y));
		return (int)(p - po);
	}

- perry.anderson November 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It doesn't hurt to have an extensive background in GPS applications, knowing right where to look!

- perry.anderson November 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested Java Code, but used 3 vs 100 to prove the point.
Approach: Tower has a max heap of 3 closest planes and map that keeps track of the planes in sight. When adding a plane it checks if the plane is already insight. If so, it updates it otherwise adds it. If heap size > 3 then we pop off the farthest plane and remove from map as well. Scan takes a snapshot of the heap as an array then sorts from lowest to highest distance.
Plane is defined by flight#, x, and y. It implements Comparable for Arrays.sort().
Next set would've been to spin off thread that either adds an new plane or updates coordinates of existing, then scans.

{{import static java.lang.Math.*;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

public class Tower {

public int maxScan;
public PriorityQueue<Plane> queue;
public Map<Integer, Plane> planeLookupMap;

public Tower( int maxScan ) {
this.maxScan = maxScan;

Comparator<Plane> comparator = new PlaneComparator();
queue = new PriorityQueue<Plane>(maxScan, comparator);
planeLookupMap = new HashMap<Integer, Plane>();
}

public void addPlane( Plane p ) {
if ( planeLookupMap.containsKey( p.flightNumber ) ) {
System.out.println( "updating: " + p );
updatePlane( p );
} else {
System.out.println( "adding: " + p );
planeLookupMap.put( p.flightNumber, p );
queue.offer( p );

if ( queue.size() > maxScan ) {
Plane deletePlane = queue.poll();
System.out.println( "deleting: " + deletePlane );
planeLookupMap.remove( deletePlane.flightNumber );
}
}

}

protected void updatePlane( Plane newPlane ) {
Plane oldPlane = planeLookupMap.get( newPlane.flightNumber );
oldPlane.x = newPlane.x;
oldPlane.y = newPlane.y;
}

public void scan() {
// If order doesn't matter then use iterator()
Plane[] array = queue.toArray(new Plane[queue.size()]);
Arrays.sort(array);

for ( Plane p : array ) {
System.out.println( p );
}
}

public static double calcDistance( Plane p ) {
return sqrt( pow(p.x,2) + pow(p.y,2) );
}

////////// PlaneComparator //////////////////////////
public class PlaneComparator implements Comparator<Plane> {
@Override
public int compare( Plane p, Plane o ) {
return (int) (calcDistance(o) - calcDistance(p));
}

}

////////// Plane //////////////////////////
public class Plane implements Comparable<Plane>{
int flightNumber;
int x;
int y;

Plane( int flightNumber, int x, int y ) {
this.flightNumber = flightNumber;
this.x = x;
this.y = y;
}

@Override
public int compareTo( Plane o ) {
double diff = calcDistance(this) - calcDistance(o);
int result = 0;
if ( diff > 0 ) { result = 1; }
if ( diff < 0 ) { result = -1; }

//System.out.println( String.format( "Comparing %s to %s ==> %f ==> %d", this, o, diff, result ) );

return result;
}

@Override
public String toString() {
return String.format( "fight %d: (%d,%d)...", flightNumber, x, y );
}
}

public static void main( String[] args ) {
int nbrOfPlanes = 3;
Tower t = new Tower(nbrOfPlanes);

for ( int i=nbrOfPlanes; i>0; i-- ) {
Plane p = t.new Plane( i, i, i );
t.addPlane( p );
}

System.out.println( "Starting..." );
t.scan();

System.out.println( "\n----------------------------");
Plane p = t.new Plane( 4, 4, 4 );
t.addPlane( p );
t.scan();

System.out.println( "\n----------------------------");
p = t.new Plane( 0, 0, 1 );
t.addPlane( p );
t.scan();

System.out.println( "\n----------------------------");
p = t.new Plane( 5, 1, 2 );
t.addPlane( p );
t.scan();

System.out.println( "\n----------------------------");
p = t.new Plane( 6, 2, 1 );
t.addPlane( p );
t.scan();

System.out.println( "\n----------------------------");
System.out.println( "Plane 2 just came in closer (1,0)" );
p = t.new Plane( 2, 1, 0 );
t.addPlane( p );
t.scan();
}

}
}}

adding: fight 3: (3,3)...
adding: fight 2: (2,2)...
adding: fight 1: (1,1)...
Starting...
fight 1: (1,1)...
fight 2: (2,2)...
fight 3: (3,3)...

----------------------------
adding: fight 4: (4,4)...
deleting: fight 4: (4,4)...
fight 1: (1,1)...
fight 2: (2,2)...
fight 3: (3,3)...

----------------------------
adding: fight 0: (0,1)...
deleting: fight 3: (3,3)...
fight 0: (0,1)...
fight 1: (1,1)...
fight 2: (2,2)...

----------------------------
adding: fight 5: (1,2)...
deleting: fight 2: (2,2)...
fight 0: (0,1)...
fight 1: (1,1)...
fight 5: (1,2)...

----------------------------
adding: fight 6: (2,1)...
deleting: fight 5: (1,2)...
fight 0: (0,1)...
fight 1: (1,1)...
fight 6: (2,1)...

----------------------------
Plane 2 just came in closer (1,0)
adding: fight 2: (1,0)...
deleting: fight 6: (2,1)...
fight 2: (1,0)...
fight 0: (0,1)...
fight 1: (1,1)...

- Alex Basile January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested Java solution - uses 3 vs 100 to prove the point.
Tower has max heap of 3 of the closest planes. Also has lookup map to for updating planes quickly. addPlane() adds/updates plane. If add and heap > 3 then pop out furthest plane from heap and map. scan() takes snapshot of heap as array and sorts them by closest distance.
Next steps would've been to spin off thread that adds/updates plane periodically.

import static java.lang.Math.*;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

public class Tower {

public int maxScan;
public PriorityQueue<Plane> queue; 
public Map<Integer, Plane> planeLookupMap;

public Tower( int maxScan ) {
    this.maxScan = maxScan;

    Comparator<Plane> comparator = new PlaneComparator();
    queue = new PriorityQueue<Plane>(maxScan, comparator);
    planeLookupMap = new HashMap<Integer, Plane>();
}

public void addPlane( Plane p ) {
    if ( planeLookupMap.containsKey( p.flightNumber ) ) {
        System.out.println( "updating: " + p );
	updatePlane( p );	
    } else {
	System.out.println( "adding: " + p );
	planeLookupMap.put( p.flightNumber, p );
        queue.offer( p );

  	if ( queue.size() > maxScan ) {
	    Plane deletePlane = queue.poll(); 
	    System.out.println( "deleting: " + deletePlane );
            planeLookupMap.remove( deletePlane.flightNumber );
  	}
    }   

}

protected void updatePlane( Plane newPlane ) {
    Plane oldPlane = planeLookupMap.get( newPlane.flightNumber );
    oldPlane.x = newPlane.x;
    oldPlane.y = newPlane.y;
}

public void scan() {
    // If order doesn't matter then use iterator()
    Plane[] array = queue.toArray(new Plane[queue.size()]);
    Arrays.sort(array);

    for ( Plane p : array ) {
	System.out.println( p );
    } 
}

public static double calcDistance( Plane p ) {
    return sqrt( pow(p.x,2) + pow(p.y,2) );
}

////////// PlaneComparator //////////////////////////
public class PlaneComparator implements Comparator<Plane> {
    @Override
    public int compare( Plane p, Plane o ) {
	return (int) (calcDistance(o) - calcDistance(p));
    }

}

////////// Plane //////////////////////////
public class Plane implements Comparable<Plane>{
    int flightNumber;
    int x;
    int y;

    Plane( int flightNumber, int x, int y ) {
        this.flightNumber = flightNumber;
        this.x = x;
    	this.y = y;
    }

    @Override
    public int compareTo( Plane o ) {
   	double diff = calcDistance(this) - calcDistance(o); 
        int result = 0; 
	if ( diff > 0 ) { result = 1; }
	if ( diff < 0 ) { result = -1; }
        
        //System.out.println( String.format( "Comparing %s to %s ==> %f ==> %d", this, o, diff, result ) );

	return result;
    }

    @Override
    public String toString() {
	return String.format( "fight %d: (%d,%d)...", flightNumber, x, y );
    }
}

public static void main( String[] args ) {
    int nbrOfPlanes = 3;
    Tower t = new Tower(nbrOfPlanes);

    for ( int i=nbrOfPlanes; i>0; i-- ) {
    	Plane p = t.new Plane( i, i, i );
        t.addPlane( p );
    } 

    System.out.println( "Starting..." );
    t.scan();

    System.out.println( "\n----------------------------");
    Plane p = t.new Plane( 4, 4, 4 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 0, 0, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 5, 1, 2 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 6, 2, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    System.out.println( "Plane 2 just came in closer (1,0)" );
    p = t.new Plane( 2, 1, 0 );
    t.addPlane( p ); 
    t.scan();
}

}

- Alex Basile January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested Java solution - uses 3 vs 100 to prove the point.
Tower has max heap of 3 of the closest planes. Also has lookup map to for updating planes quickly. addPlane() adds/updates plane. If add and heap > 3 then pop out furthest plane from heap and map. scan() takes snapshot of heap as array and sorts them by closest distance.
Next steps would've been to spin off thread that adds/updates plane periodically.

import static java.lang.Math.*;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

public class Tower {

public int maxScan;
public PriorityQueue<Plane> queue; 
public Map<Integer, Plane> planeLookupMap;

public Tower( int maxScan ) {
    this.maxScan = maxScan;

    Comparator<Plane> comparator = new PlaneComparator();
    queue = new PriorityQueue<Plane>(maxScan, comparator);
    planeLookupMap = new HashMap<Integer, Plane>();
}

public void addPlane( Plane p ) {
    if ( planeLookupMap.containsKey( p.flightNumber ) ) {
        System.out.println( "updating: " + p );
	updatePlane( p );	
    } else {
	System.out.println( "adding: " + p );
	planeLookupMap.put( p.flightNumber, p );
        queue.offer( p );

  	if ( queue.size() > maxScan ) {
	    Plane deletePlane = queue.poll(); 
	    System.out.println( "deleting: " + deletePlane );
            planeLookupMap.remove( deletePlane.flightNumber );
  	}
    }   

}

protected void updatePlane( Plane newPlane ) {
    Plane oldPlane = planeLookupMap.get( newPlane.flightNumber );
    oldPlane.x = newPlane.x;
    oldPlane.y = newPlane.y;
}

public void scan() {
    // If order doesn't matter then use iterator()
    Plane[] array = queue.toArray(new Plane[queue.size()]);
    Arrays.sort(array);

    for ( Plane p : array ) {
	System.out.println( p );
    } 
}

public static double calcDistance( Plane p ) {
    return sqrt( pow(p.x,2) + pow(p.y,2) );
}

////////// PlaneComparator //////////////////////////
public class PlaneComparator implements Comparator<Plane> {
    @Override
    public int compare( Plane p, Plane o ) {
	return (int) (calcDistance(o) - calcDistance(p));
    }

}

////////// Plane //////////////////////////
public class Plane implements Comparable<Plane>{
    int flightNumber;
    int x;
    int y;

    Plane( int flightNumber, int x, int y ) {
        this.flightNumber = flightNumber;
        this.x = x;
    	this.y = y;
    }

    @Override
    public int compareTo( Plane o ) {
   	double diff = calcDistance(this) - calcDistance(o); 
        int result = 0; 
	if ( diff > 0 ) { result = 1; }
	if ( diff < 0 ) { result = -1; }
        
        //System.out.println( String.format( "Comparing %s to %s ==> %f ==> %d", this, o, diff, result ) );

	return result;
    }

    @Override
    public String toString() {
	return String.format( "fight %d: (%d,%d)...", flightNumber, x, y );
    }
}

public static void main( String[] args ) {
    int nbrOfPlanes = 3;
    Tower t = new Tower(nbrOfPlanes);

    for ( int i=nbrOfPlanes; i>0; i-- ) {
    	Plane p = t.new Plane( i, i, i );
        t.addPlane( p );
    } 

    System.out.println( "Starting..." );
    t.scan();

    System.out.println( "\n----------------------------");
    Plane p = t.new Plane( 4, 4, 4 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 0, 0, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 5, 1, 2 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 6, 2, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    System.out.println( "Plane 2 just came in closer (1,0)" );
    p = t.new Plane( 2, 1, 0 );
    t.addPlane( p ); 
    t.scan();
}

}

- Alex Basile January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested Java solution - uses 3 vs 100 to prove the point.
Tower has max heap of 3 of the closest planes. Also has lookup map to for updating planes quickly. addPlane() adds/updates plane. If add and heap > 3 then pop out furthest plane from heap and map. scan() takes snapshot of heap as array and sorts them by closest distance.
Next steps would've been to spin off thread that adds/updates plane periodically.

import static java.lang.Math.*;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

public class Tower {

public int maxScan;
public PriorityQueue<Plane> queue; 
public Map<Integer, Plane> planeLookupMap;

public Tower( int maxScan ) {
    this.maxScan = maxScan;

    Comparator<Plane> comparator = new PlaneComparator();
    queue = new PriorityQueue<Plane>(maxScan, comparator);
    planeLookupMap = new HashMap<Integer, Plane>();
}

public void addPlane( Plane p ) {
    if ( planeLookupMap.containsKey( p.flightNumber ) ) {
        System.out.println( "updating: " + p );
	updatePlane( p );	
    } else {
	System.out.println( "adding: " + p );
	planeLookupMap.put( p.flightNumber, p );
        queue.offer( p );

  	if ( queue.size() > maxScan ) {
	    Plane deletePlane = queue.poll(); 
	    System.out.println( "deleting: " + deletePlane );
            planeLookupMap.remove( deletePlane.flightNumber );
  	}
    }   

}

protected void updatePlane( Plane newPlane ) {
    Plane oldPlane = planeLookupMap.get( newPlane.flightNumber );
    oldPlane.x = newPlane.x;
    oldPlane.y = newPlane.y;
}

public void scan() {
    // If order doesn't matter then use iterator()
    Plane[] array = queue.toArray(new Plane[queue.size()]);
    Arrays.sort(array);

    for ( Plane p : array ) {
	System.out.println( p );
    } 
}

public static double calcDistance( Plane p ) {
    return sqrt( pow(p.x,2) + pow(p.y,2) );
}

////////// PlaneComparator //////////////////////////
public class PlaneComparator implements Comparator<Plane> {
    @Override
    public int compare( Plane p, Plane o ) {
	return (int) (calcDistance(o) - calcDistance(p));
    }

}

////////// Plane //////////////////////////
public class Plane implements Comparable<Plane>{
    int flightNumber;
    int x;
    int y;

    Plane( int flightNumber, int x, int y ) {
        this.flightNumber = flightNumber;
        this.x = x;
    	this.y = y;
    }

    @Override
    public int compareTo( Plane o ) {
   	double diff = calcDistance(this) - calcDistance(o); 
        int result = 0; 
	if ( diff > 0 ) { result = 1; }
	if ( diff < 0 ) { result = -1; }
        
        //System.out.println( String.format( "Comparing %s to %s ==> %f ==> %d", this, o, diff, result ) );

	return result;
    }

    @Override
    public String toString() {
	return String.format( "fight %d: (%d,%d)...", flightNumber, x, y );
    }
}

public static void main( String[] args ) {
    int nbrOfPlanes = 3;
    Tower t = new Tower(nbrOfPlanes);

    for ( int i=nbrOfPlanes; i>0; i-- ) {
    	Plane p = t.new Plane( i, i, i );
        t.addPlane( p );
    } 

    System.out.println( "Starting..." );
    t.scan();

    System.out.println( "\n----------------------------");
    Plane p = t.new Plane( 4, 4, 4 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 0, 0, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 5, 1, 2 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 6, 2, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    System.out.println( "Plane 2 just came in closer (1,0)" );
    p = t.new Plane( 2, 1, 0 );
    t.addPlane( p ); 
    t.scan();
}

}

- Alex Basile January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import static java.lang.Math.*;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

public class Tower {

public int maxScan;
public PriorityQueue<Plane> queue; 
public Map<Integer, Plane> planeLookupMap;

public Tower( int maxScan ) {
    this.maxScan = maxScan;

    Comparator<Plane> comparator = new PlaneComparator();
    queue = new PriorityQueue<Plane>(maxScan, comparator);
    planeLookupMap = new HashMap<Integer, Plane>();
}

public void addPlane( Plane p ) {
    if ( planeLookupMap.containsKey( p.flightNumber ) ) {
        System.out.println( "updating: " + p );
	updatePlane( p );	
    } else {
	System.out.println( "adding: " + p );
	planeLookupMap.put( p.flightNumber, p );
        queue.offer( p );

  	if ( queue.size() > maxScan ) {
	    Plane deletePlane = queue.poll(); 
	    System.out.println( "deleting: " + deletePlane );
            planeLookupMap.remove( deletePlane.flightNumber );
  	}
    }   

}

protected void updatePlane( Plane newPlane ) {
    Plane oldPlane = planeLookupMap.get( newPlane.flightNumber );
    oldPlane.x = newPlane.x;
    oldPlane.y = newPlane.y;
}

public void scan() {
    // If order doesn't matter then use iterator()
    Plane[] array = queue.toArray(new Plane[queue.size()]);
    Arrays.sort(array);

    for ( Plane p : array ) {
	System.out.println( p );
    } 
}

public static double calcDistance( Plane p ) {
    return sqrt( pow(p.x,2) + pow(p.y,2) );
}

////////// PlaneComparator //////////////////////////
public class PlaneComparator implements Comparator<Plane> {
    @Override
    public int compare( Plane p, Plane o ) {
	return (int) (calcDistance(o) - calcDistance(p));
    }

}

////////// Plane //////////////////////////
public class Plane implements Comparable<Plane>{
    int flightNumber;
    int x;
    int y;

    Plane( int flightNumber, int x, int y ) {
        this.flightNumber = flightNumber;
        this.x = x;
    	this.y = y;
    }

    @Override
    public int compareTo( Plane o ) {
   	double diff = calcDistance(this) - calcDistance(o); 
        int result = 0; 
	if ( diff > 0 ) { result = 1; }
	if ( diff < 0 ) { result = -1; }
        
        //System.out.println( String.format( "Comparing %s to %s ==> %f ==> %d", this, o, diff, result ) );

	return result;
    }

    @Override
    public String toString() {
	return String.format( "fight %d: (%d,%d)...", flightNumber, x, y );
    }
}

public static void main( String[] args ) {
    int nbrOfPlanes = 3;
    Tower t = new Tower(nbrOfPlanes);

    for ( int i=nbrOfPlanes; i>0; i-- ) {
    	Plane p = t.new Plane( i, i, i );
        t.addPlane( p );
    } 

    System.out.println( "Starting..." );
    t.scan();

    System.out.println( "\n----------------------------");
    Plane p = t.new Plane( 4, 4, 4 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 0, 0, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 5, 1, 2 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    p = t.new Plane( 6, 2, 1 );
    t.addPlane( p ); 
    t.scan();

    System.out.println( "\n----------------------------");
    System.out.println( "Plane 2 just came in closer (1,0)" );
    p = t.new Plane( 2, 1, 0 );
    t.addPlane( p ); 
    t.scan();
}

}

- Alex Basile January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Testing...

- Alex Basile January 30, 2017 | 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