iteration.js

/**
 * As part of a technical on-site screening-interview I was requested to create a function
 * able to find two numbers in array `arr` that added together would equal given number `k`.
 *
 * I initially did an approach equal to run the function below with the option `reduceIterations=false`.
 *
 * My interviewer asked if I had a better approach: honestly, not only I had a headache but also I was already screened
 * remotely and was not expecting more coding review: especially on the spot. I don't know, first time interviewing
 * in the US... The thing is, he suggested using a 'table hash' (first time I heard the term) to reduce iteration. At
 * the beginning I did not understand him (probably due to my technical language barer) but then I realized he wanted
 * me to do something I used to see or refer as map object
 *
 * Thing is, wondering a bit after my interview, I realized I have come with similar approaches
 * (the one suggested by my interviewer, or the one I understood he suggested) which can be tried
 * by setting `reduceIterations=true`. Silighty different than his, but same outcome: reduces iteration.
 *
 * Below a running test of both and performance comparison.
 *
 * @param {Number[]} arr - An array with unique numbers
 * @param {Number} k
 * @param {Boolean} reduceIterations=false - Whether to reduce the amount of iterations of the algorithm by reducing
 * iterations (understanding that the array has unique numbers)
 *
 * @return {{ found, iterations }} Array with two numbers found in given `arr` that added would equals `k`
 *
 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
 * @see https://en.wikipedia.org/wiki/Hash_table
 */

function findTwoSum (arr, k, reduceIterations = false) {
  const found = []
  let iterations = 0

  main:
    for (let x = 0; x < arr.length; x++) {
      for (let y = reduceIterations ? x + 1 : 0; y < arr.length; y++) {
        iterations++
        if (arr[x] + arr[y] === k && (reduceIterations || x !== y)) {
          found.push(arr[x], arr[y])
          break main
        }
      }
    }

  return { found, iterations }
}

const arr = [2, 1, 3, 5, 7, 10, 13, 15]

const test = [
  [4, [1, 3]],
  [8, [1, 7]],
  [6, [1, 5]],
  [20, [5, 15]],
  [18, [3, 15]],
  [17, [2, 15]],
  [28, [13, 15]],
  [22, [7, 15]],
  [11, [1, 10]]
]

let efficientIterations = 0
let inefficientIterations = 0

test.forEach(([look, expected]) => {
  const { iterations } = findTwoSum(arr, look, true)
  efficientIterations += iterations
})

test.forEach(([look, expected]) => {
  const { found, iterations } = findTwoSum(arr, look)
  inefficientIterations += iterations
  console.log({ look, found }, expected.every(e => found.includes(e)) ? '' : 'NOT', 'found as expected', { iterations })
})

// counts the amount of iterations by each algorithm to come with the same result
console.log({ efficientIterations, inefficientIterations })

// { look: 4, found: [ 1, 3 ] }  found as expected { iterations: 11 }
// { look: 8, found: [ 1, 7 ] }  found as expected { iterations: 13 }
// { look: 6, found: [ 1, 5 ] }  found as expected { iterations: 12 }
// { look: 20, found: [ 5, 15 ] }  found as expected { iterations: 32 }
// { look: 18, found: [ 3, 15 ] }  found as expected { iterations: 24 }
// { look: 17, found: [ 2, 15 ] }  found as expected { iterations: 8 }
// { look: 28, found: [ 13, 15 ] }  found as expected { iterations: 56 }
// { look: 22, found: [ 7, 15 ] }  found as expected { iterations: 40 }
// { look: 11, found: [ 1, 10 ] }  found as expected { iterations: 14 }
// { efficientIterations: 138, inefficientIterations: 210 }