Difficulty: Easy · Skills: geographic distance, string parsing, min search, floating point

What this puzzle tests in a coding interview

Defibrillators measures how quickly you can pull the few fields you need out of noisy, delimiter-separated records, then run a minimum search. It mirrors everyday data cleaning tasks, which is why it shows up in screening tests.

How to solve it, step by step

1. Read your own position first, swapping each comma for a dot so the coordinates parse as decimal numbers.
2. For each defibrillator line, split on semicolons and keep the name, longitude and latitude fields.
3. Convert the coordinates to radians and compute x as the longitude difference times the cosine of the mean latitude, and y as the latitude difference.
4. Compute the distance as the square root of x squared plus y squared times 6371.
5. Keep the name with the smallest distance and print it.

Time and memory complexity

Each record is processed once, so time is O(n) and memory can be O(1) beyond the current line.

Traps to avoid

• Forgetting to swap commas for dots, so the coordinates parse as wrong numbers or fail.
• Using degrees directly in the cosine instead of radians.
• Splitting on commas instead of semicolons, which also cuts the decimal parts.

Tip for a timed test

Since only the closest point matters, you can compare squared distances and skip the square root and the 6371 factor entirely.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <float.h>

// represents a defibrillator
struct defib { char* name; double lon; double lat; };

/* Returns the distance between a point A and a point B 
   given their lat(itude) and lon(gitude)*/
double distance(double longA, double latA, double longB, double latB){
    double x = (longB-longA)*cos((latA+latB)/2);
    double y = latB - latA;
    return (sqrt(x*x+y*y) * 6371.0);
}

// Parses a double in string 'str' using atof, and replacing , by . if needed
double toDouble(char *str) {
    for(char *iter = str; *iter != '\0'; iter++)
        if (*iter == ',')
            *iter = '.';
    return atof(str);
}

// Returns a pointer on next char 'c' in 'str'
char *goToNext(char c, char *str) {
    for(; *str != c; str++);
    return str;
}

/* Reads the line 'str', and stores relevant fields in 'defib'
   pretty awful implementation, but necessary for speed*/
void getDefib(char *str, struct defib *res) {
    str = goToNext(';', str);
    res->name = ++str;
    for (int k = 0; k < 3; k++) {
        str = goToNext(';', str);
        *str = '\0';
        str++;
    }
    char *lon = str;
    str = goToNext(',', str);
    *str = '.';
    str = goToNext(';', str);
    char *lat = ++str;
    str = goToNext(',', str);
    *str = '.';
    res->lon = atof(lon);
    res->lat = atof(lat);
}

int main(int argc, char** argv)
{
    char strLon[50];
    char strLat[50];
    int N;
    scanf("%s\n%s\n%d\n", strLon, strLat, &N);
    double lon = toDouble(strLon);
    double lat = toDouble(strLat);
    
    // simple linear search amongst defibrillators
    double min = DBL_MAX;
    char output[100];
    double d;
    char line[256];
    struct defib res;

    for (int i = 0; i < N; i++) {
        getDefib(fgets(line, 256, stdin), &res);
        d = distance(lon, lat, res.lon, res.lat);
        if (d < min) {
            min = d;
            strcpy(output, res.name);
        }
    }
    printf("%s", output);
    return EXIT_SUCCESS;
}
            

import java.util.*;
import java.math.*;

class Solution {
    /** Returns the distance between a point A and a point B
     * @param longA longitude of point A
     * @param latA latitude of point A
     * @param longB longitude of point B
     * @param latB latitude of point B
     * @return distance between A and B
     */
    private static double distance(double longA, double latA, double longB, double latB){
        double x = (longB-longA)*Math.cos((latA+latB)/2);
        double y = latB - latA;
        return Math.sqrt(Math.pow(x,2) + Math.pow(y,2)) * 6371;
    }

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        
        /* as the latitude and the longitude are given with , instead of .
           it isn't possible to use nextFloat()*/
        Double lon = new Double(in.next().replace(',', '.'));
        Double lat = new Double(in.next().replace(',', '.'));
        int N = in.nextInt();
        in.nextLine();

        // simple min search amongst defibrillators
        double min = Double.POSITIVE_INFINITY;
        String res = "";
        Double d;
        for (int i = 0; i < N; i++) {
            String[] defib = in.nextLine().replace(',', '.').split(";");
            d = distance(lon, lat, new Double(defib[4]), new Double(defib[5]));
            if (d < min) {
                min = d;
                res = defib[1];
            }
        }
        System.out.println(res);
    }
}
            

import math

def distance (longA, latA, longB, latB):
    ''' return the distance between point A and point B 
    given their latitude and longitude '''
    x = (longB-longA)*math.cos((latA+latB)/2)
    y = latB-latA
    return 6371 * math.sqrt(x*x+y*y)

lon, lat, N = float(input().replace(",", ".")), float(input().replace(",", ".")), int(input())
# linear search amongst defibrillators
min, res = None, None
for i in range(N):
    defib = input().replace(",", ".").split(";")
    d = distance(lon, lat, float(defib[4]), float(defib[5]))
    if (min == None) or (d < min):
        min, res = d, defib[1]
print(res)