Network Cabling

The aim of this puzzle, is to minimize the length of cable used to connect a business park to the network, given the coordinates of all the building. There must be a main horizontal cable, and for each building a dedicated vertical cable from the building to the main cable.

If there are A buildings above it and B buildings below it, shifting it up increases the total length of vertical cables by B-A, and shifting it down increases this number by A-B. So to minimize the length:

Finally, the optimal positions for the main cable are the positions where A = B. That is why, the y-coordinate of the main cable must be a median of the set of y-coordinates of the building.

Difficulty: Medium · Skills: median, sorting, math reasoning, 64-bit integers

What this puzzle tests in a coding interview

Network Cabling is a reasoning puzzle more than a coding one: you must see that the horizontal cable length is fixed and that the best height for it is the median of the building heights. Interviewers like it because the proof fits in two sentences and the code in ten lines.

How to solve it, step by step

  1. Read every building, tracking the smallest and largest x and storing each y.
  2. Count the horizontal cable as the largest x minus the smallest x.
  3. Sort the y values and take the middle element as the cable's height.
  4. Add the absolute distance from every building's y to that median.
  5. Print the total using a 64-bit integer type.

Time and memory complexity

Sorting the y values costs O(n log n) time and O(n) memory; a selection algorithm could find the median in linear average time.

Traps to avoid

Tip for a timed test

If you cannot recall why the median works, test a quick example with three buildings; moving the cable towards the side with more buildings always shortens the total.

C

Once the array Ys of the y-coordinates of the N buildings, sorted (once again thanks to qsort, but you could use your own sorting function), the median is simply Ys[N/2].

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

/* Comparison function between two long long integers
   return -1 if a<b, 1 if a>b, 0 if a=b */
int cmp (const void * a, const void * b){
    long long aa = *(long long*)a;
    long long bb = *(long long*)b;
    return aa<bb?-1:aa>bb?1:0;
}

int main()
{
    int N;
    scanf("%d", &N);
    
    long long xMin = LLONG_MAX;
    long long xMax = 0LL;
    long long x;
    long long Ys[N];
    
    // reading coordinates, storing Ys, computing xMin and xMax
    for (int i = 0; i < N; i++) {
        long x;
        scanf("%Ld %Ld", &x, Ys+i);
        if (x < xMin) xMin = x;
        if (x > xMax) xMax = x;
    }
    // sorting Ys in ascending order
    qsort(Ys, N, sizeof(long long), cmp);
    
    /* The main horizontal cable length is xMax-xMin
       To minimize the total length of vertical cables, its 
       y-coordinate of the main cable must be a median of Ys, Ys[N/2]*/
    long long res = xMax-xMin;
    for (int i = 0 ; i < N ; i++)
        res += abs(Ys[N/2]-Ys[i]);
        
    printf("%Ld\n", res);
}