Lyft Programming Challenge

The Lyft programming challenge is an optional part of the job application to be a Software Engineer at Lyft.

This is copy pasted from the job posting:

Calculate the detour distance between two different rides. Given four latitude / longitude pairs, where driver one is traveling from point A to point B and driver two is traveling from point C to point D, write a function (in your language of choice) to calculate the shorter of the detour distances the drivers would need to take to pick-up and drop-off the other driver.

Broken down we have:

• There are two different trips
• Consisting of four points (A to B and C to D)
• Calculate which one is shorter ACDB or CABD

Using the Haversine formula, we can obtain the distance of the trip or from two different points in a plot.

JavaScript

// Config should be taken from an input
var metric = true;
var Radius; // Radius of the Earth
if (metric === true) {
    Radius = 6371; // in km
} else {
    Radius = 3963.1676; // in miles
}

/*
 *  Converts a number into radians
 */
function toRadians(num) {
   return num*Math.PI/180;
}

/*
 *  Object point in a sphere
 */
function point(lat, lon) {
    this.lat = lat;
    this.lon = lon;
}

/*
 *  Calculate the distance between two points
 */
function calcDistance(X, Y) {
    var xLat = toRadians(X.lat);
    var yLat = toRadians(Y.lat);
    var diffLat = toRadians(xLat - yLat);
    var diffLon = toRadians(X.lon - Y.lon);

    // Haversine Formula
    var a = Math.pow(Math.sin(diffLat/2), 2) + (Math.cos(xLat) * Math.cos(yLat) * Math.pow(Math.sin(diffLon/2), 2));  
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    var d = Radius * c;

    return d;
}

function test(){
    var A = new point(1, 1);
    var B = new point(2, 3);
    var C = new point(5, 8);
    var D = new point(13, 21);
    
    // Since it is a rectangle we need only calculate two trips
    var distAB = calcDistance(A, B);
    var distCD = calcDistance(C, D);

    if (distAB > distCD) {
        console.log("ACDB is the shorter path!");
    } else if (distAB == distCD) {
        console.log("Either driver can do it!")
    } else {
        console.log("CABD is the shorter path!");
    }
}