Labs » Evernote Pre-screening challenge

Summary

Write a function that finds the highest 4 integers in an unordered list of numbers and describe its performance in O(n) time. Use any language you desire. Create a solution that is well written and with good performance.

Demo

Input (parameters)

Output (sample)
Pot of gold

Code

  
(function() {
  /**
   * @return {void}
   * @param {array} array of numbers
   * @param {int} how many numbers to return
   * @param {function} optional callback
   */
  var getHighs = function(data, returnsize, callback) {
    var returnsize = returnsize && !isNaN(returnsize) ? returnsize : 4,
        min        = null,
        highs      = [];

    for (var i=0, len=data.length; i < len; i++) {
      if (isNaN(data[i])) {
        continue;
      }
      if (highs.length < returnsize) {
        highs.push(data[i]);
      } else {
        if (data[i] < min) {
          continue;
        }
        highs[highs.length - 1] = data[i];
      }
      highs.sort(function(a, b) {
        return b - a;
      });
      min = highs[highs.length - 1];
    }

    if (callback && "function" === typeof callback) {
      callback(highs);
    }
  };

  var run = function() {
    // test config
    var returnsize = parseInt(document.getElementById('input-returnsize').value, 10),
        samplesize = parseInt(document.getElementById('input-samplesize').value, 10),
        lowerbound = parseInt(document.getElementById('input-lowerbound').value, 10),
        upperbound = parseInt(document.getElementById('input-upperbound').value, 10);

    // generate test data
    var dataset    = [];
    while (samplesize--) {
      dataset.push(Math.floor(Math.random() * (upperbound - lowerbound) + lowerbound));
    }
    document.getElementById('sampleset').innerHTML = dataset.join(', ');
    getHighs(
      dataset,
      returnsize, // number of items to return
      function(rs) {
        document.getElementById('resultset').innerHTML = rs.join(', ');
      }
    );
  };

  document.getElementById('form-sample-generator').addEventListener('submit', function(event) {
    event.preventDefault();
    run();
  });
})();