Bloomberg LP Interview Question
Software Engineer / DevelopersTeam: Derivatives
Country: United States
Interview Type: In-Person
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?
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();
}
}
}
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?
"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.
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).
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.
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;
}
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.
//
//
// 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");
}
}
/**
* 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);
}
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)...
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();
}
}
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();
}
}
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();
}
}
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();
}
}
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