Coding Challenge

drone_coding_challenge.py

"""
Coding Challenge

 Given a square airspace, 128km x 128km, and N=10,000 drones occupying the
 airspace our challenge is to efficiently compute how many drones are flying
 too close to one another.

 Drone positions will be provided as an Nx2 array of [x,y]
 coordinates (in meters).  Drones must maintain a horizontal separation of
 radius 0.5km from other drones. If a drone is within 0.5km of another drone,
 both are "in conflict". Have count_conflicts return the total number of
 drones that are in a conflicted state. Not the total number of conflicts).
 Do all of your work and testing in this pad.

 Some common libraries can be imported, but not all, so relying on niche
 algorithm won't work. This is very solvable with standard python libraries,
 several ways.

 Coding style, readability, scalability, and documentation all
 matter! Consider the computational complexity of your solution.
 The N^2 answer can be coded up in 5 minutes and
 10 lines; we'd like to see something better!
 """
import random
import numpy as np
# Setting random number generator seed for repeatability
random.seed(1)


NUM_DRONES = 10000
# Meters.
AIRSPACE_SIZE = 128000
# Meters.
CONFLICT_RADIUS = 500


# Write your code inside this function
def count_conflicts(drones, conflict_radius):
    """
    Give a list of drone position and the conflict radious for every drone.

    Returns:
        The count of drones that are in conflict with other drones. A drone is
        in conflict when there is another drone within it's conflict radius

    """
    drones_in_conflict = 0
    # Transpose the drones array to get two lists. One for all the X values
    # and one for all the Y values
    X, Y = np.array(drones).T

    for d in drones:
        # For each drone position get the distance from its position to the
        # position of all the other drones
        distance = ((X - d[0])**2) + ((Y - d[1])**2)
        # Get the positions on the distance array where the distance is less
        # than the radius (meaning the points where a drone is in conflict
        # with the evaluted drone)
        drones_in_range = np.where(distance <= conflict_radius**2)[0]
        # If the drones in range is greater than 1 (we have to check if greater
        # than one because the position of the current evaluated drone will
        # always be present)
        if drones_in_range.size > 1:
            drones_in_conflict += 1

    return drones_in_conflict


# Run  tests using py.test file.py
def test_count_conflicts():
    """
    Function to test that count conflicts returns the number of conflicts
    for a drone position
    """
    conflict_radius = 10
    drones = [[1, 1], [2, 3], [20, 20]]

    # Expect two conflicts
    assert count_conflicts(drones, conflict_radius) == 2

    conflict_radius = 10
    drones = [[10, 10], [20, 20], [30, 30]]

    assert count_conflicts(drones, conflict_radius) == 0


# Do not delete or change the lines below this one
def gen_coord():
    return int(random.random() * AIRSPACE_SIZE)

positions = [[gen_coord(), gen_coord()] for i in range(NUM_DRONES)]
conflicts = count_conflicts(positions, CONFLICT_RADIUS)
print "Drones in conflict: {}".format(conflicts)

I just saw this coding question in a friends internship interview. The numpy implementation doesn't actually satisfy the better than O(N^2) complexity requirement, since under the hood it's still performing matrix math with (X - d[0])**2, which is at best O(N^2.37...).

The actual solution requires implementing a kNN algorithm using k-d trees, and calculating the distance for each drone's nearest neighbour.