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() {
  // ...
}

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;
}