JavaScript Quiz and Answer

findOutlier.js

let answer = runTest();
console.log(answer);

// do not alter the code below this point
function createPoints(randomizedIndex) {
  var startY = Math.random() * 100;
  var slope = Math.random();
  var points = [];
  for (var i = 0; i < 10; i++) {
    var x = Math.random() * 100;
    points.push({ x: x, y: x * slope + startY });
  }
  var outlier = points[randomizedIndex];
  outlier.y += Math.random() > 0.5 ? 10 : -10;
  return points;
}

function runTest() {
  var outlierIndex = Math.floor(Math.random() * 10);
  var points = createPoints(outlierIndex);
  return findOutlier(points) === points[outlierIndex];
}

function findOutlier() {
  // ...
}

Fill in the function findOutlier such that it accepts an array of point objects. All points in the array are guaranteed to form a line when graphed, except for one! Return this outlier point object.

Initial Solution

function findOutlier(points) {
  const slopes = calculateSlopes(points);
  for (let i = 0, length = slopes.length; i < length; i++) {
    const indexCurrent = i;
    const indexPrevious = i == 0 ? length - 1 : i - 1;
    const indexNext = (i + 1) % length;

    const slopeCurrent = slopes[indexCurrent];
    const slopePrevious = slopes[indexPrevious];
    const slopeNext = slopes[indexNext];

    if (slopeCurrent !== slopePrevious && slopeCurrent !== slopeNext) {
      return points[indexCurrent + 1];
    }
  }
}

function calculateSlopes(points) {
  const slopes = [];
  for (let i = 0, length = points.length; i < length; i++) {
    const p1 = points[i];
    const p2 = points[(i + 1) % length];
    const slope = (p2.y - p1.y) / (p2.x - p1.x);
    const roundedSlope = parseFloat(slope.toFixed(9));
    slopes.push(roundedSlope);
  }
  return slopes;
}

Code Review

Okay, so the initial implementation fails when outlierIndex is 0 — we can actually see that intuitively here:

if (slopeCurrent !== slopePrevious && slopeCurrent !== slopeNext) {
  return points[indexCurrent + 1]; // <-- indexCurrent will never be -1
}

What’s more, indexCurrent + 1 should actually be indexNext — aside from the underlying bug, that was simply an oversight.

There are some other minor things I would change for clarity, such as:

• Removing indexCurrent and simply using i in the findOutlier() method.
• Renaming roundedSlope to fixedSlope in the calculateSlopes() method.

Refactoring

With a little more time to think through my implementation, I think the main issue is that for any given point P, I was calculating its slope by using P and P+1 — which is ultimately where the off by one error comes from. I think a better approach would be to define the slope of a given point P by both neighbors, resulting in a 2-tuple (as array), e.g:

Doing this for each point in points would result in a 2-dimensional array of slopes, where the outlierIndex would be where both values in the slope tuple differ from the line’s slope. (In the example below, that would be 6) e.g:

This approach of course requires determining the line's slope, which in this case would be the most common value found in the 2-dimensional array of slopes — using a hash map to track each slope and its number of occurrences is the first strategy that comes to mind.

Revised Solution

function findOutlier(points) {
  const slopeTuples = getFixedSlopeTuples(points);
  const commonSlope = getCommonSlope(slopeTuples);
  for (let i = 0; i < slopeTuples.length; i++) {
    const [s1, s2] = slopeTuples[i];
    if (s1 !== commonSlope && s2 !== commonSlope) {
      return points[i];
    }
  }
}

function getCommonSlope(slopeTuples) {
  const slopes = {};
  for (let i = 0; i < slopeTuples.length; i++) {
    const [s1, s2] = slopeTuples[i];
    slopes[s1] = slopes[s1] + 1 || 1;
    slopes[s2] = slopes[s2] + 1 || 1;
  }

  let commonCount;
  let commonSlope;
  Object.keys(slopes).forEach(slope => {
    commonCount = commonCount > slopes[slope] ? commonCount : slopes[slope];
    commonSlope = commonCount > slopes[slope] ? commonSlope : slope;
  });
  return parseFloat(commonSlope);
}

function getFixedSlopeTuples(points) {
  const slopes = [];
  for (let i = 0, size = points.length; i < size; i++) {
    const indexPrev = i == 0 ? size - 1 : i - 1;
    const indexNext = (i + 1) % size;

    const pointCurr = points[i];
    const pointPrev = points[indexPrev];
    const pointNext = points[indexNext];

    const s1 = (pointCurr.y - pointPrev.y) / (pointCurr.x - pointPrev.x);
    const s2 = (pointNext.y - pointCurr.y) / (pointNext.x - pointCurr.x);

    const fixedSlopeTuple = [s1, s2].map(s => parseFloat(s.toFixed(9)));
      
    slopes.push(fixedSlopeTuple);
  }
  return slopes;
}